自測試示例， 兩表 都沒有 建立索引 情況：? start

1.? sql 語句通過 nested loop 連接,?

?

?

2. 默認 hash join?

?//end-------------------------------------------------------------------

說明：最近找到了一個不錯的國外的博客http://blogs.msdn.com/b/craigfr/,博主是Sql Server的開發人員,寫了很多Sql Server的內部原理性的文章,覺得非常有收獲。所以試著把他翻譯成中文,因為本人的英語和技術水平有限,難免會有錯誤,還請各位看官批評指教。

?

Nested Loops Join(嵌套連接)

Sql Server支持三種物理連接：nested loops join,merge join和hash join.這篇文章,我將描述nested loops join
(或者簡稱為NL)。

基本算法

最簡單的情況是,nested loop會以連接謂詞為條件取出一張表里的每一行(稱為外部表)
與另外一張表(稱為內部表)的每一行進行比較來尋找符合條件的行。(注意這里的"內部"和"外部"是具有多層含義的,必須從
上下文中來理解它們。"內部表"和"外部表"是指連接的輸入,"內連接"和"外連接"是指邏輯操作。)

我們可以用偽碼來解釋這個算法:

for each row R1 in the outer table
??? for each row R2 in the inner table
??????? if R1 joins with R2
??????????? return (R1, R2)

因為算法里的嵌套循環,所以命名為嵌套連接。

從比較的總行說來說,這種算法的成本是與外部表行數乘以內部表的行數成比例的。隨著驅動表行數的增長
的成本增長是很快的,在實際情況我們通過減少內部表行數來減小算法的成本的。

?

還是以上篇文章給出的方案為例：create table Customers (Cust_Id int, Cust_Name varchar(10)) insert Customers values (1, 'Craig') insert Customers values (2, 'John Doe') insert Customers values (3, 'Jane Doe')create table Sales (Cust_Id int, Item varchar(10)) insert Sales values (2, 'Camera') insert Sales values (3, 'Computer') insert Sales values (3, 'Monitor') insert Sales values (4, 'Printer')進行如下查詢：select * from Sales S inner join Customers C on S.Cust_Id = C.Cust_Id option(loop join)我加入了"loop join"提示來強迫優化器使用nested loops join.和"set statistics profile on" 一起運行得到如下的執行計劃：Rows Executes3 1 |--Nested Loops(Inner Join, WHERE:([C].[Cust_Id]=[S].[Cust_Id]))3 1 |--Table Scan(OBJECT:([Customers] AS [C]))12 3 |--Table Scan(OBJECT:([Sales] AS [S]))

?

?

這份執行計劃里Customers是外部表,Sales是內部表。首先掃描Customers表。每次取出一個Customer,
對于每一個customer,都要掃描Sales表。因為有3個Customers,所以Sales表被掃描了3次。每次掃描返回
4行。判斷每一個sale與當前的customer是否具有相同的Cust_Id，如果相同就返回這一對行.我們有3個
customer和4個sale所以我們進行了3*4=12次比較。其中只有3次比較符合條件。

?

如果在Sales表創建索引會是什么情況呢：create clustered index CI on Sales(Cust_Id)我們得到了如下的執行計劃：Rows Executes3 1 |--Nested Loops(Inner Join, OUTER REFERENCES:([C].[Cust_Id]))3 1 |--Table Scan(OBJECT:([Customers] AS [C]))3 3 |--Clustered Index Seek(OBJECT:([Sales].[CI] AS [S]), SEEK:([S].[Cust_Id]=[C].[Cust_Id]) ORDERED FORWARD)

?

這次,并沒有做全表掃描,而是進行了索引探尋。仍然進行了3次索引探尋-每個customer一次,
但是每次索引探尋只返回了與當前Cust-Id相匹配并滿足謂詞條件的一條記錄。所以,索引探尋只返回了
3行，而不是全表掃描的12行。

請注意這里索引探尋的依賴條件C.CustId來自于連接的外部表-Customers全表掃描。
每次我們執行索引探尋(再次說明我們執行了3次-每個用戶一次),C_CustId有不同的值。
我們稱C.CustId為"關聯參數";如果一個nested loops join有關聯參數,執行計劃里會以"OUTER REFERENCES"
顯示出來。我們經常把這種以依賴于關聯參數的索引探尋方式執行的nested loop join稱為
"索引連接"。這是非常常見的場景。

　　

Nested loops join支持什么類型的連接謂詞？

?

Nested loops join支持包括相等連接謂詞和不等謂詞連接在內的所有連接謂詞。

?

Nested loops join支持什么類型的邏輯連接？

?

Nested loops join支持以下類型的邏輯連接：

* Inner join
* Left outer join
* Cross join
* Cross apply and outer apply
* Left semi-join and left anti-semi-join

