閉包テーブル (Closure Table) に順序を持たせソートした結果を取得する #SQL

はじめに

対象となる読者

ツリー構造のデータを RDB で扱うために閉包テーブル (Closure Table) を検討している人
閉包テーブルで順序を保持する方法を探している人

この記事を読んだ後できるようになること

閉包テーブルで順序を保持する方法がわかります
閉包テーブルから深さ優先探索 (前順・先行順・前置順・行きがけ順) でソートした結果を取得できます
この方法を採用する場合に注意すべき点がわかります

この記事を書いたときの環境

DB: PostgreSQL 9.6.1

なぜ閉包テーブル (Closure Table) を採用しようと思ったか

今まではツリー構造のデータを扱うときに入れ子集合 (Nested Set) を採用することが多かったのですが、このモデルの問題はノードを挿入するために隙間を開ける必要があり、挿入するノードの right より大きい left or/and right を持つ全てのレコードを更新する必要があります。詳しくは SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデルなどを参照ください。
例えば10,000件で構成されるツリーがあって、ルートの 最初の子 として挿入する場合は INSERT に加えて、10,000件のレコードの UPDATE が必要になります。
そのため、頻繁に追加 (更新、削除) を行うような編集機能で大量のデータを扱うとパフォーマンスが問題になることが多くありました。

そんなとき、SQLアンチパターンを読んで 閉包テーブル (Closure Table) というモデルの存在を知りました。
閉包テーブルでは頻繁に追加が発生する場合でも挿入位置によらず一定のパフォーマンスが期待できます (階層の非常に深いノードに追加する場合は問題が出る可能性がありますが・・・)。
しかし、単純な閉包テーブルでは兄弟の順序を保持しないため、順序でソートした結果を取得することができません。

この記事では、閉包テーブルを拡張し、深さ優先探索 (前順・先行順・前置順・行きがけ順) でソートした結果を取得するための方法を説明します。

当記事で扱うサンプル

順序があるツリー構造の例としては料理のレシピなどがあります。
ここでは次の卵焼きのレシピを題材にします。 ※このレシピでおいしい卵焼きが作れるかは保証しません。

卵焼き
1. 下ごしらえ
  1. ボウルに卵を割り入れる
  2. 調味料を加える
  3. かきまぜる
2. 焼く
  1. フライパンを中火で熱する
  2. 油をしく
  3. 卵を流し入れる
  4. 均一に広げる
3. 盛り付ける
  1. 1口大に切る
  2. お皿に並べる

スキーマの定義とデータの準備

CREATE TABLE recipes (
    id   BIGINT NOT NULL PRIMARY KEY,
    name TEXT NOT NULL
);

CREATE TABLE steps (
    recipe_id   BIGINT NOT NULL,
    id          BIGINT NOT NULL,
    description TEXT NOT NULL,
    nth_child   BIGINT NOT NULL,
    PRIMARY KEY (recipe_id, id),
    FOREIGN KEY (recipe_id) REFERENCES recipes(id)
);

CREATE TABLE tree_paths (
    recipe_id   BIGINT NOT NULL,
    ancestor    BIGINT NOT NULL,
    descendant  BIGINT NOT NULL,
    path_length BIGINT NOT NULL,
    PRIMARY KEY (recipe_id, ancestor, descendant),
    FOREIGN KEY (recipe_id) REFERENCES recipes(id),
    FOREIGN KEY (recipe_id, ancestor) REFERENCES steps(recipe_id, id),
    FOREIGN KEY (recipe_id, descendant) REFERENCES steps(recipe_id, id)
);

拡張したポイントは次の2つです。

steps.nth_child: 何番目の兄弟か
tree_paths.path_length: 子孫 (descendant) から祖先 (ancestor) までの距離

※tree_paths.path_length は SQLアンチパターンにも登場しています。

データを流し入れます。

INSERT INTO recipes (id, name) VALUES
(1, '卵焼き');

INSERT INTO steps (recipe_id, id, description, nth_child) VALUES
(1, 1, '卵焼き', 1),

(1, 2, '下ごしらえ', 1),
(1, 5, 'ボウルに卵を割り入れる', 1),
(1, 6, '調味料を加える', 2),
(1, 7, 'かきまぜる', 3),

(1, 3, '焼く', 2),
(1, 8, 'フライパンを中火で熱する', 1),
(1, 9, '油をしく', 2),
(1, 10, '卵を流し入れる', 3),
(1, 11, '均一に広げる', 4),

(1, 4, '盛り付ける', 3),
(1, 12, '1口大に切る', 1),
(1, 13, 'お皿に並べる', 2);

INSERT INTO tree_paths (recipe_id, ancestor, descendant, path_length) VALUES
(1, 1, 1, 0),

