「Nested Loopは悪か？」――PostgreSQLの結合アルゴリズムを再考する
PostgreSQLのクエリプランナと長く付き合っていると、時折「Nested Loop Join」に対して過剰な嫌悪感を抱いているエンジニアに出会うことがあります。「ハッシュ結合の方が計算量が少ないはずだ」という直感は、大規模なデータセットでは正しい。しかし、PostgreSQLの内部アーキテクチャを深く理解すればするほど、Nested Loopが実は極めて「エレガントな武器」になり得ることに気づくはずです。
今回は、この「古くて新しい」結合手法を、いかに味方につけるかという話をしましょう。
—
なぜNested Loopは「選ばれる」のか
PostgreSQLのプランナがNested Loopを選択する際、そこには明確な意図があります。それは「外部表（Outer Table）の行数が少ない」または「内部表（Inner Table）の結合キーに効率的なインデックスが存在する」という確信がある場合です。
Nested Loopの計算量は、シンプルに `(外部表の行数) × (内部表へのアクセスコスト)` で決まります。この「内部表へのアクセス」が、インデックス（特にB-tree）によって`O(log N)`で解決されるのであれば、ハッシュ表をメモリ上に構築するオーバーヘッドや、ソートのコストよりも遥かに低レイテンシで結果を返せるのです。
現場で直面する「Nested Loopの罠」
パフォーマンスチューニングの現場でよく見る悲劇は、「プランナを信じすぎた結果」です。
特に、以下のようなケースでNested Loopは牙を剥きます。
- 統計情報の鮮度不足: `ANALYZE`が長期間実行されておらず、プランナが「外部表は少ないはずだ」と誤認している。
- 相関関係の欠如: 複数カラムにまたがる条件があるにもかかわらず、拡張統計（Extended Statistics）が定義されておらず、カーディナリティの推定が大きく外れている。
- インデックスの不適合: 結合キーの型が微妙に一致せず（例: `text`と`varchar`の比較など）、暗黙の型変換が発生してインデックスが効いていない。
これらは`EXPLAIN (ANALYZE, BUFFERS)`を叩けばすぐに露呈しますが、意外と見落とされがちなのが「Nested Loopが延々と繰り返される際のI/O負荷」です。メモリに乗るはずのインデックスがページキャッシュから溢れ始めた瞬間、Nested Loopは一気にシステム全体のボトルネックへと変貌します。
チューニングの勘所：どこから手を付けるか
Nested Loopを最適化する際、私がまず確認するのは「インデックスの質」です。単にカラムにインデックスを貼るだけでは不十分です。
1. インデックス・オンリー・スキャンの追求
もし内部表へのアクセスが、インデックスだけで完結するなら最高です。`INCLUDE`句を使ったカバリングインデックスを検討してください。ヒープ（テーブル本体）にアクセスしに行く必要がなくなるだけで、Nested Loopのコストは劇的に下がります。
2. `enable_nestloop`をいじる前に
「Nested Loopが遅いからオフにする」という安易なショートカットは推奨しません。それよりも、プランナに正確な情報を与えることが先決です。`ALTER TABLE … SET STATISTICS`でヒストグラムの解像度を上げるか、あるいは`CREATE STATISTICS`でカラム間の相関をプランナに教えてあげてください。
3. 実行計画の「期待値」と「現実」のギャップを埋める
`EXPLAIN ANALYZE`の出力で `loops` の数と `actual rows` を見比べてください。もし、ループ回数に対して返される行数が異常に多ければ、それはNested Loopの使い所を間違えています。ハッシュ結合やマージ結合への誘導を考えるべきですが、それでもNested Loopにこだわるなら、インデックスの再設計（複合インデックスの順序見直しなど）が必要です。
—
最後に：エンジニアとしての矜持
Nested Loopは、PostgreSQLの結合アルゴリズムの中で最も「素直」な手法です。データへの物理的なアクセス経路が明確であり、チューニングの成果が直結しやすいからです。
「Nested Loopだから遅い」と決めつけるのではなく、「なぜプランナはこれを選んだのか？」「どのインデックスが使われていないのか？」と、データベースの思考プロセスをトレースしてみてください。
高度なチューニングとは、魔法の呪文を唱えることではありません。PostgreSQLが抱える「情報の非対称性」を、我々エンジニアが統計情報やインデックス設計という形で埋めてあげる、その対話のプロセスそのものだと私は信じています。
皆さんのデータベースに、今日もしなやかなクエリが走りますように。
コメント