[PostgreSQL 8.4+] WITH RECURSIVEの動作を理解する

この記事が前提とする環境

PostgreSQL 8.4以上
※PostgreSQLに限らずWITH RECURSIVEが存在するDBMSならこの記事の内容は概ね通用すると思いますが、動作確認していないので前提とする環境からは外しています

この記事が想定する読者

• WITHは知っているが、WITH RECURSIVEは知らない人
• WITHを用いたクエリは書けるが、WITH RECURSIVEを用いたクエリは書けない人

この記事の目的

PostgreSQL 8.4以上に存在するWITH RECURSIVEは、連番のような、結果の出力にループ処理が必要なものを作るときに便利です。

WITH RECURSIVE seq(i) AS (
    SELECT 1
    UNION ALL
    SELECT i + 1 FROM seq WHERE i < 3
)
SELECT i FROM seq;

i
1
2
3

しかし初見では上のクエリがどのようにして下の結果を出力しているのかよく分からないと思います。そこで、この記事ではWITH RECURSIVEを用いたクエリの動作を説明します。

WITH RECURSIVEを用いたクエリの動作

WITH RECURSIVEを用いたクエリは、通常のWITHを用いたクエリ同様、まずWITH RECURSIVE句の結果を計算した後、最後のSELECTを実行するという順番で処理されます。

WITH RECURSIVE seq(i) AS (
    SELECT 1
    UNION ALL
    SELECT i + 1 FROM seq WHERE i < 3
)
SELECT i FROM seq

この例の場合、seqを計算した後、SELECT i FROM seqを実行します。

WITH RECURSIVE句の結果の計算方法が問題なのですが、その説明をする前にまずは用語の定義をしておきます。公式ドキュメントによれば、WITH RECURSIVE句は必ず次のような形をとらなければならないとされています。

WITH RECURSIVE hoge AS (
    FROM hogeを含まないSELECT
    UNION ALLまたはUNION
    FROM hogeを含むSELECT
)

このとき、FROM hogeを含まないSELECTのことを非再帰項、FROM hogeを含むSELECTのことを再帰項と呼びます。

WITH RECURSIVE句の結果は次のようにして計算されます。

非再帰項を計算し、結果を作業テーブルと呼ばれる一時的な表に格納する
while (作業テーブルが空でない場合) {
    再帰項の「FROM hoge」部分を「FROM 作業テーブル」に置換し、計算結果を作業テーブルに再代入する
}
これまでの作業テーブルの各状態をUNION ALLまたはUNIONしたものをWITH RECURSIVE句の結果とする

実際に次の例を計算してみましょう。

WITH RECURSIVE seq(i) AS (
    SELECT 1
    UNION ALL
    SELECT i + 1 FROM seq WHERE i < 3
)

まず非再帰項を計算し、結果を作業テーブルの初期状態とします。

SELECT 1

i
1

現在の作業テーブルを元に作業テーブルを更新し、作業テーブルが空になるまでループを続けます。

SELECT i + 1 FROM 作業テーブル WHERE i < 3

i
2

↓

i
3

↓

i

これまでの作業テーブルの各状態をUNION ALLでまとめたものをseqとします。

i
1
2
3

これでWITH RECURSIVE句の結果が計算できました。

まとめ

whileループが出てきたことからも分かるように、WITH RECURSIVE句が実際に行っているのは再帰と言うよりもむしろ反復です（公式ドキュメントもそう言っています）。この点が理解できればWITH RECURSIVEを用いて複雑なクエリを書くこともできるようになると思います。

参考リンク

sql - How to select using WITH RECURSIVE clause - Stack Overflow

おまけ

再帰といえばフィボナッチですが、フィボナッチはこう書けます。

WITH RECURSIVE fibonacci(i, x, y) AS (
    SELECT 0, 0, 1
    UNION ALL
    SELECT i + 1, y, x + y FROM fibonacci WHERE i < 10
)
SELECT i, x FROM fibonacci;

| i | x|
|----+----|
| 0 | 0|
| 1 | 1|
| 2 | 1|
| 3 | 2|
| 4 | 3|
| 5 | 5|
| 6 | 8|
| 7 | 13|
| 8 | 21|
| 9 | 34|
| 10 | 55|