SQL Server 查詢優化器核心 JOIN 算法深度解析

在關係型資料庫中，JOIN 操作是多表查詢的基石。SQL Server 的查詢優化器支援三大核心 JOIN 算法：Nested Loop（嵌套循環）、Sort-Merge（排序合併） 與 Hash Join（哈希聯結）。雖然原理不複雜，但在產品級實現中，優化器往往採用改進的變種（如 Block Nested Loops、Index Nested Loops、Hash Team 等）以榨乾效能。本文將以兩張表 R（M 頁）和 S（N 頁）為模型，深入剖析這三大算法的原型、成本模型與適用場景。

1. Nested Loop Join（嵌套循環聯結）

算法邏輯

思路直觀：以外層表驅動內層表，逐行比對 JOIN 條件。偽碼如下：

foreach tuple r in R do
    foreach tuple s in S do
        if r.i == s.j then add to result

成本分析

• I/O 成本：假設 page-at-a-time，外層表掃描一次（M），內層表掃描 M 次（M × N），總計 M + M×N。
• CPU 成本：記憶體內比較，複雜度 O(n × m)，通常非瓶頸。

關鍵點：外/內層順序對 I/O 影響劇烈。小表做外層、大表有索引做內層效能最佳。

適用場景

• 一大一小：小表作外層，I/O 效能優異。
• 外層極小、內層極大且 JOIN 欄位有索引：索引查找替換全掃描。
• 僅一側有索引：有索引的一方必須置為內層。
• 一對一唯一匹配：找到匹配即可跳過該內層剩餘迭代（類似 continue）。

2. Sort-Merge Join（排序合併聯結）

算法邏輯

1. 排序階段：分別按 JOIN 鍵對兩輸入集排序（若已有聚集索引可省略）。
2. 合併階段：雙指針同步掃描，比對鍵值；遇重複值需做特殊「分區」處理。

成本模型

取決於兩因素：是否預排序 以及 重複值比例。

• 最佳：雙方已排序且至少一方無重複值 → O(n + m)，單掃描即可。
• 最差：雙方未排序且全為重複值 → O(n log n + m log m + n×m)，需兩次排序 + 笛卡爾積。

實戰建議

• 雙大表且具聚集索引（預排序）時首選，效能三者之冠。
• 主鍵-外鍵關聯典型適用：聚集索引保證有序，一對多保證單邊無重複。
• 查詢本身含 GROUP BY/ORDER BY/CUBE 等排序操作時，可重用排序結果，Merge Join 更具優勢。

3. Hash Join（哈希聯結）

核心限制

僅支援等值聯結。哈希函數的確定性與無序性導致無法處理範圍、不等式等非等值條件。

算法兩階段

1. Build Input Phase：以較小表 S 為輸入，依 JOIN 鍵經哈希函數 h2 建立記憶體哈希表，同鍵值以鏈表形成桶。
2. Probe Input Phase：掃描較大表 R，對每行 r 計算哈希定位桶，若桶非空則逐行比對 r.i == s.j 輸出結果。

成本特徵

• CPU：O(m + n × b)，b 為桶平均行數。大表每行需遍歷對應桶內所有行，為主要耗時點。
• 記憶體壓力大：哈希表須駐留記憶體，不足時溢寫至 tempdb 導致效能暴跌。

優化器決策邏輯

優化器優先考慮 Nested Loop 與 Sort-Merge；僅當雙表皆大且缺乏合適索引 時才退而求其次選擇 Hash Join。

• 廣泛用於 INNER/OUTER JOIN、INTERSECT、EXCEPT 等集合運算（皆須等值）。
• 變種可用於去重、分組（單輸入同時扮演 Build/Probe 角色）。

總結與實踐指引

產品級優化器對三大算法均有深度改進（如 Batch Mode、Adaptive Join 等），實際執行計畫往往呈現混合形態。分析計畫時，關注 Join Type、Estimated Rows、Memory Grant 及 Spill Warnings，結合統計資料準確度，方能精準判斷優劣、導向最優調優路徑。