階層構造を表現するデータ構造とリファクタリング〜1年で10倍成長したプロダクトの変化と課題〜

階層構造を表現するデータ構造とリファクタリング〜1年で10倍成長したプロダクトの変化と課題〜 Kaigi on Rails 2025 yuhi

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日目

階層構造を持つサービス例 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 ノード

RDBで階層化機能をどのように表現するんだろう？

なんとなくで表現すると大変なことになるかも ...

本日話すこと • 階層構造を表現するデータ構造とそのリファクタリング • 急成⻑サービスにおける変化と課題本日話さないこと • 下記のデータ構造について ◦ 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

Adjacency List（隣接リスト）

Adjacency List（隣接リスト）とは • 各レコードが⾃⾝の親レコードへの参照を持っている • parent_idが親レコードへの参照

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テーブル

SQLで階層構造を操作してみよう

親ノードを取得（ 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のノードを取得する

問題1: 子ノードを取得する SQLを答えよ

子ノードを取得（ 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

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のメリット • シンプル • 書き込み操作が容易 ◦ ⼦ノードを作成 ◦ ノードを移動

子ノードを作成（ 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

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にする

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

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のデメリット • 親⼦関係を超えた読み込み操作が困難 ◦ 祖先ノード取得 ◦ ⼦孫ノード取得

祖先ノードを取得（ 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

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

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

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

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

Folderモデル（Adjacency List）

親への関連⼦への関連 Folderモデル（Adjacency List）

全ての祖先を配列で取得全ての⼦孫を配列で取得 Folderモデル（Adjacency List）

祖先ノードを取得（ Adjacency List）

祖先ノードを取得（ Adjacency List）配列の結合

祖先ノードを取得（ Adjacency List）親の配列

祖先ノードを取得（ Adjacency List）親の祖先

祖先ノードを取得（ Adjacency List）再帰処理

祖先ノードを取得（ Adjacency List）親が存在しなくなるまで繰り返す

子孫ノードを取得（ Adjacency List）

子孫ノードを取得（ Adjacency List）配列の結合

子孫ノードを取得（ Adjacency List）⼦の配列

子孫ノードを取得（ Adjacency List）それぞれの⼦の⼦孫

子孫ノードを取得（ Adjacency List）再帰処理

Adjacency List まとめ • メリット ◦ 実装が容易 ▪ 直感的なFolderモデルで実装できる ◦
書き込みが容易 ▪ SQL問い合わせ1回 • デメリット ◦ 親⼦関係を超えた読み込み操作が困難 ▪ SQL問い合わせを複数回⾏う必要がある

フォルダ階層化機能の開発（ 1年前）

フォルダ階層化機能とは • サクミルではフォルダに階層構造を持たせてファイルを管理することができる • フォルダの閲覧‧作成‧移動‧削除ができる

開発当時のプロダクト状況 • 導⼊社数が100社とユーザー数が少ない ◦ パフォーマンスが問題になりにくい • プロダクト全体の機能が不⼗分 ◦ 新機能を素早くリリースして機能を充実させたい

開発当時のプロダクト状況 • 導⼊社数が100社とユーザー数が少ない ◦ パフォーマンスが問題になりにくい • プロダクト全体の機能が不⼗分 ◦ 新機能を素早くリリースして機能を充実させたい実装が容易なAdjacency
Listでフォルダ階層化機能を実装

プロダクト状況の変化と課題（ 1年後）

プロダクト状況の変化 • 1年で導⼊社数が1,000社へと10倍成⻑した • プロダクト全体の機能も充実してきた • プロダクトを使い込んでいただけるお客様も増えた

プロダクト状況の変化 • 1年で導⼊社数が1,000社へと10倍成⻑した • プロダクト全体の機能も充実してきた • プロダクトを使い込んでいただけるお客様も増えた顧客体験がより重要視されるフェーズに

フォルダ階層化機能の課題 • 巨⼤な階層構造が作成されるケースが出てきたことにより⼤量のN+1問題が発⽣

大量の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: 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（閉包テーブル）

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=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のメリット • 親⼦関係を超えた読み込みが容易 ◦ 祖先ノードを取得 ◦ ⼦孫ノードを取得

祖先ノードを取得（ 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

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を結合

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である経路に絞る

問題2: 子孫ノードを取得する SQLを答えよ

