再帰クエリで循環参照した時にどうなるのか?(SQL Server, PostgreSQL)

PostgreSQL で循環参照したらどうなるん?って聞かれたので。

PostgreSQL

with recursive d as (
select 1 as id, 4 as parentid
union 
select 2 as id, 1 as parentid
union 
select 3 as id, 2 as parentid
union 
select 4 as id, 3 as parentid
), cte as (
  select id, parentid, 1 as level from d where id = 1
  union all
  select d.id, d.parentid, cte.level + 1 as level
  from cte inner join d on cte.parentid = d.id
  -- where cte.level < 100 これないと無限に再帰する
)
select * from cte
where cte.level < 100 -- ここで条件書いても無限再帰は止まらない!!
 --limit 100 limit 付けてると無限に再帰するやつでも先頭 n 件だけで返ってくる

特に上限回数みたいなのは無いっぽい、リソースが尽きるまで回り続けるんかな?

7.6. LIMITとOFFSET
7.8. WITH問い合わせ(共通テーブル式)

ループするかどうか確信が持てない問い合わせをテストする有益な秘訣として、親問い合わせにLIMITを配置します。 例えば、以下の問い合わせはLIMITがないと永久にループします。

WITH RECURSIVE t(n) AS (
SELECT 1
UNION ALL
SELECT n+1 FROM t
)
SELECT n FROM t LIMIT 100;

これが動作するのは、PostgreSQLの実装が、実際に親問い合わせで取り出されるのと同じ数のWITH問い合わせの行のみを評価するからです。 この秘訣を実稼動環境で使用することは勧められません。 他のシステムでは異なった動作をする可能性があるからです。 同時に、もし外部問い合わせを再帰的問い合わせの結果を並べ替えたり、またはそれらを他のテーブルと結合するような書き方をした場合、動作しません。 このような場合、外部問い合わせは通常、WITH問い合わせの出力をとにかくすべて取り込もうとするからです。

SQL Server

ついでに SQL Server も。

with d as (
select 1 as id, 4 as parentid
union 
select 2 as id, 1 as parentid
union 
select 3 as id, 2 as parentid
union 
select 4 as id, 3 as parentid
), cte as (
  select id, parentid, 1 as level from d where id = 1
  union all
  select d.id, d.parentid, cte.level + 1 as level
  from cte inner join d on cte.parentid = d.id
  -- where cte.level < 100 これないと無限に再帰する
)
select /*top(100)*/ * from cte -- top が無いと再帰回数上限エラーが出る
where cte.level < 100 -- ここで条件書いても無限再帰は止まらない!!

SQL Server再帰の上限回数が既定では 100 になってるので、100 回再帰した時点でエラー。
再帰回数の上限や上限変更方法は、
WITH common_table_expression (Transact-SQL) - SQL Server | Microsoft Docs *1
見てね。

再帰回数を1000回にする例だと…

with d as (
select 1 as id, 4 as parentid
union 
select 2 as id, 1 as parentid
union 
select 3 as id, 2 as parentid
union 
select 4 as id, 3 as parentid
), cte as (
  select id, parentid, 1 as level from d where id = 1
  union all
  select d.id, d.parentid, cte.level + 1 as level
  from cte inner join d on cte.parentid = d.id
)
select top(1000) * from cte
option (maxrecursion 1000)

後は、TOP (Transact-SQL) - SQL Server | Microsoft Docs
ORDER BY 句 (Transact-SQL) - SQL Server | Microsoft Docs
は似たような動きするけど、このケースでは offset fetch はダメ。
offset fetch は order by 必須なので、並び替え中に再帰の上限に達してエラーになる。

SQL Server の Top は PostgreSQL の limit と同じで order by 無いと全データ見ないで返す感じになってるみたい。

まとめ

  • 再帰クエリの外で条件書いても再帰の上限は変わらない
  • どうしても条件書けないときは limit / top で件数絞る!
    • order by はダメ。

*1:日本語は訳が酷いので英語の方が良さげ