SQLite WITH RECURSIVE入門：再帰CTEで木構造と連番生成

SQLでの再帰って一見とっつきにくい — でも仕組みを見れば腑に落ちる

普通のクエリは、すでに存在するデータから行を返すだけです。ところが再帰CTE（WITH RECURSIVE）はちょっと違っていて、自分自身の出力を次の入力として食わせながら、新しい行が出なくなるまで一段ずつ行を組み立てていきます。深さが分からないツリーをたどったり、番号テーブルなしで1から100までの連番を作ったりできるのは、この仕組みのおかげです。

書き方の型はいつも同じです。

WITH RECURSIVE name(columns) AS (
    -- アンカー: 開始行
    SELECT ...
    UNION ALL
    -- 再帰: 前のステップから導出される行
    SELECT ... FROM name WHERE ...
)
SELECT * FROM name;

アンカー句を上、UNION ALL、再帰句を下に書きます。SQLite はまずアンカー句を1回だけ実行し、その後は前回得られた行を入力にして再帰句を繰り返し実行します。新しい行が返らなくなった時点で停止する、という流れです。

1から10までの連番を生成する

一番シンプルな再帰CTEの使い方は、連番の生成です。テーブルは一切不要:

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter WHERE n < 10
)
SELECT n FROM counter;

動きを順番に追ってみましょう。

1. アンカー部が n = 1 という1行を返す。
2. 再帰ステップがその行を受け取り、n + 1 = 2 を計算する。2 < 10 が真なので、その行を残す。
3. 次のイテレーションでは n = 2 を受け取って n = 3 を返す。これを繰り返していく。
4. n が 10 に達したところで 10 < 10 は偽になるため、再帰ステップは行を返さず、SQLiteは処理を止める。

ここで WHERE n < 10 が停止条件の役割を果たしています。これを書き忘れると、再帰CTEは無限ループに陥ってしまいます。

日付の連続データを生成する

同じ仕組みは実務のレポートでも役立ちます。たとえば、何も起きなかった日も含めて、ある期間のすべての日付を埋めたいときです。

WITH RECURSIVE days(d) AS (
    SELECT date('2024-01-01')
    UNION ALL
    SELECT date(d, '+1 day') FROM days WHERE d < '2024-01-07'
)
SELECT d FROM days;

通常はこれをイベントテーブルに対して LEFT JOIN し、イベントが 0 件の日も正しくカウントできるようにします。素の GROUP BY date だとイベントがない日は丸ごと抜け落ちてしまいますが、日付シリーズを用意しておけば、どの日にも必ず 1 行が割り当てられます。

親子ツリーをたどる

再帰CTEといえばこれ、という定番のユースケースです。各行が自分の上司を指している社員テーブルを例に見てみましょう。

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE org(id, name, manager_id, depth) AS (
    SELECT id, name, manager_id, 0
    FROM employees
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, org.depth + 1
    FROM employees e
    JOIN org ON e.manager_id = org.id
)
SELECT printf('%.*c%s', depth * 2, ' ', name) AS tree
FROM org;

アンカー部分でルート（上司を持たない人）を選び、再帰部分では employees テーブルを CTE 自身と JOIN して、manager_id が CTE に既に入っている id と一致する行を拾っていきます。1回の反復ごとに階層が1つ深くなる仕組みです。depth は出力をインデントするために足しているただのカウンタです。

このやり方なら、ツリーの深さがどれだけあっても同じクエリで対応できます。2階層でも10階層でも、書き換える必要はありません。

特定の行のすべての祖先をたどる

今度は向きを逆にしてみましょう。ルートから下に降りていくのではなく、特定の社員から 上に さかのぼって、上司の連鎖をすべて取得します。

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE chain(id, name, manager_id) AS (
    SELECT id, name, manager_id
    FROM employees
    WHERE name = 'Diego'
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e
    JOIN chain ON chain.manager_id = e.id
)
SELECT name FROM chain;

アンカー部分が出発点となる従業員で、再帰ステップごとに上司（親）へとさかのぼっていきます。SQLite はルートに到達した時点で止まります。manager_id IS NULL になると JOIN の結果が空になるからです。

