<a href="http://www.cnblogs.com/fish-li/archive/2011/06/06/2073626.html">看懂SqlServer查詢計劃</a>
在Sql Server中，每一個join指令，在内部執行時，都會采用三種更具體的join方式來運作。這三種join的方法是：nested loops join、merge join和hash join。這三種方法，沒有哪一種是永遠最好的，但是都有其最适合的上下文。SQL Server會根據兩個結果集所基于的表格結構，以及結果集的大小，選擇最合适的聯接方法。當然，使用者也可以在語句裡指定join的方法，也就是添加join hint，SQL Server會盡力尊重你的選擇。但是，有些查詢按照指定的join方法可能做不出執行計劃，SQL Server會報錯。而且建議不要使用sql hint，因為SqlServer的選擇基本上都是正确的
sql server有三種join方式，那麼就有三種join hint，如下所示就是按照三種join hint執行的聯結以及其所對應的執行計劃，
View Code
執行計劃：
Nested Loops是一種最基本的聯接方法，被SQL Server廣泛使用。對于兩張要被join在一起的表格，SQL Server選擇一張做Outer table(在執行計劃的上端，SalesOrderHeader_test)，另外一張做Inner table(在執行計劃的下端，SalesOrderDetail_test)。如下圖所示
其算法是：
以上面的查詢為例子，SQL Server選擇了SalesOrderHeader_test作為Outer table，SalesOrderDetail_test作為Inner table。首先SQL Server在SalesOrderHeader_test上做了一個clustered index seek，找出每一條a.SalesOrderID >43 659 and a.SalesOrderID< 53 660的記錄。每找到一條記錄，SQL Server都進入Inner table，找能夠和它join傳回資料的記錄（a.SalesOrderID = b.SalesOrderID）。由于Outer Table SalesOrderHeader_test上有10 000條SalesOrderID在43 659和53 660的記錄，每一條SQL Server都要到inner table裡去找能join的row，是以inner table SalesOrderDetail_test被掃描了10 000次，在執行計劃中的展現就是：Clustered index seek傳回的row有10000，而executes的次數是1。而Index Seek被執行的次數executes為10000，這是因為inner table被掃描了10000次。外表的rows決定了内表的executes。
Nested Loops Join是一種基本的聯接方式。它不需要SQL Server為join建立另外的資料結構，是以也比較省記憶體空間，也無須使用tempdb的空間。它适用的Join類型是非常廣泛的。有些聯接是merge和hash做不了的，但Nexted Loops可以做。是以這種聯接方式的優點是很明顯的，但是它的缺點也很明顯。
如果資料集能夠事先排序好，做Nested loops當然能夠更快一些。當然如果沒有排序，Nested Loops Join也能做得出來，就是cost會大大增加。
nested loop算法會逐一拿着Outer table裡的每一個值，在Inner table裡找所有符合條件的記錄，是以在Inner table裡找得快慢也能很大程度上影響整體的速度。如果進行檢索的字段上有一個索引，查找的速度會大大加快，Inner table資料集稍微大一點也沒關系。否則就要每次做整個資料集的掃描，是很浪費資源的。
總之，Nested Loops Join對資料集比較小的聯接，效率是最高的，是以在SQL Server裡使用得很廣泛。當SQL Server發現能夠選擇一個很小的資料集作為Outer table的時候，它往往會選擇Nested Loops，性能也比較好。但是Nested Loops Join對資料集大小的敏感性太強。如果SQL Server預測發生錯誤，用大的資料集做Outer table，性能會急劇下降。很多語句性能問題，都是由于這個造成的。
在前面提到過，Nested Loops Join隻适用于Outer table資料集比較小的情況。如果資料集比較大，SQL Server會使用其他兩種聯接方式，Merge Join和Hash Join。如果需要連接配接的兩張表已經聯接列上排序（例如，如果它們是通過掃描已排序的索引獲得的），則Merge Join是最快的聯接操作。如果兩個聯接輸入都很大，而且這兩個輸入的大小差不多，則預先排序的Merge Join提供的性能與Hash Join相近。但是，如果這兩個輸入的大小相差很大，則Hash Join操作通常快得多。
Merge Join算法如下：
也就是說，從兩邊的資料集裡各取一個值，比較一下。如果相等，就把這兩行聯接起來傳回。如果不相等，那就把小的那個值丢掉，按順序取下一個更大的。兩邊的資料集有一邊周遊結束，整個Join的過程就結束。是以整個算法的複雜度是O(M+N)，這個比起Nested Loops Join兩個資料集相乘的複雜度O(M*N)，的确是小了很多。是以在資料集大的情況下，Merge Join的優勢是非常明顯的。
但是從上面的Merge Join算法看出，它的局限性也很強，是以在實際的語句裡，使用得并不是那麼的普遍。它的局限性主要有：
這個先決條件是Merge Join算法的基礎，而對大的資料集排序本來就是一件比較複雜的事情。不過有些資料集是基于Join的那個字段上的索引得到的，是以能夠不費額外的資源就排好了順序，這時候使用Merge Join可能就比較合适。例如範例查詢，兩個資料集都是根據在SalesOrderID字段的索引上seek出來的，是以不需要再做排序。範例查詢的執行計劃如下所示：
從查詢計劃中我們可以看到merge join的範例查詢可以分解成兩個查詢，
第一個查詢使用clustered index seek，因為有聚集索引，是以查詢結果肯定按照聚集索引列SalesOrderID排序。第二個查詢雖然SalesOrderID不是SalesOrderDetail_test表的聚集索引鍵，但是因為在SalesOrderDetail_test表上有非聚集索引，而且隻需要查詢count(SalesOrderID)，是以之在非聚集索引上面查詢，查詢結果也是按照SalesOrderID排序。進而最終兩個結果集都是按照SalesOrderID排序的。
在SQL Server掃描資料集時，如果資料集1有兩個或者多個記錄值相等，SQL Server必須得把資料集2裡掃描過的資料暫時建立一個資料結構存放起來，萬一資料集1裡下一個記錄還是這個值，那還有用。這個臨時資料結構被稱為“Worktable”，會被放在tempdb或者記憶體裡。這樣做很耗資源，是以在上面的執行計劃裡，Merge Join的兩句子句的Subtree Cost分别為0.202和0.109。但Many-To-Many的Join子句Subtree Cost是5.051。也就是說，Join自己的cost是4.74（5.051 – 0.202 – 0.109 =4.74)）。這是一個不小的cost。
如果在[SalesOrderHeader_test]表的SalesOrderID列上再添加一個Unique的索引（或者将原來的聚集索引改成唯一聚集索引），
SQL Server就知道資料集1（SalesOrderHeader_test）的值不會重複的，也就不需要做Many-To-Many Join。執行計劃果然發生變化，預估的cost降低了一個數量級。
總結:
上面這兩個限制，影響了Merge Join的使用範圍。但是Merge Join的一個獨特好處是，傳回的資料集也是按照順序排好的。這裡順便提一下結果集的順序問題。我們在使用同一個查詢的時候，會發現結果集有時候是按我們想要的順序排列，有時候又不是。或者是在SQL Server 2000裡是這個順序，到了SQL Server 2005/2008又是另外順序。在講完了Merge Join以後，我們就能夠明白，同樣做Join操作，Merge Join就能夠按順序傳回，但是Nested Loops就不能。隻要語句裡沒有指定“Order By”，SQL Server選取哪一種Join并不需要考慮結果集是否是按順序傳回的。它更多考慮的是哪一種Join算法代價最小。如果資料量和資料分布讓SQL Server覺得Nested Loops劃算，它就轉用Nested Loops。結果集就不按順序傳回了，但是SQL Server并沒有做錯什麼。一句話，如果想要結果集按照某個順序傳回，就要明确地用“order by”指定。如果沒有指定，哪怕一模一樣的查詢，結果集順序這一次和上一次不一樣是很正常的。因為資料發生變化，或者參數不同，SQL Server很可能就會選擇不同的執行計劃。
算法描述：
選擇兩個需要join的表中的一個a，對于a中的每一個記錄R1，計算其聯接列的hash值，然後根據hash值将R1插入到hash bucket當中。
選擇兩外一張表b，對于b中的每一條記錄R2，我們也計算其聯接列的hash值，然後去hash bucket上查找。如果hash bucket上有R1能夠跟R2進行連接配接，那麼久輸出(R1,R2)的聯接結果，可能有多個R1的記錄。
其結構可以參考下圖所示：
上面的0-15就是hash bucket，而右邊的那些節點就是R1。
和其他兩種Join算法比，Hash Join的優點是很明顯的。
這對于資料集比較大的Join，其複雜度能夠控制在合理的範圍以内。相對于已經排好序的Merge Join，Hash Join多了一步計算Hash值，是以複雜度要比Merge Join要高一些，但是比Nested Loops要簡單許多。
因為聯接使用的是雜湊演算法，對輸入沒有限制，不需要SQL Server像為Merge Join一樣，事先準備好一個排過序的輸入。由于做Hash Join總是要把兩邊的資料集都要掃描一遍，是以有沒有索引其實幫助也不大。沒有索引，對性能也不會有太大的影響。
因為算法沒有要求代入的資料有任何次序，是以用多個CPU并行完成是比較容易的。
總之，Hash Join是一種适合于要Join的資料集比較大，上面沒有合适的索引的情況。像剛才的那個例子，是一個10 000條記錄的資料集和一個50 577條記錄的資料集之間的聯接。使用Nested Loops要循環10 000次，代價比較高。SQL Server預估出來的cost是2.233。使用Merge Join時，雖然兩個資料集都是排序好的，但是由于可能有重複的值，SQL Server隻好使用Many-To-Many的join方式，cost也很高，預估是5.882。使用Hash Join，預估的cost是0.727，比前兩個都小。是以如果不代入Join Hint的話，SQL Server預設會對這句話使用Hash Join。
但是，Hash Join并不是一種最優的Join算法，隻是SQL Server在輸入不優化（Join的資料集比較大，或上面沒有合适的索引）的時候的一種不得已選擇。這是因為Hash Join是一種最耗資源的Join算法。它在做Join之前，要先在記憶體裡建立一張Hash表。建立的過程需要CPU資源，Hash表需要用記憶體或tempdb存放。而Join的過程也要使用CPU資源來計算（“Probe”）。如果同時有很多使用者在用Hash算法做Join，對SQL Server的整體負擔是比較重的。從降低SQL Server整體負荷的角度考慮，還是要盡量降低Join輸入的資料集的大小，配以合适的索引，引導SQL Server盡量使用Nested Loops Join或者Merge Join。
下面用表對這三種Join方式作一下比較。
Nested Loops Join
Merge Join
Hash Join
最适合于
相對較小的兩個資料集，inner table在做Join的字段上有一個索引
輸入資料集大小中等或較大，且在Join字段上有索引幫助排序，或者語句要求傳回一個排好序的結果集
輸入資料集較大。尤其适合于Data warehouse 環境下的那些複雜的查詢語句
并發性
能夠支援大量的并發使用者同時運作
有索引支援的Many-to-one的join并發性較好，Many-To-Many的就差了
最好同時隻有少數使用者在同時運作
Join時要否兩個字段相等
不要
要(除非是full outer join)
要
要否使用記憶體資源
不使用
不使用(如果要為Merge Join做排序，可能要使用)
使用
要否使用tempdb
many-to-many join要使用
輸入資料集要否排序
希望輸入資料集排序否
希望outer input是排序的
是的
在SQL Server做聯接的時候，會按照輸入資料集所基于的表格的結構，衡量可能利用的索引，也根據統計資訊，預估兩個輸入資料集的大小，選擇使用三種Join方式其中的一種。如果選得不對，可能就會造成Join的速度非常慢。
題目的大緻意思是：
假如要查詢在a表中存在，但是在b表中不存在的記錄，應該如何查詢。為了便于說明，我們假設a表和b表都隻有一個字段id，a表中的記錄為{1,2,3,4,5}，b表中的記錄為{2,4}，那麼我們需要通過一個sql查詢得到{1,3,5}這樣的結果集。還有就是a和b表中id不一定是排序的，a表的資料集大，b表的資料集小。