recursive query

はしがき

友達と話し合いしながら、db の recursive query に対して話題がありました。
recursive の意味はしっていますが、db からはどうやって実行されているか。わからないので、投稿します。

recursive とは？

コードの中から、自信を繰り返して呼び出して、大きい問題を小さい問題で分け、解決することです。
有名な factorial の例を javascript で書きます。

// javascript
const factorialRecursive = (n) => {
    if (n < 1) return -1
    if (n === 1) return 1
    return n * factorialRecursive(n - 1)
}
factorialRecursive(-1) // -1
factorialRecursive(1) // 1
factorialRecursive(3) // 6
factorialRecursive(5) // 120

繰り返して、自分自身を呼び出すことです。

recursive query とは？

SQL(mysql を前提で書きます)の recursive query は上の recursive と同じように、結果を出すために、繰り返して自分を呼び出すことです。

recursive query にたいして、以下のことの理解が必要そうです。

1. Common Table Expression (CTE): sql から記述された臨時の結果で、main query から呼び出すことができます。WITH で始まります。複雑な query を単純に、もしくは、ロジックを小さくなるためのことです。
2. Recursive Part: cte の recursive part は cte を参考します。なので、参考する基本的な部分と、recursive する部分があります。

WITH RECURSIVE cte AS (
  -- 基本的な部分
  UNION ALL
  -- recursive part
)

SELECT ...
FROM cte;

recursive query は以下のような挙動します。

1. 基本的な部分から始まり、テーブルを呼び出します。
2. cte がテーブルのように使い、基本的な部分をもとして、recursive part の部分を実行
3. 終了の条件にあたるまで上の２番目を実行

例

これがどんな状況から使われるか考えました。
たぶん、hierarchical data structure の場合使われると思います。
たとえば、breadcrumbs、menu のように、hierarchical なデータがあるテーブルです。

今回は breadcrumbs で説明します。

テーブルを作ります。

breadcrumbs

Name	Type	nullable
id	INT	FALSE
title	VARCHAR	FALSE
parent_id	INT	TRUE

CREATE TABLE breadcrumbs (
  id INT AUTO_INCREMENT PRIMARY KEY,
  title VARCHAR(255) NOT NULL,
  parent_id INT
);

テスト用のデータを作ります。

id	title	parent id
1	Home	NULL
2	Category	1
3	SubCategory	2
4	Item 1	3
5	Item 2	3
6	Another Category	1
7	Another SubCategory	6

INSERT INTO breadcrumbs (title, parent_id) VALUES
  ('Home', NULL),
  ('Category', 1),
  ('Subcategory', 2),
  ('Item 1', 3),
  ('Item 2', 3),
  ('Another Category', 1),
  ('Another Subcategory', 6);

recursive query 作成

breadcrumbs の level(どのぐらいの parent を持っているか)と root（Home） から、child までの title 全部を一気に見たいです。
結果は以下と予想します。

id	path	level
1	Home	0
6	Home > Another Category	1
7	Home > Another Category > Another Subcategory	2
2	Home > Category	1
3	Home > Category > Subcategory	2
4	Home > Category > Subcategory > Item 1	3
5	Home > Category > Subcategory > Item 2	3

WITH RECURSIVE breadcrumb_path AS (
  SELECT 
    id,
    title AS path,
    0 AS level
  FROM breadcrumbs
  WHERE parent_id IS NULL

  UNION ALL

  SELECT 
    b.id,
    CONCAT(bp.path, ' > ', b.title) AS path,
    bp.level + 1
  FROM breadcrumbs AS b
  INNER JOIN breadcrumb_path AS bp
    ON b.parent_id = bp.id
)
SELECT * FROM breadcrumb_path ORDER BY path, level;

参考したサイト

https://www.mysqltutorial.org/mysql-basics/mysql-recursive-cte/
https://medium.com/@ugorjicalebchijindu/explaining-recursive-query-in-sql-38c043fcc740
https://medium.com/learning-sql/understanding-recursive-sql-for-hierarchical-data-structures-76e3ac29c693
https://qiita.com/Shoyu_N/items/f1786f99545fa5053b75