Zenn
シェルフィープロダクトチームPublicationへの投稿
📚

入れ子集合モデルについて考えてみた（「達人に学ぶDB設計　徹底指南書(初版)」を読んで

kohino
2024/09/09に公開
PostgreSQL
tech

シェルフィー株式会社のエンジニア、hinoです！

今までDBについてしっかり学ぶ機会がありませんでしたが、業務の中でDBについてテーブルの構造やらSQLのクエリやらを考える比重が増えてきたので、定番と言われているものをいくつか読むところから初めてみています。

先日「達人に学ぶDB設計 徹底指南書（初版）」（読み終わってすぐに第2版が出ると聞きました👏😭）を読み終わったのですが、その中で木構造について触れている部分がありました。

業務内でも木構造をDBで扱っている部分があるので、いい機会だと思い自分なりにもう少し深ぼってみることにしました！

入れ子集合モデルと経路列挙モデル

書籍で紹介されていたモデルとしては3つあり、

  • 隣接リストモデル
  • 入れ子集合モデル
  • 経路列挙モデル

このうち業務内でも 経路列挙モデル を採用している部分が存在しています。

業務で関わっているシステムの内、建設現場内での会社同士の関係（元請、1次請、2次請…）を表す箇所があるのですが、その中で元請から自社までのルートを経路列挙モデルとして保持しているようなイメージです。

例えば下記のような状態

元請A
　┣　1次請B
　┃　　┗　2次請D
　┃　　　　　┗　3次請E
　┗　1次請C

経路
A ... /A/
B ... /A/B/
C ... /A/C/
D ... /A/B/D/
E ... /A/B/D/E/

書籍を読んでいて、経路列挙モデルと入れ子集合モデルのどちらも、木構造を表すための比較的新しい手法として紹介されていたので、入れ子集合モデルではどのようになるのか気になりました。

ということで試してみたいと思います！

前提

テーブル（DB: PostgreSQL）

  • company（会社を表すテーブル）

  • nested（会社同士の関係を入れ子モデルで表すテーブル）

  • path（会社同士の関係を経路列挙モデルで表すテーブル）

  • テーブル定義

    Table "public.company"
 Column |          Type          | Collation | Nullable |               Default
--------+------------------------+-----------+----------+--------------------------------------
 id     | integer                |           | not null | nextval('company_id_seq'::regclass)
 name   | character varying(255) |           |          |
Indexes:
    "company_pkey" PRIMARY KEY, btree (id)
Referenced by:
    TABLE "nested" CONSTRAINT "nested_id_fkey" FOREIGN KEY (id) REFERENCES company(id)

Table "public.nested"
   Column   |  Type   | Collation | Nullable | Default
------------+---------+-----------+----------+---------
 id         | integer |           | not null |
 left_edge  | integer |           |          |
 right_edge | integer |           |          |
Indexes:
    "nested_pkey" PRIMARY KEY, btree (id)
Foreign-key constraints:
    "nested_id_fkey" FOREIGN KEY (id) REFERENCES company(id)

Table "public.path"
 Column |  Type   | Collation | Nullable | Default
--------+---------+-----------+----------+---------
 id     | integer |           | not null |
 path   | text    |           |          |
Indexes:
    "path_pkey" PRIMARY KEY, btree (id)
Foreign-key constraints:
    "path_id_fkey" FOREIGN KEY (id) REFERENCES company(id)

DBテーブル上で木構造を作る

テストデータとして、会社10,000社（もっと多くても良かったかもしれません）が参加する現場の中の上位会社・下請会社の関係を木構造として表すことにしてみます。

ひとまずid = 1の会社をトップに一社ずつ下請会社がついていき、10000まで直列の構造を作成します。

  • 作成SQL

    -- 会社
INSERT INTO company(
    name
)
SELECT
    '会社' || lpad(gs :: text, 5, '0')
FROM generate_series(1, 10000) gs;

-- 入れ子
INSERT INTO nested(
		id,
		left_edge,
		right_edge
)
SELECT
		id,
		id,
		20001 - id
