物理設計・インデックス・障害回復重要度:★★★出題: AM2・PM1・PM2

結合アルゴリズム（Nested Loops法・Sort-Merge法・Hash法）

けつごうあるごりずむ / Join Algorithms (Nested Loops, Sort-Merge, Hash Join)

RDBMSのクエリ(SQL)オプティマイザが複数テーブルを結合する際の代表的な3つの物理実行方式（入れ子ループ法、ソートマージ法、ハッシュ法）。

3行速習ポイント

Nested Loops（入れ子ループ）法：外部表（駆動表）の各行について内部表を探索する。外部表が小さく内部表の結合列に索引がある場合に最も高速
Sort-Merge（ソートマージ）法：両方の表を結合列でソートしてから先頭から順に突き合わせる。既にソート済みの索引がある場合や不等号結合にも有効
Hash（ハッシュ）法：小さい方の表（ビルド表）からメモリ上にハッシュ表を作成し、大きい方の表（プローブ表）を走査して等値結合する。索引がない大量データ同士の等値結合で高速

図3大結合アルゴリズムの特性比較

OLTP向け

Nested Loops法

少量の駆動表×内部表の結合列索引があるオンライン検索に最適

ソート突合

Sort-Merge法

双方を結合キーでソートして突合せ。範囲結合やソート済索引に有効

バッチ・DWH

Hash結合法

小表からメモリ上にハッシュ表を構築。索引なし大量データの等値結合に最適

午前IIの物理データベース問題および午後I・午後IIのSQL性能チューニング問題で頻出のトピックです。オプティマイザが統計情報に基づいて最適な結合方式を選択しますが、索引の有無やデータ件数・メモリ量に応じた各アルゴリズムのI/O特性を理解しておく必要があります。

Nested Loops法では「絞り込み後の行数が少ない表」を外部表（駆動表 / Driving Table）に選び、内部表の結合キーにB+木索引を定義するのが鉄則
Hash結合は等値結合（＝）にのみ適用可能であり、ハッシュ表がワークメモリ（PGA/work_mem）に収まらない場合は一時ディスク書き出しが発生して性能が低下する
統計情報が古いとオプティマイザが行数を誤認し、大量行の結合に誤ってNested Loops法を選択して極端な性能劣化を招くことがある