Posted at

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

More than 1 year has passed since last update.


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 だけだったので、多分効率的に探索が組めるはず。