(1, 1, 2, 1),
(1, 2, 2, 0),
(1, 1, 5, 2),
(1, 2, 5, 1),
(1, 5, 5, 0),
(1, 1, 6, 2),
(1, 2, 6, 1),
(1, 6, 6, 0),
(1, 1, 7, 2),
(1, 2, 7, 1),
(1, 7, 7, 0),

(1, 1, 3, 1),
(1, 3, 3, 0),
(1, 1, 8, 2),
(1, 3, 8, 1),
(1, 8, 8, 0),
(1, 1, 9, 2),
(1, 3, 9, 1),
(1, 9, 9, 0),
(1, 1, 10, 2),
(1, 3, 10, 1),
(1, 10, 10, 0),
(1, 1, 11, 2),
(1, 3, 11, 1),
(1, 11, 11, 0),

(1, 1, 4, 1),
(1, 4, 4, 0),
(1, 1, 12, 2),
(1, 4, 12, 1),
(1, 12, 12, 0),
(1, 1, 13, 2),
(1, 4, 13, 1),
(1, 13, 13, 0);

深さ優先探索 (前順・先行順・前置順・行きがけ順) でソートした結果を取得するクエリ

これがこの記事の本題です。

SELECT s.id, s.description, t.path
 FROM (
SELECT t1.descendant, STRING_AGG(LPAD(CAST(ss.nth_child AS text), 2, '0'), '-' ORDER BY t2.path_length DESC) AS path
  FROM tree_paths AS t1
 INNER JOIN tree_paths AS t2
    ON t2.recipe_id = t1.recipe_id
   AND t2.descendant = t1.descendant
 INNER JOIN steps AS ss
    ON ss.recipe_id = t2.recipe_id
   AND ss.id = t2.ancestor
 WHERE t1.recipe_id = 1
   AND t1.ancestor = 1
 GROUP BY t1.descendant
) AS t
 INNER JOIN steps AS s
    ON s.recipe_id = 1
   AND s.id = t.descendant
 ORDER BY path ASC;

結果:

id	description	path
1	卵焼き	01
2	下ごしらえ	01-01
5	ボウルに卵を割り入れる	01-01-01
6	調味料を加える	01-01-02
7	かきまぜる	01-01-03
3	焼く	01-02
8	フライパンを中火で熱する	01-02-01
9	油をしく	01-02-02
10	卵を流し入れる	01-02-03
11	均一に広げる	01-02-04
4	盛り付ける	01-03
12	1口大に切る	01-03-01
13	お皿に並べる	01-03-02

少し補足すると、STRING_AGG(LPAD(CAST(ss.nth_child AS text), 2, '0'), '-' ORDER BY t2.path_length DESC) AS path のゼロパディングする桁数 (この例だと 2) は必要十分な長さにしておくか、事前に MAX(nth_child) で最大値を取得して必要な桁数を計算しておきます。

この例は PostgreSQL ですが MySQL でも同等のやり方ができます。ただし、使用する関数が変わるのでこのクエリにポータビリティはありません。

パフォーマンスの問題

ここで紹介したクエリにはパフォーマンスの問題があります。原因は、結合するレコード数が比較的多くなることやソートキー (path) を動的に生成しているためです。

僕が実際に作成しているプロダクトでのベンチマークでは、52,001件で構成されるツリー全体を取得したら次のような結果になりました。

Model	ms
Closure Table	2852.243
Nested Set	119.762

約24倍くらいの差が出てしまいました。取得件数の増加にともなって指数関数的に性能が悪化しているようでした。
僕のプロダクトでは1度に取得する件数はこのくらいが最大になると予測していて、全体を取得するのはページロード時だけでその後は更新が主になる予定なのでギリギリ耐えられる速度かなと。どうだろう・・・

この問題を解決するために explain でボトルネックを解析してみたり、インデックスを張ってみたりしましたが改善されませんでした。
あと、ソートキー (かその中間結果) を挿入時に生成しておくことについても様々なパターンを机上で考えましたが、どの考えも挿入位置以降の全ノードの更新が必要になるという結論にいきつくばかりでした。

今、考えている他のアイデアは、ツリー全体の読み込みは編集開始前が多いので一定のタイミングで別形式に変換したデータをどこかにキャッシュしておくことです。キャッシュが最新であればキャシュから読み込むようにすれば早くなるけど、同期のしくみとかダーティーリードしないようなしくみとかちょっと複雑にはなってしまいますが効果はあるでしょう。

まとめ

閉包テーブルは順序を持たない階層構造を扱う場合にはなかなか使えると思います。
ここで紹介した方法で順序を持つ場合にも対応できますが、1度に大量のデータをソートして取得する場合はパフォーマンスが問題にならないことを事前に検証したほうがいいです。

他に何かいい解決策があればご紹介いただけるとうれしいです。

閉包テーブル (Closure Table) に順序を持たせソートした結果を取得する