Nested Loop / Hash / Merge Join

このレッスンで分かること

3 種類の JOIN アルゴリズムの仕組み

データ量・インデックスごとの最適選択

プランナが JOIN タイプをどう決めるか

Nested Loop / Hash / Merge Join とは

3 種類の結合アルゴリズムと最適な場面を比較する。本レッスンでは、Nested Loop / Hash / Merge Join の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

JOIN は意外と多様

JOIN 文を書くと内部では 3 つのアルゴリズムから 1 つが選ばれます。データ量とインデックスの状況で最適解が変わります。

Nested Loop Join — 二重ループで素直に結合
Hash Join — 片方をハッシュテーブル化して O(1) 検索
Merge Join — 両方をソート済みにして 1 パス結合

diagram (will load when visible)

Nested Loop Join

最も単純な方式です。外側ループ の各行に対し、内側ループ で結合相手を探します。

pseudo

for u in users:
    for o in orders:
        if o.user_id == u.id:
            output(u, o)

素朴な実装は O(n × m) ですが、内側に インデックス があれば内側ループが O(log m) に下がり、全体で O(n × log m) になります。これを Indexed Nested Loop Join と呼びます。

シーン	適性
外側が小さい	良い
内側にインデックスあり	良い
両方大きい	悪い

実務では「外側にフィルタが効いて少数」「内側に PK / インデックスあり」のときに圧倒的に強い。MySQL は伝統的に Nested Loop を多用します。

Hash Join

片方のテーブル（通常は小さい方）を ハッシュテーブル に展開し、もう片方を 1 件ずつハッシュで突き合わせます。

pseudo

hash_table = {}
for u in users:
    hash_table[u.id] = u
for o in orders:
    if o.user_id in hash_table:
        output(hash_table[o.user_id], o)

計算量は O(n + m)。等価結合 (=) でしか使えません（>、LIKE は不可）。ハッシュテーブル分のメモリが必要で、収まらないと グレースハッシュ（バケットごとに一時ファイルへ分割）で処理します。

シーン	適性
両方が大きい	良い
等価結合	必須
インデックス無し	良い（インデックスがあっても選ばれる）
メモリ十分	良い

PostgreSQL は Hash Join を積極的に使います。MySQL は 8.0 で Hash Join をサポートし、それまでは Nested Loop 一辺倒でした。

Merge Join

両テーブルを 同じキーでソート済み にしておき、両方を 1 パスでマージします。

pseudo

sort_users_by_id()
sort_orders_by_user_id()
i = 0, j = 0
while i < n and j < m:
    if users[i].id < orders[j].user_id: i += 1
    elif users[i].id > orders[j].user_id: j += 1
    else: output(...); j += 1

計算量は ソート済みなら O(n + m)、ソートが必要なら O(n log n + m log m)。

シーン	適性
両方ソート済み（PK や複合インデックス順）	良い
メモリが限られ Hash Join できない	良い
非等価結合（`>=`、`BETWEEN`）	Nested Loop と並ぶ有力な選択肢（ソート順を活かせる場合）

PostgreSQL では大規模 JOIN で Hash か Merge かを動的に選択します。

選択の判断軸

プランナは次を見て決めます。

結合キーが等価結合か — = 以外なら Nested Loop か Merge
片方が極端に小さいか — 小さい方を内側にしたインデックス付き Nested Loop
両方が大きく等価結合か — Hash Join（メモリ収容ならハッシュ、外れるならグレースハッシュ）
既にソート済みか — Merge Join

実例で見る

SQL クエリ

EXPLAIN SELECT u.name, COUNT(o.id)
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.country = 'JP'
GROUP BY u.id;

PostgreSQL の出力例：

プレーンテキスト

HashAggregate
  Group Key: u.id
  ->  Hash Join
        Hash Cond: (o.user_id = u.id)
        ->  Seq Scan on orders o
        ->  Hash
              ->  Index Scan using idx_country on users u
                    Index Cond: (country = 'JP'::text)

Hash Join が選ばれ、users がハッシュテーブル化されて orders を逐次スキャン。これが大規模 JOIN の典型形です。

性能改善の手筋

小さい方を WHERE で更に絞る — Hash テーブルが小さくなる
両方に複合インデックスを貼る — Merge Join が使える条件を整える
JOIN 順序を変える — STRAIGHT_JOIN (MySQL) や CTE で順序を制御
work_mem を増やす (PostgreSQL) — Hash がメモリ内で完結

JOIN が遅いときは EXPLAIN で どの方式か を必ず確認。Nested Loop で大規模 JOIN している場合はインデックスかメモリ拡張で改善する。

やってみよう

自分のプロジェクトで JOIN を含むクエリを 3 つ EXPLAIN する
どの JOIN タイプが使われているか分類する
小さいテーブルの方を WHERE でさらに絞ったら計画が変わるか試す

よくある質問

Q. INNER JOIN と LEFT JOIN の違いは？

A. INNER は両側に一致するレコードのみ、LEFT は左側を全て残し右側に一致するものを結合します。LEFT で右側が無いと NULL になります。「ユーザーごとに購入履歴を、購入が無いユーザーも含めて出したい」場合は LEFT JOIN が必須です。

Q. 3 テーブル以上を JOIN できますか？

A. できます。a JOIN b ON ... JOIN c ON ... のように繋げます。JOIN は順番に評価されるため、絞り込みの強い条件を先に置くとパフォーマンスが上がります。EXPLAIN で実行計画を確認しながら順序を見直すのが定石です。

Q. JOIN したら行数が増えたのはなぜ？

A. 右側に複数の一致レコードがある（多対多）場合、その分だけ行が増えます。意図しない重複が出たら GROUP BY や DISTINCT で集約するか、サブクエリで先に集計してから JOIN すると行数が安定します。

次のレッスン

次は インデックスチューニング で、3 種類の結合アルゴリズムと最適な場面を比較するを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

Nested Loop / Hash / Merge Join の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. Nested Loop / Hash / Merge Join とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン