「結合の基本」と侮るなかれ。PostgreSQLのNested Loop Joinを現場目線で紐解く
エンジニアの皆さん、お疲れ様です。データベースのパフォーマンスチューニングで頭を抱える夜、ありますよね。
「実行計画を見たら、またNested Loop Join（ネステッドループ結合）か……」とため息をついたこと、一度はあるはずです。Hash JoinやMerge Joinに比べて、何となく「古典的で遅いアルゴリズム」なんてレッテルを貼られがちなNested Loopですが、実はこれ、PostgreSQLのアーキテクチャにおいて最も洗練された「切り札」の一つなんです。
今日は、教科書的な説明はさらっと流して、現場でどう捉えるべきか、深掘りしていきましょう。
—
Nested Loop Joinの正体：意外とシンプルな「二重ループ」
仕組みは至ってシンプルです。外側のテーブル（Outer Table）から1行ずつ取り出し、その値を使って内側のテーブル（Inner Table）をスキャンする。要はプログラミングの二重ループと同じです。
for each row in outer_table:
for each row in inner_table:
if join_condition matches:
yield (row)
直感的に「これだと行数が増えたら指数関数的に遅くなるのでは？」と感じたあなた、鋭いです。その通り。データ量が膨大ならNested Loopは地獄への入り口です。でも、PostgreSQLのクエリプランナがNested Loopをあえて選ぶのには、明確な理由があるんですよ。
なぜプランナは「Nested Loop」を愛するのか
現場でよく見る「Nested Loopが最適解になるパターン」は、主に以下の2つです。
1. インデックスが効いているとき
内側のテーブルの結合キーにインデックスが張られている場合、Nested Loopは「爆速」になります。Hash Joinのようにテーブル全体をハッシュ化するオーバーヘッドがないからです。
2. 圧倒的に絞り込まれるとき
WHERE句で外側のテーブルが数行に絞り込まれるような場合、全データをスキャンする他の結合方式よりも、必要な行だけをインデックス経由で拾いに行くNested Loopの方が圧倒的に低コストです。
実践：こんなクエリで力を発揮する
例えば、ECサイトで「特定のユーザーの最新注文履歴」を取得するようなケースです。
SELECT u.name, o.order_date
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE u.id = 12345;
`users`テーブルの`id`にPKがあり、`orders`テーブルの`user_id`にインデックスがあれば、プランナは迷わずNested Loopを選択します。このとき、メモリ上に巨大なハッシュテーブルを作る必要はなく、ピンポイントでデータにアクセスできる。これこそがNested Loopの真骨頂です。
現場で「遅いNested Loop」に遭遇したらどうするか？
もしクエリが遅くて、実行計画を見たら「Nested Loop」が犯人だった。そんな時は以下の手順でチェックしてみてください。
- インデックスの確認: 内側のテーブルの結合キーにインデックスが貼られているか？（一番多いミスです）
- プランナの誤認: 「テーブルの行数は少ないはずなのに」とプランナが勘違いしてNested Loopを選んでいないか？（`ANALYZE`を実行して統計情報を最新にしましょう）
- そもそも結合の粒度: 結合対象のテーブルが数万行を超えていないか？ もしそうなら、インデックスが効いていない証拠です。
先輩からのアドバイス：Nested Loopは「精度」の証
Hash Joinが「力技の効率化」だとしたら、Nested Loopは「精巧な外科手術」です。インデックスというメスを正しく使えば、どんなに巨大なデータベースでも、Nested Loopは一瞬で狙ったデータを見つけ出します。
もし、開発中のアプリでNested Loopが多発しているなら、それは「インデックス設計がうまくいっている」というポジティブなサインかもしれません。逆に、Nested Loopが全く選ばれないなら、インデックスが活用されていないか、あるいは統計情報が古くなっている可能性があります。
「Nested Loopだからダメ」と決めつけず、「なぜこのクエリでNested Loopが選ばれたのか？ それは理想的なアクセスパスなのか？」と問いかけてみてください。データベースの奥深さが、少しずつ見えてくるはずです。
それでは、また次回のチューニング会議でお会いしましょう！
コメント