在產品環境中，往往存在著大量的表連接情景，不管是inner join、outer join、cross join和full join（邏輯連接符號），在內部都會轉化為物理連接（Physical Join），SQL Server共有三種物理連接：Nested Loop（嵌套迴圈），Merge Join ...
在產品環境中，往往存在著大量的表連接情景，不管是inner join、outer join、cross join和full join（邏輯連接符號），在內部都會轉化為物理連接（Physical Join），SQL Server共有三種物理連接：Nested Loop（嵌套迴圈），Merge Join（合併連接）和Hash Join（哈希連接）。這三個物理連接的處理方式不同，分別應用在不同的場景中。
在同一時刻，表連接只能是兩表（或者是數據集，也就是表的一部分）之間的連接，通常按照表處於Join操作的位置來區分，把Join操作符前面的表叫做左表，把Join操作符後面的表叫做右表。如果有n個表連接，那麼必須進行n-1次關聯操作，上一次關聯操作的結果作為下一次關聯操作的一個數據集。On子句用於設置連接條件，可以決定連接的順序。
一，嵌套迴圈
嵌套迴圈是最基本的Join演算法，分為兩個迴圈，內部迴圈和外部迴圈，內部迴圈嵌套在外部迴圈內部。任何一個連接語句，都包含兩個表，內部迴圈對應內部表，外部迴圈對應外部表。在圖形執行計劃中，上面的輸入表是外部表，下麵的輸入表是內部表。
在嵌套迴圈中，外部迴圈逐行處理外部表，內部迴圈針對每一個外部行到內部表中進行查找，以找出所有匹配外部行的數據行。外部迴圈每輸出一行，內部表中所有行都會和外部行進行匹配，假如外部表有N行，內部表有M行，對於外部表的每一行，內部表都會匹配M行，這種演算法的開銷是基於外部表的行數 乘以內部表的行數來確定，即以 N*M 來確定開銷。
如果內部迴圈在連接條件上存在索引，那麼把連接條件的每一個值叫做關聯參數（Correlated Parameter），使用關聯參數可以應用index seek演算法去查找匹配行。
嵌套迴圈適用於：大表和小表進行連接，並且大表在連接條件上存在索引。當把外部表是小表，內部表是大表，且內部表是在連接列上有索引時，優化器傾向於使用嵌套迴圈。優化器對嵌套迴圈的優化是：
1，如果內部表在連接列上存在索引，那麼優化器把外部表的輸入行作為關聯參數，基於關聯參數對內部表使用index seek查詢
2，對內部表使用Lazy Spool，Spool是指緩存中間結果集，以便重用。當內部表在連接條件上有很多重覆值，但只有少數行可以和外部行匹配時，Nested Loop演算法的效率非常高。
不是所有的Join都有相關參數，如果沒有合適的索引，或者on子句沒有指定合適的連接條件，就不會使用index seek演算法，也就不會有相關參數，通常情況下，inner join和left join 可以有相關參數，而right join，cross join和full join 沒有相關參數。
二，合併連接
合併連接使用的是合併演算法，要求至少存在一個相等的連接謂詞（on子句中至少存在一個相等條件），並且兩個輸入在合併列上必須是有序的。通常情況下，查詢優化器會掃描表上的索引，以檢查是否有索引包含合併列；如果沒有適當的索引，那麼合併連接的後面使用sort操作符對合併列進行排序，索引和Sort操作符都是為了滿足“合併演算法對兩個輸入必須是有序的”這一硬性要求。合併連接，也稱作排序-合併-連接（Sort-Merge-Join）。
如果合併連接需要對數據集進行排序，那麼還需要為Sort操作符向系統申請授予記憶體（Granted Memory），以存儲排序的中間結果集。如果查詢語句輸出的結果在連接鍵上是有序，order by join-keys，那麼連接查詢傾向於使用合併連接，如果排序是不必要的，那麼可以去掉order by子句。
由於兩個輸入都已經排序，Merge Join操作符從每一輸入各獲取一行進行比較，例如，對於inner join，如果兩行相等，則放回這個相等的結果；如果不相等，則廢棄值較小的行，並從該輸入中獲取下一行。這一過程重覆進行，直到處理完所有的數據行。
如果兩個輸入是有序的數據，那麼Merge Join的執行速度很快，但是，當需要添加Sort操作符對輸入數據進行排序時，選擇使用Merge Join操作符將十分費時。對於數據量大，並且可以從B-Tree索引中獲得已排序的數據，那麼Merge Join是執行速度最快的連接演算法。
三，哈希連接
哈希連接（Hash Join）適用於無序的大表之間的連接，有兩個輸入：生成輸入（Build Input） 和 探測輸入（Porbe Input），查詢優化器使用兩個輸入中較小的作為生成輸入。哈希連接掃描生成輸入，載入到記憶體中，生成哈希表，這個過程叫做生成階段（build phrase）。當生成輸入的所有行都載入到Hash 表之後，開始探測階段（probe phrase）：對於探測輸入的每一行，計算其Hash值，和哈希表進行匹配，輸出匹配的數據行。在探測階段，每做一次哈希連接操作，探測輸入的每一行只會掃描一次，再根據哈希鍵值去掃描整個哈希表。
Hash連接的兩個階段是有先後順序的，生成階段在前，探測階段在後。Hash連接在生成階段需要生成Hash Table，這需要向系統申請授予記憶體（granted memory），以存儲Hash值，如果授予記憶體不足，那麼Hash連接就不會開始。
1，哈希連接的記憶體消耗和溢出
在Hash連接開始執行前，SQL Server嘗試估計需要多少記憶體去創建Hash表，優化器使用預估的行數和每行的平均大小去估算需要的記憶體大小。為了最小化記憶體的使用，優化器從兩個表中選擇一個小表作為生成輸入（Build Input），SQL Server通過向系統申請授予記憶體來保證Hash表可以有“足夠”的記憶體創建成功。
如果SQL Server授予哈希連接的記憶體小於實際需要的記憶體，那麼Hash連接在生成階段會耗盡授予的記憶體，並把部分Hash表的數據溢出到硬碟上，也就是tempdb的workfile文件中。在這樣的情景下，Hash連接維護的Hash 桶（Hash Bucket）實際上存儲在兩個地方：記憶體中的hash表和硬碟上的workfile。
Hash連接會記錄Hash桶存儲的位置，當從生成輸入中繼續讀取一行數據時，它檢查該行是映射到記憶體的Hash桶中，還是映射到硬碟的Hash桶中，如果映射到記憶體的Hash桶中，那麼把該Hash值寫入到記憶體中；如果映射到硬碟的Hash桶中，那麼把該Hash值寫入到硬碟上的workfile結構中。
在探測階段，對於探測表的每一行，優化器都會檢查該行是映射到記憶體中的Hash 桶，還是映射到硬碟上的Hash 桶。如果映射到記憶體中hash桶，優化器就探測Hash表，產生連接的數據集存儲到記憶體中，並捨棄當前行；如果映射到硬碟的Hash桶，它會被寫入到硬碟中，暫時不做Join運算，當Hash的探測階段完成之後，Hash連接會把溢出到硬碟的數據讀取到記憶體，為每個Hash 桶重建記憶體Hash表，做Join運算。也就是說，哈希連接把硬碟上的結果集和記憶體中的結果集合併為最終的結果集。
2，Hash連接的性能優化
Hash連接使用授予記憶體來創建哈希表，如果授予記憶體不足，那麼部分哈希桶就會被溢出到硬碟，硬碟的讀取和寫入都會影響哈希連接的性能。因此，應該為Hash連接分配足夠的授予記憶體。優化器使用統計信息來預估授予記憶體的大小，如果統計信息過時，導致預估的授予記憶體過小，這會嚴重降低Hash連接的性能。
還有一種可能性是，參與Hash連接的兩個表都很大，以至於不能分配足夠的記憶體來構建哈希表，這也會導致哈希桶被溢出到workfile，導致哈希連接的性能低下。對於大表之間的映射，儘量使連接列有序，進而使用合併演算法來做連接。
3，哈希連接的類型
本文只簡單介紹記憶體哈希連接和Grace 哈希連接，對於遞歸哈希連接（Recursive Hash Join）和 Hash Bailout 是這兩個連接類型的優化，不再贅述。
（1），記憶體哈希連接（In-Memory Hash Join）
哈希連接計算整個生成輸入，然後在記憶體中創建一個哈希表（Hash Table）。每一個行都根據哈希值（Hash Value）計算Hash鍵，插入到相應的哈希桶（Hash Bucket）中。如果整個生成輸入小於可能的記憶體，那麼所有的數據行都會被存儲到記憶體中哈希表中。
（2），Grace 哈希連接（Grace Hash Join）
如果生成輸入太大，不能放到記憶體中，那麼Hash Join將會被處理成多個步驟，這就是Grace 哈希連接。每一個步驟都有一個生成階段和探測階段。首先，Grace 哈希連接使用一個哈希函數，把整個生成輸入和探測輸入按照Hash鍵進行分區，把分區輸入到不同的文件中，分區的規則是：
hash_func(join-field)
由於使用相同的hash演算法，在連接列上進行分區，這就保證了匹配的任意兩行數據都位於相同的文件對中，我推測：文件是在tempdb中創建的workfile，也就是說，需要調用IO子系統，把數據寫入到硬碟中。Grace hash join的主要的貢獻就在於，它使得每條數據只需要Join一次。
Grace 哈希連接首先把兩個大的輸入，分割成多個小的輸入，然後再對每個文件對進行哈希連接操作，最後把每個分區Join的結果合併作為連接操作最終輸出的結果。
參考文檔：
Advanced Query Tuning Concepts
