圖2.循環(huán)嵌套連接的第二步

    通過嵌套循環(huán)連接也可以看出，隨著數(shù)據(jù)量的增長(zhǎng)這種方式對(duì)性能的消耗將呈現(xiàn)出指數(shù)級(jí)別的增長(zhǎng)，所以數(shù)據(jù)量到一定程度時(shí)，查詢分析器往往就會(huì)采用這種方式。

    下面我們通過例子來看一下循環(huán)嵌套連接,利用微軟的AdventureWorks數(shù)據(jù)庫(kù):

    圖3.一個(gè)簡(jiǎn)單的嵌套循環(huán)連接   

    圖3中ProductID是有索引的，并且在循環(huán)的外部表中（Product表）符合ProductID=870的行有4688條，因此，對(duì)應(yīng)的SalesOrderDetail表需要查找4688次。讓我們?cè)谏厦娴牟樵冎性倏紤]另外一個(gè)例子,如圖4所示。

    圖4.額外的列帶來的額外的書簽查找

    由圖4中可以看出，由于多選擇了一個(gè)UnitPrice列，導(dǎo)致了連接的索引無法覆蓋所求查詢，必須通過書簽查找來進(jìn)行，這也是為什么我們要養(yǎng)成只Select需要的列的好習(xí)慣，為了解決上面的問題，我們既可以用覆蓋索引，也可以減少所需的列來避免書簽查找。另外，上面符合ProductID的行僅僅只有5條，所以查詢分析器會(huì)選擇書簽查找，假如我們將符合條件的行進(jìn)行增大，查詢分析器會(huì)傾向于表掃描（通常來說達(dá)到表中行數(shù)的1%以上往往就會(huì)進(jìn)行table scan而不是書簽查找，但這并不絕對(duì)），如圖5所示。

    圖5.查詢分析器選擇了表掃描

    可以看出，查詢分析器此時(shí)選擇了表掃描來進(jìn)行連接，這種方式效率要低下很多，因此好的覆蓋索引和Select *都是需要注意的地方。另外，上面情況即使涉及到表掃描，依然是比較理想的情況，更糟糕的情況是使用多個(gè)不等式作為連接時(shí)，查詢分析器即使知道每一個(gè)列的統(tǒng)計(jì)分布，但卻不知道幾個(gè)條件的聯(lián)合分布，從而產(chǎn)生錯(cuò)誤的執(zhí)行計(jì)劃,如圖6所示。

    圖6.由于無法預(yù)估聯(lián)合分布，導(dǎo)致的偏差

   由圖6中，我們可以看出，估計(jì)的行數(shù)和實(shí)際的行數(shù)存在巨大的偏差，從而應(yīng)該使用表掃描但查詢分析器選擇了書簽查找，這種情況對(duì)性能的影響將會(huì)比表掃描更加巨大。具體大到什么程度呢？我們可以通過強(qiáng)制表掃描和查詢分析器的默認(rèn)計(jì)劃進(jìn)行比對(duì)，如圖7所示。

    圖7.強(qiáng)制表掃描性能反而更好

    談到合并連接，我突然想起在西雅圖參加SQL Pass峰會(huì)晚上酒吧排隊(duì)點(diǎn)酒，由于我和另外一哥們站錯(cuò)了位置，貌似我們兩個(gè)在插隊(duì)一樣，我趕緊說:I'm sorry,i thought here is end of line。對(duì)方無不幽默的說:”It's OK,In SQL Server,We called it merge join”。

    由上面的小故事不難看出，Merge Join其實(shí)上就是將兩個(gè)有序隊(duì)列進(jìn)行連接，需要兩端都已經(jīng)有序，所以不必像Loop Join那樣不斷的查找循環(huán)內(nèi)部的表。其次，Merge Join需要表連接條件中至少有一個(gè)等號(hào)查詢分析器才會(huì)去選擇Merge Join。

    Merge Join的過程我們可以簡(jiǎn)單用下面圖進(jìn)行描述:

    圖8.Merge Join第一步

    Merge Join首先從兩個(gè)輸入集合中各取第一行，如果匹配，則返回匹配行。加入兩行不匹配，則有較小值的輸入集合+1，如圖9所示。

    圖9.更小值的輸入集合向下進(jìn)1

    用C#代碼表示Merge Join的話如代碼1所示。

    因此，通常來說Merge Join如果輸入兩端有序，則Merge Join效率會(huì)非常高，但是如果需要使用顯式Sort來保證有序?qū)崿F(xiàn)Merge Join的話，那么Hash Join將會(huì)是效率更高的選擇。但是也有一種例外，那就是查詢中存在order by,group by,distinct等可能導(dǎo)致查詢分析器不得不進(jìn)行顯式排序，那么對(duì)于查詢分析器來說，反正都已經(jīng)進(jìn)行顯式Sort了,何不一石二鳥的直接利用Sort后的結(jié)果進(jìn)行成本更小的MERGE JOIN？在這種情況下，Merge Join將會(huì)是更好的選擇。

    另外，我們可以由Merge Join的原理看出，當(dāng)連接條件為不等式(但不包括!=)，比如說> >=等方式時(shí)，Merge Join有著更好的效率。

    下面我們來看一個(gè)簡(jiǎn)單的Merge Join,這個(gè)Merge Join是由聚集索引和非聚集索引來保證Merge Join的兩端有序，如圖10所示。

    圖10.由聚集索引和非聚集索引保證輸入兩端有序

    當(dāng)然，當(dāng)Order By,Group By時(shí)查詢分析器不得不用顯式Sort,從而可以一箭雙雕時(shí)，也會(huì)選擇Merge Join而不是Hash Join,如圖11所示。

    圖11.一箭雙雕的Merge Join

    哈希匹配連接相對(duì)前面兩種方式更加復(fù)雜一些，但是哈希匹配對(duì)于大量數(shù)據(jù)，并且無序的情況下性能均好于Merge Join和Loop Join。對(duì)于連接列沒有排序的情況下(也就是沒有索引)，查詢分析器會(huì)傾向于使用Hash Join。

    哈希匹配分為兩個(gè)階段,分別為生成和探測(cè)階段，首先是生成階段，第一階段生成階段具體的過程可以如圖12所示。

    圖12.哈希匹配的第一階段

    圖12中，將輸入源中的每一個(gè)條目經(jīng)過散列函數(shù)的計(jì)算都放到不同的Hash Bucket中，其中Hash Function的選擇和Hash Bucket的數(shù)量都是黑盒，微軟并沒有公布具體的算法，但我相信已經(jīng)是非常好的算法了。另外在Hash Bucket之內(nèi)的條目是無序的。通常來講，查詢優(yōu)化器都會(huì)使用連接兩端中比較小的哪個(gè)輸入集來作為第一階段的輸入源。

    接下來是探測(cè)階段，對(duì)于另一個(gè)輸入集合，同樣針對(duì)每一行進(jìn)行散列函數(shù)，確定其所應(yīng)在的Hash Bucket,在針對(duì)這行和對(duì)應(yīng)Hash Bucket中的每一行進(jìn)行匹配，如果匹配則返回對(duì)應(yīng)的行。

    通過了解哈希匹配的原理不難看出，哈希匹配涉及到散列函數(shù)，所以對(duì)CPU的消耗會(huì)非常高，此外，在Hash Bucket中的行是無序的，所以輸出結(jié)果也是無序的。圖13是一個(gè)典型的哈希匹配，其中查詢分析器使用了表數(shù)據(jù)量比較小的Product表作為生成，而使用數(shù)據(jù)量大的SalesOrderDetail表作為探測(cè)。

    圖13.一個(gè)典型的哈希匹配連接