特定のIdを含む全経路を取得する with 閉包テーブル

閉包テーブルにて「特定のIdを含む根～葉までの全経路」を取得しようとしたら、意外とめんどうだったのでメモ。

最適化全然出来ない。

サンプルデータ

• データ

memoId	body	previousId
1	Body 1	-1
2	Body 2	1
3	Body 3	1
4	Body 4	3
5	Body 5	3
6	Body 6	3
7	Body 7	4

• 閉包テーブル（memo_closure）

ancestor	descendant	depth
1	1	0
1	2	1
1	3	1
1	4	2
1	5	2
1	6	2
1	7	3
2	2	0
3	3	0
3	4	1
3	5	1
3	6	1
3	7	2
4	4	0
4	7	1
5	5	0
6	6	0
7	7	0

木構造のイメージはこちら。

memoId = 3を含む全経路を取得するとして、欲しい出力はこちら。 （※GROUP_CONCATを使用しているので、カンマ区切りの文字列となっている）

1,3,4,7
1,3,5
1,3,6

memoId = 4とすればこんな感じ。

1,3,4,7

クエリ

Daoにて下記のクエリを叩くことで、上記の出力が得られる。

  @Query(
    "Select GROUP_CONCAT(ancestor) as path from " +
    "  (Select ancestor, descendant from memo_closure order by depth DESC) " +
    "where descendant in " +
    "  (Select ancestor from " +
    "    (Select ancestor, count(*) as cnt from memo_closure where ancestor in " +
    "      (Select descendant from memo_closure where ancestor = :memoId) group by ancestor) where cnt = 1) " +
    "group by descendant order by path"
    )
  fun getPathEnumeration(memoId: Int): List<String>

分解

部分木の葉を取得する

基準とするmemoIdについて、部分木の葉のIdを取得する。

// `memoId`を`descendant`にもつレコードを取得。
// memo_closureの表の上で、(3, 3, 0)以下を取得
Select descendant from memo_closure where ancestor = :memoId … ①

// ancestor で group byすることで、(3, 4, 5, 6, 7)を取得。
Select ancestor, count(*) as cnt from memo_closure where ancestor in (①) group by ancestor

// count(*) = 1 により、(5, 6, 7)を取得。
// 1行しかない＝部分木の葉を表す。
Select ancestor from (...) where cnt = 1

ここまでで、memoId = 3を基準とした場合の葉のmemoId = (5, 6, 7)を取得完了。

全経路を取得する

次に、全経路を取得するクエリを作ったのち、(5, 6, 7)を含むものだけを取得していく。

// depthの逆順でソート
Select ancestor, descendant from memo_closure order by depth DESC

// depthの逆順でソートしたテーブルに対し、descendant でグループ化し、さらに
// descendant = (5, 6, 7)を含むレコードだけを取得する。
from (Select ancestor, descendant from memo_closure order by depth DESC) where descendant in (...) group by descendant

// GROUP_CONCAT関数でdescendantのグループ毎に結合して返す。
Select GROUP_CONCAT(ancestor) as path from (...) group by descendant order by path

途中、descendantでグループ化したときのイメージはこんな感じ（depthでソート済み）。

ancestor	descendant	depth
1	1	0
1	2	1
2	2	0
1	3	1
3	3	0
1	4	2
3	4	1
4	4	0
1	5	2
3	5	1
5	5	0
1	6	2
3	6	1
6	6	0
1	7	3
3	7	2
4	7	1
7	7	0

これに対し、where descendant in (5, 6, 7)を掛けることでancestor = (1, 3, 5 / 1, 3, 6 / 1, 3, 4, 7)のグループを得られる。

参考

tociyuki.hatenablog.jp