1、Hash join 的兩個(gè)階段

第一階段是build揽碘，數(shù)據(jù)庫(kù)會(huì)讀取一個(gè)表的所有記錄生成一個(gè)保存在內(nèi)存中的hash表（對(duì)其中每個(gè)元組上的連接屬性（join attribute)采用哈希函數(shù)得到哈希值，從而建立一個(gè)哈希表）。這個(gè)階段往往會(huì)選擇較小的表生成hash表乌逐，因?yàn)閔ash表太大的話會(huì)占大量?jī)?nèi)存，而且也會(huì)消耗較多的cpu資源支子。build階段選擇的表也稱為left input或者build input。另外达舒，hash表的key就是兩個(gè)表join的equijoin字段值朋。

第二階段是probe，數(shù)據(jù)庫(kù)會(huì)逐一迭代另一個(gè)表的所有記錄來查詢hash表（即對(duì)另一個(gè)表巩搏，掃描它的每一行并計(jì)算連接屬性的哈希值昨登，與bulid phase建立的哈希表對(duì)比，若有落在同一個(gè)bucket的贯底，如果滿足連接謂詞（predicate)則連接成新的表）篙骡，從而生成join結(jié)果。probe階段選擇的表也稱為right input或者probe input。

NOTE：在build階段糯俗，hash join不會(huì)輸出任何結(jié)果；從probe階段開始睦擂，hash join才會(huì)輸出結(jié)果得湘。

2、Hash join 的內(nèi)存分配
如前文所說顿仇，build階段的hash表非常消耗內(nèi)存淘正。所以數(shù)據(jù)庫(kù)會(huì)從做join操作的兩個(gè)表中選擇較小的那個(gè)表來生成hash表，并且根據(jù)這個(gè)表的大小來預(yù)估并分配所需的內(nèi)存臼闻。但是鸿吆，如果內(nèi)存不夠會(huì)怎樣？這種情況下述呐，hash表會(huì)有一小部分保存在磁盤上惩淳，其他部分仍然保存在內(nèi)存中。當(dāng)我們從build input中讀取一條新的記錄的時(shí)候乓搬，如果hash表在內(nèi)存中思犁，那么我們就把記錄寫進(jìn)內(nèi)存；如果hash表在磁盤上进肯，那么我們就把記錄寫進(jìn)磁盤激蹲。類似地，probe階段如果內(nèi)存不夠江掩，也會(huì)把部分記錄寫進(jìn)磁盤学辱。

2、Hash join 的 Join Tree 類型
hash join tree的形狀會(huì)影響內(nèi)存的使用环形。如下圖所示策泣，hashjoin tree分為L(zhǎng)eft deep， right deep和 bushy hash斟赚。我們應(yīng)該根據(jù)表的size和join的結(jié)果來決定使用哪種tree着降，不過大多數(shù)情況下，我們可以直接使用sqlserver的優(yōu)化結(jié)果拗军。下文舉例一一介紹三種tree任洞。

hash join tree type

select *
from (T1 join T2 on T1.a = T2.a)
join T3 on T1.b = T3.a

數(shù)據(jù)庫(kù)選擇了left deep tree: 我們先join T1 和 T2盅弛，并且因?yàn)門1比較小，所以選擇T1生成hash表。又因?yàn)楸敬蝚oin只生成了34條記錄遠(yuǎn)遠(yuǎn)小于T3挪鹏，所以基于本次join的輸出生成了下一次join的hash表见秽。我覺得，當(dāng)中間join的結(jié)果集較小的時(shí)候我們可以考慮用left deep讨盒。

2）right deep hash join
而對(duì)于right deep解取，前一個(gè)join的probe output會(huì)成為下一個(gè)join的probe input，這樣會(huì)導(dǎo)致所有的pair同時(shí)占用內(nèi)存計(jì)算hash表返顺，所以對(duì)于上圖的right deep禀苦，峰值內(nèi)存是max(HJ1 + HJ2 + HJ3)。

select *
from (T1 join T2 on T1.a = T2.a)
join T3 on T1.b = T3.a
where T1.a < 100

因?yàn)橛衱here T1.a < 100遂鹊，并且T1.a = T2.a振乏，所以有where T2.a < 100。因?yàn)門1和T2在where過濾之后都很小秉扑，所以sqlserver選擇了right deep tree慧邮，這樣兩個(gè)join操作可以基于這兩個(gè)表建立hash表，并且對(duì)較大的T3表做probe邻储。這樣要比基于join的中間結(jié)果生成hash表高效赋咽。我覺得，當(dāng)有一個(gè)大表多個(gè)小表的時(shí)候吨娜，可以考慮用right deep脓匿。

3）bushy hash join
對(duì)于bushy join，實(shí)際上是一顆平衡二叉樹宦赠，它使用的內(nèi)存會(huì)隨著樹的高度逐級(jí)減少陪毡。峰值內(nèi)存顯然是最底一層join的pair個(gè)數(shù)，在上圖中應(yīng)該是max(HJ1 + HJ2)勾扭。

select * 
from (T1 join T3 on T1.a = T3.a) 
join
(T2 join T4 on T2.a = T4.a)
on T1.a = T2.a

使用option(force order)強(qiáng)制生成bushy形狀的tree毡琉。我們可以看到T1和T3，T2和T4分別做join妙色，然后對(duì)兩個(gè)join的結(jié)果再做join桅滋。可能是出于節(jié)省內(nèi)存的目的考慮身辨，sqlserver的優(yōu)化很少會(huì)生成bushy tree丐谋。我個(gè)人也覺得，bushy tree沒什么必要煌珊，因?yàn)閎ushy實(shí)際上可以用left deep或者right deep替代号俐。

參考：
https://www.freesion.com/article/426544799/