淺談查詢優化器三大 JOIN 演算法：Nested Loop / Sort-Merge / Hash Join

假設表 R (M 頁)、S (N 頁)。

1. Nested Loop Join (NLJ)

foreach r in R:
  foreach s in S:
    if r.i == s.j: output

I/O 成本 = M + M×N。適用場景：
• 外層小、內層大且有索引 → 索引 NLJ 極快。
• 一對一唯一聯結 → 找到即可跳過內層剩餘。

2. Sort-Merge Join (SMJ)

1. 雙邊按 JOIN 鍵排序（若已有叢集索引則免排）。
2. 歸併掃描，處理重複值分區。

成本取決於是否預排序與重複值多寡：
• 最佳 (已排序、無重複)：O(M+N)。
• 最差 (未排序、全重複)：O(M log M + N log N + M×N)。

3. Hash Join

建構雜湊表 (通常取較小輸入) → 掃描另一輸入探測。適合大表無索引、無序場景。SQL Server 另支援 Grace Hash、Recursive Hash 處理記憶體不足溢寫。

優化器選擇邏輯

依據統計資訊估算行數、是否有索引/排序、記憶體授予大小動態決定。理解三大演算法特性，有助於解讀執行計畫、指導索引/統計維護。