我們先看 NestedLoop 和 MergeJoin 的算法（以下為引用，見 RicCC 的《 通往性能優(yōu)化的天堂 - 地獄 JOIN 方法說明 》 ):
==================================
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:
兩個表都按照關(guān)聯(lián)字段排序好之后， merge join 操作從每個表取一條記錄開始匹配，如果符合關(guān)聯(lián)條件，則放入結(jié)果集中；否則，將關(guān)聯(lián)字段值較小的記錄拋棄，從這條記錄對應(yīng)的表中取下一條記錄繼續(xù)進(jìn)行匹配，直到整個循環(huán)結(jié)束。
==================================

?

我們通過最簡單的情況來計算 NestedLoop 和 MergeJoin 的消耗：
兩張表 A 、 B ，分別有 m 、 n 行數(shù)據(jù)（ m < n ），占用基礎(chǔ)表物理存儲空間分別為 a 、 b 頁，聚集索引樹非葉節(jié)點都是兩層（一層根節(jié)點，一層中間級節(jié)點）， A 、 B 的聚集索引建在 A.col1 、 B.col1 上。一條查詢語句：
select A.col1, B.col2 from A inner join B where A.col1 = B.col1 。

?

執(zhí)行 NestedLoop 操作 ：
A 作為 outer input ， B 作為 inner input 時： A 帶來的 IO 為 a ；每次通過 clustered index seek 執(zhí)行內(nèi)部循環(huán)，花費 3( 一個根節(jié)點、一個中間集結(jié)點、一個葉節(jié)點。當(dāng)然也可能直接從根節(jié)點就拿到要的數(shù)據(jù)，我們只考慮最壞的情況），這樣執(zhí)行整個嵌套循環(huán)過程消耗 IO 為 a + 3*m 。如果 B 作為 inner input ， A 作為 outer input 分析類似。

執(zhí)行 MergeJoin :
MergeJoin 要把 A 、 B 兩張表做個 Scan ，然后進(jìn)行 Merge 操作。所以 A 、 B 分別帶來 IO 為 a + b 就是總的邏輯 IO 開銷。

?

從上述分析來看，若 a + 3*m << a + b ，即 3*m << b ，那么 NestedLoop 性能是極佳的。當(dāng)然，我們比較 A 表的行和 B 表所占數(shù)據(jù)頁大小看上去有點夸張，但是量化分析確實如此。在這里，我們沒有計算 NestedLoop 和 MergeJoin 本身的 cpu 計算開銷，特別是后者，這部分并不能完全忽略，但是也來得有限。

?

OK ，現(xiàn)在我們試圖執(zhí)行實際的語句驗證我們的觀點，看看能發(fā)現(xiàn)什么。

我有兩張表，一張表 charge ，聚集索引在 charge_no 上，它是個 int identity(1,1) ，共 10 萬行，數(shù)據(jù)頁 582 張，聚集索引非葉節(jié)點 2 層。一張表 A ，聚集索引在 col1 上（唯一），共 999 行，數(shù)據(jù)頁 2 張，聚集索引兩層。 min(A.col1) = min(charge.charge_no) 、 Max(A.col1) < max(charge.charge_no) 。

我們在 set statistics io on 和 set statistics time on 之后，執(zhí)行語句：

select A . col1 , charge . member_no from A inner join charge

??? on A . col1 = charge . charge_no

option ( loop join) -– 執(zhí)行 NestedLoop

go

select A . col1 , charge . member_no from A inner join charge

??? on A . col1 = charge . charge_no

option ( merge join)-- 執(zhí)行 MergeJoin 。

結(jié)果集都是 999 行，而且我們看到消息窗口中輸出為：



?

（圖 1 ）

從上圖中我們注意到幾點比較和最初分析不同的地方：

1. ????? Nested Loop 時，表 A 的邏輯讀是 4 ，而不是預(yù)計中的表 A 數(shù)據(jù)頁大小 2 ； charge 邏輯讀 2096 ，而不是預(yù)計中的 3 × 999 。

2. ????? Merge Join 時，表 Charge 的邏輯讀只有 8 。

對 1 來說，表 A 的邏輯讀是 4 是因為 clustered index scan 需要從聚集索引樹根節(jié)點開始去找最開始的那張數(shù)據(jù)頁，表 A 的聚集索引樹深度為 2 ，所以多了兩個非頁節(jié)點的 IO 。不是3×999是因為有些記錄（設(shè)為n）直接從根節(jié)點就能找到，也就是說有些是2×n + （999-n)* 3

