閉包テーブルの再帰クエリ

概要

弊社業務にて閉包テーブルを使った設計を取り入れました。
この時閉包テーブルがどういったものなのか、またSQLを書く際にどのように考えていけばいいのか少し苦戦したのでまとめておきます。
使用しているDBはpostgresql ver14.4です。

閉包テーブルとは

RDBで階層構造を表現する際に用いられるデータモデルです。
一つのレコードに対して、また別のレコードが連なっていくことで階層構造を表現することができます。
イメージしやすいのは会社の組織でしょうか。

ER図

会社組織を参考に、閉包テーブルを考えてみます。
基本的なER図は下記のようになります。

• departments: 組織の部署など役割を表す
• department_closure_tables: 組織の階層構造を表現する
  • ancestor: 祖先を表す
  • descendant: 子孫を表す
  • path_length: 祖先 ~ 子孫までの距離を表す

実際に階層構造をレコードで表現してみる

簡単にするために下記のようなごく単純な階層を表現してみます。

departmentsテーブル

key	name
top	社長
department1	開発部
department2	営業部
devision1	toC開発課

department_closure_tables

これだけの構造を表現するだけでもレコード数が多くちょっと大変ですね・・。
ポイントは階層構造を表現するためにancestor_keyとdescendant_keyと組み合わせを網羅する必要があることかなと思います。

No	ancestor_key	descendant_key	path_length
1	top	top	0
2	top	department1	1
3	top	devision1	2
4	department1	department1	0
5	department1	devision1	1
6	devision1	devision1	0
7	top	department2	1
8	department2	department2	0

閉包テーブルのSQL

実際にSQLを書いてみようと思います。
再帰参照などを用いた複雑なクエリになることが多いです。

あるancestorを起点に、ある深さまで階層を取得する

上記のようなレコードを取りたい場合、下記のようなクエリになります。

WITH RECURSIVE tree as (
	SELECT
		0 AS depth,
		dcs.ancestor_key AS ancestor_key,
		dcs.descendant_key AS descendant_key,
		dcs.path_length AS path_length
	FROM department_closure_tables dcs
	WHERE
		dcs.ancestor_key = ${from} AND dcs.path_length = 0
UNION ALL
	SELECT
		depth + 1 AS depth,
		dcs2.ancestor_key,
		dcs2.descendant_key,
		dcs2.path_length
	FROM department_closure_tables dcs2
	JOIN tree t ON t.descendant_key = dcs2.ancestor_key AND dcs2.path_length = 1 AND t.depth < ${to}
)
SELECT
    t.depth, t.ancestor_key AS ancestor_key, t.descendant_key AS descendant_key, r.name AS department_name
FROM tree t
INNER JOIN departments d ON d."key" = t.descendant_key
;

クエリの実行結果

変数を下記のように設定した場合の実行結果です。

• from = 'top'
• to = 2

depth	ancestor_key	descendant_key	resource_name
0	top	top	社長
1	top	department1	開発部
1	top	department2	営業部
2	department1	devision1	toC開発課

クエリの解説

非再起のクエリ部分

• 起点となる階層を選んでいる この時のdepthを0とする

	SELECT
		0 AS depth,
		dcs.ancestor_key AS ancestor_key,
		dcs.descendant_key AS descendant_key,
		dcs.path_length AS path_length
	FROM department_closure_tables dcs
	WHERE
		dcs.ancestor_key = 'top' AND dcs.path_length = 0

depth	ancestor_key	descendant_key	path_length
0	top	top	0

次に再起的に実行する部分

• 起点の子孫(descendant_key)からpath_length = 1 のレコードを探します。
• これを検索結果が空になるまで(depthが2より小さい間)続けます。

	SELECT
		depth + 1 AS depth,
		dcs2.ancestor_key,
		dcs2.descendant_key,
		dcs2.path_length
	FROM department_closure_tables dcs2
	JOIN tree t ON t.descendant_key = dcs2.ancestor_key AND dcs2.path_length = 1 AND t.depth < 2

depth = 0 の時、実行結果はdepth = 1になる

depth	ancestor_key	descendant_key	path_length
1	top	department1	1
1	top	department2	1

depth = 1 の時、実行結果はdepth = 2 になる

depth	ancestor_key	descendant_key	path_length
2	department1	devision1	1

検索結果を統合する部分

• 上記の検索結果全てをUNION ALLする
• このUNION ALLしたテーブルをtreeと名付ける

WITH RECURSIVE tree as (
	SELECT
		0 AS depth,
		rcs.ancestor_key AS ancestor_key,
		rcs.descendant_key AS descendant_key,
		rcs.path_length AS path_length
	FROM resource_closure_tables rcs
	WHERE
		rcs.ancestor_key = 'org1' AND rcs.path_length = 0
UNION ALL
	SELECT
		depth + 1 AS depth,
		rcs2.ancestor_key,
		rcs2.descendant_key,
		rcs2.path_length
	FROM resource_closure_tables rcs2
	JOIN tree t ON t.descendant_key = rcs2.ancestor_key AND rcs2.path_length = 1 AND t.depth < 2
)

treeテーブル

depth	ancestor_key	descendant_key	path_length
0	org1	org1	0
1	org1	loc1	1
1	org1	loc2	1
2	loc2	pos1	1

selectで欲しい値を取得する部分

上記で取得したtreeテーブルと、departmentsテーブルをJOINします。
その後SELECTで欲しいカラムを指定しています。

SELECT
    t.depth, t.ancestor_key AS ancestor_key, t.descendant_key AS descendant_key, r.name AS department_name
FROM tree t
INNER JOIN departments d ON d."key" = t.descendant_key

まとめ

閉包テーブルの再帰参照について書きました。
再帰クエリは使う機会が少ないこともありあまり慣れておらず、文法もクセがあるので理解するまでに少し時間がかかりましたが、使えるようになると非常に便利だなと感じました。
今回の記事では記載しなかったのですが、閉包テーブルを用いることで階層の末尾に新しいレコードを追加したり、階層の中間に新しいレコードを追加したりかなり自由度高く表現することができます。

さいごに

トレタでは一緒に開発する仲間を募集しています。

興味がある方は是非カジュアル面談へお越しください！