Limit で制限する前提の無限再帰 CTE は MySQL では動かない。 Posgresql なら動く。

TL; DR

• MySQL の再帰 CTE は、一回その結果をすべて materialize している
  • なので、クエリのパフォーマンスは注意が必要
• Postgresql ならば、幅優先探索ができるはず。

本文

実証:

MySQL

mysql> select version();
+-----------+
| version() |
+-----------+
| 8.0.11    |
+-----------+
1 row in set (0.00 sec)

mysql> with recursive r as ( select 1 as n UNION ALL select n + 1 from r ) select * from r limit 10;
ERROR 3636 (HY000): Recursive query aborted after 1001 iterations. Try increasing @@cte_max_recursion_depth to a larger value.

Postgresql

test=# select version();
                                                    version                                                    
---------------------------------------------------------------------------------------------------------------
 PostgreSQL 10.5 on x86_64-apple-darwin17.7.0, compiled by Apple LLVM version 9.1.0 (clang-902.0.39.2), 64-bit
(1 row)

test=# with recursive r as ( select 1 as n UNION ALL select n + 1 from r ) select * from r limit 10;
 n  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
(10 rows)

理由

Postgresql は、そのセレクトのクエリにおいては、クエリグラフのようなものを用意し、必要な分だけ計算する。 Haskell 的なノリで、 fetch by need する。おそらくそれが効いている。

MySQL は、以下の explain を見ていると分かるけれども、

mysql> explain with recursive r as ( select 1 as n UNION ALL select n + 1 from r ) select * from r limit 10;                            
+----+-------------+------------+------------+------+---------------+------+---------+------+------+----------+----------------+
| id | select_type | table      | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra          |
+----+-------------+------------+------------+------+---------------+------+---------+------+------+----------+----------------+
|  1 | PRIMARY     | <derived2> | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    3 |   100.00 | NULL           |
|  2 | DERIVED     | NULL       | NULL       | NULL | NULL          | NULL | NULL    | NULL | NULL |     NULL | No tables used |
|  3 | UNION       | r          | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    2 |   100.00 | Recursive      |
+----+-------------+------------+------------+------+---------------+------+---------+------+------+----------+----------------+
3 rows in set, 1 warning (0.00 sec)

cte の結果のテーブルが導出されて、そこから PRIMARY の駆動が ALL で走っている。ちなみに、id=3 の駆動の type=ALL は、少なくとも公式ドキュメントを見る限りでは、1回前で新しく追加された rows に対しての ALL を表している様子。

MySQL は、 join にならないかぎり、ある駆動表が依存するテーブルたちは、一度中間テーブルとして全体が実体化される。今回は cte のテーブルを実体化している最中に再帰の上限値をオーバーした。

何が言えるか

MySQL で再帰CTE を使う場合は、それは何かしらの(条件付き)閉包を計算したくて、かつ、その結果自体がほしかったものである場合、においてのみ使うとよさそう。具体的には子孫列挙とか。

postgres の性質を活かすと、たとえばグラフ構造をデータベースに突っ込んで、幅優先探索を再帰 CTE 、でできると思われる。where finished = true limit 1 で終了条件として、 CTE を組めば多分これができる。今回の数列の select を、 limit 1 offset 10000000 とかにしてみても、利用するリソースは CPU だけだったので、多分効率的に探索が組めるはず。