我們先看NestedLoop和MergeJoin的算法（以下為引用，見(jiàn)RicCC的《通往性能優(yōu)化的天堂-地獄 JOIN方法說(shuō)明》):
==================================
NestedLoop:
foreach rowA in tableA where tableA.col2=?
{
search rowsB from tableB where tableB.col1=rowA.col1 and tableB.col2=? ;
if(rowsB.Count<=0)
discard rowA ;
else
output rowA and rowsB ;
}
MergeJoin:
兩個(gè)表都按照關(guān)聯(lián)字段排序好之后，merge join操作從每個(gè)表取一條記錄開(kāi)始匹配，如果符合關(guān)聯(lián)條件，則放入結果集中；否則，將關(guān)聯(lián)字段值較小的記錄拋棄，從這條記錄對應的表中取下一條記錄繼續進(jìn)行匹配，直到整個(gè)循環(huán)結束。
==================================
我們通過(guò)最簡(jiǎn)單的情況來(lái)計算NestedLoop和MergeJoin的消耗：
兩張表A、B，分別有m、n行數據（m < n），占用基礎表物理存儲空間分別為a、b頁(yè)，聚集索引樹(shù)非葉節點(diǎn)都是兩層（一層根節點(diǎn)，一層中間級節點(diǎn)），A、B的聚集索引建在A.col1、B.col1上。一條查詢(xún)語(yǔ)句：
select A.col1, B.col2 from A inner join B where A.col1 = B.col1。
執行NestedLoop操作：
A作為outer input，B作為inner input時(shí)：A帶來(lái)的IO為a；每次通過(guò)clustered index seek執行內部循環(huán)，花費3(一個(gè)根節點(diǎn)、一個(gè)中間集結點(diǎn)、一個(gè)葉節點(diǎn)。當然也可能直接從根節點(diǎn)就拿到要的數據，我們只考慮最壞的情況），這樣執行整個(gè)嵌套循環(huán)過(guò)程消耗IO為a + 3*m。如果B作為inner input，A作為outer input分析類(lèi)似。
執行MergeJoin:
MergeJoin要把A、B兩張表做個(gè)Scan，然后進(jìn)行Merge操作。所以A、B分別帶來(lái)IO為a + b就是總的邏輯IO開(kāi)銷(xiāo)。
從上述分析來(lái)看，若a + 3*m << a + b，即3*m << b，那么NestedLoop性能是極佳的。當然，我們比較A表的行和B表所占數據頁(yè)大小看上去有點(diǎn)夸張，但是量化分析確實(shí)如此。在這里，我們沒(méi)有計算NestedLoop和MergeJoin本身的cpu計算開(kāi)銷(xiāo)，特別是后者，這部分并不能完全忽略，但是也來(lái)得有限。
OK，現在我們試圖執行實(shí)際的語(yǔ)句驗證我們的觀(guān)點(diǎn)，看看能發(fā)現什么。
我有兩張表，一張表charge，聚集索引在charge_no上，它是個(gè)int identity(1,1)，共10萬(wàn)行，數據頁(yè)582張，聚集索引非葉節點(diǎn)2層。一張表A，聚集索引在col1上（唯一），共999行，數據頁(yè)2張，聚集索引兩層。min(A.col1) = min(charge.charge_no)、Max(A.col1) < max(charge.charge_no)。
我們在set statistics io on和set statistics time on之后，執行語(yǔ)句：
select A.col1, charge.member_no from A inner join charge
on A.col1 = charge.charge_no
option(loop join) -–執行NestedLoop
go
select A.col1, charge.member_no from A inner join charge
on A.col1 = charge.charge_no
option(merge join)--執行MergeJoin。
結果集都是999行，而且我們看到消息窗口中輸出為：
（圖1）
從上圖中我們注意到幾點(diǎn)比較和最初分析不同的地方：
1. Nested Loop時(shí)，表A的邏輯讀是4，而不是預計中的表A數據頁(yè)大小2；charge邏輯讀2096，而不是預計中的3×999。
2. Merge Join時(shí)，表Charge的邏輯讀只有8。
對1來(lái)說(shuō)，表A的邏輯讀是4是因為clustered index scan需要從聚集索引樹(shù)根節點(diǎn)開(kāi)始去找最開(kāi)始的那張數據頁(yè)，表A的聚集索引樹(shù)深度為2，所以多了兩個(gè)非頁(yè)節點(diǎn)的IO。不是3×999是因為有些記錄（設為n）直接從根節點(diǎn)就能找到，也就是說(shuō)有些是2×n + （999-n)* 3
對2來(lái)說(shuō)，MergeJoin時(shí)，表Charge并不是從頭到尾掃描，而是從A表的最大最小值圈定的范圍之內進(jìn)行掃描，所以實(shí)際上它只讀取了6張數據頁(yè)。
OK ,為了驗證對2的解釋?zhuān)覀冊诒?/span>A中插入一條col1 > max(charge.charge_no)的記錄，然后執行：
select A.col1, charge.member_no from A inner join charge
on A.col1 = charge.charge_no
option(merge join)--執行MergeJoin。
（圖2）
現在charge邏輯讀成了582 + 2 = 584，驗證了我們的想法。
那么如果min(A.col1) > min(charge.charge_no)，max(A.col1) = max(charge.charge_no)時(shí)SQLServer會(huì )不會(huì )聰明到再次選擇一個(gè)較小的掃描范圍呢？很遺憾，不會(huì )-_-….不知道MS這里基于什么考慮。
========================================
我們現在回到圖1，實(shí)際上我們從圖1中還能發(fā)現SQL的分析編譯占用時(shí)間相對執行占用時(shí)間不僅不能忽略，還占了很大比重，所以能避免編譯、重編譯，還是要盡可能的避免。
========================================
OK，現在我們開(kāi)始分析分析執行計劃，看看SQLServer如何在不同的執行計劃之間做選擇。
我們首先把A表truncate掉，然后里面就填充一條數據，update statistics A之后，看看執行計劃：
（圖3：NestedLoop的執行計劃）
（圖4：MergeJoin的執行計劃）
我們把鼠標分別移到圖3和圖4中A表的Clustered Index Scan上，會(huì )看到完全一樣的tip：
這個(gè)“I/O開(kāi)銷(xiāo)”就是兩個(gè)邏輯IO的開(kāi)銷(xiāo)（就一條記錄，自然是一個(gè)聚集索引根節點(diǎn)頁(yè)，一個(gè)數據頁(yè)，所以是2）；估計行數為1，很準確，我們就1行記錄。
現在我們把鼠標分別移動(dòng)到圖3、圖4中charge表的Clustered Index Scan上，看到的則略有不同
（圖5：NestedLoop） （圖6：Merge Join）
Nested Loop中的開(kāi)銷(xiāo)評估看起來(lái)還算正常，運算符開(kāi)銷(xiāo)=（估計IO開(kāi)銷(xiāo) + 估計CPU開(kāi)銷(xiāo)）×估計行數。（注意，NestedLoop中，大表是作為內存循環(huán)存在的，計算運算符開(kāi)銷(xiāo)別忘了乘上估計行數）。
但是Merge Join中我們發(fā)現“估計行數”很不正常，居然是總行數（相應的，估計IO開(kāi)銷(xiāo)和估計CPU開(kāi)銷(xiāo)自然都是全表掃描的開(kāi)銷(xiāo)，這個(gè)可以跟select * from charge的執行計劃做個(gè)對比）。顯然，執行計劃中顯示的和實(shí)際執行情況非常不同，實(shí)際情況按照我們上面的分析，應該就讀取3張數據頁(yè)，估計行數應該為1。誤差是非常巨大的，3IO直接給估算成了584IO。翻了翻在pk_charge上的統計信息，采樣行數10w，和總行數相同，再加上第二個(gè)結果集提供的信息，已經(jīng)足夠采取優(yōu)化算法去評估查詢(xún)計劃。不知道MS為什么沒(méi)有做。
好吧，我們假設執行計劃的評估總是估算最壞的情況。由于Merge Join算法比較簡(jiǎn)單，后面我們只關(guān)注NestedLoop.
我們首先給A表增加一行(值為2)，然后再來(lái)分析執行計劃。
（圖7：A表NestedLoop） (圖8：charge表NestedLoop)
我們從圖7上可以看到，IO開(kāi)銷(xiāo)沒(méi)有增加，CPU開(kāi)銷(xiāo)略微增加，這很容易理解，A表只增加了一行，其占用索引頁(yè)和數據頁(yè)和原來(lái)一樣。但是由于行數略有增加，cpu消耗一定會(huì )略有增加。
奇怪的是圖8顯示的charge表上的seek.對比圖5，運算符開(kāi)銷(xiāo)并沒(méi)有像我們預料的那樣增加一倍，而是增加了0.003412 – 0.003283 = 0.000129.這個(gè)數值遠小于IO開(kāi)銷(xiāo)。為了多對比一次，這次我們再往A表里面插入一條記錄（值為3），再來(lái)看看charge表上的運算：
（圖9，charge表NestedLoop）
這次我們又發(fā)現，這次增加的消耗是0.0035993 – 0.003412 = 0.0001873，仍然遠遠小于一次的IO開(kāi)銷(xiāo)。
好吧，那么我們假設執行計劃估算算法認為，如果某一頁(yè)緩存被讀到SQL Engine中之后就不會(huì )再被重復讀取。為了驗證它，我們試試把A表連續地增加到1000行，然后看看執行計劃：
（圖10，charge表NestedLoop）
我們假設每次進(jìn)行clustered index seek消耗的cpu是相同的，那么我們可以計算出來(lái)查詢(xún)計劃認為的IO共有：（運算符開(kāi)銷(xiāo) – cpu開(kāi)銷(xiāo)*1000）/ IO開(kāi)銷(xiāo) = 5.81984。要知道charge表數據頁(yè)總數為582，1000行恰好是100000的百分之一，1000行恰好占用了5.82頁(yè)……（提醒一把，這1000行是連續值）
OMG…這次執行計劃算法明顯的比實(shí)際算法聰明?？瓷先ハ袷?，NestedLoop在每次Loop時(shí)都會(huì )緩存本次Loop中讀取的數據頁(yè)，這樣當下次Loop時(shí)，如果目標數據頁(yè)已經(jīng)讀取過(guò)，就不再讀取，而直接從Engine內存中取。
=========================================================
從上面的討論可以看出，有時(shí)候執行計劃挺聰明，有時(shí)候實(shí)際的執行又很聰明，總之，咱是不知道為啥微軟不讓執行計劃和實(shí)際的執行一樣聰明，或者一樣愚蠢。這樣，至少SQL引擎在評估查詢(xún)計劃的時(shí)候可以比較準確。
btw:接著(zhù)圖10的例子，各位安達還可以自己去試試insert 一條大于max(charge.charge_no)的記錄到表A里，然后試試看看charge表運算符上有什么變化。
==================================================
回到最初的主題，根據我們看到的SQL引擎實(shí)際執行看，只有A表行集遠遠小于charge_no的時(shí)候，SQLServer為我們選擇的NestedLoop才是非常高效的；為了保證更小的IO，當(B表索引樹(shù)深度*A表行數>B表數據頁(yè)+B表索引樹(shù)深度）的時(shí)候，就可以考慮是否要指定MergeJoin。
值得一提的是，經(jīng)過(guò)多次的實(shí)驗，SQL這樣評估MergeJoin和NestedLoop，最后選擇它認為更優(yōu)的查詢(xún)計劃，居然多數情況下都是正確的……我是暈了，不知道你暈了沒(méi)有。
==================
============================
俺也不知道有多少人讀到了這里，呵呵。
So盼望有人可以解釋以上這些東西。
聯(lián)系客服
