【テクニカル・上級編】ネステッドループ結合 – PostgreSQL

データベースの実行計画を見ているとき、あるいはスロークエリのプロファイルに頭を抱えているとき、我々はしばしば `Nested Loop` という文字と向き合うことになります。

「Nested Loopは単純で遅い」。そう断じるのは簡単ですが、PostgreSQLのエンジン内部で何が起きているかを理解すれば、それが単なる「力技」ではなく、特定のコンテキストにおいて驚異的な効率を発揮する洗練されたアルゴリズムであることが見えてきます。

今日は、この「古典的かつ最強」な結合アルゴリズムの内部構造と、現場で遭遇するトラブルシューティングの勘所について、少し深掘りしてみましょう。

—

Nested Loop Join（NLJ）の基本動作は、外側のテーブル（Outer）の各行に対して、内側のテーブル（Inner）をスキャンする、という極めてシンプルなものです。

計算量は $O(M \times N)$。教科書的には「最悪」の選択肢に見えますよね。しかし、PostgreSQLのプランナーがNLJを選択するとき、そこには明確な意図があります。

最初の1行を返すまでのレイテンシが極めて短い： Hash Joinのように結合前にハッシュテーブルを構築する必要がないため、ストリーミング的に行を返せます。
インデックスの恩恵をフルに受ける： 内側のテーブルに適切なインデックス（特にB-tree）が存在すれば、実質的なコストは $O(M \times \log N)$ にまで劇的に低下します。
メモリ消費が極めて低い： 大量のメモリを占有するハッシュテーブルが不要です。

つまり、NLJは「小規模なデータセット」あるいは「非常に効率的なインデックスが存在する環境」において、PostgreSQLが誇る最強の武器になるのです。

—

PostgreSQLのソースコードレベルで追っていくと、`ExecNestLoop` 関数がこの処理の中核を担っています。面白いのは、この関数が単なる二重ループではないという点です。

Outer Relationのイテレーション： PostgreSQLはOuterテーブルから行を取得する際、`ExecProcNode` を呼び出します。ここにはソートやフィルタリングの結果が渡されることもあります。
Inner Relationの再スキャン： 内側のテーブルがインデックススキャンであれば、`ExecReScan` を繰り返すことになります。ここで重要なのが「インデックスのプリフェッチ」や「バッファキャッシュの局所性」です。

もしNested Loopが遅いと感じたなら、それはアルゴリズムのせいではなく、「内側のスキャンがインデックスにヒットしていない（＝シーケンシャルスキャンが発生している）」可能性を疑うべきです。ループの回数分だけフルスキャンを回していれば、どんなシステムでも悲鳴を上げます。

—

Nested Loopがボトルネックになっている場合、以下の順序で診断を行うのが「熟練エンジニアの流儀」です。

`EXPLAIN ANALYZE` を実行し、内側のテーブルが `Seq Scan` になっていないかを確認します。もしそうなっていれば、結合条件にインデックスが張られていないことが原因です。

プランナーが「Outerテーブルは1行しか返さない」と誤解しているのに、実際には数千行返している場合、プランナーは「Nested Loopが最速だ」と判断してしまいます。これは統計情報（`ANALYZE`）の更新不足が主犯です。

データ量が増え、Nested Loopが「遅い」と感じるようになったなら、それは閾値を超えたサインです。

もし結合対象が数万行を超えているなら、`enable_nestloop = off` で強制的にHash JoinやMerge Joinへ誘導し、実行時間の変化を比較してみてください。ただし、これは劇薬です。インデックスの最適化が先であることは忘れないでください。

—

PostgreSQLのプランナーは非常に優秀ですが、人間が提供する統計情報やインデックス設計という「地図」が古ければ、彼らも迷子になります。

Nested Loopを「遅いアルゴリズム」と決めつけるのではなく、「システムが提供するインデックスという武器を最大限に活かそうと努力しているアルゴリズム」だと捉えてみてください。そうすれば、クエリの改善案は自然と浮かんでくるはずです。

データベースは、結局のところ「いかに効率よくデータに辿り着くか」という知的なゲームです。皆さんのクエリが、今日も最小限のI/Oで駆け抜けることを願っています。