結合アルゴリズム — 2つの表を賢くつなぐ

「注文」表と「顧客」表を顧客IDでつなぐ——SQLでは JOIN の一言ですが、その裏でDBはどの行とどの行が一致するかを膨大に照合しています。同じ結合でも、やり方はネステッドループ・ハッシュ・ソートマージの3通り。それぞれの手数（比較回数）を数えながら、いつどれが速いのかを動かして理解します。

1. 総当たりでつなぐ — ネステッドループ結合

一番素朴なやり方。表Aの1行ごとに、表Bを先頭から全部見て一致を探します。二重ループなので比較回数は n × m。小さい表どうしや、片方が索引で一発に絞れるときは十分速いのですが、両方が大きいと手数が爆発します。

下で外側（A）と内側（B）のポインタが動く様子を見てください。緑の線が見つかった一致（結合される行ペア）です。

二重ループ — Aの各行がBを全部なめる
青＝外側ループの現在行（A）、オレンジ＝内側ループが走査中の行（B）。キーが一致したら緑の線でつなぎます。右上の比較カウンタが n×m へ向かって増えるのに注目。行数を増やすと手数が二乗で膨らみます。
POINT — 小さい表が味方 ネステッドループの費用は n × m。だが内側の表Bに索引があれば、Bを全走査せず O(log m) で該当行へ飛べる（インデックスネステッドループ）。外側を小さい表にし、内側を索引で引く——これが実際のDBでこの方式が今も使われる理由。
ネステッドループ結合の比較回数 ≈ n × m n=m=1,000 なら100万回。ただし内側に索引があれば n × log m まで下がる

2. ハッシュで一発照合 — ハッシュ結合

もっと賢く。まず小さいほうの表Aのキーをハッシュ表に登録しておきます（ビルド）。次に表Bの各行のキーをハッシュして、同じ入れ物（バケツ）だけを覗いて一致を探します（プローブ）。ハッシュは平均 O(1) で入れ物にたどり着くので、全体の手数はおよそ n + m。総当たりの n×m から劇的に減ります。

下で、Aがバケツに入っていく構築と、Bが自分のバケツだけ調べる照合の2段階を見てください。

構築 → 照合 — 同じバケツだけを見る
前半＝Aの各キーを h(key)=key mod 5 でバケツへ登録（青）。後半＝Bの各キーを同じ関数でバケツに飛ばし、そのバケツの中だけ比較（オレンジ→一致は緑）。Bは表A全体ではなく同じバケツの数個としか比べません。作業量が n+m で収まる様子を見てください。
POINT — 等値結合の主力 A.id = B.id のような等値結合では、ハッシュ結合が大きい表どうしの定番。弱点はハッシュ表がメモリに乗る前提であること（乗らなければ分割して処理する）と、< や > の範囲結合には使えないこと（同じ値しか同じバケツに来ないため）。

3. 並べてから突き合わせる — ソートマージ結合

3つめは、両方の表をキーで並べ替えてから、2本の指で先頭を突き合わせる方法。小さいほうの指を進めながら、一致したら結果に出す——各行を一度ずつ見るだけなので、マージ自体は n + m。ただし前もってソートに n log n かかります。

下で、まず両表が整列し、次に2つのポインタが小さいほうを追い越さないように進む様子を見てください。

ソート → 2本指でマージ
前半＝両表がキー順に整列（バラバラ→昇順）。後半＝A側とB側のポインタが進み、A[i]<B[j] ならA、A[i]>B[j] ならBを1つ進め、等しければ緑でつないで両方進める。指は戻らないので、突き合わせは各行1回ずつで済みます。
ソートマージ結合 ≈ n log n + m log m + (n + m) マージ本体は n+m と軽い。費用の主役はソート。だから入力がすでに整列済み（索引順に読める等）なら、この方式が一気に有利になる

4. いつどれが速い？ — コスト比較

3つの方式に絶対の勝者はなく、表の大きさ・索引の有無・並び順で最適解が変わります。オプティマイザ（次のレッスン）はこの費用を見積もって方式を選びます。下で件数を動かし、比較回数がどう変わるかを見てください。

3方式の作業量くらべ（対数目盛り）
棒は各方式の推定作業量（縦は対数目盛り）。ネステッドループ n×m は件数が増えると突出し、ハッシュ n+m は最も低く、ソートマージはソートぶんだけ中間。件数を極端に変えて、勝者（枠が光る）が入れ替わるのを確かめてください。
注意 — 「ハッシュ結合が常に最強」ではない ハッシュは等値結合でメモリに乗るときの主役にすぎない。範囲結合（<, BETWEEN）はソートマージの独壇場だし、片方が数行なら索引付きネステッドループが最速。データがすでに索引順で整列済みならソートを省けてマージが圧勝する。方式の良し悪しは常に文脈しだい。
一歩先へ — オプティマイザと結合順序 3表以上の結合では、どのペアから、どの方式でつなぐかの組み合わせが膨大になる。DBのコストベースオプティマイザは、統計情報（行数・値の分布・索引）から各プランの費用を見積もり、探索して最良の実行計画を選ぶ。結合の順序次第で中間結果の大きさが桁違いになるため、順序決定は最適化の核心。巨大分析ではハッシュ結合＋並列化、トランザクション処理では索引ネステッドループが主役——というのが現場の勘どころ。

5. まとめ — 結合の道具箱