結合アルゴリズムの内部

なぜ「結合方式」が問題になるのか

JOIN は論理的には「2つのテーブルを結合キーで突き合わせる」操作ですが、どう突き合わせるかの物理的な手段は1つではありません。RDB のオプティマイザは、同じ結合に対して Nested Loop Join / Hash Join / Sort-Merge Join の3方式を候補にし、推定コストが最小のものを選びます。どれを選ぶかで実行時間は数十〜数百倍変わるため、上級者は実行計画でこの選択を読めることが重要です。

以下では2つの表を、外側（駆動表）を N 行、内側を M 行として説明します。

Nested Loop Join

最も素朴な方式です。外側の表を1行ずつ走査し、その各行について内側の表を探して一致を探します。

for each row r in Outer(N rows):       -- 外側を1行ずつ
    for each row s in Inner(M rows):   -- 内側を総当たり
        if r.key == s.key:
            emit (r, s)

何も工夫しなければ内側を毎回フルスキャンするので、計算量は O(N × M)。N=1万・M=1万なら1億回の比較になり、大集合同士では破綻します。

ただし内側の結合キーにインデックスがあると話が変わります。内側のフルスキャン（M）が索引探索（log M 程度）に置き換わり、全体は O(N × log M) になります。これが Nested Loop の本領で、「外側 N が小さく、内側に索引がある」状況では最速になります。

メモリ使用は基本的にごく小さく、1行ずつ処理するため結果を逐次返せる（最初の数行を早く返せる）のも特徴です。LIMIT 付きや、外側がごく少数に絞れるクエリで選ばれやすい理由です。

Hash Join

等値結合（a.id = b.id）専用の方式です。2フェーズで動きます。

-- Build フェーズ: 小さい方(Build側)でハッシュテーブルを作る
for each row s in Build(M rows):
    insert s into HashTable[ hash(s.key) ]

-- Probe フェーズ: 大きい方(Probe側)を1行ずつ照合
for each row r in Probe(N rows):
    for each s in HashTable[ hash(r.key) ]:
        if r.key == s.key: emit (r, s)

各行はハッシュ計算で O(1) 相当の探索になるため、両表を1回ずつ読むだけで済み、計算量は O(N + M)。索引がなくても大集合同士の等値結合を高速にこなせるのが最大の強みです。

代償はメモリです。Build 側のハッシュテーブルを作業メモリに載せる必要があり、載りきらないと Grace Hash Join（両表を結合キーのハッシュでパーティション分割し、ディスクに書き出してから小分けに処理する方式）に切り替わります。これはディスク I/O を伴うため、メモリが足りているかが性能を大きく左右します。

Sort-Merge Join

両表をそれぞれ結合キーでソートし、2つのソート済み列を併走させながらマージしていく方式です。

sort Outer by key;  sort Inner by key;   -- 事前にソート
i = j = 0
while i < N and j < M:
    if Outer[i].key == Inner[j].key: emit; 進める
    elif Outer[i].key <  Inner[j].key: i++   -- 小さい方を進める
    else: j++

マージ自体は両表を1回ずつ舐めるだけで O(N + M) ですが、支配的なのはソートのコストで、全体は O(N log N + M log M) になります。ただし入力が既にソート済みなら（結合キーに索引があってその順で読める、前段の ORDER BY で並んでいる等）ソートを省け、メリットが一気に増します。

範囲条件の結合や、結果をソート順で欲しい場合（直後に ORDER BY / GROUP BY / マージ系の集計が続く）に有利です。メモリ使用はソート用のワークスペースが要りますが、Hash Join のように「全体を一度に載せる」必要はなく、外部マージソートでディスクに溢れても比較的なだらかに劣化します。

オプティマイザはどう選ぶか

3方式の使い分けは、結合条件の種類・推定行数・索引やソート順の有無・作業メモリで決まります。

オプティマイザは各候補の総コストを見積もって比較します。原理は次の通りです。

• 結合条件: 等値でなければ Hash Join は脱落。範囲・不等号は Nested Loop か Sort-Merge に絞られる。
• 推定行数（カーディナリティ）: 外側が極端に少なければ Nested Loop の N が小さく有利。両方とも大きければ起動コストはあるが N+M で済む Hash / Sort-Merge が逆転する。
• 索引・ソート順: 内側の結合キー索引は Nested Loop を、入力のソート済み順は Sort-Merge を後押しする。
• 作業メモリ（work_mem 等のパラメータ）: Build 側が載るなら Hash Join が安く、溢れるなら Grace Hash のディスクコストが乗って不利になる。

まとめ

• 同じ JOIN でも物理的な実行方式は3つ。計算量とメモリの特性が異なる。
• Nested Loop＝外側が小・内側に索引ありで最速（O(N×log M)）、メモリ極小で先頭を早く返せる。
• Hash Join＝等値結合の大集合に強い（O(N+M)）が、Build 側を載せるメモリが要り、溢れるとディスクへ。
• Sort-Merge＝ソート込みで O(N log N + M log M)。範囲条件・ソート済み入力・順序が要る結果に有利。
• オプティマイザは結合条件・推定行数・索引/ソート順・作業メモリから総コスト最小を選ぶ。統計を最新に保つことが正しい選択の土台。