對 2 來說， MergeJoin 時，表 Charge 并不是從頭到尾掃描，而是從 A 表的最大最小值圈定的范圍之內(nèi)進(jìn)行掃描，所以實際上它只讀取了 6 張數(shù)據(jù)頁。

OK , 為了驗證對 2 的解釋，我們在表 A 中插入一條 col1 > max(charge.charge_no) 的記錄，然后執(zhí)行：

select A . col1 , charge . member_no from A inner join charge

??? on A . col1 = charge . charge_no

option ( merge join)-- 執(zhí)行 MergeJoin 。

?

（圖 2 ）

現(xiàn)在 charge 邏輯讀成了 582 + 2 = 584 ，驗證了我們的想法。

那么如果 min(A.col1) > min(charge.charge_no) ， max(A.col1) = max(charge.charge_no) 時 SQLServer 會不會聰明到再次選擇一個較小的掃描范圍呢？很遺憾，不會 -_-…. 不知道 MS 這里基于什么考慮。

========================================

我們現(xiàn)在回到圖 1 ，實際上我們從圖 1 中還能發(fā)現(xiàn) SQL 的分析編譯占用時間相對執(zhí)行占用時間不僅不能忽略，還占了很大比重，所以能避免編譯、重編譯，還是要盡可能的避免。

========================================

?

OK ，現(xiàn)在我們開始分析分析執(zhí)行計劃，看看 SQLServer 如何在不同的執(zhí)行計劃之間做選擇。

我們首先把 A 表 truncate 掉，然后里面就填充一條數(shù)據(jù)， update statistics A 之后，看看執(zhí)行計劃：



?

（圖 3 ： NestedLoop 的執(zhí)行計劃）

?

（圖 4 ： MergeJoin 的執(zhí)行計劃）

我們把鼠標(biāo)分別移到圖 3 和圖 4 中 A 表的 Clustered Index Scan 上，會看到完全一樣的 tip ：



?

這個“ I/O 開銷”就是兩個邏輯 IO 的開銷（就一條記錄，自然是一個聚集索引根節(jié)點頁，一個數(shù)據(jù)頁，所以是 2 ）；估計行數(shù)為 1 ，很準(zhǔn)確，我們就 1 行記錄。

現(xiàn)在我們把鼠標(biāo)分別移動到圖 3 、圖 4 中 charge 表的 Clustered Index Scan 上，看到的則略有不同

?

（圖 5 ： NestedLoop ） ??????????????? （圖 6 ： Merge Join ）

Nested Loop 中的開銷評估看起來還算正常，運算符開銷 = （估計 IO 開銷 + 估計 CPU 開銷）×估計行數(shù)。（注意， NestedLoop 中，大表是作為內(nèi)存循環(huán)存在的，計算運算符開銷別忘了乘上估計行數(shù)）。

但是 Merge Join 中我們發(fā)現(xiàn)“估計行數(shù)”很不正常，居然是總行數(shù)（相應(yīng)的，估計 IO 開銷和估計 CPU 開銷自然都是全表掃描的開銷，這個可以跟 select * from charge 的執(zhí)行計劃做個對比）。顯然，執(zhí)行計劃中顯示的和實際執(zhí)行情況非常不同，實際情況按照我們上面的分析，應(yīng)該就讀取 3 張數(shù)據(jù)頁，估計行數(shù)應(yīng)該為 1 。誤差是非常巨大的， 3IO 直接給估算成了 584IO 。翻了翻在 pk_charge 上的統(tǒng)計信息，采樣行數(shù) 10w ，和總行數(shù)相同，再加上第二個結(jié)果集提供的信息，已經(jīng)足夠采取優(yōu)化算法去評估查詢計劃。不知道 MS 為什么沒有做。

好吧，我們假設(shè)執(zhí)行計劃的評估總是估算最壞的情況。由于 Merge Join 算法比較簡單，后面我們只關(guān)注 NestedLoop.

我們首先給 A 表增加一行 ( 值為 2) ，然后再來分析執(zhí)行計劃。


?