FROM company;

-- 経路列挙
CREATE OR REPLACE FUNCTION create_path() RETURNS VOID AS $$
DECLARE
    _rec record;
    i int;
    s text;
BEGIN
    FOR _rec IN
        SELECT id
        FROM company
        ORDER BY id
    LOOP
        s := '/';
        FOR i IN 1 .. _rec.id
        LOOP
            s = s || i || '/' ;
        END LOOP;
        INSERT INTO path (id, path) VALUES (_rec.id, s);
    END LOOP;
    RETURN;
END;
$$ LANGUAGE plpgsql;

SELECT * FROM create_path();

-- company 
   id |    name
------+-------------
    1 | 会社00001
    2 | 会社00002
			  ...
10000 | 会社10000

-- nested
   id | left_edge | right_edge
------+-----------+------------
    1 |         1 |      20000
    2 |         2 |      19999
					  ...
10000 |     10000 |      10001

-- path
 id |  path
----+---------
  1 | /1/
  2 | /1/2/
  3 | /1/2/3/
  ...

入れ子集合モデルとしては、木構造のルートである 会社00001 が他の会社全てを包含（一番上の上位会社）しており、リーフである 会社10000 がどの会社も包含していない（下請会社を持たない一番下の下請会社）という構造になっています。

一方経路列挙モデルは一番上の上位会社から自分までの間の上位会社を全て表しています。

テーブルデータを眺める時の見た目としては経路列挙モデルの方が直感的に上下関係を理解しやすい印象ですね。

データを検索する

検索と言っても様々ありますが、弊社の業務内でよく使われそうな操作として

  • ルート（元請）を検索
  • リーフ（下請会社を持たない会社）を検索
  • 直近の上位会社を検索
  • 直近の下請会社を検索

あたりが考えられます。ルートとリーフの検索は書籍にもあるので省くとして、それ以外の部分を入れ子集合モデルではどうなるかやってみると…

  • 直近の上位会社を検索

    SELECT * 
FROM nested 
WHERE left_edge = (
		SELECT MAX(upper.left_edge) 
		FROM nested lower 
		INNER JOIN nested upper 
		ON lower.left_edge > upper.left_edge 
			AND lower.left_edge < upper.right_edge 
		WHERE lower.id = 10000 -- この会社の直近上位会社を検索
		GROUP BY lower.id
);
	
  id  | left_edge | right_edge
------+-----------+------------
 9999 |      9999 |      10002
(1 row)
Time: 3.292 ms

  • 直近の下請会社を検索

    SELECT lower.id, lower.left_edge, lower.right_edge
FROM nested lower
INNER JOIN nested upper
ON upper.left_edge = (
		SELECT MAX(left_edge) 
		FROM nested 
		WHERE lower.left_edge > left_edge 
			AND lower.right_edge < right_edge
)
AND upper.id = 2 -- この会社の直近下請会社を検索
;

id  | left_edge | right_edge
----+-----------+------------
  3 |        13 |      20010
9997|         3 |         12
(2 rows)
Time: 5220.552 ms (00:05.221)

下請会社と上位会社の位置関係（上位会社.left_edge < 下請会社.left_edge < 下請会社.right_edge < 上位会社.right_edge）を理解していればわりと簡単に検索できますね！

ただ、直近の下請会社を検索する場合は他のクエリと比較してかなりパフォーマンスが落ちていたのでもう少し工夫の余地があるかもしれません。。。。

経路列挙モデルだと文字列の前方一致や区切り文字（今回は/）を利用する等の文字列操作で検索するのに対して、入れ子集合モデルだと数値の大小関係の比較に落とし込める、といった感じでしょうか。

データを更新する

経路列挙モデルと入れ子集合モデルのどちらも難ありと紹介されていた更新について見ていきます！

更新については

  • リーフ（下請会社を持たない会社）に下請会社を追加
  • 上位会社を変更、下請会社がいれば下請会社も一緒に移動（部分木の移動）

の2つが基本操作として考えられます。

