１．はじめに
RDBでの階層構造の関係を持つデータを扱う上で、
効率的なデータの持ち方や抽出方法について検証を行っています。
結論から先に
- 階層構造を扱う方法として下記の種類があります。
- 隣接リスト
- 経路列挙
- 入れ子集合
- 閉包テーブル
- 再帰クエリ（
WITH RECURSIVE）を使うと階層データを扱う上でのパフォーマンスが得られます。 - 検索性、更新量、データ量など加味すると隣接リストで再帰クエリを用いるのがよさそう。
２．階層構造を持つデータの概要
階層構造を持つデータとは
複数の要素（データ）が親子関係で結びついている構造を持つデータ
1つの要素が複数の要素の親になることができ、
また、1つの要素が複数の子要素を持つこともあります。
ある要素を親として、細分化された子要素であったり、
類似する要素を抽象化したものを親要素とするようなデータ。
階層構造を持つデータの例
- 組織における事業部、部署、係、チームのような組織構造
- 都道府県、市区町村の階層
- 商品カテゴリ（大分類、中分類、小分類など）
- パソコンのファイルシステム（ディレクトリ、ファイル）
- ゲームのステージ構成（ワールド、エリア、ステージ）
階層構造を持つデータの問題点
- データの参照が複雑になる
親子関係の関係性を表示するため、親要素に紐づく子要素を取得し、
子要素に紐づく孫要素を取得するなど、データ取得回数が増加していく。 - データの更新が複雑になる
子要素の削除や親要素の変更などに伴い、
それに紐づく階層構造を整合性を保ちながら
更新する必要がある - 結果、実行時間が掛かり処理が遅くなる。
３．階層構造データを表現する方法
種類
- 隣接リスト（ナイーブツリー（素朴な木））
- 経路列挙（Path Enumeration）
- 入れ子集合
- 閉包テーブル
階層データの例
ここでは下記のような階層を持つデータについてそれぞれの表現方法で考えてみます。
まずは種類ごとにざっくりイメージ図
隣接リスト（ナイーブツリー（素朴な木））
- 一番単純な構造。そのため、ナイーブツリー（素朴な木）と呼ばれます。
- ある要素のデータについて、その親データのIDを持たせます。
- SQLアンチパターンでは、よくない例＝アンチパターンとして位置づけられている構造です。
経路列挙（Path Enumeration）
- ある要素のデータについて、その要素までの親データのIDをパス（経路）情報として持たせます。
入れ子集合
- ある要素を円とみなして、階層関係を円の抱合関係として捉え直した構造。
子要素は親要素の円の中に囲まれている、という構造です。
閉包テーブル（Closure Table）
- ある要素のデータについて、それに連なる子データのIDを持ったテーブルを別で用意します。
隣接リスト（ナイーブツリー）のデータの持ち方
ある要素のデータについて、その親データのIDを持たせる。
データ
| ID | 親ID | 名前 |
|---|---|---|
| 1 | なし | リニューアル案件 |
| 11 | 1 | ユビキタス言語 |
| 12 | 1 | 設計 |
| 121 | 12 | アーキテクチャ構成 |
| 122 | 12 | ドメインモデル |
| 123 | 12 | 機能一覧 |
| 1221 | 122 | クライアント |
| 1222 | 122 | アカウント |
| 1223 | 122 | リソース |
クエリ
検索
-- 子を取得する
SELECT g1.id, g1.name, g1.parent_id
, g2.id, g2.name, g2.parent_id
, g3.id, g3.name, g3.parent_id
FROM `groups` g1
LEFT JOIN `groups` g2 ON g2.parent_id = g1.id
LEFT JOIN `groups` g3 ON g3.parent_id = g2.id
WHERE g1.id = '1d2a8b1';
-- 親を取得する
SELECT g1.id, g1.name, g1.parent_id
, g2.id, g2.name, g2.parent_id
, g3.id, g3.name, g3.parent_id
FROM `groups` g1
LEFT JOIN `groups` g2 ON g2.id = g1.parent_id
LEFT JOIN `groups` g3 ON g3.id = g2.parent_id
WHERE g1.id = '1d2a8b3';
挿入
INSERT INTO `groups` (id, parent_id, name)
VALUES (5, 4, 'グループ５');
更新
UPDATE `groups` SET parent_id = 6 WHERE parent_id = 5;
削除
DELETE `groups` WHERE id = 5;
隣接リストの特徴
- 追加：親のIDを指定してレコードを追加。◎
- 変更：親のIDを付け替える。◎
- 削除：階層の途中を削除する場合、子要素が紐づく親が存在しなくなる。✖
- 検索：階層構造の全体や、ある要素からの階層を取得するのが困難。✖
１つ上の親要素のIDしか持たないため、親IDを元に親要素を取得し、
その要素の親IDを取得し、と1つずつ辿っていく必要があるため。
対策
- 再帰クエリを使用する。使用できるDBを選択する。
- 階層の数を制限する。
- 削除時の階層不整合を起こさせないため、
論理削除を用いてデータ上は階層状態を維持させる。
経路列挙のデータの持ち方
ある要素のデータについて、その要素までの親データのIDをパス（経路）情報として持たせる。
データ
| ID | パス | 名前 |
|---|---|---|
| 1 | 1/ | リニューアル案件 |
| 11 | 1/11/ | ユビキタス言語 |
| 12 | 1/12/ | 設計 |
| 121 | 1/12/121/ | アーキテクチャ構成 |
| 122 | 1/12/122/ | ドメインモデル |
| 123 | 1/12/123/ | 機能一覧 |
| 1221 | 1/12/122/1221/ | クライアント |
| 1222 | 1/12/122/1222/ | アカウント |
| 1223 | 1/12/122/1223/ | リソース |
クエリ
検索
-- 子を取得する
SELECT * FROM `groups`
WHERE path LIKE '1/%';
SELECT * FROM `groups`
WHERE path LIKE '1/11/%';
-- 親を取得する
SELECT * FROM `group`
WHERE '1/2/3/' LIKE CONCAT(path, '%');
‘1/’ => '1/2/3/' LIKE ‘1/%’ ・・・〇
‘1/2/’ => '1/2/3/' LIKE ‘1/2/%’ ・・・〇
‘1/2/3/’ => '1/2/3/' LIKE ‘1/2/3/%’ ・・・〇
‘1/2/3/4/’ => '1/2/3/' LIKE ‘1/2/3//%’ ・・・✖
挿入
INSERT INTO `groups` (id, path, name)
VALUES (5, CONCAT('1/4/', ‘5/’), 'グループ５');
削除
DELETE `groups` WHERE path LIKE '1/4/%';
経路列挙の特徴
-
追加：パスが分かっているのでパス＋自身のIDでパスが決まる。◎
-
変更：パスの途中を書き換える必要があり更新対象が増える。
子要素にもパス情報が入っているため、すべて書き換える必要がある。✖ -
削除：削除自体はパスの中の自身の情報を取り除くことでパス上から削除可能。
更新同様子要素に対して同様の更新対象が増える。✖ -
検索：階層全体は個々のレコードにパスを持っているため把握しやすい。○
パターンマッチを行うことで検索は比較的容易。○ -
パスというデータの持ち方がアンチパターン（Jaywalk）
パスの途中の値に限定した検索の場合、インデックスが効かない。✖
1カラムに複数要素を持つため、外部キーが貼れない、入力ミスを防げない。✖ -
パスは伸びるよどこまでも。TEXT型などで制限は取り除けるが・・・
対策
- パスを持つという方針上、インデックス、更新、削除のデメリットを回避する方法がない。
入れ子集合のデータの持ち方
ある要素を円とみなして、階層関係を円の抱合関係として捉え直す。
それぞれの要素の左端と右端の座標を持つデータとして表現
- 最上位階層から左回りに線をまたがないように辿るイメージ
データ
| 名前 | 左 | 右 |
|---|---|---|
| リニューアル案件 | 1 | 18 |
| ユビキタス言語 | 2 | 3 |
| 設計 | 4 | 17 |
| アーキテクチャ構成 | 5 | 6 |
| ドメインモデル | 7 | 14 |
| 機能一覧 | 15 | 16 |
| クライアント | 8 | 9 |
| アカウント | 10 | 11 |
| リソース | 12 | 13 |
クエリ
検索
-- 子を取得する
SELECT Boss.id AS boss_id, Boss.name AS boss, Worker.name AS worker
FROM `groups` Boss
LEFT OUTER JOIN `groups` Worker
ON Boss.lft = (
SELECT MAX(lft)
FROM `groups`
WHERE Worker.lft > lft
AND Worker.lft < rgt
);
-- 子を取得する
SELECT parent.*
FROM Comments AS c
INNER JOIN Comments AS parent
ON parent.left < c.left AND c.left < parent.right
LEFT OUTER JOIN Comments AS in_between
ON in_between.left < c.left AND c.left < in_beetween.right
AND parent.left < in_between.left AND in_between.left < parent.right
WHERE c.comment_id = 3
AND in_between.comment_id IS NULL;
追加
-- 子を追加する
-- 第一段階：追加するノードの席を空ける
UPDATE OrgChart
SET lft = CASE WHEN lft > :parent_rgt
THEN lft + 2
ELSE lft END,
rgt = CASE WHEN rgt >= :parent_rgt
THEN rgt + 2
ELSE rgt END
WHERE rgt >= :parent_rgt;
-- 第二段階：ノードを追加する
INSERT INTO OrgChart VALUES ('国見', :parent_rgt, (:parent_rgt + 1));
-- 親を追加する
-- 第一段階：既存ノードの添え字をずらす
UPDATE OrgChart
SET lft = CASE WHEN lft BETWEEN :child_lft AND :child_rgt THEN lft + 1
WHEN lft > :child_rgt THEN lft + 2
ELSE lft END,
rgt = CASE WHEN rgt BETWEEN :child_lft AND :child_rgt THEN rgt + 1
WHEN rgt > :child_rgt THEN rgt + 2
ELSE rgt END
WHERE lft >= :child_lft OR rgt >= :child_rgt;
--第二段階：親ノードを追加する
INSERT INTO OrgChart VALUES ('国見', :child_lft, (:child_rgt + 2));
特徴
-
検索：１クエリで多様な階層情報を取得することが可能。〇
https://qiita.com/reflet/items/a454b40b57de81598732
最下層の一覧、最上部の一覧、ノードの深さを計算、ノードの最大深さを計算する、
階層をインデントで表現する、親から見た場合の子供、子から見た場合の親、親の持つ子供の数、
部分木を求める、パスを列挙する（列持ちバージョン）、
ノード間のパスを検索する (単調下降の場合はOK)、ノード同士の関係性を表示する、
左端座標と右端座標の和集合、歯抜けチェック -
直下の階層を取得するのは苦手。✖
隣接リストより遅くなる。 -
追加、変更、削除：あらゆる要件に1クエリで対応出来る柔軟性を持つ。○
親の追加、要素の入れ替え、添え字の欠番を埋める、
削除時は子要素が自動的に親要素のグループ所属になる。
https://mickindex.sakura.ne.jp/database/db_tree_ns.html -
要素を変える行為は階層全体の座標の変更を引き起こす。✖
変更箇所が直属の階層以外にも及ぶ。 -
SQL操作が全般的に複雑になりがち。✖
-
仕様変更時にメンテ出来るか、引継ぎにあたっての技術継承面での不安
閉包テーブル（Closure Table）のデータの持ち方
ある要素のデータについて、それに連なる子データのIDを持ったテーブルを別で用意する。
データ
| 親 | 子孫 |
|---|---|
| 1 | 1 |
| 1 | 11 |
| 1 | 12 |
| 1 | 121 |
| 1 | 122 |
| 1 | 123 |
| 1 | 1221 |
| 1 | 1222 |
| 1 | 1223 |
| 11 | 11 |
| 12 | 12 |
| 12 | 121 |
| 12 | 122 |
| 12 | 123 |
| 12 | 1221 |
| 12 | 1222 |
| 12 | 1223 |
| 121 | 121 |
| 122 | 122 |
| 122 | 1221 |
| 122 | 1222 |
| 122 | 1223 |
| 123 | 123 |
| 1221 | 1221 |
| 1222 | 1222 |
| 1223 | 1223 |
クエリ
検索
-- 子孫を取得する
SELECT * FROM `groups`
INNER JOIN tree_paths
ON tree_paths.child = `groups`.id
WHERE tree_paths.parent = 1;
-- 親を取得する（子の取得から親と子の指定を逆にする）
SELECT * FROM `groups`
INNER JOIN tree_paths
ON tree_paths.parent = `groups`.id
WHERE tree_paths.child = 1;
挿入
1 => 4 => 5 の 5を追加
-- 元データの追加
INSERT INTO `groups` (id, name)
VALUES (5, 'グループ５');
-- 閉包テーブルの追加
INSERT INTO tree_paths (parent, child)
VALUES (5, 5), (4, 5), (1, 5), ;
削除
1 => 4 => 5 の 5を削除
-- 元データの削除
DELETE FROM `groups` WHERE id = 5;
-- 閉包テーブルの削除
DELETE FROM tree_paths WHERE parent = 5;
DELETE FROM tree_paths WHERE child = 5;
特徴
- 追加：閉包テーブルに対して追加したＩＤを追加する。◎
- 変更：閉包テーブルの対象要素に対してDelete Insert。対象データは多い。▲
一方で元のテーブルには変更がない。○ - 削除：閉包テーブルからのデータ削除。更新同様対象が多い。▲
- 検索：階層全体は閉包テーブルで取得可能。○
すべての要素に対して子孫の全データを持ち、閉包テーブルのデータ量が増大✖
更新、削除における閉包テーブルの更新対象が多い✖ - 構造上はシンプルなので保守面は安定しそう。◎
対策
- 方針上、データ量の増大は避けられない。
一旦整理
- 隣接リストはシンプルですが、階層データの取得に難あり。
- 経路列挙は隣接リストにおける階層データの取得を解決できますが、更新削除操作の影響が広がり、データ整合性が損なわれます。
- 入れ子集合も階層データ取得の優位性はありますが、データの変更における左右の座標更新が煩雑
- 閉包テーブルは構造が他より単純であり、更新も手軽。データ量の増加がネック
- 閉包テーブルはデータ量以外はバランスが取れているので良さそうですが、再帰クエリが使える場合、隣接リストの欠点を補えます。
| 手法 | 親子へのクエリ | ツリーへのクエリ | 挿入 | 削除 | 整合性維持 | ひとこと |
|---|---|---|---|---|---|---|
| 隣接リスト | ○ | ✖ | ○ | ○ | ✖ | 仕様を満たすのであれば最もシンプルで簡単 |
| 隣接リスト＋再帰クエリ | ○ | ○ | ○ | ○ | ○ | RDBMSに再帰クエリが対応していれば最も簡単 |
| 経路列挙 | ○ | ○ | ○ | ○ | ✖不可 | Jaywalk的なデメリットが問題なければ |
| 入れ子集合 | ✖ | ○ | ✖ | ✖ | ✖不可 | 参照専門なら可 |
| 閉包テーブル | ○ | ○ | ○ | ○ | ○ | 容量とるのとトレードオフ |
続けて再帰クエリについて掘り下げてみます。
４．再帰的なクエリについて
再帰クエリ
再帰とは・・・自分自身を参照し、前に行った処理の結果を利用して同じ処理を繰り返す。
再帰クエリ
あるクエリの結果を用いて、そのクエリを再度実行して結果を抽出するクエリ。
具体的な構文としてはWITH RECURSIVEを用います。
代表的なRDBMSでは対応されており利用可能です。
※再帰クエリ可能：MySQL8以降、PostgreSQL、Oracle、MS SQL Server、DB2、SQLite
※再帰クエリ不可：MS Access、MS FoxPro、Sybase ASEなど。
以降に出てくるSQLはMySQLでの実装例となっています。
クエリの構造
1. WITH RECURSIVE r AS (
2. SELECT * FROM `groups` WHERE id = 1
3. UNION ALL
4. SELECT `groups`.* FROM `groups`, r
5. WHERE `groups`.parent_id = r.id
6. )
7. SELECT * FROM r;
1行目：再帰クエリの開始。rは共通テーブルとしての名前。任意に決めて良い。
2行目：非再帰的部分。最初に実行されるクエリ
4行目：再帰的部分。この実行結果が r に設定され、改めてここのクエリに使われ、結果が無くなるまで実行されます。
7行目：WITH句で抽出された結果が r として使えるので、続くSELECT句ではテーブルのように扱えます。UPDATE, DELETEも可能
クエリが実行される流れ
再帰クエリを実行した結果どのようにデータが取得されていくかを示していきます。
使用するのは隣接リストで示したデータ
| ID | 親ID | 名前 |
|---|---|---|
| 1 | なし | リニューアル案件 |
| 11 | 1 | ユビキタス言語 |
| 12 | 1 | 設計 |
| 121 | 12 | アーキテクチャ構成 |
| 122 | 12 | ドメインモデル |
| 123 | 12 | 機能一覧 |
| 1221 | 122 | クライアント |
| 1222 | 122 | アカウント |
| 1223 | 122 | リソース |
-
id=1で検索した結果がｒとして一時保存されます。
SELECT * FROM `groups` WHERE id = 1- 一時保存されているｒのデータ
ID 親ID 名前 1 なし リニューアル案件 -
rのid（1）と
groupsのparent_idが一致したデータを取得し、ｒとして一時保存されます。SELECT `groups`.* FROM `groups`, r WHERE `groups`.parent_id = r.id- 一時保存されているｒのデータ
ID 親ID 名前 11 1 ユビキタス言語 12 1 設計 -
rのid（11、12）と
groupsのparent_idが一致したデータを取得しｒとして一時保存されます。SELECT `groups`.* FROM `groups`, r WHERE `groups`.parent_id = r.id- 一時保存されているｒのデータ
ID 親ID 名前 121 12 アーキテクチャ構成 122 12 ドメインモデル 123 12 機能一覧 -
rのid（121、122、123）と
groupsのparent_idが一致したデータを取得しｒとして一時保存されます。SELECT `groups`.* FROM `groups`, r WHERE `groups`.parent_id = r.id- 一時保存されているｒのデータ
ID 親ID 名前 1221 122 クライアント 1222 122 アカウント 1223 122 リソース -
rのid（1221、1222、1223）と
groupsのparent_idが一致した結果がなくなり、
再帰が終了してｒが確定します。再帰が終了した段階で、1～5までの中で取得した結果すべてがｒという共通テーブルとして扱えるようになります。
-
SELECT句によってｒの一覧を取得します。
SELECT * FROM r;ID 親ID 名前 1 なし リニューアル案件 11 1 ユビキタス言語 12 1 設計 121 12 アーキテクチャ構成 122 12 ドメインモデル 123 12 機能一覧 1221 122 クライアント 1222 122 アカウント 1223 122 リソース
再帰クエリの使用例
1 ～ 5 までの順序を出力
WITH RECURSIVE cte (n) AS
(
SELECT 1
UNION ALL
SELECT n + 1 FROM cte WHERE n < 5
)
SELECT * FROM cte;
+------+
| n |
+------+
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
+------+
文字列を継ぎ足し
WITH RECURSIVE cte AS
(
SELECT 1 AS n, CAST('abc' AS CHAR(20)) AS str
UNION ALL
SELECT n + 1, CONCAT(str, str) FROM cte WHERE n < 3
)
SELECT * FROM cte;
+------+--------------+
| n | str |
+------+--------------+
| 1 | abc |
| 2 | abcabc |
| 3 | abcabcabcabc |
+------+--------------+
指定グループの下位グループを取得
WITH RECURSIVE layer(id, client_id, group_type_id, name, depth, path) AS (
SELECT g.id, g.client_id, g.group_type_id, g.name, 1, CAST(g.name AS CHAR(1000))
FROM `groups` g
WHERE g.client_id = ? AND g.id = ?
UNION ALL
SELECT g.id, g.client_id, g.group_type_id, g.name, layer.depth + 1, CONCAT(layer.path, ' > ', g.name)
FROM `groups` g, layer
WHERE g.client_id = ? AND g.parent_id = layer.id
AND layer.depth < ?
)
SELECT l.* FROM layer l
所属グループを指定し、そのグループおよび下位グループに所属しているリソースを取得
WITH RECURSIVE search_tree(id, name, depth) AS (
SELECT g.id, g.name, 1 FROM `groups` g WHERE g.id = 1
UNION ALL
SELECT g.id, g.name, search_tree.depth + 1
FROM `groups` g, search_tree
WHERE g.parent_id = search_tree.id
)
SELECT s.*, r.* FROM search_tree s
INNER JOIN edges e ON e.to_node = s.id
AND e.relation = 'join'
INNER JOIN resources r ON e.from_node = r.id
ORDER BY s.id
以下のようなデータ量で検索
リソース：70万件
グループ：1000件 最上位が10グループで各グループが100階層
それぞれのグループに平均的にリソースが紐づいている状態。１グループあたり700件程度
1秒程度で返ってきます。
再帰クエリ内でJOIN
WITH RECURSIVE search_tree(id, name, tid, tname, depth) AS (
SELECT g.id, g.name, gt.id AS tid, gt.name AS tname, 1
FROM `groups` g INNER JOIN group_types gt ON g.group_type_id = gt.id
WHERE g.id = 'base'
UNION ALL
SELECT g.id, g.name, gt.id AS tid, gt.name AS tname, search_tree.depth + 1
FROM `groups` g INNER JOIN group_types gt ON g.group_type_id = gt.id
, search_tree
WHERE g.parent_id = search_tree.id
)
SELECT s.*, r.* FROM search_tree s
INNER JOIN edges e ON e.end_node = s.id AND e.relation = 'joined'
INNER JOIN resources r ON e.start_node = r.id
ORDER BY s.id
再帰クエリの注意点
- パンくずリストなど、再帰クエリ内でサイズが可変する場合、カラム幅に注意
非再帰的クエリによってカラム幅が決まるため、CASTして幅を広げます。
文字列の場合CHARで定義。VARCHAR, TEXTに変えるのは出来なそう。 - 階層の深さはデフォルトで1,000。超えるクエリはエラー発生
システム変数で変更可能（cte_max_recursion_depth） - LIMIT指定はあくまで件数なので、N階層まで取得したい等の場合は再帰クエリ内に深さを示す値を用意する必要があります。
参考情報
Discussion