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

前言

MySQL 5.7 僅支援 Nested-Loop Join（NLJ），不支援 Hash Join。理解 NLJ 及其變體對 SQL 優化至關重要。本文解析 Simple NLJ、Block NLJ、Index NLJ 三種演算法原理、偽代碼與優化策略。

一、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 row 滿足 JOIN 條件:
        SEND TO client

對應 EXPLAIN 的 type：range、ref、ALL。最內層 t3 全表掃描，效能極差。

驅動表概念

• 外層循環表 = 驅動表
• MySQL 優化器傾向選擇結果集最小的表作為驅動表
• 可用 STRAIGHT_JOIN 強制指定連接順序

二、Block Nested-Loop Join（BNLJ，MySQL 優化版）

偽代碼

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 combination IN join_buffer:
          IF 滿足條件: SEND TO client
      EMPTY buffer

IF buffer NOT EMPTY:
  FOR each row IN t3:
    FOR each t1,t2 combination IN join_buffer:
      IF 滿足條件: SEND TO client

核心改進

• 將外層循環的列緩存到 join_buffer（默認 256KB，可調 join_buffer_size）
• 內層表掃描一次，與緩存中的所有組合比對
• 減少內層表掃描次數：掃描次數 = (S × C) / join_buffer_size + 1
• 當緩存能裝下所有外層組合時，內層表僅掃描一次，接近 Hash Join 效果

優化建議

• 增大 join_buffer_size（如 4MB~8MB），但避免 OOM
• 只選擇必要列（SELECT a,b 而非 SELECT *），減少緩存佔用
• 為 JOIN 條件列建立索引，盡量走 ref 而非 ALL

三、Index Nested-Loop Join（INLJ，有索引時）

當 JOIN 條件列有索引，MySQL 會嘗試使用索引查找而非全表掃描，效能大幅提升。若無索引，絕不會 退回到 Simple NLJ（太慢），而是強制使用 BNLJ。

四、實戰優化清單

五、總結

• MySQL 5.7 僅有 NLJ 變體，理解 BNLJ 緩存機制是優化關鍵
• EXPLAIN 中 type=ALL 且 Extra=Using join buffer 表示 BNLJ
• 長期規劃：升級 MySQL 8.0+ 獲得 Hash Join、更智能的優化器