入れ子集合モデルではどちらも

  1. 新しい下請会社を追加できるスペース（left_edgeとright_edgeの幅）を確保する
  2. 追加もしくは更新

の流れで実現できそうですね。今回もリーフに追加は書籍にあるので省略します。

  • 上位会社を変更、下請会社がいれば下請会社も一緒に移動（部分木の移動）

    -- １つの会社とその下請会社４社を移動
  id   | left_edge | right_edge
-------+-----------+------------
  9997 |      9997 |      10006
  9998 |      9998 |      10005
  9999 |      9999 |      10004
 10000 |     10000 |      10003
 10001 |     10001 |      10002
 
 -- 移動先(id=2 の下請会社、id=3 と同階層)
  id | left_edge | right_edge
----+-----------+------------
  2 |         2 |      19999
  3 |         3 |      19998
 
-- 移動先のスペースを開ける 
UPDATE nested 
SET left_edge = CASE WHEN left_edge > 2 
								THEN left_edge + 10 ELSE left_edge END,
	  right_edge = CASE WHEN right_edge > 2 
								 THEN right_edge + 10 ELSE right_edge END 
WHERE left_edge >= 2;

UPDATE 9999
Time: 45.141 ms
 id | left_edge | right_edge
----+-----------+------------
  2 |         2 |      20011
  3 |        13 |      20010
 
 -- 移動
UPDATE nested 
SET left_edge = left_edge - 10004,
		right_edge = right_edge - 10004 
WHERE id BETWEEN 9997 AND 10001;

UPDATE 5
Time: 3.860 ms
  id   | left_edge | right_edge
-------+-----------+------------
     2 |         2 |      20011
  9997 |         3 |         12
  9998 |         4 |         11
  9999 |         5 |         10
 10000 |         6 |          9
 10001 |         7 |          8
     3 |        13 |      20010

今回のデータ量だと一つ一つのクエリの実行時間自体はそれほど大きくないものの、やはり検索のようにクエリ１発で解決！というわけにはいきませんね…。

（上位会社の変更について、5人の会社が移動する前のスペースが空いているままですが今回はそのままにします）

経路列挙モデルでは移動対象の分だけ（上位会社と下請会社の間に割って入るなら移動先の下請会社の分も）ループしてpathを書き換える必要があることを考えると、複雑な木構造になるほど入れ子集合モデルの方が更新しやすくなりそうです。

ただ、今は元請（ルート）がid=1 の一つだけですが、現場によっては複数の元請が存在する場合もありえますし、元請が一つでも複数現場の編成（上位会社・下請会社の関係）を一つのテーブルで管理することも普通のユースケースかと思います。そうなってくると元請同士の数値上の間隔によっては一つの元請下の編成を更新するために別の元請下の編成更新しなければならなくなりそうです。

その場合は

  • 元請同士の間隔をあらかじめ離しておく（定期的に間を離す）
  • 編成ID 等を作成してその編成ID、left_edge、right_edgeの3つで木構造を決定する

等の対策が考えられそうですね。

まとめ

ローカルかつ生SQLを実行しているので業務での環境とは乖離がありましたが、実際にデータを作成してクエリを考えて実行してみることで色々気づきがありました！

入れ子集合モデルの場合は階層構造を数値の大小関係に置き換えるという部分がクリアになっていれば扱いやすいモデルだなと感じました。

一方で調査等の際にテーブルデータを見た時に1レコードだけでは分からない部分が多くなりそうなので、そのあたりを重視するのであれば経路列挙モデルや隣接リストモデルの方が良さそうだなと思いました。

弊社のテーブル構造もこのあたりを重視しているのかもしれないなと感じたので、社内でも話題にしてみようと思います。

いずれのモデルを採用するにしろ、各モデルの特性を理解した上で、業務要件に合わせた工夫をしていくということは大事だなと改めて実感しました！

シェルフィープロダクトチーム
シェルフィープロダクトチームPublication

「現場に馴染む」安全書類管理サービス「Greenfile.work」をつくる人として支えているプロダクトチームが日々向き合っていることや雰囲気をお届けします。

Discussion