再帰クエリが使えると何が嬉しいのか

2018年4月にリリースされたMySQL 8.0の新機能として、CTE(共通テーブル式)が導入されました。いわゆるWITH句というやつです。

今までFROM句にサブクエリで書いていたような式をWITH句で定義しておくことで再利用ができたり、可読性が上がったりと何かと便利です。

ただこのCTEの本当に嬉しいところは「再帰クエリ」が書けるようになることだと思っています。実際に使ってみたいと思います。

再帰とは

再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。
出典: https://ja.m.wikipedia.org/wiki/再帰

SQLを一旦離れて一般的な話をすると、再帰処理を使うとフィボナッチ数列を計算するプログラムや、ツリー構造(例えばファイルシステム内のフォルダ)をパースしていくプログラムを簡潔に書くことができます。

Rubyで書いたn番目のフィボナッチ数を求める関数(計算量がとんでもないことになるので本当はメモ化などを使ったほうがいい)↓
このように関数の定義の中で自分自身を呼び出すようになっています。

def fib(n)
   return n if n == 0 || n == 1
   return fib(n - 1) + fib(n - 2)
end

その他の例を出すと、「再帰的頭字語」という言葉を聞いたことあるでしょうか。

再帰的頭字語（さいきてきとうじご、英: recursive acronym）は、その正式名称の中にそれ自身が含まれている頭字語を指す。
出典: https://ja.wikipedia.org/wiki/再帰的頭字語

例えば以下のような頭字語(アルファベットで表した略称)が再帰的頭字語です。

VISA - Visa International Service Association
PHP - PHP: Hypertext Preprocessor
cURL - Curl URL Request Library
GNU - GNU's Not Unix
YAML - YAML Ain't Markup Language

ご覧の通り、頭字語の定義自体に頭字語が記述されています。
因みにこれ街で見つけるとテンション上がるので是非探してみてください。

再帰クエリが使えると何が嬉しいのか

ずばりRDBで階層構造を表すために「ナイーブツリー」を採用したときめちゃめちゃ便利です。ナイーブツリーとは各レコードに親のidを持たせて階層構造を表す方法です。

例として以下のような構造を作ってみます。

foo
  └ bar
      └ baz - fuga - piyo
          └ hoge
      
+------+-----------+------+
| id   | parent_id | name |
+------+-----------+------+
|    1 |      NULL | foo  |
|    2 |         1 | bar  |
|    3 |         1 | baz  |
|    4 |         3 | hoge |
|    5 |         3 | fuga |
|    6 |         5 | piyo |
+------+-----------+------+

ここでidが1のレコードの子レコードを取得したいとき、再帰クエリを使わない場合は以下のように取得します。

【1階層だけ取得】

(
  SELECT
    *
  FROM
    naive_tree
  WHERE
    id = 1
)
UNION
ALL (
  SELECT
    n. *
  FROM
    naive_tree n
    JOIN (
      SELECT
        id
      FROM
        naive_tree
      WHERE
        id = 1
    ) p ON n.parent_id = p.id
);

- 結果 -
+----+-----------+------+
| id | parent_id | name |
+----+-----------+------+
|  1 |      NULL | foo  |
|  2 |         1 | bar  |
|  3 |         1 | baz  |
+----+-----------+------+

【2階層だけ取得】

(
  SELECT
    *
  FROM
    naive_tree
  WHERE
    id = 1
)
UNION
ALL (
  SELECT
    n. *
  FROM
    naive_tree n
    JOIN (
      SELECT
        id
      FROM
        naive_tree
      WHERE
        id = 1
    ) p ON n.parent_id = p.id
)
UNION
ALL (
  SELECT
    n. *
  FROM
    naive_tree n
    JOIN (
      SELECT
        n. *
      FROM
        naive_tree n
        JOIN (
          SELECT
            id
          FROM
            naive_tree
          WHERE
            id = 1
        ) q ON n.parent_id = q.id
    ) p ON n.parent_id = p.id
);

- 結果 -
+----+-----------+------+
| id | parent_id | name |
+----+-----------+------+
|  1 |      NULL | foo  |
|  2 |         1 | bar  |
|  3 |         1 | baz  |
|  4 |         3 | hoge |
|  5 |         3 | fuga |
+----+-----------+------+

このように取得する階層が増えるたびにUNIONする回数が増えていきます。最初から何階層まで取得するか分かっていればいいですが、割とあるケースが最下層まで取得したいというパターン。その場合はかなりクエリが複雑になっていきます。

そこで再帰クエリの登場です。再帰クエリを使うとこんなにシンプルに書くことができます。

【再帰クエリを使って最下層まで取得】

WITH RECURSIVE cte AS (
  SELECT
    n. *
  FROM
    naive_tree n
  WHERE
    id = 1
  UNION
  ALL
  SELECT
    child_naive_tree. *
  FROM
    naive_tree AS child_naive_tree,
    cte
  WHERE
    cte.id = child_naive_tree.parent_id
)
SELECT
  *
FROM
  cte;

- 結果 -
+------+-----------+------+
| id   | parent_id | name |
+------+-----------+------+
|    1 |      NULL | foo  |
|    2 |         1 | bar  |
|    3 |         1 | baz  |
|    4 |         3 | hoge |
|    5 |         3 | fuga |
|    6 |         5 | piyo |
+------+-----------+------+

理論上、何階層あっても同じクエリで最下層まで取得することができます。
再帰の定義にあった通り、WITH句で定義したcteという共通テーブル式の中にcte自身が記述されています。

FROM
  naive_tree AS child_naive_tree,
  cte <- ここ

まとめ

このように再帰クエリをうまく使うことで、使わない場合よりかなりクエリをシンプルに書くことができます。
ただしRDBで階層構造を表すためにナイーブツリーを使うのは割とアンチパターンだったりします。(更新時などに整合性を保つのが大変)

次回は階層構造を表す別の方法(経路列挙モデルや閉包テーブルモデルなど)についてまとめてみます。

(サムネイルは街で見つけたイケてる再帰的頭字語)
YES - Yes! English School