やあ。今日はデータベースエンジニアなら避けては通れない「結合アルゴリズム」の話をしよう。
PostgreSQLの実行計画を見ていると、`Nested Loop` という単語を嫌というほど目にするよね。これ、新人エンジニアの間では「なんか遅い奴」というレッテルを貼られがちなんだけど、実は使い方次第で最強の武器にもなるんだ。
今日は、この「ネステッドループ（Nested Loop Join）」の正体を、現場の視点から紐解いていこうか。
—
ネステッドループ結合：基本は「二重ループ」
仕組みは驚くほどシンプルだ。コードで書くとこうなる。
概念的なネステッドループ
for outer_row in outer_table:
for inner_row in inner_table:
if outer_row.key == inner_row.key:
yield (outer_row, inner_row)
そう、ただの二重ループ。外側のテーブル（Outer）から1行ずつ取り出して、そのたびに内側のテーブル（Inner）を全件スキャンする……というのが基本形だ。
これだけ見ると「え、全件スキャンするの？ 遅くない？」と思うよね。その感覚は正しい。単純にやれば、計算量は O(M × N) になってしまうからね。
なぜPostgreSQLはこれを選ぶのか？
じゃあ、なんでオプティマイザはわざわざネステッドループを選ぶのか。それは、「外側の行数が非常に少ない」あるいは「内側の結合対象にインデックスが効いている」場合、他のどのアルゴリズムよりも速いからだ。
特に、内側のテーブルの結合キーにインデックスがある場合、内側のループは全件スキャンじゃなくて「インデックス・ルックアップ」に昇格する。こうなると、計算量は劇的に減るんだ。
- 得意なシチュエーション
- 外側のテーブルが非常に小さい（数行〜数十行）。
- 内側のテーブルの結合キーにインデックスが張られていて、ピンポイントでアクセスできる。
- 「最初の数件だけ」を素早く返したい（LIMIT句など）。
悲劇の始まり：性能劣化のメカニズム
逆に、一番やってはいけないのは、「外側が巨大なテーブル」かつ「内側のインデックスが使えない（または無い）」ケースだ。
例えば、100万行あるテーブル同士をネステッドループで結合しようとしたらどうなるか。想像するだけで冷や汗が出るよね。100万回、相手のテーブルにインデックスなしで突撃するわけだから、クエリが終わる頃には日が暮れているだろう。
現場で「なぜかクエリが遅い」と相談された時、実行計画を確認すると、たいていはこのパターンだ。
- 結合キーの型が違っていて、暗黙の型変換が走りインデックスが使われていない。
- 統計情報が古くて、オプティマイザが「外側の行数は少ないはずだ」と誤認している。
実務でのチューニングTips
もしキミが現場でネステッドループの性能に悩んだら、まずは以下の順でチェックしてみてほしい。
1. インデックスの確認: 内側のテーブルの結合キーに、適切なインデックスはあるか？
2. 統計情報の更新: `ANALYZE` を実行してみよう。PostgreSQLが「このテーブルは小さい」と勘違いしているだけかもしれない。
3. 型変換の有無: `WHERE a.id = b.char_col` のように、型が不一致でインデックスが効かない状態になっていないか？
4. オプティマイザの説得: どうしてもネステッドループが選ばれて遅いなら、`SET enable_nestloop = off;` を一時的に試して、別のアルゴリズム（Hash Joinなど）が速いか確認してみるのも一つの手だ。ただ、これは最終手段ね。
—
まとめ
ネステッドループは、使いどころさえ間違えなければ、非常にレスポンスの良い優秀なアルゴリズムだ。特にWebアプリケーションの「特定の1ユーザの注文履歴を表示する」といった、キーを指定した検索には欠かせない存在だよ。
「ネステッドループ＝悪」と決めつけず、実行計画の「なぜオプティマイザはこれを選んだのか？」という意図を想像できるようになると、一段上のエンジニアになれるはずだ。
また何か詰まったら、いつでも聞きに来てくれよ。現場からは以上だ！
コメント