本文作者先對SQL Server三大算法的IO成本進行分析，然後提出優化原則。希望可以給讀者帶來幫助。
1. Nested Loop Join(嵌套循環聯結)
算法：
其思路相當的簡單和直接：對於關系R的每個元組 r 將其與關系S的每個元組 s 在JOIN條件的字段上直接比較並篩選出符合條件的元組。寫成偽代碼就是：
代價：
被聯結的表所處內層或外層的順序對磁盤I/O開銷有著非常重要的影響。而CPU開銷相對來說影響較小，主要是元組讀入內存以後(in-memory)的開銷，是 O (n * m)
對於I/O開銷，根據 page-at-a-time 的前提條件，I/O cost = M + M * N，
翻譯一下就是 I/O的開銷 = 讀取M頁的I/O開銷 + M次讀取N頁的I/O開銷。
2. Sort-Merge Join (排序合並聯結)
Nested Loop一般在兩個集合都很大的情況下效率就相當差了，而Sort-Merge在這種情況下就比它要高效不少，尤其是當兩個集合的JOIN字段上都有聚集索引(clustered index)存在時，Sort-Merge性能將達到最好。
算法：
基本思路也很簡單(復習一下數據結構中的合並排序吧)，主要有兩個步驟：
a.按JOIN字段進行排序
b.對兩組已排序集合進行合並排序，從來源端各自取得數據列後加以比較(需要根據是否在JOIN字段有重復值做特殊的“分區”處理)
代價：(主要是I/O開銷)
有兩個因素左右Sort-Merge的開銷：JOIN字段是否已排序 以及 JOIN字段上的重復值有多少。
◆最好情況下(兩列都已排序且至少有一列沒有重復值)：O (n + m) 只需要對兩個集合各掃描一遍。（這裡的m，n如果都能用到索引那就更好了）
◆最差情況下(兩列都未排序且兩列上的所有值都相同)：O (n * log n + m * log m + n * m) 兩次排序以及一次全部元組間的笛卡爾乘積
