1. Nested Loops Join (NLJ) - 嵌套循環
演算法
FOR each row r in Outer (R)
FOR each row s in Inner (S)
IF r.JoinKey = s.JoinKey OUTPUT (r,s);
I/O 成本 (Page-at-a-time 假設)
Cost = M + M × N
M = 外部輸入頁數 (Outer);
N = 內部輸入頁數 (Inner);
- 含義:掃描 1 次外部 (M) + 對每一外部頁掃描 1 次內部 (M×N)。
適用場景
- 外部極小 (經過高選擇性篩選);
- 內部有高選擇性索引 Seek;
- 並發高、記憶體受限環境 (無需大量記憶體授予)。
2. Merge Join (SMJ) - 排序合併
演算法
- 兩輸入分別按 Join Key 排序 (若已有序/聚集索引則省略);
- 雙指標合併:同時讀取兩有序流,比較 Key,輸出匹配,推進指標。
I/O 成本
| 場景 | 成本 | 條件 |
| 最佳 | O(M + N) | 兩輸入已有序 (聚集索引/預排序),且至少一邊 Key 唯一 |
| 一般 | O(M log M + N log N + M + N) | 需額外排序 |
| 最差 | O(M log M + N log N + M × N) | 兩邊全重複值 → 笛卡爾積處理 |
關鍵點
- 需至少一個等值條件;
- 大量重複值會觸發「多對多」合併,產生工作表 (tempdb) 儲存重複組,I/O 暴增;
- 適合大表關聯、已排序輸入、報表/批次查詢。
3. Hash Join (HJ) - 雜湊聯結
演算法 (兩階段)
- Build:掃描較小輸入 (Build Input),按 Join Key 雜湊分桶 (Bucket) 存入記憶體雜湊表 (鍵值相同 → Linked List);
- Probe:掃描較大輸入 (Probe Input),對每行計算雜湊,定位桶,逐行比對輸出。
成本
- CPU:
O(M + N × b),b = 平均桶大小 (重複值越多 b 越大);
- I/O: 理想情況全記憶體,若 Build Input 超記憶體授予 → 溢寫到 tempdb (分區遞迴),I/O 暴增;
- 僅支援等值聯結 (=),不支援不等式/範圍聯結。
適用場景
- 大表關聯、無索引/無序、等值 JOIN;
- 低並發、記憶體充足 (避免溢寫);
- 並行查詢 (Parallel Hash Join) 可線性擴展。
優化器選擇邏輯與人工干預
| 條件 | 傾向算法 |
| 小外部 + 內部有索引 Seek | NLJ |
| 大表關聯、雙邊已排序/聚集索引 | Merge Join |
| 大表關聯、無序、等值、記憶體足 | Hash Join |
人工干預手段:
- 索引設計 (建立覆蓋索引/聚集索引引導 Merge);
OPTION (LOOP JOIN / MERGE JOIN / HASH JOIN) 強制提示 (慎用);
- 查詢重寫 (分解大 JOIN、預先篩選縮小外部輸入);
- 統計資料更新 (
UPDATE STATISTICS / sp_updatestats) 讓優化器估算準確。
總結:三大原則
- 避免大數據 Hash Join (佔記憶體、易溢寫 tempdb、高並發災難);
- 引導轉向 Merge Join / NLJ (索引、排序、篩選下推);
- 綜合運用表結構設計、索引調整、SQL 改寫、業務邏輯優化。