Postgresqlで再帰SQLの復習 (original) (raw)

先日、たまたま再帰 SQLを書く機会があり、
私自身なんとなく存在と仕組みはわかるけどちゃんとは学んだことないなという格好だったので、ここら辺で基礎を復習しておこうと思います。
（利用するDBはタイトルの通りPostgresqlです）

再帰SQL -図解-の記事の図が非常にわかりやすかったので図で処理というか評価のフローを見たい方はこちらを参考になさるといいかと思います。

SQLの構造としてはこんな感じ。

with recursive r as (

select * from tree where id = 1 
union all

select tree.* from tree
inner join r 
  on tree.parent = r.id

) select * from r order by id ;

非再帰項と呼ばれる再帰のスタート位置になるクエリ部分と再帰項とよばれる非再帰項のあとにグルグル再帰的に実行されるクエリ部分で構成されています。

なんとなくイメージ的には

非再帰項を評価して一時テーブルに投入。
再帰項を評価して一時テーブルに投入。
2.をひたすら繰り返す。

みたいな感じのようです。（正確には再帰SQL -図解-に記載の通り、もう少し複雑なようですが、わかりやすさ重視で今回は簡略化した感じで理解しておきましょう。）

実際に書いてみる

今回はPOSTGRES の再帰処理の基本 ( WITH RECURSIVE )のサンプルテーブル・データを流用させていただきます。

▼DDL

drop table tree;

create table tree ( id integer, parent integer );

▼DML

insert into tree (id, parent) values (1, null), (2, 1), (3, 1), (4, 3), (5, null), (6, 5), (7, 6), (8, 7) ;

▼再帰 SQL

with recursive r as (

select * from tree where id = 1 
union all

select tree.* from tree
inner join r 
  on tree.parent = r.id

) select * from r order by id ;

▼取得結果

id	parent
1	null
2	1
3	1
4	3

実行計画

最後に再帰 SQLを紹介している記事ではあまり見かけなかったんですが、実行計画を見ておきましょう。

explain analyze with recursive r as (

select * from tree where id = 1 
union all

select tree.* from tree
inner join r 
  on tree.parent = r.id

) select * from r order by id ;

▼実行計画

QUERY PLAN Sort (cost=1952.85..1983.96 rows=12441 width=8) (actual time=0.078..0.079 rows=4 loops=1) Sort Key: r.id Sort Method: quicksort Memory: 25kB CTE r -> Recursive Union (cost=0.00..857.87 rows=12441 width=8) (actual time=0.019..0.068 rows=4 loops=1) -> Seq Scan on tree (cost=0.00..38.25 rows=11 width=8) (actual time=0.017..0.019 rows=1 loops=1) Filter: (id = 1) Rows Removed by Filter: 7 -> Hash Join (cost=3.58..57.08 rows=1243 width=8) (actual time=0.010..0.011 rows=1 loops=3) Hash Cond: (tree_1.parent = r_1.id) -> Seq Scan on tree tree_1 (cost=0.00..32.60 rows=2260 width=8) (actual time=0.002..0.003 rows=8 loops=3) -> Hash (cost=2.20..2.20 rows=110 width=4) (actual time=0.002..0.002 rows=1 loops=3) Buckets: 1024 Batches: 1 Memory Usage: 9kB -> WorkTable Scan on r r_1 (cost=0.00..2.20 rows=110 width=4) (actual time=0.001..0.001 rows=1 loops=3) -> CTE Scan on r (cost=0.00..248.82 rows=12441 width=8) (actual time=0.020..0.069 rows=4 loops=1) Planning Time: 0.166 ms Execution Time: 0.122 ms