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

?

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

?

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

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

?

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

?

OK ，現在我們試圖執行實際的語句驗證我們的觀點，看看能發現什么。

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

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

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 ）

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

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

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

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

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

OK , 為了驗證對 2 的解釋，我們在表 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) 時 SQLServer 會不會聰明到再次選擇一個較小的掃描范圍呢？很遺憾，不會 -_-…. 不知道 MS 這里基于什么考慮。

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

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

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

?

OK ，現在我們開始分析分析執行計劃，看看 SQLServer 如何在不同的執行計劃之間做選擇。

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



?

（圖 3 ： NestedLoop 的執行計劃）

?

（圖 4 ： MergeJoin 的執行計劃）

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



?

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

現在我們把鼠標分別移動到圖 3 、圖 4 中 charge 表的 Clustered Index Scan 上，看到的則略有不同

?

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

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

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

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

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


?

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

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

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

?

（圖 9 ， charge 表NestedLoop）

這次我們又發現，這次增加的消耗是 0.0035993 – 0.003412 = 0.0001873 ，仍然遠遠小于一次的 IO 開銷。

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

?

（圖 10 ， charge 表NestedLoop）

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

OMG… 這次執行計劃算法明顯的比實際算法聰明。看上去像是， NestedLoop 在每次 Loop 時都會緩存本次 Loop 中讀取的數據頁，這樣當下次 Loop 時，如果目標數據頁已經讀取過，就不再讀取，而直接從 Engine 內存中取。

?

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

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

?

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

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

?

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

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

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

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

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

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

寫有效率的SQL查詢（VI）