我們先看 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)條件，則放入結(jié)果集中；否則，將關(guān)聯(lián)字段值較小的記錄拋棄，從這條記錄對(duì)應(yīng)的表中取下一條記錄繼續(xù)進(jìn)行匹配，直到整個(gè)循環(huán)結(jié)束。
==================================

?

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

?

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

執(zhí)行 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 性能是極佳的。當(dāng)然，我們比較 A 表的行和 B 表所占數(shù)據(jù)頁(yè)大小看上去有點(diǎn)夸張，但是量化分析確實(shí)如此。在這里，我們沒(méi)有計(jì)算 NestedLoop 和 MergeJoin 本身的 cpu 計(jì)算開(kāi)銷(xiāo)，特別是后者，這部分并不能完全忽略，但是也來(lái)得有限。

?

OK ，現(xiàn)在我們?cè)噲D執(zhí)行實(shí)際的語(yǔ)句驗(yàn)證我們的觀點(diǎn)，看看能發(fā)現(xiàn)什么。

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

我們?cè)? set statistics io on 和 set statistics time on 之后，執(zhí)行語(yǔ)句：

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 ）

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

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

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

對(duì) 1 來(lái)說(shuō)，表 A 的邏輯讀是 4 是因?yàn)? clustered index scan 需要從聚集索引樹(shù)根節(jié)點(diǎn)開(kāi)始去找最開(kāi)始的那張數(shù)據(jù)頁(yè)，表 A 的聚集索引樹(shù)深度為 2 ，所以多了兩個(gè)非頁(yè)節(jié)點(diǎn)的 IO 。不是3×999是因?yàn)橛行┯涗洠ㄔO(shè)為n）直接從根節(jié)點(diǎn)就能找到，也就是說(shuō)有些是2×n + （999-n)* 3

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

OK , 為了驗(yàn)證對(duì) 2 的解釋?zhuān)覀冊(cè)诒? 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 ，驗(yàn)證了我們的想法。

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

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

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

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

?

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

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



?

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

?

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

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



?

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

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

?

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

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

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

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

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


?

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

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

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

?

（圖 9 ， charge 表NestedLoop）

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

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

?

（圖 10 ， charge 表NestedLoop）

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

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

?

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

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

?

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

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

?

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

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

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

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

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

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

寫(xiě)有效率的SQL查詢（VI）