SQL Server 查詢最佳化器三大 JOIN 演算法原理與選擇策略

查詢最佳化器支援三種基礎 JOIN 演算法：Nested Loop、Sort-Merge、Hash Join。理解其原理與代價模型，才能正確解讀執行計畫並進行調優。

假設環境

• 兩張表 R (M 頁) 與 S (N 頁)
• 元組分別為 r, s；JOIN 欄位為 i, j

1. Nested Loop Join (巢狀迴圈聯結)

演算法

foreach r in R:
  foreach s in S:
    if r.i == s.j: add to result

I/O 代價

M + M × N（外層掃描 M 頁 + 內層重複掃描 N 頁 M 次）

適用場景

• 一大一小：小表做外層
• 內層大表但 JOIN 欄位有索引
• 僅一表有索引：有索引者做內層
• 一對一唯一 JOIN：找到匹配可跳過剩餘內層

2. Sort-Merge Join (排序合併聯結)

演算法

1. 依 JOIN 欄位排序兩表
2. 雙指標合併掃描，比較並輸出匹配（需處理重複值分區）

I/O 代價

• 最佳（已排序且至少一無重複）：O(M + N) — 單掃描
• 最差（未排序且全重複）：O(M log M + N log N + M×N) — 雙排序 + 笛卡兒積

適用場景

• 兩大表關聯
• JOIN 欄位有叢集索引（已排序）
• PK-FK 關聯：天然具備排序與單邊唯一，效能最佳
• 查詢本身含 GROUP BY/ORDER BY 可重用排序結果

3. Hash Join (雜湊聯結)

限制

僅支援 等值聯結（雜湊函數決定性）

演算法

1. Build 階段： 小表 S 依 JOIN 欄位建立記憶體雜湊表，同鍵值串成桶
2. Probe 階段： 掃描大表 R，雜湊定位桶，逐一比對輸出

CPU 代價

O(M + N × b)，b 為平均桶大小

適用場景

• 兩大表、無合適索引
• 等值聯結：INNER/LEFT/RIGHT/FULL OUTER JOIN、INTERSECT、EXCEPT
• 變種可用於 DISTINCT、GROUP BY（單輸入兼 Build/Probe）

最佳化器選擇優先序

1. 優先考慮 Nested Loop、Sort-Merge
2. 兩表皆大且無索引 → Hash Join

實務提醒

• 產品級最佳化器使用改良版（Block/Index Nested Loop、Hash Team 等）
• 統計資料準確度決定選擇品質
• 查看執行計畫時，關注 Join Type、Estimated Rows、Index Seek vs Scan

掌握三大演算法特性，配合索引設計與統計維護，即能引導最佳化器產出高效執行計畫。