MySQL Nested-Loop Join 算法深度解析：從 Simple 到 Block 再到 Index

為什麼 MySQL 只支援 Nested-Loop Join？

MySQL 5.7 仍不支援 Hash Join，唯一的連接算法是 Nested-Loop Join（NLJ）及其變體。雖然 Oracle 12c 早已實現 Hash Join、Sort-Merge Join，但理解 NLJ 的演進邏輯，對於寫出高效 JOIN SQL、調優執行計劃至關重要。

1. Simple Nested-Loop Join：最朴素的雙重循環

for each row in t1 matching range {
  for each row in t2 matching ref_key {
    for each row in t3 {          -- 全表掃描
      if join_condition send to client
    }
  }
}

對應 EXPLAIN type：range → ref → ALL。
驅動表（最外層）通常是結果集最小的表，MySQL 優化器會自動選擇。若驅動表為大表（type=ALL），內層表每行都要掃描一次外層結果，複雜度 O(M×N)，資料量大時極其緩慢。

2. Block Nested-Loop Join (BNL)：Join Buffer 的引入

MySQL 為減少內表掃描次數，引入 join_buffer：

for each row in t1 matching range {
  for each row in t2 matching ref_key {
    store used columns from t1,t2 in join_buffer
    if buffer_full {
      for each row in t3 {
        for each t1,t2 combo in join_buffer {
          if join_condition send to client
        }
      }
      empty buffer
    }
  }
}
-- 處理剩餘 buffer
if buffer_not_empty {
  for each row in t3 {
    for each t1,t2 combo in join_buffer { ... }
  }
}

核心邏輯：將外層循環的所需欄位批次緩存至 join_buffer，內層表每行與 buffer 中所有組合比對，將內表掃描次數從「外層行數」降為 ceil(外層資料量 / join_buffer_size) 次。

掃描次數公式：

(S × C) / join_buffer_size + 1

• S：t1,t2 組合在 buffer 中的大小
• C：組合數量
• 當 join_buffer_size ≥ 所有外層組合大小時，內表僅掃描一次，逼近 Hash Join 效果

3. Index Nested-Loop Join：有索引時的優先選擇

當 JOIN 條件欄位有索引，MySQL 傾向使用 Index NLJ（對應 EXPLAIN ref/eq_ref），直接透過索引查找匹配行，避免全表掃描。此時 join_buffer 不生效。

4. 無索引場景的現實：為什麼不直接用 Simple NLJ？

若 JOIN 欄位無索引，Simple NLJ 會導致內表重複全掃描，資料量稍大查詢可能跑「幾年」出不來結果。MySQL 會強制使用 Block NLJ（有 join_buffer 時）或提示建立索引。結論：大表 JOIN 必須有索引支援，否則依賴 BNL 也是杯水車薪。

5. 實戰優化啟示

• 驅動表選擇：用 STRAIGHT_JOIN 強制指定小結果集為驅動表（左表）
• 縮小驅動表結果集：WHERE 條件下推、分區裁剪、索引覆蓋
• 調大 join_buffer_size：Session 級參數，大表 JOIN 時可臨時調大（如 32M~256M），但勿全域設大導致 OOM
• 避免 SELECT *：只取 JOIN 需要的欄位，減少 buffer 佔用，提高緩存命中率
• 升級 8.0+：MySQL 8.0.18+ 引入 Hash Join，徹底改寫無索引大表 JOIN 痛點

總結對比表

理解 NLJ 演進，本質是理解「如何減少內表存取」。下一代 MySQL 已引入 Hash Join，但 NLJ 仍是基石，索引設計與驅動表選擇永遠是第一生產力。