このパターンは、パンくずリスト、スレッド型コメント、カテゴリのパス表示など、「上までたどる」処理が必要な場面で重宝します。

終了条件と無限ループに注意

再帰CTEで一番ハマりやすいバグは、終了条件を書き忘れる、もしくは書いたつもりでも一度も発火しないケースです。次の例を見比べてみてください。

-- 永遠に実行される:
WITH RECURSIVE bad(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM bad
)
SELECT n FROM bad;

ゼロ行を返す WHERE 句がどこにもありません。これだとSQLiteは平気で無限にカウントし続けてしまいます。

無限ループを防ぐコツは2つ。

1. 再帰部分には必ず WHERE 句を書いて、行が増え続けないように歯止めをかける。
2. 開発中は外側の SELECT に LIMIT を付けておく。これは保険のようなもので、停止条件を間違えていてもクエリはちゃんと終わってくれます。

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter
)
SELECT n FROM counter LIMIT 5;

CTE 自体には終わりがありませんが、外側のクエリの LIMIT 5 で早めに打ち切られます。SQLite は賢いので、LIMIT で必要な分を超えて再帰し続けることはありません。動作確認や試行には便利ですが、本番コードではきちんとした停止条件の代わりにはなりません。

グラフの循環に注意

ツリーには循環がありませんが、一般的なグラフには循環がありえます。データに循環があると、素朴に書いた再帰 CTE は無限ループに陥ります。これを防ぐには、ここまでたどった経路を記録して、同じノードを再訪しないようにします。

CREATE TABLE edges (a INTEGER, b INTEGER);
INSERT INTO edges VALUES (1, 2), (2, 3), (3, 1), (3, 4);

WITH RECURSIVE walk(node, path) AS (
    SELECT 1, ',1,'
    UNION ALL
    SELECT e.b, path || e.b || ','
    FROM edges e
    JOIN walk ON e.a = walk.node
    WHERE instr(path, ',' || e.b || ',') = 0
)
SELECT node, path FROM walk;

path には、これまでにたどったノードをカンマ区切りで連結した文字列が入っています。新しいノードを追加する前に、WHERE 句でそのノードがすでに含まれていないかをチェックしているわけです。このガードを外すと、1 → 2 → 3 → 1 のような循環で無限ループに陥ります。

SQL には「訪問済みセット」のような組み込み機能はありません。文字列として持ち回るか、これまでの CTE 結果と JOIN するなどして、自分で用意する必要があります。

再帰CTE と自己結合の使い分け

階層を1〜2段だけたどれば十分なら、自己結合（self join）の方がシンプルで速いです。

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

SELECT e.name AS employee, m.name AS manager
FROM employees e
LEFT JOIN employees m ON e.manager_id = m.id;

これだけなら「各メンバーの直属の上司」までは追えます。でも「アダの下にぶら下がっている全員を、何階層下だろうと全部出したい」となると話は別です。深さが事前にわからないケースをきれいに書けるのは、再帰CTE（WITH RECURSIVE）だけです。深さに合わせて道具を選びましょう。

• 深さが固定で浅い場合: 自己結合を2〜3回つなぐ。
• 深さが不明、または任意の深さの場合: WITH RECURSIVE。

sqlite 再帰CTEのイメージをつかむ

再帰CTEは、宣言的に書かれたループだと思ってください。

• アンカー部はループの初期値。
• 再帰部はループ本体で、いまある行から次の行たちを生成する。
• 停止条件はループの抜け道で、再帰部が0行を返した時点でループが終わる。
• UNION ALL が、各イテレーションの結果を最終結果セットにどんどん積み上げていく。

このイメージさえ頭に入れば、構文の違和感はすっと消えます。要はSQLで書く for ループです。

次のステップ: インデックス

再帰CTEは大量の行を歩き回りますし、再帰部の中の結合は反復ごとに毎回走ります。結合に使う列にインデックスが張られていないと、パフォーマンスは一気に崖から落ちます。次の章ではインデックスを扱いますが、manager_id はまさにインデックスの恩恵を受ける典型的な列です。