「ネステッドループ結合」という原点、あるいはその深淵について
PostgreSQLのクエリプランナと対峙していると、時折「なぜここでNested Loopを選んだのか？」と問い詰めたくなる瞬間があるはずだ。Hash Joinが花形で、Merge Joinが効率の代名詞だと思われがちな昨今、あえてネステッドループ結合（Nested Loop Join）に焦点を当ててみたい。
一見すると、最も原始的で、計算量 $O(N \times M)$ という「最悪」の響きを持つこのアルゴリズム。しかし、この簡素な構造の中にこそ、PostgreSQLの最適化の神髄が隠されていることを、ベテランのエンジニア諸君なら理解しているだろう。
1. なぜ「原始的」な結合が選ばれるのか
Nested Loopが真価を発揮するのは、決して「小規模なテーブル同士の結合」だけではない。我々が注目すべきは、外部テーブル（Outer Table）のカーディナリティが極めて小さく、かつ内部テーブル（Inner Table）に適切なインデックスが存在する場合の爆発的なパフォーマンスだ。
PostgreSQLのオプティマイザは、コストモデルに基づき、内部テーブルへのアクセスがインデックス・スキャン（Index Scan）やビットマップ・スキャンで完結する場合、Nested Loopを積極的に採用する。これは、メモリ上に大きなハッシュテーブルを構築する必要がないため、メモリ消費を抑えつつ、最初の数行を即座に返せる「レスポンス速度」において圧倒的な優位性を持つからだ。
2. 内部アーキテクチャの冷徹な現実
Nested Loopの動作は単純だ。外部テーブルから1行取り出し、そのキーを使って内部テーブルを検索する。これを繰り返すだけ。だが、ここで意識したいのは「プリフェッチ」と「バッファキャッシュ」の挙動だ。
インデックス・スキャンが繰り返される際、内部テーブル側のインデックスツリーがメモリに乗っていれば驚異的な速さを叩き出す。しかし、インデックスが巨大で、かつ外部テーブルの行数が多い場合、Nested Loopは「ランダムI/Oの嵐」へと変貌する。
もし `EXPLAIN ANALYZE` を叩いて、「Nested Loop」のコストが跳ね上がっているのを見たなら、以下の項目を疑ってほしい。
- インデックスの欠如： 結合キーにインデックスがない場合、Nested Loopはフルスキャンを繰り返す。これはシステムにとっての「自殺行為」だ。
- 不適切なインデックス構成： 結合キーだけでなく、SELECT句で必要なカラムまでをカバーする「カバリングインデックス」を検討すべきフェーズかもしれない。
- プランナの誤算： `pg_stats` が古いせいで、外部テーブルの行数を過小評価していないか？ `ANALYZE` を実行するだけで、ハッシュ結合へプランが切り替わり、劇的に改善することもある。
3. パフォーマンストラブルシューティングの勘所
Nested Loopで詰まったとき、私がまず確認するのは「ループの回数」と「1ループあたりのコスト」のバランスだ。
よくある悲劇は、外部テーブルが「小規模なテーブル（例えばパラメータテーブル）」であるはずが、アプリケーション側の条件指定の漏れにより、意図せず数万行のレコードが外部テーブルに流し込まれているケースだ。
— よくある悪夢のパターン
SELECT FROM orders o
JOIN users u ON o.user_id = u.id
WHERE o.created_at > ‘2023-01-01’;
このクエリで `orders` が巨大な場合、プランナが `users` を外部テーブルとしてNested Loopを選択しようとすると、破滅的な遅延を招く。こういったケースでは、インデックスを増やすだけでなく、結合順序をコントロールする `JOIN_COLLAPSE_LIMIT` の調整や、CTEを用いたプランの強制といった「外科手術」が必要になることもある。
結びとして：Nested Loopと向き合うということ
Nested Loopは、PostgreSQLのオプティマイザが持つ「最も素直な反応」を示してくれるアルゴリズムだ。データ構造、インデックスの有効性、そしてクエリの意図。これらが正しく噛み合っているとき、Nested Loopはハッシュ結合をも凌駕する軽快さを発揮する。
「Nested Loopは遅いから避けるべき」という短絡的な思考は、エンジニアとしての視野を狭める。むしろ、なぜあえてこの単純なアルゴリズムが選択されたのか、その裏にあるデータの分布とインデックスの状態を読み解くこと。それこそが、データベースの深淵を覗き込み、システムを極限までチューニングする醍醐味ではないだろうか。
今日もまた、クエリプランナと静かな対話を楽しんでほしい。
コメント