萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 資料庫 >> MS SQL 資料庫

SQL Server 三大 JOIN 算法 I/O 成本模型深度解析:Nested Loops、Merge Join、Hash Join

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) - 排序合併

演算法

  1. 兩輸入分別按 Join Key 排序 (若已有序/聚集索引則省略);
  2. 雙指標合併:同時讀取兩有序流,比較 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) - 雜湊聯結

演算法 (兩階段)

  1. Build:掃描較小輸入 (Build Input),按 Join Key 雜湊分桶 (Bucket) 存入記憶體雜湊表 (鍵值相同 → Linked List);
  2. Probe:掃描較大輸入 (Probe Input),對每行計算雜湊,定位桶,逐行比對輸出。

成本

  • CPU: O(M + N × b),b = 平均桶大小 (重複值越多 b 越大);
  • I/O: 理想情況全記憶體,若 Build Input 超記憶體授予 → 溢寫到 tempdb (分區遞迴),I/O 暴增;
  • 僅支援等值聯結 (=),不支援不等式/範圍聯結。

適用場景

  • 大表關聯、無索引/無序、等值 JOIN;
  • 低並發、記憶體充足 (避免溢寫);
  • 並行查詢 (Parallel Hash Join) 可線性擴展。

優化器選擇邏輯與人工干預

條件傾向算法
小外部 + 內部有索引 SeekNLJ
大表關聯、雙邊已排序/聚集索引Merge Join
大表關聯、無序、等值、記憶體足Hash Join

人工干預手段:

  • 索引設計 (建立覆蓋索引/聚集索引引導 Merge);
  • OPTION (LOOP JOIN / MERGE JOIN / HASH JOIN) 強制提示 (慎用);
  • 查詢重寫 (分解大 JOIN、預先篩選縮小外部輸入);
  • 統計資料更新 (UPDATE STATISTICS / sp_updatestats) 讓優化器估算準確。

總結:三大原則

  1. 避免大數據 Hash Join (佔記憶體、易溢寫 tempdb、高並發災難);
  2. 引導轉向 Merge Join / NLJ (索引、排序、篩選下推);
  3. 綜合運用表結構設計、索引調整、SQL 改寫、業務邏輯優化。
copyright © 萬盛學電腦網 all rights reserved