MySQL 核心演算法深度解析：Nested Loop Join 與兩種排序策略

MySQL 的查詢優化器相較於 Oracle、PostgreSQL 等商用資料庫，演算法選擇較為單一。本文深入剖析 MySQL 唯一的 Join 演算法——Nested Loop Join，以及兩種排序演算法的運作機制與調優關鍵參數 max_length_for_sort_data。

一、Nested Loop Join：MySQL 唯一的 Join 策略

MySQL 不支援 Hash Join、Sort Merge Join，所有多表連接均採用 Nested Loop Join（巢狀迴圈連接）。

運作流程

1. 選擇驅動表（通常是小表或過濾後行數少的表）
2. 遍歷驅動表結果集，逐行取出關聯鍵值
3. 以該鍵值為條件，查詢被驅動表（通常走索引）
4. 合併結果，若還有第三張表，重複上述步驟

優化關鍵：

• 確保被驅動表的 Join 欄位有索引
• 驅動表儘量小（透過 WHERE 過濾）
• 使用 EXPLAIN 檢查 type 是否為 ref 或 eq_ref

二、兩種排序演算法詳解

演算法一：雙路排序（舊版預設）

1. 取出滿足條件的排序欄位 + 行指標
2. 在 Sort Buffer 中排序
3. 按排序後的行指標回表讀取其他需求欄位
4. 回傳客戶端

特點：兩次 I/O，排序緩衝區較小，適用於需回傳欄位較大的場景。

演算法二：單路排序（改進版）

1. 一次取出排序欄位 + 所有需求欄位
2. 非排序欄位暫存記憶體區
3. 在 Sort Buffer 排序「排序欄位 + 行指標」
4. 按行指標匹配記憶體區資料，組裝結果集

特點：單次 I/O，但佔用更多 Sort Buffer，適用於需回傳欄位總長度較小的場景。

三、關鍵參數：max_length_for_sort_data

MySQL 依據「所有回傳欄位最大長度」是否小於此參數，決定採用哪種演算法：

• 總長度 < 參數值 → 單路排序（快）
• 總長度 ≥ 參數值 → 雙路排序（慢）

調優建議

SET GLOBAL max_length_for_sort_data = 4096;  -- 預設 1024，視記憶體調大

若系統記憶體充足，調大此值可強制使用單路排序，顯著提升 ORDER BY、GROUP BY、DISTINCT 等排序操作效能。

四、實戰驗證

EXPLAIN SELECT * FROM orders WHERE user_id=100 ORDER BY created_at DESC LIMIT 20;

觀察 Extra 欄位：

• Using filesort：觸發排序
• 配合 optimizer_trace 可見具體演算法選擇

五、總結

理解核心演算法，才能對症下藥，寫出高效 SQL。