淺析SQL Server三大算法的I/O成本
1. Nested Loop Join(嵌套循環(huán)聯(lián)結(jié))
算法：
其思路相當(dāng)?shù)暮?jiǎn)單和直接：對(duì)于關(guān)系R的每個(gè)元組 r 將其與關(guān)系S的每個(gè)元組 s 在JOIN條件的字段上直接比較并篩選出符合條件的元組。寫(xiě)成偽代碼就是：
代價(jià)：
被聯(lián)結(jié)的表所處內(nèi)層或外層的順序?qū)Υ疟P(pán)I/O開(kāi)銷(xiāo)有著非常重要的影響。而CPU開(kāi)銷(xiāo)相對(duì)來(lái)說(shuō)影響較小，主要是元組讀入內(nèi)存以后(in-memory)的開(kāi)銷(xiāo)，是 O (n * m)
對(duì)于I/O開(kāi)銷(xiāo)，根據(jù) page-at-a-time 的前提條件，I/O cost = M + M * N，
翻譯一下就是 I/O的開(kāi)銷(xiāo) = 讀取M頁(yè)的I/O開(kāi)銷(xiāo) + M次讀取N頁(yè)的I/O開(kāi)銷(xiāo)。
2. Sort-Merge Join (排序合并聯(lián)結(jié))
Nested Loop一般在兩個(gè)集合都很大的情況下效率就相當(dāng)差了，而Sort-Merge在這種情況下就比它要高效不少，尤其是當(dāng)兩個(gè)集合的JOIN字段上都有聚集索引(clustered index)存在時(shí)，Sort-Merge性能將達(dá)到最好。
算法：
基本思路也很簡(jiǎn)單(復(fù)習(xí)一下數(shù)據(jù)結(jié)構(gòu)中的合并排序吧)，主要有兩個(gè)步驟：
a.按JOIN字段進(jìn)行排序
b.對(duì)兩組已排序集合進(jìn)行合并排序，從來(lái)源端各自取得數(shù)據(jù)列后加以比較(需要根據(jù)是否在JOIN字段有重復(fù)值做特殊的“分區(qū)”處理)
代價(jià)：(主要是I/O開(kāi)銷(xiāo))
有兩個(gè)因素左右Sort-Merge的開(kāi)銷(xiāo)：JOIN字段是否已排序 以及 JOIN字段上的重復(fù)值有多少。
◆最好情況下(兩列都已排序且至少有一列沒(méi)有重復(fù)值)：O (n + m) 只需要對(duì)兩個(gè)集合各掃描一遍。（這里的m，n如果都能用到索引那就更好了）
◆最差情況下(兩列都未排序且兩列上的所有值都相同)：O (n * log n + m * log m + n * m) 兩次排序以及一次全部元組間的笛卡爾乘積
3. Hash Join (哈希聯(lián)結(jié))
Hash Join在本質(zhì)上類似于兩列都有重復(fù)值時(shí)的Sort-Merge的處理思想——分區(qū)(patitioning)。但它們也有區(qū)別：Hash Join通過(guò)哈希來(lái)分區(qū)(每一個(gè)桶就是一個(gè)分區(qū))而Sort-Merge通過(guò)排序來(lái)分區(qū)(每一個(gè)重復(fù)值就是一個(gè)分區(qū))。
值得注意的是，Hash Join與上述兩種算法之間的較大區(qū)別同時(shí)也是一個(gè)較大限制是它只能應(yīng)用于等值聯(lián)結(jié)(equality join)，這主要是由于哈希函數(shù)及其桶的確定性及無(wú)序性所導(dǎo)致的。
算法：
基本的Hash Join算法由以下兩步組成：
同nested loop，在執(zhí)行計(jì)劃中build input位于上方，probe input位于下方。
hash join操作分兩個(gè)階段完成：build（構(gòu)造）階段和probe（探測(cè)）階段。
a.Build Input Phase： 基于JOIN字段，使用哈希函數(shù)h2為較小的S集合構(gòu)建內(nèi)存中(in-memory)的哈希表，相同鍵值的以linked list組成一個(gè)桶(bucket)
b.Probe Input Phase： 在較大的R集合上對(duì)哈希表進(jìn)行核對(duì)以完成聯(lián)結(jié)。
代價(jià)：
值得注意的是對(duì)于大集合R的每個(gè)元組 r ，hash bucket中對(duì)應(yīng) r 的那個(gè)bucket中的每個(gè)元組都需要與 r 進(jìn)行比較，這也是算法最耗時(shí)的地方所在。
CPU開(kāi)銷(xiāo)是O (m + n * b) b是每個(gè)bucket的平均元組數(shù)量。
總結(jié)：
三種join方法，都是擁有兩個(gè)輸入，優(yōu)化的基本原則：
1.避免大數(shù)據(jù)的hash join，（hash join適合低并發(fā)情況，他占用內(nèi)存和io是很大的）；
2.盡量將其轉(zhuǎn)化為高效的merge join、nested loop join。可能使用的手段有表結(jié)構(gòu)設(shè)計(jì)、索引調(diào)整設(shè)計(jì)、SQL優(yōu)化，以及業(yè)務(wù)設(shè)計(jì)優(yōu)化。
【編輯推薦】
