ネステッドループ結合：その「単純さ」に隠された深淵を読み解く
PostgreSQLのクエリプランナと対峙しているとき、`Nested Loop`という文字が実行計画のトップに現れると、どう感じますか？ 多くのエンジニアは「ああ、小規模な結合か」と反射的に納得するかもしれません。しかし、大規模システムを運用していると、この「単純なはずのアルゴリズム」が、時にパフォーマンスのボトルネックとなり、時に最適解となるその「揺らぎ」に翻弄されることがあります。
今日は、PostgreSQLにおけるネステッドループの深淵を、エンジニアの視点で少し掘り下げてみたいと思います。
ネステッドループの本質とは何か
ネステッドループの仕組み自体は、大学のアルゴリズムの授業で習う通りです。外側（Outer）テーブルの各行を取り出し、それに対応する内側（Inner）テーブルの行を検索する。この繰り返しです。
しかし、PostgreSQLの内部では、この「検索」のプロセスにいくつかの最適化が施されています。単なるフルスキャンを繰り返すのであればO(NM)の悪夢ですが、適切なインデックスが存在する場合、内側の検索はO(log M)へと劇的に圧縮されます。
ここで重要なのは、「外側テーブルのサイズ」と「内側テーブルのインデックスへのアクセス負荷」のバランスです。
なぜ「プランナ」はネステッドループを選ぶのか
クエリプランナがネステッドループを好むのは、単にデータが小さいからだけではありません。以下の条件が揃ったとき、ネステッドループは最強の武器になります。
- 外側テーブルの行数が極めて少ない場合：セットアップコストがほぼゼロに近いため、ハッシュ結合のようなメモリ確保（`work_mem`）やソートのオーバーヘッドを嫌う場合に選ばれます。
- 内側テーブルの結合キーにインデックスが効いている場合：これが全てです。B-treeインデックスがあれば、内側の検索は非常に効率的になります。
- リミット（LIMIT）句がある場合：先頭の数行だけが必要なとき、ハッシュ結合のように「全データをメモリにロードしてハッシュを作る」のを待つ必要はありません。ネステッドループは最初の1行を見つけた瞬間に結果を返せます。
現場で遭遇する「罠」とトラブルシューティング
僕が現場でよく見る「ネステッドループによる事故」は、往々にしてプランナの誤解から生じます。
1. 統計情報の陳腐化
一番多いのが、「実際には数百万行あるテーブルなのに、統計情報が古くて数行しかないと見積もられている」ケースです。プランナは自信満々にネステッドループを選択しますが、実際には内側の検索でインデックスが効かない、あるいはランダムアクセスが多発してIO待ちが爆発します。
- 対策: `ANALYZE`の徹底はもちろんですが、実行計画上の「Estimated rows」と「Actual rows」の乖離を定期的に監視してください。
2. 「Index Scan」の甘い罠
内側テーブルにインデックスがあっても、そのインデックスが結合条件（WHERE句）だけをカバーしていて、SELECT句に必要な他のカラムまで読みに行っている（Heap Fetchが発生している）場合、IOコストは跳ね上がります。
- 対策: `INCLUDE`句を使ったカバリングインデックスを検討しましょう。インデックスだけでクエリが完結すれば、ネステッドループの速度は別次元になります。
3. 結合順序の逆転
プランナが「小さい」と判断したテーブルが、実は結合の結果として膨れ上がるような場合、ネステッドループは地獄の入り口になります。
- 対策: `pg_stat_activity`や`EXPLAIN (ANALYZE, BUFFERS)`を使い、どのループでキャッシュミス（Shared HitではなくReadが発生しているか）が起きているかを特定してください。
エンジニアとしての矜持
結局のところ、ネステッドループは「非常に素直なアルゴリズム」です。複雑なハッシュ結合やマージ結合と違い、挙動が予測可能で、インデックス設計の良し悪しをダイレクトに反映します。
もし、あなたのデータベースでネステッドループが「遅い」と感じたなら、それはアルゴリズムのせいではありません。インデックスが物理的なIOを減らすために十分でないか、あるいはデータモデルが検索効率を考慮していないことを、データベースが静かに教えてくれているのです。
PostgreSQLは正直です。実行計画が教えてくれる「小さな予兆」を無視せず、なぜそのプランナがその選択をしたのかを想像すること。それが、データベースエンジニアとして一つ上のステージに登るための、唯一の近道だと僕は信じています。
皆さんのクエリが、今日もインデックスの恩恵を最大限に受けられますように。
コメント