子孫(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

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

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である経路に絞る

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である経路に絞る

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

FolderPathモデル

Folderモデル（Closure Table）

Folderモデル（Closure Table）祖先経路への関連⼦孫経路への関連

Folderモデル（Closure Table）全ての祖先を取得全ての⼦孫を取得

Closure Tableのデメリット • ストレージコスト • 書き込みの操作が困難（経路を管理する必要がある） ◦ ⼦ノードを作成 ◦ ノードを移動
◦ ノードとその全ての⼦孫ノードを削除

子ノードを作成（ Closure Table） id: 3 parent_id: 2 id: 3 parent_id:

子ノードを作成（ 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 ノードを挿⼊して

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）親が終点の経路を取得し

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

Folder作成時にFolderPathを作成親ノードが終点の経路を取得 id: 3 parent_id: 2 id: 8 parent_id: 7

Folder作成時にFolderPathを作成⾃⾝が終点の経路作成 id: 3 parent_id: 2 id: 8 parent_id: 7

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: 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 親を更新して

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 ⼦孫を取得して

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 ⾃⾝と⼦孫が終点である経路を削除

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 ⾃⾝が終点の経路を作成

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

3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 親の変更時にコールバックを実⾏

3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫のノードを取得

3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 id: 3 parent_id: 2 ⾃⾝と⼦孫の経路を削除

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回 •
デメリット ◦ ストレージコスト ◦ 書き込み操作が困難 ▪ 経路を正しい状態に維持する必要がある ◦ 実装が複雑

Adjacency List + Recursive CTE（再帰CTE）

• 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）とは

Recursive CTEの基本構造

Recursive CTEの基本構造 WITH句でCTEを定義利⽤

Recursive CTEの基本構造⾮再帰項: 初回だけ実⾏される

Recursive CTEの基本構造再帰項: 繰り返し実⾏される

Recursive CTEの基本構造 1つ前の実⾏結果を参照

Recursive CTEの基本構造新たなレコードが⽣じなくなるまで繰り返す

Recursive CTEの基本構造レコードの重複の扱い UNION ALL: 重複削除なし UNION: 重複削除

Recursive CTEの手順 n nums

Recursive CTEの手順 n 1 nums ⾮再帰項を実⾏

Recursive CTEの手順 n 1 2 nums

Recursive CTEの手順 n 1 2 3 nums 新たなレコードが⽣じなくなるまで繰り返す

Recursive CTEの手順 n 1 2 3 4 nums 新たなレコードが⽣じなくなるまで繰り返す

Recursive CTEの手順 n 1 2 3 4 5 nums 新たなレコードが⽣じなくなるまで繰り返す

Recursive CTEの手順 n 1 2 3 4 5 nums numsを取得

祖先ノードを取得（ 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

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を定義

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 ⾮再帰項: 初回だけ実⾏される

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 再帰項: 繰り返し実⾏される

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: 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を利⽤

Folderモデル祖先ノードを取得（ Adjacency List + Recursive 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

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を定義

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 ⾮再帰項: 初回だけ実⾏される

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 再帰項: 繰り返し実⾏される

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: 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を利⽤

Folderモデル子孫ノードを取得（ Adjacency List + Recursive CTE）

Adjacency List + Recursive CTE 概要 • メリット ◦ Adjacency
Listからデータ構造を変える必要がない ▪ 問い合わせ⽅法が変わるのみ ◦ 親⼦関係を超えた読み込みをクエリ1回で取得できる ◦ Adjacency Listのままなので書き込みが容易 • デメリット ◦ DB内で再帰処理を繰り返す必要があるため深い階層だと低速になる

リファクタリング手法の決定

リファクタリング手法の決定 Closure Table 読み込み非常に高速書き込み低速データ構造閉包テーブルを追加実装
複雑 Recursive CTE 高速高速（追加操作なし）変更なし容易 • Adjacency Listからの移⾏についてClosure TableとRecursive CTEを⽐較

• フォルダ階層化機能を整理 ◦ 読み込みが多いワークロード ▪ ⼀度作成されたフォルダは継続的に閲覧される ◦ 階層制限がないリファクタリング手法の決定

• フォルダ階層化機能を整理 ◦ 読み込みが多いワークロード ▪ ⼀度作成されたフォルダは継続的に閲覧される ◦ 階層制限がないリファクタリング手法の決定読み取りが⾼速なClosure
Tableを選択

パフォーマンス実験

実験:子孫ノードを探索 • 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

実験条件 • DBスキーマ

実験コードサンプルコード • 3つの⼿法それぞれについて別プロセスでベンチマークを実⾏する

実験結果深さ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 への移行手順

非循環のバリデーション • 階層構造には循環がないことが前提なので、⾮循環のバリデーションを⾏う

階層構造を表現するデータ構造とリファクタリング 〜1年で10倍成長したプロダクトの変化と課題〜

階層構造を表現するデータ構造とリファクタリング 〜1年で10倍成長したプロダクトの変化と課題〜

More Decks by yuhi

Other Decks in Programming

Featured

Transcript

階層構造を表現するデータ構造とリファクタリング〜1年で10倍成長したプロダクトの変化と課題〜

階層構造を表現するデータ構造とリファクタリング〜1年で10倍成長したプロダクトの変化と課題〜