Nested loops join不支持以下邏輯連接：

* Right and full outer join
* Right semi-join and right anti-semi-join

?

為什么Nested loops join 只支持左連接？

?

我們很容易擴展Nested loops join 算法來支持left outer 和semi-joins.例如，下邊是左外連接的偽碼。
我們可以寫出相似的代碼來實現 left semi-join 和 left anti-semi-join.

for each row R1 in the outer table
??? begin
??????? for each row R2 in the inner table
??????????? if R1 joins with R2
??????????????? return (R1, R2)
??????? if R1 did not join
??????????? return (R1, NULL)
??? end

這個算法記錄我們是否連接了一個特定的外部行。如果已經窮盡了所有內部行,但是沒有找到一個
符合條件的內部行,就把該外部行做為NULL擴展行輸出。

那么我們為什么不支持right outer join呢。在這里,我們想返回符合條件的行對(R1,R2)
和不符合連接條件的(NULL,R2)。問題是我們會多次掃描內部表-對于外部表的每行都要掃描一次。
在多次掃描過程中我們可能會多次處理內部表的同一行。這樣我們就無法來判斷某一行到底符合
不符合連接條件。更進一步,如果我們使用index join,一些內部行可能都不會被處理,但是這些行在
外連接時是應該返回的。

幸運的是right outer join可以轉換為left outer join,right semi-join可以轉換為left semi-join,
所以right outer join和semi-joins是可以使用nested loops join的。但是,當執行轉換的時候可能會
影響性能。例如,上邊方案中的"Customer left outer join Sales",由于表內部表Sales有聚集索引,所以
我們在連接過程中可以使用索引探尋。如果"Customer right outer join Sales" 轉換為 "Sales left outer?
join Customer”,我們則需要在Customer表上具有相應的索引了。

?

full outer joins是什么情況呢？

?

nested loops join完全支持outer join.我們可以把"T1 full outer join T2"轉換為"T1 left outer join T2?
UNION T2 left anti-semi-join T1".可以這樣來理解,將full outer join轉換為一個左連接-包含T1和T2所有的
符合條件的連接行和T1表里沒有連接的行,然后加上那些使用anti-semi-join從T2返回的行。下邊是轉換過程：

?

select *
from Customers C full outer join Sales S
on C.Cust_Id = S.Cust_Id

Rows Executes
??
?
5??? 1??????? |--Concatenation
?
4??? 1?????????? |--Nested Loops(Left Outer Join, WHERE:([C].[Cust_Id]=[S].[Cust_Id]))
?
3??? 1?????????? |??? |--Table Scan(OBJECT:([Customers] AS [C]))
?
12?? 3?????????? |??? |--Clustered Index Scan(OBJECT:([Sales].[Sales_ci] AS [S]))
?
0??? 0?????????? |--Compute Scalar(DEFINE:([C].[Cust_Id]=NULL, [C].[Cust_Name]=NULL))
?
1??? 1??????????????? |--Nested Loops(Left Anti Semi Join, OUTER REFERENCES:([S].[Cust_Id]))
?
4??? 1????????????????? |--Clustered Index Scan(OBJECT:([Sales].[Sales_ci] AS [S]))
?
3??? 4????????????????? |--Top(TOP EXPRESSION:((1)))
?
3??? 4?????????????????????? |--Table Scan(OBJECT:([Customers] AS [C]), WHERE:([C].[Cust_Id]=[S].[Cust_Id]))
?

注意：在上邊的例子中,優化器并選擇了聚集索引掃描而不是探尋。這完全是基于成本考慮而做出的決定。表非常小(只有一頁)
所以掃描或探尋并沒有什么性能上的區別。

?

NL join好還是壞？

?

實際上,并沒有所謂"最好"的算法,連接算法也沒有好壞之分。每一種連接方式在正確的環境下性能非常好,
而在錯誤的環境下則非常差。因為nested loops join的復雜度是與驅動表大小和內部表大小乘積成比例的,所以在驅動表比較小
的情況下性能比較好。內部表不需要很小,但是如果非常大的話,在具有高選擇性的連接列上建立索引將很有幫助。

一些情況下,Sql Server只能使用nested loops join算法,比如Cross join和一些復雜的cross applies,outer applies,
(full outer join是一個例外)。如果沒有任何相等連接謂詞的話nested loops join算法是Sql Server的唯一選擇。

?

參考 ：

https://blog.csdn.net/wangyihbu/article/details/6209294

?https://blog.csdn.net/oxlshmily/article/details/8563785

轉載于:https://www.cnblogs.com/xiaohuizhenyoucai/p/11010088.html

總結

以上是生活随笔為你收集整理的SqlServer 算法 ：Nested Loops Join(嵌套连接)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。