Nested Loop Join（ネステッドループ結合）
外側テーブルの各行に対して内側テーブルの全行を走査し、結合条件を評価する最も基本的なJOINアルゴリズム O(N×M)
📌Nested Loop Joinとは
Nested Loop Join（ネステッドループ結合）は、リレーショナルデータベースにおける最も基本的なJOINアルゴリズムです。SQLの SELECT * FROM users JOIN departments ON users.dept_id = departments.id のようなJOIN文がデータベース内部でどのように実行されるかを理解するための基礎となるアルゴリズムです。
日常的な例で考えてみましょう。教室で出席確認をする場面を想像してください。名簿の1人目「田中」に対して、教室にいる全員に「あなたは田中さんですか？」と順番に聞いていきます。全員に聞き終わったら、名簿の2人目「鈴木」に対して、再び教室にいる全員に「あなたは鈴木さんですか？」と聞いていく。これをすべての名前について繰り返す。これがまさにNested Loop Joinの動作です。
技術的には、外側テーブル（駆動表）の各行に対して、内側テーブル（内部表）の全行を走査する二重ループ構造です。計算量は O(N × M) で、外側テーブルがN行、内側テーブルがM行のとき、最大N×M回の比較が発生します。このデモでは5行×3行 = 15回の比較を行います。
PostgreSQLで EXPLAIN を使うと、実行計画に Nested Loop と表示されることがあります。これは、オプティマイザがこのアルゴリズムを選択したことを意味します。特に小さいテーブル同士のJOINや、内側テーブルにインデックスがある場合に選ばれやすいアルゴリズムです。
- SELECT u.name, d.dept_name FROM users u JOIN departments d ON u.dept_id = d.id
- SELECT o.order_id, c.name FROM orders o JOIN customers c ON o.customer_id = c.id WHERE o.date > '2024-01-01'
- SELECT e.name, m.name AS manager FROM employees e JOIN employees m ON e.manager_id = m.id
🔍このツールの値は何を表している？
上のビジュアライザでは、2つのテーブルを使ってNested Loop Joinの動作を可視化しています。外側テーブル = users（社員テーブル）には5名の社員データが、内側テーブル = departments（部署テーブル）には3つの部署データが入っています。
usersテーブルの dept_id カラムが外部キーで、departmentsテーブルの id カラムに対応しています。例えば dept_id=1 は「営業部」、dept_id=2 は「開発部」、dept_id=3 は「人事部」に対応します。
JOINの結合条件は users.dept_id = departments.id です。この条件が一致する行の組み合わせが結果として出力されます。紫色のハイライトは現在比較中の行を、緑色は既にマッチが見つかった行を示しています。
⚙️Nested Loop Joinの仕組み
1. 二重ループの構造
Nested Loop Joinは名前のとおり、ネスト（入れ子）されたループで構成されます。外側ループが1回進むたびに、内側ループが最初から最後まで全行走査します。
2. 比較の流れ（全15ステップ）
各ステップで外側テーブルの1行と内側テーブルの1行を比較します。外側のポインタが固定されている間に内側のポインタが全行を走査する様子を確認してください。
| # | 外側(users) | 内側(departments) | 比較 | 結果 |
|---|---|---|---|---|
| 1 | 田中(dept_id=1) | 営業部(id=1) | 1==1 | マッチ |
| 2 | 田中(dept_id=1) | 開発部(id=2) | 1!=2 | - |
| 3 | 田中(dept_id=1) | 人事部(id=3) | 1!=3 | - |
| 4 | 鈴木(dept_id=2) | 営業部(id=1) | 2!=1 | - |
| 5 | 鈴木(dept_id=2) | 開発部(id=2) | 2==2 | マッチ |
| 6 | 鈴木(dept_id=2) | 人事部(id=3) | 2!=3 | - |
| 7 | 佐藤(dept_id=1) | 営業部(id=1) | 1==1 | マッチ |
| 8 | 佐藤(dept_id=1) | 開発部(id=2) | 1!=2 | - |
| 9 | 佐藤(dept_id=1) | 人事部(id=3) | 1!=3 | - |
| 10 | 高橋(dept_id=3) | 営業部(id=1) | 3!=1 | - |
| 11 | 高橋(dept_id=3) | 開発部(id=2) | 3!=2 | - |
| 12 | 高橋(dept_id=3) | 人事部(id=3) | 3==3 | マッチ |
| 13 | 伊藤(dept_id=2) | 営業部(id=1) | 2!=1 | - |
| 14 | 伊藤(dept_id=2) | 開発部(id=2) | 2==2 | マッチ |
| 15 | 伊藤(dept_id=2) | 人事部(id=3) | 2!=3 | - |
3. マッチ判定の仕組み
各比較ステップで、外側テーブルの結合カラム（dept_id）と内側テーブルの結合カラム（id）が等しいかを判定します。一致すれば両方の行を結合して結果行として出力します。
📊特徴
🎯ユースケース
📖用語解説
📋Nested Loop Joinの手順
⚖️JOINアルゴリズム比較
| Nested Loop Join | Block NLJ | Index NLJ | Hash Join | Sort-Merge Join | |
|---|---|---|---|---|---|
| 計算量 | O(N×M) | O(N×M/B) | O(N×logM) | O(N+M) | O(NlogN+MlogM) |
| メモリ | 最小 | 中（バッファ） | 最小 | 大（ハッシュ表） | 大（ソート領域） |
| インデックス | 不要 | 不要 | 必須（内側） | 不要 | 不要（あると有利） |
| 結合条件 | 任意 | 任意 | 等価/範囲 | 等価のみ | 等価/範囲 |
| 小規模テーブル | 最適 | 良好 | 最適 | 構築コスト大 | ソートコスト大 |
| 大規模テーブル | 非効率 | 改善 | インデックス次第 | 最適 | 良好 |
| ソート済み出力 | なし | なし | なし | なし | あり |
Block Nested Loop Join（Block NLJ）は、外側テーブルの行を1行ずつではなくブロック単位でバッファに読み込み、内側テーブルの各行をバッファ内の全行と一度に比較するバリエーションです。ディスクI/Oの回数を大幅に削減できるため、通常のNLJよりも効率的です。MySQLでは join_buffer_size パラメータでバッファサイズを調整できます。
Index Nested Loop Join（Index NLJ）は、内側テーブルの結合カラムにインデックスがある場合に使われます。内側テーブルの全行走査がインデックスルックアップに置き換わるため、計算量がO(N × log M)に改善されます。実際のデータベースでは最もよく使われるNLJの形態です。
Hash JoinとSort-Merge Joinは大規模テーブルのJOINに適したアルゴリズムです。Hash Joinは内側テーブルのハッシュテーブルを構築してO(1)ルックアップを実現し、Sort-Merge Joinは両テーブルをソートしてマージすることで効率的に結合します。
