■ 1. 階層構造の基本と背景
- 階層構造の例: クラウドストレージサービスにおけるフォルダやレシピサイトにおける材料タグは階層構造を持ち、親ノード・子ノード・祖先ノード・子孫ノードの取得、子ノードの作成、ノードの移動、ノードとその全ての子孫ノードの削除などの機能が必要である
- プロダクトの成長: 開発当時は導入社数が100社とユーザー数が少なくパフォーマンスが問題になりにくく、プロダクト全体の機能が不十分で新機能を素早くリリースして機能を充実させたいという状況だったが、1年で導入社数が1,000社へと10倍成長し、プロダクト全体の機能も充実し、プロダクトを使い込んでいただけるお客様も増え、顧客体験がより重要視されるフェーズになった
- 課題の発生: 巨大な階層構造が作成されるケースが出てきたことにより大量のN+1問題が発生し、深い階層構造では1,000回ものクエリ実行が必要になる状況になった
■ 2. Adjacency List（隣接リスト）
- 基本構造: 各レコードが自身の親レコードへの参照を持っており、parent_idが親レコードへの参照となり、親ノードの取得や子ノードの取得は単純なWHERE句で実現できる
- メリット: 実装が容易で直感的なFolderモデルで実装でき、書き込み操作（子ノードを作成、ノードを移動）がSQL問い合わせ1回で容易に実行できる
- デメリット: 親子関係を超えた読み込み操作（祖先ノード取得、子孫ノード取得）が困難であり、SQL問い合わせを複数回行う必要があり、再帰処理により親が存在しなくなるまで繰り返すため、深い階層では大量のN+1問題が発生する
- 初期採用の理由: 開発当時のプロダクト状況では、導入社数が100社とユーザー数が少なくパフォーマンスが問題になりにくく、新機能を素早くリリースして機能を充実させたいという要件から、実装が容易なAdjacency Listでフォルダ階層化機能を実装した
■ 3. Closure Table（閉包テーブル）
- 基本構造: 階層構造における全ての経路を保持しているテーブルで、Adjacency Listへの関連を持ち、ancestor_idは祖先のid、descendant_idは子孫のid、depthは経路長を表し、祖先・子孫の関係によって経路を表現する
- メリット: 親子関係を超えた読み込み（祖先ノード取得、子孫ノード取得）がJOINを伴うSQL問い合わせ1回で容易に実行できる
- デメリット: ストレージコストがかかり、書き込み操作が困難で経路を正しい状態に維持する必要があり、実装が複雑である
- 書き込み操作の実装: ノード作成時はコールバックを実行し、親ノードが終点の経路を取得して自身が終点の経路を作成してバルクインサートし、ノード移動時は自身と子孫のノードを取得して自身と子孫の経路を削除してから自身と子孫の経路を作成する
■ 4. Recursive CTE（再帰CTE）
- 基本概念: SQLにおけるCTE（Common Table Expression）の一種でWITH句を使い、再帰的にクエリを実行でき、MySQL 8.0、PostgreSQL 8.4、SQLite 3.8.3などの主要なRDBMSでサポートされており、Rails 7.2.0からQueryMethods#with_recursiveが登場した
- 基本構造: 非再帰項（初回だけ実行される）と再帰項（繰り返し実行される）で構成され、1つ前の実行結果を参照し、新たなレコードが生じなくなるまで繰り返す
- Adjacency List + Recursive CTEのメリット: Adjacency Listからデータ構造を変える必要がなく問い合わせ方法が変わるのみで、親子関係を超えた読み込みをクエリ1回で取得でき、Adjacency Listのままなので書き込みが容易である
- デメリット: DB内で再帰処理を繰り返す必要があるため深い階層だと低速になる
■ 5. リファクタリング手法の選定と実験
- 比較検討: Closure Tableは読み込みが非常に高速だが書き込みが低速で閉包テーブルを追加する必要があり実装が複雑、Recursive CTEは読み込みが高速で書き込みも高速（追加操作なし）でデータ構造の変更なく実装が容易である
- フォルダ階層化機能の特性: 読み込みが多いワークロード（一度作成されたフォルダは継続的に閲覧される）であり、階層制限がないため、読み取りが高速なClosure Tableを選択した
- パフォーマンス実験: ActiveRecord上でトップレベルのノードから葉ノード探索処理の実行時間を計測し、深さ6（127ノード）ではAdjacency Listが38.050ms、Closure Tableが4.228ms、Recursive CTEが10.869msで、深さ13（16,383ノード）ではAdjacency Listが3749.056ms、Closure Tableが4.024ms、Recursive CTEが14.111msとなり、Adjacency Listと比較してClosure Tableでは大幅に高速化を達成した
- 実験結果の考察: Closure Tableは横ばいで、Recursive CTEは深くなるほど低速になり、深さ13ではAdjacency Listと比較してClosure Tableは約931倍高速化を達成した
■ 6. まとめと推奨手法
- 推奨手法の整理: 開発初期はAdjacency List、小規模の階層（100ノード）はAdjacency List + Recursive CTE、中規模の階層（1,000ノード）は読み込みが多い場合はClosure Tableで書き込みが多い場合はAdjacency List + Recursive CTE、大規模の階層（10,000ノード）は頻繁に書き込みがなければClosure Tableを推奨する
- 本発表の目的: ツリー構造（親を一つだけ持つ）のみを扱い、階層構造を表現する2つのデータ構造（Adjacency ListとClosure Table）を理解し、Recursive CTEの概要を理解し、階層化機能において適切な手法を選択ができるようになることを目指した