結合アルゴリズム：3方式で手数が違う
2つのテーブルを JOIN するとき、ネステッドループ・ソートマージ・ハッシュ結合は「手数（比較回数）」がまるで違います。行数を動かして勝敗を見ます。
2,000
2,000
グラフの縦軸:
ネステッドループ
—
ソートマージ
—
ハッシュ結合
—
いちばん手数が少ない
—
3方式の手数（比較・処理回数）
手数 vs 左テーブル行数 N（M は固定。縦線が現在の N）
同じ
ネステッドループは R の各行について S を全走査するので、ざっくり N×M。行数が増えると一気に重くなります。
ソートマージは両方を並べ替えてから一度すれ違うだけ。整列に N·logN + M·logM、マージに N+M。
ハッシュ結合は片方でハッシュ表を作り（ビルド）、もう片方で引く（プローブ）ので N+M。
スライダーで N と M を動かし、どのサイズ比でどの方式が勝つかを実測カウンタで確かめましょう。
R JOIN S でも、DBMS の中では「手数（処理ステップ数）」が方式ごとに大きく違います。ネステッドループは R の各行について S を全走査するので、ざっくり N×M。行数が増えると一気に重くなります。
ソートマージは両方を並べ替えてから一度すれ違うだけ。整列に N·logN + M·logM、マージに N+M。
ハッシュ結合は片方でハッシュ表を作り（ビルド）、もう片方で引く（プローブ）ので N+M。
スライダーで N と M を動かし、どのサイズ比でどの方式が勝つかを実測カウンタで確かめましょう。
いま何が起きている？
ここがポイント
- ネステッドループ ≈ N×M ── 行数が増えると手数が爆発する（二次関数）。小さなテーブルや索引付き結合では今でも有効。
- ソートマージ ≈ N·logN + M·logM + (N+M) ── 整列のコストが効く。すでに整列済み・索引順なら一気に有利。
- ハッシュ結合 ≈ N+M ── 等値結合の主力。手数は線形で最小だが、ハッシュ表をメモリに載せる必要がある。
- 勝者は行数とサイズ比で変わる ── 極小ではネステッドループも互角、大規模ではハッシュ／ソートマージが圧勝。「絶対的な最強」はない。