Share
Embed
階層構造を表現するデータ構造とリファクタリング 〜1年で10倍成長したプロダクトの変化と課題〜
Kaigi on Rails 2025 資料です。
https://kaigionrails.org/2025/talks/Yuhi-Sato/#day2
yuhi
September 26, 2025
Transcript
194 slides
-
yuhi 株式会社プレックス / 24卒 yuhi_junior Yuhi-Sato 自己紹介 • 建設系SaaS サクミル
開発 • 24th Dev, Wakate.rb主催 • Rails歴 2年 • Kaigi on Rails初参加🙌 -
階層構造を持つサービス例 1 クラウドストレージサービスにおけるフォルダは階層構造 id: 3 parent_id: 2 Kaigi on Rails
id: 3 parent_id: 2 2023 id: 3 parent_id: 2 2024 id: 3 parent_id: 2 2025 id: 3 parent_id: 2 1日目 id: 3 parent_id: 2 2日目 -
階層化機能のよくある要件 • 階層構造の読み込み ◦ 親ノードを取得 ◦ ⼦ノードを取得 ◦ 祖先ノードを取得 ◦
⼦孫ノードを取得 • 階層構造の書き込み ◦ ⼦ノードを作成 ◦ ノードを移動 ◦ ノードとその全ての⼦孫ノードを削除 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ノード -
本日話すこと • 階層構造を表現するデータ構造とそのリファクタリング • 急成⻑サービスにおける変化と課題 本日話さないこと • 下記のデータ構造について ◦ Path
Enumeration(経路列挙) , Nested Sets(⼊れ⼦集合) • 階層構造を表現する特定のgemについて ◦ gemの裏側で使われているデータ構造の話をします はじめに -
はじめに ゴール 1. 階層構造を表現する2つのデータ構造を理解する(SQLクイズを出題!) ◦ Adjacency List(隣接リスト) ◦ Closure Table(閉包テーブル)
2. Recursive CTE(再帰CTE)の概要を理解する 3. 階層化機能において適切な⼿法を選択ができるようになる -
本発表では階層構造の中でも ツリー構造(= 親を⼀つだけ持つ) のみを扱います はじめに id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3
parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 Adjacency Listの例 id parent_id 1 null 2 1 3 2 4 3 5 3 6 1 7 6 foldersテーブル -
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3
parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 Adjacency Listの例 id parent_id 1 null 2 1 3 2 4 3 5 3 6 1 7 6 foldersテーブル -
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3
parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 Adjacency Listの例 id parent_id 1 null 2 1 3 2 4 3 5 3 6 1 7 6 foldersテーブル -
親ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 -
親ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 parent_id=3という情報から id=3のノードを取得する -
親ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 parent_id=3という情報から id=3のノードを取得する -
子ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
子ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ? 空欄に⼊るのは? 1. parent_id = 3 2. id = 3 -
子ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 空欄に⼊るのは? 1. parent_id = 3 2. id = 3 親のidが3のノードを取得する -
子ノードを作成( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 8 parent_id: 7 -
子ノードを作成( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 8 parent_id: 7 親のidを7にする -
子ノードを作成( Adjacency List) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 8 parent_id: 7 親のidを7にする -
ノードを移動( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 -
ノードを移動( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 -
ノードを移動( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 親のidを7に変更する -
ノードを移動( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 親のidを7に変更する -
祖先ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 -
祖先ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 -
祖先ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 -
祖先ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 -
全ての祖先ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 クエリ実⾏回数: 3 -
子孫ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
子孫ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
子孫ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
子孫ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 -
子孫ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 -
子孫ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 -
子孫ノードを取得( Adjacency List) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 -
子孫ノードの取得( Adjacency List) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 クエリ実⾏回数: 7 -
Adjacency List まとめ • メリット ◦ 実装が容易 ▪ 直感的なFolderモデルで実装できる ◦
書き込みが容易 ▪ SQL問い合わせ1回 • デメリット ◦ 親⼦関係を超えた読み込み操作が困難 ▪ SQL問い合わせを複数回⾏う必要がある -
大量のN+1が発生する例 : 子孫ノードを探索( Adjacency List) id: 3 parent_id: 2 id:
3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1000 parent_id: xxx -
大量のN+1が発生する例 : 子孫ノードを探索( Adjacency List) id: 3 parent_id: 2 id:
3 parent_id: 1 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1000 parent_id: xxx -
大量のN+1が発生する例 : 子孫ノードを探索( Adjacency List) id: 3 parent_id: 2 id:
3 parent_id: 1 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1000 parent_id: xxx -
大量のN+1が発生する例 : 子孫ノードを探索( Adjacency List) id: 1 parent_id: null id:
6 parent_id: 1 id: 700 parent_id: xxx id: 2 parent_id: 1 id: 1,000 parent_id: xxx -
子孫ノードを探索( Adjacency List) id: 1 parent_id: null id: 6 parent_id:
1 id: 700 parent_id: xxx id: 2 parent_id: 1 id: 1,000 parent_id: xxx クエリ実⾏回数: 1,000 N+1問題が⾟すぎる😭 -
子孫ノードを探索( Adjacency List) id: 1 parent_id: null id: 6 parent_id:
1 id: 700 parent_id: xxx id: 2 parent_id: 1 id: 1,000 parent_id: xxx リファクタリングでN+1問題を解消しよう -
• 検討した⼿法は2つ ◦ Closure Table(閉包テーブル) ◦ Adjacency List + Recursive
CTE(再帰CTE) リファクタリング -
Closure Table(閉包テーブル)とは • 階層構造における全ての経路を保持しているテーブル • Adjacency Listへの関連を持っている • ancestor_idは祖先のid、descendant_idは⼦孫のid •
祖先‧⼦孫の関係によって経路を表現(= 経路の始点‧終点の関係) • depthは経路⻑ -
Closure Tableの例(始点が id=1の経路のみ) ancestor_id descendant_id depth 1 1 0 1
2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 folder_pathsテーブル id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 -
Closure Tableの例(始点が id=1の経路のみ) ancestor_id descendant_id depth 1 1 0 1
2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 folder_pathsテーブル id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 -
Closure Tableの例(始点が id=1の経路のみ) ancestor_id descendant_id depth 1 1 0 1
2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 folder_pathsテーブル id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 -
Closure Tableの例(始点が id=2の経路のみ) folder_pathsテーブル ancestor_id descendant_id depth 2 2 0
2 3 1 2 4 2 2 5 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 -
Closure Tableの例(始点が id=2の経路のみ) folder_pathsテーブル ancestor_id descendant_id depth 2 2 0
2 3 1 2 4 2 2 5 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 -
Closure Tableの例(始点が id=2の経路のみ) folder_pathsテーブル ancestor_id descendant_id depth 2 2 0
2 3 1 2 4 2 2 5 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 -
祖先ノードを取得( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 -
祖先ノードを取得( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 -
祖先ノードを取得( Closure Table) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 foldersとfolder_pathsを結合 -
祖先ノードを取得( Closure Table) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 終点がid=4である経路に絞る -
子孫(descendant)ノードを取得( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
子孫(descendant)ノードを取得( Closure Table) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ? 空欄に⼊るのは? 1. descendant_id = 1 2. ancestor_id = 1 -
子孫(descendant)ノードを取得( Closure Table) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ? 空欄に⼊るのは? 1. descendant_id = 1 2. ancestor_id = 1 始点がid=1である経路に絞る -
子孫(descendant)ノードを取得( Closure Table) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 空欄に⼊るのは? 1. descendant_id = 1 2. ancestor_id = 1 始点がid=1である経路に絞る -
子孫(descendant)ノードを取得( Closure Table) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 始点がid=1である経路に絞る 空欄に⼊るのは? 1. descendant_id = 1 2. ancestor_id = 1 -
Closure Tableのデメリット • ストレージコスト • 書き込みの操作が困難(経路を管理する必要がある) ◦ ⼦ノードを作成 ◦ ノードを移動
◦ ノードとその全ての⼦孫ノードを削除 -
子ノードを作成( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 8 parent_id: 7 -
子ノードを作成( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 8 parent_id: 7 -
子ノードを作成( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 8 parent_id: 7 ノードを挿⼊して -
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3
parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 8 parent_id: 7 子ノードを作成( Closure Table) 親が終点の経路を取得し -
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3
parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 8 parent_id: 7 子ノードを作成( Closure Table) 親の経路を使って ⾃⾝が終点の経路を挿⼊ -
Folder作成時にFolderPathを作成 id: 3 parent_id: 2 id: 8 parent_id: 7 id:
3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
Folder作成時にFolderPathを作成 ノード作成時にコールバックを実⾏ id: 3 parent_id: 2 id: 8 parent_id: 7
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
Folder作成時にFolderPathを作成 経路をバルクインサートするための配列を定義 id: 3 parent_id: 2 id: 8 parent_id: 7
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 バルクインサート -
Folder作成時にFolderPathを作成 ⾃⾝への経路を配列に追加 id: 3 parent_id: 2 id: 8 parent_id: 7
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
Folder作成時にFolderPathを作成 親ノードが終点の経路を取得 id: 3 parent_id: 2 id: 8 parent_id: 7
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
Folder作成時にFolderPathを作成 ⾃⾝が終点の経路作成 id: 3 parent_id: 2 id: 8 parent_id: 7
id: 3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
Folder作成時にFolderPathを作成 id: 3 parent_id: 2 id: 8 parent_id: 7 id:
3 parent_id: 2 id: 6 parent_id: 1 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 7 parent_id: 6 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 バルクインサート -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 親を更新して -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⼦孫を取得して -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⾃⾝と⼦孫が終点である 経路を削除 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⾃⾝と⼦孫が終点である 経路を削除 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⾃⾝と⼦孫が終点である 経路を削除 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⾃⾝と⼦孫が終点である 経路を削除 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⾃⾝と⼦孫が終点である 経路を削除 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⾃⾝と⼦孫が終点である 経路を削除 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 3 parent_id:
2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⾃⾝と⼦孫が終点である 経路を削除 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⾃⾝が終点の経路を作成 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⼦孫が終点の経路を作成 -
ノードを移動( Closure Table) id: 3 parent_id: 2 id: 6 parent_id:
1 id: 3 parent_id: 2 id: 3 parent_id: 7 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 ⼦孫が終点の経路を作成 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 親の変更時にコールバックを実⾏ -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫のノードを取得 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を削除 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を削除 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を削除 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を削除 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を削除 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を削除 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を削除 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を作成 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を作成 -
Folder移動時にFolderPathを削除・作成 id: 3 parent_id: 2 id: 3 parent_id: 2 id:
3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を作成 -
Closure Table まとめ • メリット ◦ 親⼦関係を超えた読み込みが容易 ▪ JOINを伴うSQL問い合わせ1回 •
デメリット ◦ ストレージコスト ◦ 書き込み操作が困難 ▪ 経路を正しい状態に維持する必要がある ◦ 実装が複雑 -
• SQLにおけるCTE (Common Table Expression) の⼀種 ◦ WITH句のやつ • 再帰的にクエリを実⾏できる
• 主要なRDBMSでサポートされている ◦ MySQL 8.0 ◦ PostgreSQL 8.4 ◦ SQLite 3.8.3 • Rails 7.2.0からQueryMethods#with_recursiveが登場 Recursive CTE(再帰CTE)とは -
祖先ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 -
祖先ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 CTEを定義 -
祖先ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾮再帰項: 初回だけ実⾏される -
祖先ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 再帰項: 繰り返し実⾏される -
祖先ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 再帰項: 繰り返し実⾏される -
祖先ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 3 parent_id: 2 CTEを利⽤ -
子孫ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 -
子孫ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 CTEを定義 -
子孫ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 6 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾮再帰項: 初回だけ実⾏される -
子孫ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 6 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 7 parent_id: 6 再帰項: 繰り返し実⾏される -
子孫ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 6 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 再帰項: 繰り返し実⾏される -
子孫ノードを取得( Adjacency List + Recrusive CTE) id: 3 parent_id: 2
id: 6 parent_id: 1 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 2 parent_id: 1 id: 3 parent_id: 2 id: 4 parent_id: 3 id: 3 parent_id: 2 id: 5 parent_id: 3 id: 3 parent_id: 2 id: 7 parent_id: 6 CTEを利⽤ -
Adjacency List + Recursive CTE 概要 • メリット ◦ Adjacency
Listからデータ構造を変える必要がない ▪ 問い合わせ⽅法が変わるのみ ◦ 親⼦関係を超えた読み込みをクエリ1回で取得できる ◦ Adjacency Listのままなので書き込みが容易 • デメリット ◦ DB内で再帰処理を繰り返す必要があるため深い階層だと低速になる -
リファクタリング手法の決定 Closure Table 読み込み 非常に高速 書き込み 低速 データ構造 閉包テーブルを追加 実装
複雑 Recursive CTE 高速 高速(追加操作なし) 変更なし 容易 • Adjacency Listからの移⾏についてClosure TableとRecursive CTEを⽐較 -
実験:子孫ノードを探索 • ActiveRecord上でトップレベルの ノードから葉ノード探索処理の 実⾏時間を計測 • 3つの⼿法(Adjacency List, Closure Table,
Adjacency List + Recursive CTE)の パフォーマンスを⽐較 • 階層構造は完全2分⽊とする • 深さを変えて実験 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 1 parent_id: null id: 3 parent_id: 2 id: 3 parent_id: 2 id: 512 parent_id: xxx id: 3 parent_id: 2 -
実験条件 • ローカルPCのDocker環境(PostgreSQL + Ruby) • PostgreSQL バージョン: 17.5 •
Ruby バージョン: 3.4.3 • Rails バージョン: 8.0.2.1 -
実験結果 深さ6 (127ノード) 深さ9 (1,023ノード) 深さ13 (16,383ノード) Adjacency List (real
[ms]) 38.050 244.622 3749.056 Closure Table (real [ms]) 4.228 4.020 4.024 Recursive CTE (real [ms]) 10.869 10.918 14.111 • Adjacency Listと⽐較して、Closure Tableでは⼤幅に⾼速化を達成 • Closure Tableは横ばい、Recursive CTEは深くなるほど低速 -
深さ6 (127ノード) 深さ9 (1,023ノード) 深さ13 (16,383ノード) Adjacency List (real [ms])
38.050 244.622 3749.056 Closure Table (real [ms]) 4.228 4.020 4.024 Recursive CTE (real [ms]) 10.869 10.918 14.111 実験結果 • Adjacency Listと⽐較して、Closure Tableでは⼤幅に⾼速化を達成 • Closure Tableは横ばい、Recursive CTEは深くなるほど低速 x 8 x 60 x 931 -
実験結果 • Adjacency Listと⽐較して、Closure Tableでは⼤幅に⾼速化を達成 • Closure Tableは横ばい、Recursive CTEは深くなるほど低速 深さ6
(127ノード) 深さ9 (1,023ノード) 深さ13 (16,383ノード) Adjacency List (real [ms]) 38.050 244.622 3749.056 Closure Table (real [ms]) 4.228 4.020 4.024 Recursive CTE (real [ms]) 10.869 10.918 14.111 -
実験結果 • Adjacency Listと⽐較して、Closure Tableでは大幅に高速化を達成 • Closure Tableは横ばい、Closure Tableは深くなるほど低速 深さ6
(127ノード) 深さ9 (1,023ノード) 深さ13 (16,383ノード) Adjacency List (real [ms]) 38.050 244.622 3749.056 Closure Table (real [ms]) 4.228 4.020 4.024 Recursive CTE (real [ms]) 10.869 10.918 14.111 Closure TableとRecursive CTEについて SQLクエリの実⾏時間を⾒てみよう -
深さ6 (127ノード) 深さ9 (1,023ノード) 深さ13 (16,383ノード) Closure Table (Execution Time
[ms]) 0.037 0.031 0.023 Recursive CTE (Execution Time [ms]) 0.056 0.274 4.185 クエリの実行時間( Closure Table vs Recursive CTE) • EXPLAIN ANALYZE で実⾏時間の測定 • 結果、クエリ実⾏⾃体はClosure Tableの⽅が⾼速 ◦ ActiveRecord上ではクエリ実⾏以外にボトルネックがあり、 パフォーマンス差がでていなかった可能性 -
まとめ ゴール 1. ✅ 階層構造を表現する2つのデータ構造を理解する ◦ Adjacency List(隣接リスト) ◦ Closure
Table(閉包テーブル) 2. ✅ Recursive CTE(再帰CTE)の概要を理解する 3. 階層化機能において適切な⼿法を選択ができるようになる -
まとめ • 階層化機能(親⼦関係を超えた読み込みを伴う場合)のおすすめ⼿法 おすすめ手法 開発初期 Adjacency List 小規模の階層(100ノード) Adjacency List
+ Recursive CTE 中規模の階層(1,000ノード) 読み込みが多い → Closure Table 書き込みが多い → Adjacency List + Recursive CTE 大規模の階層(10,000ノード) 頻繁に書き込みがなければ Closure Table -
まとめ ゴール 1. ✅ 階層構造を表現する2つのデータ構造を理解する a. Adjacency List(隣接リスト) b. Closure
Table(閉包テーブル) 2. ✅ Recursive CTE(再帰CTE)の概要を理解する 3. ✅ 階層化機能において適切な⼿法を選択ができるようになる -
参考文献 • Models for hierarchical data with SQL and PHP
◦ https://www.slideshare.net/slideshow/models-for-hierarchical-data/4179181 • Bill Karwin「SQLアンチパターン 第⼆版 」 ◦ https://www.oreilly.co.jp/books/9784814400744 • Add support for recursive CTEs in ActiveRecord ◦ https://github.com/rails/rails/pull/51601 • ancestory ◦ https://github.com/stefankroes/ancestry • closure_tree ◦ https://github.com/ClosureTree/closure_tree • PostgreSQL Wiki CTEReadme ◦ https://wiki.postgresql.org/wiki/CTEReadme • MySQL 8.0 レファレンスマニュアル 13.2.15 WITH (共通テーブル式) ◦ https://dev.mysql.com/doc/refman/8.0/ja/with.html -
1. folder_pathsテーブルを作成 2. FolderPathモデルを作成 3. Folderモデルに build_pathメソッドを実装 4. 右のスクリプトを実⾏する ◦
トップフォルダから順に build_pathメソッドを叩いて 経路を作成している Adjacency List から Closure Table への移行手順