Alopex DBの再帰CTE ― PostgreSQL・SQLite・DataFusionと実装を比べる

社員から組織の最上位まで上司を遡る、部品表を展開するなど、階層の深さが決まっていない問い合わせには、WITH RECURSIVEを使います。

Alopex DBはv0.8.7から再帰CTEに対応済みです。この記事では、Alopex DBの再帰CTEがどのように動き、どこで止まるのかを説明します。あわせて、PostgreSQL、SQLite、DataFusionの実装と比べて、違いを整理します。

再帰CTEの動き

再帰CTEは最初の行を作る非再帰項（アンカーとも呼ばれます）と、自分自身を参照する再帰項の二つでできています。次の例は1から5までの数を作る問い合わせです。

WITH RECURSIVE counter(n) AS (
    SELECT 1                              -- 非再帰項
    UNION ALL
    SELECT n + 1 FROM counter WHERE n < 5 -- 再帰項
)
SELECT n FROM counter ORDER BY n;

最初に非再帰項を一度だけ実行して、最初の行を作ります。次に、直前の反復で増えた行をcounterの中身として再帰項を実行し、新しい行を作ります。この操作を繰り返し、新しい行が出なくなった時点で終わりです。

どの実装も直前の反復で増えた行を保持し、重複の扱いと止め方を決めています。実装ごとの違いはこの保持のしかたと止め方に出ます。

Alopex DBの実装

再帰かどうかの判定

WITH RECURSIVEと書いてあっても、CTEが自分を参照していなければ、再帰の処理は必要ありません。Alopex DBでは、CTE同士の参照に循環があるときだけ再帰として扱っています。循環がないときは、通常のCTEとして実行します。

実行前の形のチェック

再帰として扱うと判断したあと、実行の前に、問い合わせの形が次の条件に合っているかを確認しています。

• CTEが一つだけであること
• UNIONまたはUNION ALLが一つだけであること
• 非再帰項が自分を参照していないこと
• 再帰項が自分を直接一回だけ参照していること
• 再帰項に、副問い合わせ、入れ子のWITH、集合演算がないこと
• CTEの本体に、ORDER BY、LIMIT、OFFSETがないこと
• 非再帰項と再帰項で、列の数と型が一致していること

条件に合わない問い合わせは、ALOPEX-F001を返して未対応であることを知らせます。RECURSIVEを無視して一回だけ実行する、といった動き方はしません。

増えた行による反復計算

再帰の計算は、新しい行が出なくなるまで、直前の反復で増えた行を使って反復する形で行っています。流れは次のとおりです。

累積 = 非再帰項の結果
増えた行 = 累積
増えた行が空でない間:
    増えた行を自己参照の中身として、再帰項を実行する
    UNIONの場合は、すでに出た行を除く
    累積に追加し、今回増えた行を次の反復に引き継ぐ

再帰項が読むのは、前の反復で増えた行だけです。これまでに累積した全行は読みません。UNIONの場合は、反復をまたいで出た行を覚えておき、同じ行を二度加えないようにしています。UNION ALLの場合は、重複した行もそのまま加えます。

階層をたどる例も紹介します。次の問い合わせはid = 3の行から始めて、parent_idをたどって最上位の行まで遡ります。

CREATE TABLE employees (id INTEGER PRIMARY KEY, parent_id INTEGER, name TEXT);
INSERT INTO employees VALUES
    (1, NULL, 'root'), (2, 1, 'manager'), (3, 2, 'worker');

WITH RECURSIVE ancestors AS (
    SELECT id, parent_id, name FROM employees WHERE id = 3
    UNION ALL
    SELECT e.id, e.parent_id, e.name
    FROM employees e JOIN ancestors a ON e.id = a.parent_id
)
SELECT id, name FROM ancestors ORDER BY id;

[{'id': 1, 'name': 'root'}, {'id': 2, 'name': 'manager'}, {'id': 3, 'name': 'worker'}]

rootのparent_idはNULLなので、JOINの結果が空になります。新しい行が出なくなるため、そこで処理が終わります。

止まらない問い合わせの上限

UNION ALLで循環するデータを扱うと、行が増え続けて処理が終わりません。そのためAlopex DBでは現時点で次の三つの上限を設けています。

どれかを超えると、ALOPEX-E003を返して処理を止めます。たとえば、次の問い合わせは自分自身の行を増やし続けるため、反復回数の上限に達して止まります。

WITH RECURSIVE c(n) AS (SELECT 1 UNION ALL SELECT n FROM c)
SELECT n FROM c;

error[ALOPEX-E003]: resource exhausted: recursive CTE 'c' reached iteration limit 1000

現時点では、この値をSQLから変えることはできません。上限を調整したい場面があれば、ご要望をお寄せください。ご要望に応じて改修します。

他の実装との違い

PostgreSQL

PostgreSQLも前の反復で増えた行だけを次の反復に渡す方式です。二つの表を用意し、反復のたびに入れ替えながら、前の反復の結果を次の反復に引き継ぎます。UNIONの場合は、ハッシュ表を使って重複を除いています。

再帰項に対する制限はAlopex DBとよく重なります。再帰参照は副問い合わせの中、外部結合の中、INTERSECTやEXCEPTの中に置けません。同じCTEを二回以上参照することもできません。相互再帰と、再帰クエリでのORDER BYやLIMITは未実装です。一方で、反復回数や行数の上限は設けられていません。

SQLite

SQLiteは行を一つずつ処理する方式です。非再帰項の行をQueueに入れ、そこから一行ずつ取り出して出力します。取り出した行を自己参照の中身にして再帰項を実行し、その結果をQueueに戻します。この繰り返しが処理の流れです。

ORDER BYを付けると、Queueが先入れ先出しから優先度付きになり、たどる順番を指定できます。LIMITを付けると、指定した行数を出力した時点で処理が止まります。無限に続く問い合わせを止めるのは、利用者が付けるLIMITの役目です。なお、再帰クエリでは窓関数と集約を使えません。

DataFusion

DataFusionは非再帰項と再帰項の二つを持ちます。前の反復の結果を作業テーブルに入れ、再帰項に渡す点はAlopex DBと同じです。UNIONの場合は、重複を除いてから次の反復に渡します。自己参照が二つ以上ある問い合わせは受け付けません。

Alopex DBとの違いは結果の返し方と止め方にあります。DataFusionはバッチを受け取るたびに結果を出力へ流します。Alopex DBは再帰が終わるまで結果を集めてから返す方式です。DataFusionには無限再帰を検出する仕組みがなく、ソースのコメントには、無限再帰を避けるのは計画を作る側の役目だと書かれています。

比較結果

四つの実装を、反復の単位、結果の返し方、止め方、自己参照の扱いで比べると、次のようになります。

Alopex DBの増えた行の扱いは、PostgreSQLに近い形です。前の反復で増えた行だけを再帰項に渡し、UNIONの場合は全反復をまたいで重複を除いています。

止め方については、SQLiteは利用者が付けるLIMITに任せ、DataFusionは計画を作る側に任せています。Alopex DBは、利用者が何も書かなくても処理が止まるように、実行側に上限を置きました。

対応していない形の問い合わせは、黙って実行せず、ALOPEX-F001を返して未対応であることをお知らせします。

再帰CTEはクイックスタートから試せます。

参考資料

• Alopex DB（GitHub）
• PostgreSQL nodeRecursiveunion.c
• PostgreSQL parse_cte.c
• SQLite select.c
• DataFusion recursive_query.rs