SQL練習室
← SQLガイド

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のない結果の行順は保証されません。

employees:社員6人
idnamemanager_id
1山本NULL
2田中1
3佐藤1
4鈴木2
5高橋2
6伊藤4
routes:経路5件
from_nodeto_node
AB
AC
BD
CD
DE

WITH RECURSIVE(再帰CTE)の基本構文

sql
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を付けるのを忘れないでください。

sql
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行多くなるので、条件は「次に作る値」で判断します。

sql
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人全員が出ます。何段あるか分からなくても、部下が見つからなくなるまで自動で続きます。

sql
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;
実行結果
idnamelevel
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のように絞ります。

sql
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;
実行結果
idnamelevel
2田中1
4鈴木2
5高橋2
6伊藤3

経路(上司の連なり)を文字列で作る

階層の途中の値は、再帰項で文字列として引き継げます。非再帰項ではpathをnameだけにし、再帰項でtree.path || ' > ' || employees.nameとつなぐと、社長からその人までの道すじが残ります。伊藤の経路は「山本 > 田中 > 鈴木 > 伊藤」です。非再帰項と再帰項で列の型は同じにします。ここではどちらもtextです。経路を持たせると、誰の配下かを1行で読め、後からLIKEで特定の部署以下を絞ることもできます。

sql
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;
実行結果
idpath
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のように行ごとに値が変わる列を持つと、同じ地点でも別の行とみなされて止まりません。

sql
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_rowsunion_rows
75

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公式ドキュメントを参照し、初めて学ぶ人向けに日本語で整理しています。