（圖 7 ： A 表NestedLoop） ?? ?????????????????????????????????? ( 圖 8 ： charge 表NestedLoop )

我們從圖 7 上可以看到， IO 開銷沒有增加， CPU 開銷略微增加，這很容易理解， A 表只增加了一行，其占用索引頁和數(shù)據(jù)頁和原來一樣。但是由于行數(shù)略有增加， cpu 消耗一定會略有增加。

奇怪的是圖 8 顯示的 charge 表上的 seek. 對比圖 5 ，運算符開銷并沒有像我們預(yù)料的那樣增加一倍，而是增加了 0.003412 – 0.003283 = 0.000129. 這個數(shù)值遠(yuǎn)小于 IO 開銷。為了多對比一次，這次我們再往 A 表里面插入一條記錄（值為 3 ），再來看看 charge 表上的運算：

?

（圖 9 ， charge 表NestedLoop）

這次我們又發(fā)現(xiàn)，這次增加的消耗是 0.0035993 – 0.003412 = 0.0001873 ，仍然遠(yuǎn)遠(yuǎn)小于一次的 IO 開銷。

好吧，那么我們假設(shè)執(zhí)行計劃估算算法認(rèn)為，如果某一頁緩存被讀到 SQL Engine 中之后就不會再被重復(fù)讀取。為了驗證它，我們試試把 A 表連續(xù)地增加到 1000 行，然后看看執(zhí)行計劃：

?

（圖 10 ， charge 表NestedLoop）

我們假設(shè)每次進(jìn)行 clustered index seek 消耗的 cpu 是相同的，那么我們可以計算出來查詢計劃認(rèn)為的 IO 共有：（運算符開銷 – cpu 開銷 *1000 ） / IO 開銷 = 5.81984 。要知道 charge 表數(shù)據(jù)頁總數(shù)為 582 ， 1000 行恰好是 100000 的百分之一， 1000 行恰好占用了 5.82 頁……（提醒一把，這 1000 行是連續(xù)值）

OMG… 這次執(zhí)行計劃算法明顯的比實際算法聰明。看上去像是， NestedLoop 在每次 Loop 時都會緩存本次 Loop 中讀取的數(shù)據(jù)頁，這樣當(dāng)下次 Loop 時，如果目標(biāo)數(shù)據(jù)頁已經(jīng)讀取過，就不再讀取，而直接從 Engine 內(nèi)存中取。

?

=========================================================

從上面的討論可以看出，有時候執(zhí)行計劃挺聰明，有時候?qū)嶋H的執(zhí)行又很聰明，總之，咱是不知道為啥微軟不讓執(zhí)行計劃和實際的執(zhí)行一樣聰明，或者一樣愚蠢。這樣，至少 SQL 引擎在評估查詢計劃的時候可以比較準(zhǔn)確。

?

btw: 接著圖 10 的例子，各位安達(dá)還可以自己去試試 insert 一條大于 max(charge.charge_no) 的記錄到表 A 里，然后試試看看 charge 表運算符上有什么變化。

==================================================

?

回到最初的主題，根據(jù)我們看到的SQL引擎實際執(zhí)行看，只有 A 表行集遠(yuǎn)遠(yuǎn)小于 charge_no 的時候， SQLServer 為我們選擇的 NestedLoop 才是非常高效的；為了保證更小的IO，當(dāng)(B表索引樹深度*A表行數(shù)>B表數(shù)據(jù)頁+B表索引樹深度）的時候，就可以考慮是否要指定MergeJoin。

值得一提的是，經(jīng)過多次的實驗， SQL 這樣評估 MergeJoin 和 NestedLoop ，最后選擇它認(rèn)為更優(yōu)的查詢計劃，居然多數(shù)情況下都是正確的……我是暈了，不知道你暈了沒有。

==================

剛才（22:00)本子待機了一次，然后再開機的時候我沒辦法重現(xiàn)SQLServer自己選擇NestedLoop總是比MergeJoin的cpu占用時間短了。現(xiàn)在的情況是：SQLServer每次都錯誤的選擇了NestedLoop，導(dǎo)致的結(jié)果是IO相差20 ～ 30倍，執(zhí)行時間多了百分之50。?
============================

俺也不知道有多少人讀到了這里，呵呵。

So盼望有人可以解釋以上這些東西。

寫有效率的SQL查詢（VI）