頻出中 ⏱ 7分★★★☆☆

結合戦略

NL Join・Hash Join・Merge Joinのしくみと使い分けを完全習得

結合戦略とは

DBMS がクエリを実行する際に選択する「テーブルの結合アルゴリズム」のこと。選択されたアルゴリズムによって実行時間が大きく変わる。オプティマイザが自動選択するが、仕組みを理解することで設計・チューニングに活かせる。

主要な結合アルゴリズム比較
3大結合アルゴリズム
アルゴリズム仕組み計算量（概略）適した状況
ネステッドループ
（NL Join）		外側の各行 × 内側の全行を総当たりO(N×M)外側が少行、内側にインデックスあり
ハッシュ結合
（Hash Join）		片方をハッシュテーブルに展開してもう片方でルックアップO(N+M)大規模テーブル間、インデックス不要
マージ結合
（Merge Join）		両テーブルをソートしてポインタを進めながら結合O(N logN + M logM)結合キーでソート済み、等値結合
ネステッドループ結合（NL Join）

最もシンプルなアルゴリズム。外側テーブルの各行に対して内側テーブルを走査する。

動作イメージ
外側テーブルから1行取り出す
↓
内側テーブルを結合キーで検索（インデックスがあれば高速）
↓
一致した行を結果に追加
↓ 外側を全行処理するまで繰り返す
完了
内側テーブルの結合キーにインデックスがある場合は O(N × log M) に改善。OLTP クエリで最も多く使われる。
ハッシュ結合（Hash Join）

小さい方のテーブルをハッシュテーブルに展開し、大きい方でプローブ（照合）する。

-- ハッシュ結合が選ばれやすいクエリ例（インデックスなし・大規模）
SELECT o.注文ID, c.顧客名
FROM   注文履歴 o               -- 大テーブル（100万行）
JOIN   顧客 c ON c.顧客ID = o.顧客ID  -- 結合キーにインデックスなし
WHERE  o.注文日 >= '2024-01-01';
ハッシュテーブルがメモリに収まらない場合は一時ディスクに退避（スピル）し性能が著しく低下する。work_mem（PostgreSQL）などを調整する。
マージ結合（Merge Join / Sort-Merge Join）

両テーブルが結合キーでソートされていれば O(N+M) で結合できる。クラスタ化インデックスがあると特に有効。

結合順序の重要性

N テーブルの結合順序は N! 通りある。オプティマイザが統計情報から最適順序を選ぶが、統計が古いと誤った計画を選ぶことがある。

ポイント内容
駆動表（外側）先に処理するテーブル。行数が少ない方が有利（NL Join の場合）
統計情報ANALYZE（PostgreSQL）/ DBMS_STATS（Oracle）で最新化
ヒント句USE_NL, USE_HASH など（製品依存、最終手段）
試験頻出ポイント

📝 理解度チェック

ネステッドループ結合が最も効率よく動作する条件はどれか？
ハッシュ結合（Hash Join）で性能が著しく低下する原因はどれか？
マージ結合が有効な場面はどれか？

読了ボタンを押すとトップページの進捗に反映されます

← 自己結合サブクエリ →