三大聯結演算法與 I/O 成本模型
假設外部輸入關係 R (M 頁)、內部關係 S (N 頁)，每頁可容納多筆資料。CPU 成本相對較小，重點在 **磁碟 I/O (頁面讀取次數)**。
1. Nested Loop Join (巢狀迴圈聯結)
邏輯：對 R 每列，掃描 S 全表 (或索引 Seek) 尋找匹配。
偽代碼：
for each r in R:
for each s in S:
if r.key == s.key: output(r,s)
I/O 成本 (Page-at-a-time 假設)：
`Cost = M + M × N` (最壞：無索引、全表掃描 S)
- 讀取 R：M 次 I/O
- 對 R 每列，讀取 S：M × N 次 I/O
優化關鍵：
- **小表做外層 (驅動表)**：M 越小越好。
- **內層有索引**：`Cost ≈ M + M × (Index Depth + Matching Pages)`，大幅降低。
- **適用場景**：外層極小 (< 100 列)、內層有高選擇性索引、或記憶體足夠容納內層 (緩存命中)。
2. Sort-Merge Join (排序合併聯結)
邏輯：兩輸入分別按聯結鍵排序 → 雙指標合併掃描 (類似合併排序合併步驟)。
步驟：
- Sort R on Join Key
- Sort S on Join Key
- Merge Scan：同步游標比對，輸出匹配列 (處理重複值需「分區」邏輯)
I/O 成本：
- **最佳**：兩輸入**已排序** (叢集索引/覆蓋索引順序滿足) 且**至少一方無重複值** → `Cost = M + N` (單次掃描)。
- **最差**：兩輸入**未排序** 且**全為重複值** → `Cost = M log M + N log N + M × N` (兩次外部排序 + 笛卡兒積)。
適用場景：大表聯大表、聯結鍵有叢集索引、或已預排序 (如 `ORDER BY` 相同)。
3. Hash Join (雜湊聯結) — 現代 OLAP 主流
邏輯**：
- Build Phase：掃描較小輸入 (Build Input)，在記憶體建立雜湊表 (Bucket → 鏈表)。
- Probe Phase：掃描較大輸入 (Probe Input)，計算雜湊值探測雜湊表，輸出匹配。
- 若記憶體不足，**Grace Hash Join**：將 Build/Probe 依雜湊值分割寫入 TempDB (Partition)，再遞迴處理各分區。
I/O 成本**：
- **記憶體足夠**：`Cost = M + N` (各掃描一次，零 TempDB I/O)。
- **記憶體不足 (Grace)**：`Cost = 2×(M+N) + 2×(M+N) + ...` (多輪分割/讀寫 TempDB)。
適用場景**：大表聯大表、無合適索引、並行查詢、資料倉庫/OLAP 負載。
成本比較總結表
| 演算法 | 最佳 I/O | 最差 I/O | 記憶體敏感度 | 平行化 | 典型適用 |
|---|
| Nested Loop | M + M×IndexSeek | M + M×N | 低 | 差 (單執行緒) | 小表驅動大表、索引 Seek |
| Sort-Merge | M + N (已排序) | M log M + N log N + M×N | 中 (排序需記憶體) | 好 (並行排序) | 大表聯大表、已排序輸入 |
| Hash Join | M + N (記憶體足) | 多輪 TempDB 讀寫 | 高 (需足夠記憶體避免分割) | 極好 (並行 Build/Probe) | 大表聯大表、無索引、OLAP |
優化器選擇邏輯與干預
- **統計資料準確** 是前提：`UPDATE STATISTICS WITH FULLSCAN`。
- **強制指定**：`OPTION (LOOP JOIN | MERGE JOIN | HASH JOIN)` — 僅限測試/極特殊情況。
- **記憶體授予**：`MAX_GRANT_PERCENT`、`MIN_GRANT_PERCENT` (SQL 2012+)、Resource Governor 控制 Hash/Sort 記憶體。
- **避免隱式轉換、函數包裹聯結鍵** → 導致統計失效、優化器誤判基數 → 選錯演算法。
結語
理解三大聯結演算法的 I/O 成本曲線，能讓你從「看執行計畫」進階到「預測與干預優化器」。核心永遠是：**準確統計 + 合適索引 + 足夠記憶體 = Hash Join 稱霸大表聯結；小表驅動 + 索引 Seek = Nested Loop 稱霸 OLTP。**
