數據庫連接算子深度對比：Hash Join vs Nested Loop vs Sort Merge

數據庫連接算子深度對比：Hash Join vs Nested Loop vs Sort Merge

連接是 SQL 執行計劃核心操作。優化器根據表大小、索引、內存、並行度在三種連接算子中選擇。理解其原理、適用場景、調優參數對 SQL 性能調優至關重要。

一、Nested Loop Join (NLJ)

執行邏輯

for each row in outer_table:
    for each row in inner_table:
        if join_condition:
            output row

適用條件

• 驅動表 (Outer) 結果集小 (< 1 萬行)
• 被驅動表 (Inner) 連接列有索引
• 索引選擇性高，單次索引查找返回少量行

優化提示

• USE_NL(t1 t2) 強制 NLJ
• ORDERED 指定連接順序
• 確保 Inner 表連接列有索引，必要時創建覆蓋索引

避坑指南

驅動表大、無索引、或全表掃描 Inner 表時性能劇烈下降，優化器會轉向 Hash Join。

二、Hash Join (HSJ)

執行邏輯

1. Build 階段：掃描小表 (Build 表)，按連接鍵計算 Hash 值構建內存 Hash 表
2. Probe 階段：掃描大表 (Probe 表)，計算 Hash 探測 Hash 表，輸出匹配行

內存管理

• Hash 表完全放入內存：成本 ≈ 兩表全掃描之和
• 內存不足：分區溢寫臨時段 (Temp Tablespace)，多輪 Probe，成本顯著增加
• 關鍵參數：HASH_AREA_SIZE (手動) / PGA_AGGREGATE_TARGET + WORKAREA_SIZE_POLICY=AUTO (9i+ 推薦)

適用場景

• 大表關聯大表 (無索引或索引失效)
• 大表關聯小表 (小表作 Build 端)
• 等值連接 (=)，不支持範圍連接

並行優化

分區級並行：Build/Probe 表按相同鍵分區，多進程並行 Join 再合併，需 PARALLEL 屬性或 Hint。

三、Sort Merge Join (SMJ)

執行邏輯

1. 對兩表分別按連接鍵全表掃描 + 排序
2. 雙指針歸併：同步掃描兩有序結果集，輸出匹配行

成本結構

開銷集中在 全表掃描 + 排序。9i 後 Hash Join 普及，SMJ 大幅減少，除非：

• 輸入已有序 (索引順序掃描 / 前序操作產生有序流)
• 需保持輸出順序 (Hash Join 不保序)
• 非等值連接 (如 >, <, BETWEEN)

算子選擇決策樹

DB2 特殊說明

舊版 DB2 存在錯誤選擇 SMJ 的 Bug，可通過 DB2_REDUCED_OPTIMIZATION=CAP OFF 修正，並應用最新 Fixpack。

實戰調優清單

1. 收集統計信息：ANALYZE TABLE / DBMS_STATS
2. 檢查執行計劃：EXPLAIN PLAN / SET AUTOTRACE
3. 確認連接列數據類型一致 (隱式轉換導致索引失效)
4. 調整 PGA/Workarea 參數保證 Hash Join 內存充足
5. 必要時用 Hint 干預，但優先修正統計信息與索引

掌握三大連接算子特性，結合執行計劃分析，是 SQL 調優從入門到精通的核心技能。