MySQL Nested-Loop Join 與 Block Nested-Loop Join 算法深度解析：驅動表選擇、Join Buffer 優化

MySQL Nested-Loop Join 算法家族深度解析

一、基礎 Nested-Loop Join (NLJ) 偽代碼

FOR each row in t1 matching range:
  FOR each row in t2 matching ref_key:
    FOR each row in t3:                    -- 驅動表 (最內層)
      IF row satisfies join conditions:
        SEND to client

• 對應 EXPLAIN 中的 type=range/ref/ALL
• 最內層表 (t3) **全表掃描**，外層每行都需掃描一次內層 → 複雜度 O(N×M)
• MySQL **不支援 Hash Join**，僅有 NLJ 及其變體

二、驅動表選擇原則

MySQL 優化器傾向選擇 **結果集最小的表作為驅動表 (最內層)**，以最小化內層掃描次數。可用 STRAIGHT_JOIN 強制指定連接順序。

三、Block Nested-Loop Join (BNLJ) — 利用 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 matches: SEND to client
      EMPTY buffer

IF buffer_not_empty:
  FOR each row in t3:
    FOR each (t1,t2) combo IN join_buffer:
      IF matches: SEND to client

核心思想

• 將外層 (t1,t2) 所需列**批量緩存**到 join_buffer (內存)
• 內層表 (t3) **一次全掃描**，對比 Buffer 中所有組合
• 掃描次數從 O(N×M) 降為 O(N + M) 級別

官方示例解讀

若 Buffer 緩存 10 行組合，內層每行與這 10 組比較 → 內層掃描 1 次，而非 10 次。

掃描次數公式

t3 掃描次數 ≈ (S × C) / join_buffer_size + 1
S = 每組組合大小, C = 組合數量

• join_buffer_size 越大 → 掃描次數越少
• 當 Buffer 能裝下所有外層組合時，效能最優；再增大無收益

四、實戰優化建議

1. 小表驅動大表：確保驅動表 (最內層) 行數最少
2. 適當增大 join_buffer_size：會話級別 SET join_buffer_size=32M，避免全局過大佔用內存
3. 覆蓋索引：只將 JOIN 所需列放入 Buffer，減少 S
4. 避免不必要的列：SELECT * 會把所有列塞入 Buffer，劇增 S
5. 觀察 EXPLAIN：Extra=Using join buffer (Block Nested Loop) 確認 BNLJ 生效

五、總結

MySQL 僅支援 Nested-Loop 系連接算法。理解 **NLJ → BNLJ** 的演進、join_buffer 的作用、驅動表選擇邏輯，是編寫高效連接查詢、調優大表 JOIN 的核心基礎。期待未來版本引入真正的 Hash Join / Merge Join。