查詢最佳化器根據統計資料、索引、資料量選擇聯結演算法。理解三大演算法 I/O 與 CPU 成本模型，能指導索引設計與查詢改寫。
1. Nested Loops Join (巢狀迴圈聯結)
演算法
FOR each row r IN OuterTable
FOR each row s IN InnerTable
IF r.JoinKey = s.JoinKey THEN OUTPUT
I/O 成本 (Page-at-a-time)
Cost = M + M × N
M：外部表頁數 (Outer)。N：內部表頁數 (Inner)。- 讀取外部表 1 次 (M) + 對外部表每列掃描內部表 (M × N)。
適用場景
- 外部極小 (如 < 100 列)、內部有索引求。
- OLTP 單筆/小批量查詢。
2. Merge Join (合併聯結)
演算法
- 雙方依聯結鍵排序 (若已有序則省略)。
- 雙指標合併掃描，類似合併排序。
成本決定因素
- 聯結鍵是否已排序 (叢集索引/排序過)。
- 重複值多寡 (重複值多需「分區」處理，成本上升)。
成本範圍
- 最佳 (雙方已序、至少一方無重複)：**O(M + N)**，單次掃描。
- 最差 (雙方未序、全重複)：**O(M log M + N log N + M × N)**，雙重排序 + 笛卡兒積。
適用場景
- 大型資料集、雙方聯結鍵有叢集索引、範圍查詢、排序輸出。
3. Hash Join (雜湊聯結)
演算法
- Build 階段：掃描較小輸入 (Build Input)，依聯結鍵雜湊分桶，同鍵值串成鏈表。
- Probe 階段：掃描較大輸入 (Probe Input)，雜湊定位桶，逐一比對。
限制
僅支援等值聯結 (Equi-Join)，因雜湊函數無序性不支援範圍/不等式。
成本
- CPU：**O(M + N × b)**，
b 為平均桶長度。
- I/O：若雜湊表超過記憶體會溢寫至
tempdb，產生額外 I/O。
適用場景
- 大型資料集、無合適索引、等值聯結、平行查詢 (Parallelism)。
- 低併發環境 (佔用大量記憶體)。
三大演算法選擇總結
| 演算法 | 適用資料量 | 索引需求 | 記憶體壓力 | 並列度 |
|---|
| Nested Loops | 小外部 + 索引內部 | 內部需索引求 | 低 | 低 |
| Merge Join | 大型、已排序 | 雙方叢集索引最佳 | 中 | 中 |
Hash Join
大型、無索引/等值 |
不需索引 |
高 (溢寫 tempdb) |
高 (支援平行) |
優化導向原則
- 避免大資料量 Hash Join：高併發下記憶體/IO 壓力大，嘗試改寫為 Merge Join 或 Nested Loops。
- 手段：建立叢集/覆蓋索引 → 強制排序 → 引導最佳化器選擇 Merge Join；或縮小外部輸入 (過濾/分頁) → 引導 Nested Loops。
- 查詢提示：
OPTION (LOOP JOIN / MERGE JOIN / HASH JOIN) 僅作測試，生產環境優先透過索引/統計資料引導。
- 業務設計：將大表聯結下推至資料倉儲/預先彙總表，避免線上交易系統執行重聯結。
深入理解聯結演算法成本模型，是 SQL 調優從「試錯」進化為「科學推演」的關鍵。
