SQLのWITH RECURSIVE(再帰CTE)とは?連番の生成・組織図の階層・経路の作り方
WITH RECURSIVEは、CTEの中で自分自身を参照し、前の結果から次の行を作り続ける構文です。上司と部下のように何段つながるか分からないデータを、1つのSELECTでたどれます。入門のWITHの続きとして、連番、組織図、経路、終了条件を順に確認します。
例で使う表
employeesは1行が社員1人で、manager_idは上司のidです。山本は社長でmanager_idがNULLです。山本の部下が田中と佐藤、田中の部下が鈴木と高橋、鈴木の部下が伊藤で、最も深い階層は4段です。routesは1行が片道の経路で、A→B、A→C、B→D、C→D、D→Eがあり、AからDへ行く道が2通りあります。ORDER BYのない結果の行順は保証されません。
| id | name | manager_id |
|---|---|---|
| 1 | 山本 | NULL |
| 2 | 田中 | 1 |
| 3 | 佐藤 | 1 |
| 4 | 鈴木 | 2 |
| 5 | 高橋 | 2 |
| 6 | 伊藤 | 4 |
| from_node | to_node |
|---|---|
| A | B |
| A | C |
| B | D |
| C | D |
| D | E |
WITH RECURSIVE(再帰CTE)の基本構文
WITH RECURSIVE tree AS (
SELECT id, name, 1 AS level
FROM employees
WHERE manager_id IS NULL
UNION ALL
SELECT employees.id, employees.name, tree.level + 1
FROM employees
JOIN tree ON employees.manager_id = tree.id
)
SELECT id, name, level
FROM tree
ORDER BY level, id;再帰CTEで1から5までの連番を作る
再帰CTEは「非再帰項」「UNION ALL」「再帰項」の3部分でできています。非再帰項は最初の1回だけ実行され、ここでは1を返します。再帰項はCTE自身(numbers)を読み、直前に出た行のnに1を足した行を作ります。WHERE n < 5があるので、nが4の行から5が作られた後は新しい行が出ず、ここで終わります。結果は1〜5の5行です。WITHのあとにRECURSIVEを付けるのを忘れないでください。
WITH RECURSIVE numbers AS (
SELECT 1 AS n
UNION ALL
SELECT n + 1
FROM numbers
WHERE n < 5
)
SELECT n
FROM numbers
ORDER BY n;| n |
|---|
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
終了条件のWHEREが「次の行を作るか」を決める
再帰項のWHEREは、直前の行から次の行を作ってよいかを判定します。再帰項が1行も返さなくなった時点で再帰が終わります。ここでは前の値を2倍し、2倍した結果が100以下のときだけ続けます。64の次は128になって100を超えるため作られず、結果は1、2、4、8、16、32、64の7行です。終了条件が無いか、いつまでも成り立つ条件だと、再帰は止まらずエラーやタイムアウトになります。nが100未満かを見る書き方だと、64から128が作られて1行多くなるので、条件は「次に作る値」で判断します。
WITH RECURSIVE doubling AS (
SELECT 1 AS n
UNION ALL
SELECT n * 2
FROM doubling
WHERE n * 2 <= 100
)
SELECT n
FROM doubling
ORDER BY n;| n |
|---|
| 1 |
| 2 |
| 4 |
| 8 |
| 16 |
| 32 |
| 64 |
上司から部下へたどり、階層の深さ(level)を付ける
組織図は、非再帰項で最上位(manager_idがNULLの山本)を取り、再帰項でemployeesをtreeにJOINして「直前の行の部下」を取り出します。JOINのON条件は、部下のmanager_idが直前の行のidに等しいことです。levelは非再帰項で1とし、再帰項でtree.level + 1とすると深さになります。山本が1、田中と佐藤が2、鈴木と高橋が3、伊藤が4で、6人全員が出ます。何段あるか分からなくても、部下が見つからなくなるまで自動で続きます。
WITH RECURSIVE tree AS (
SELECT id, name, 1 AS level
FROM employees
WHERE manager_id IS NULL
UNION ALL
SELECT employees.id, employees.name, tree.level + 1
FROM employees
JOIN tree ON employees.manager_id = tree.id
)
SELECT id, name, level
FROM tree
ORDER BY level, id;| id | name | level |
|---|---|---|
| 1 | 山本 | 1 |
| 2 | 田中 | 2 |
| 3 | 佐藤 | 2 |
| 4 | 鈴木 | 3 |
| 5 | 高橋 | 3 |
| 6 | 伊藤 | 4 |
非再帰項の起点を変えて、特定の人の配下だけをたどる
たどり始める行は非再帰項のWHEREで決まります。manager_id IS NULLの代わりにid = 2とすると、田中を起点(level 1)として、田中の部下の鈴木と高橋(level 2)、鈴木の部下の伊藤(level 3)だけが出ます。佐藤は別の系統なので入りません。起点の田中自身も結果に含まれる点に注意してください。自分を除きたいときは外側のSELECTでlevel > 1のように絞ります。
WITH RECURSIVE subordinates AS (
SELECT id, name, 1 AS level
FROM employees
WHERE id = 2
UNION ALL
SELECT employees.id, employees.name, subordinates.level + 1
FROM employees
JOIN subordinates ON employees.manager_id = subordinates.id
)
SELECT id, name, level
FROM subordinates
ORDER BY level, id;| id | name | level |
|---|---|---|
| 2 | 田中 | 1 |
| 4 | 鈴木 | 2 |
| 5 | 高橋 | 2 |
| 6 | 伊藤 | 3 |
経路(上司の連なり)を文字列で作る
階層の途中の値は、再帰項で文字列として引き継げます。非再帰項ではpathをnameだけにし、再帰項でtree.path || ' > ' || employees.nameとつなぐと、社長からその人までの道すじが残ります。伊藤の経路は「山本 > 田中 > 鈴木 > 伊藤」です。非再帰項と再帰項で列の型は同じにします。ここではどちらもtextです。経路を持たせると、誰の配下かを1行で読め、後からLIKEで特定の部署以下を絞ることもできます。
WITH RECURSIVE tree AS (
SELECT id, name, name AS path
FROM employees
WHERE manager_id IS NULL
UNION ALL
SELECT employees.id, employees.name, tree.path || ' > ' || employees.name
FROM employees
JOIN tree ON employees.manager_id = tree.id
)
SELECT id, path
FROM tree
ORDER BY id;| id | path |
|---|---|
| 1 | 山本 |
| 2 | 山本 > 田中 |
| 3 | 山本 > 佐藤 |
| 4 | 山本 > 田中 > 鈴木 |
| 5 | 山本 > 田中 > 高橋 |
| 6 | 山本 > 田中 > 鈴木 > 伊藤 |
UNION ALLとUNIONで、同じ行の扱いが変わる
再帰CTEのUNION ALLは、出た行をそのまま全部残します。UNIONに替えると、すでに出た行と同じ行は捨てて、新しい行が無くなった時点で終わります。routesでAから行ける場所をたどると、Dへは「A→B→D」と「A→C→D」の2通りあります。UNION ALLではDとEが2回ずつ出て7行、UNIONでは重複が消えて5行(A、B、C、D、E)です。同じ地点を何度も通る循環のあるデータでも、UNIONなら行が重複せず止まります。ただしlevelやpathのように行ごとに値が変わる列を持つと、同じ地点でも別の行とみなされて止まりません。
WITH RECURSIVE
all_rows AS (
SELECT 'A'::text AS node
UNION ALL
SELECT routes.to_node
FROM routes
JOIN all_rows ON routes.from_node = all_rows.node
),
distinct_rows AS (
SELECT 'A'::text AS node
UNION
SELECT routes.to_node
FROM routes
JOIN distinct_rows ON routes.from_node = distinct_rows.node
)
SELECT
(SELECT COUNT(*) FROM all_rows) AS union_all_rows,
(SELECT COUNT(*) FROM distinct_rows) AS union_rows;| union_all_rows | union_rows |
|---|---|
| 7 | 5 |
WITH RECURSIVE(再帰CTE)でよくある間違い
終了条件が無い再帰は止まらない
再帰項のWHEREを書き忘れる、または常に成り立つ条件にすると、再帰項が新しい行を作り続けて終わりません。数や深さに上限があるデータでは、WHERE n < 5のように必ず終了条件を置きます。上司の連なりに循環(Aの上司がBで、Bの上司がA)が紛れ込むと、組織図でも同じことが起きます。この例は動かなくなるため、コードは載せません。
非再帰項と再帰項で列の型が合わないとエラーになる
非再帰項の列の型と、再帰項が返す列の型は一致している必要があります。たとえば非再帰項のpathを文字数の決まった型で作り、再帰項でそれより長い文字列をつなぐと、型が一致しないというエラーになります。経路や連番は、textやintegerなど最初から余裕のある型で始めてください。この例はエラーになるため、コードは載せません。
実際に1問解いてみる
WITH RECURSIVE
再帰CTEを使って、1から7までの連番を1列(nという名前)で取得してください。行順は問いません。
関連構文
WITH RECURSIVE(再帰CTE)についてよくある質問
- 再帰CTEはどんなときに使いますか?
- 深さが決まっていない親子関係(組織図、カテゴリの階層、部品表)をたどるとき、連番や日付の並びを作るとき、経路をたどるときに使います。深さが2〜3段で固定なら、JOINを段数分だけ重ねる書き方でも足ります。
- UNION ALLとUNIONはどちらを使いますか?
- 階層をたどる通常の用途ではUNION ALLを使います。重複を調べる手間がなく、levelやpathのような列も持てます。同じ行が何度も出る経路探索で、重複を除きながら止めたいときだけUNIONを検討します。
- 再帰項の中でCTEを何回参照できますか?
- 再帰項の中で、そのCTE自身を参照できるのは1回だけです。ほかにも、再帰項の中では集計関数を使えないといった制限があります。集計したいときは、外側のSELECTへ移します。
- 連番を作るだけなら再帰CTEが最適ですか?
- 再帰CTEでも作れますが、PostgreSQLにはgenerate_series関数があり、連番だけならそちらのほうが簡潔です。再帰CTEは、前の行の値から次の行を作る必要があるときに向いています。
参考文献
内容はPostgreSQL公式ドキュメントを参照し、初めて学ぶ人向けに日本語で整理しています。
- PostgreSQL公式:再帰クエリ(WITH RECURSIVE) — 非再帰項と再帰項、UNIONとUNION ALL、再帰の終了と評価の仕組み
- PostgreSQL公式:循環の検出(CYCLE句) — CYCLE句による循環検出と、上限を付けて止める方法