SQL夯實基礎（八）：聯接運算符算法歸類
今天主要介紹三個常用聯接運算符算法：合并聯接（Merge join），哈希聯接（Hash Join）和嵌套循環聯接（Nested Loop Join）。（mysql至8.0版本，都隻支援Nested Loop Join,下一篇文章我會單獨說下mysql對Nested Loop Join的使用）
一個關系可以是：
1 一個表
2 一個索引
3 上一個運算的中間結果（比如上一個聯接運算的結果）
當你聯接兩個關系時，聯接算法對兩個關系的處理是不同的。在本文剩餘部分，我将假定：
外關系是左側資料集（驅動表），内關系是右側資料集（非驅動表、被驅動表）。
比如， A JOIN B 是 A 和 B 的聯接，這裡 A 是外關系，B 是内關系。多數情況下，A JOIN B 的成本跟 B JOIN A 的成本是不同的。
在這一部分，我還将假定外關系有 N 個元素，内關系有 M 個元素。要記住，真實的優化器通過統計知道 N 和 M 的值。
注：N 和 M 是關系的基數。【基數】
驅動表與被驅動表
這裡我們叫他外關系和内關系（因為很多文章對這兩個概念有不同的命名，很容易混亂）：
驅動表，即需要從驅動表中拿出來每條記錄，去與被驅動表的所有記錄進行比對探測。
了解驅動表和被驅動表的差異，最本質的問題，需要了解順序讀取和随機讀取的差異，記憶體是适合随機讀取的，但是硬碟就不是（固态随機讀稍微好些，但是對比順序讀有差距），對于硬碟來說順序讀取的效率比較好。
1、驅動表，作為外層循環，若能隻進行一次IO把所有資料拿出來最好，這就比較适合順序讀取，一次性批量的把資料讀取出來，這裡沒考慮緩存等細節。
2、被驅動表，即裡層循環，由于需要不斷的拿外層循環傳進來的每條記錄去比對，是以如果是适合随機讀取的，那麼效率就會比較高。如果表上有索引，實際上就意味着這個表是适合随機讀取的。如果表的資料量較大，且沒有索引，那麼就不适合多次的随機讀取，比較适合一次性的批量讀取，就應該作為驅動表。
嵌套循環聯接
嵌套循環聯接是最簡單的。
道理如下：
1 針對外關系的每一行
2 檢視内關系裡的所有行來尋找比對的行
下面是僞代碼：
nested_loop_join(array outer, array inner)
for each row a in outer
for each row b in inner
if (match_join_condition(a,b))
write_result_in_output(a,b)
end if
end for
end for 由于這是個雙疊代，時間複雜度是 O(N*M)。
在磁盤 I/O 方面， 針對 N 行外關系的每一行，内部循環需要從内關系讀取 M 行。這個算法需要從磁盤讀取 N+ N*M 行。但是，如果内關系足夠小，你可以把它讀入記憶體，那麼就隻剩下 M + N 次讀取。這樣修改之後，内關系必須是最小的，因為它有更大機會裝入記憶體。
在CPU成本方面沒有什麼差別，但是在磁盤 I/O 方面，最好的是每個關系隻讀取一次。
當然，内關系可以由索引代替，對磁盤 I/O 更有利。
由于這個算法非常簡單，下面這個版本在内關系太大無法裝入記憶體時，對磁盤 I/O 更加有利。道理如下：
1 為了避免逐行讀取兩個關系，
2 你可以成簇讀取，把（兩個關系裡讀到的）兩簇資料行儲存在記憶體裡，
3 比較兩簇資料，保留比對的，
4 然後從磁盤加載新的資料簇來繼續比較
5 直到加載了所有資料。
可能的算法如下：
// improved version to reduce the disk I/O.
nested_loop_join_v2(file outer, file inner)
for each bunch ba in outer
// ba is now in memory
for each bunch bb in inner
// bb is now in memory
for each row a in ba
for each row b in bb
if (match_join_condition(a,b))
write_result_in_output(a,b)
end if
end for
end for
end for
end for 使用這個版本，時間複雜度沒有變化，但是磁盤通路降低了：
1 用前一個版本，算法需要 N + N*M 次通路（每次通路讀取一行）。
2 用新版本，磁盤通路變為外關系的資料簇數量 + 外關系的資料簇數量 * 内關系的資料簇數量。
3 增加資料簇的尺寸，可以降低磁盤通路。
哈希聯接
哈希聯接更複雜，不過在很多場合比嵌套循環聯接成本低。
哈希聯接的道理是：
1) 讀取内關系的所有元素
2) 在記憶體裡建一個哈希表
3) 逐條讀取外關系的所有元素
4) （用哈希表的哈希函數）計算每個元素的哈希值，來查找内關系裡相關的哈希桶内
5) 是否與外關系的元素比對。
在時間複雜度方面我需要做些假設來簡化問題：
1 内關系被劃分成 X 個哈希桶
2 哈希函數幾乎均勻地分布每個關系内資料的哈希值，就是說哈希桶大小一緻。
3 外關系的元素與哈希桶内的所有元素的比對，成本是哈希桶内元素的數量。
時間複雜度是 (M/X) * N + 建立哈希表的成本(M) + 哈希函數的成本 * N。如果哈希函數建立了足夠小規模的哈希桶，那麼複雜度就是 O(M+N)。
還有個哈希聯接的版本，對記憶體有利但是對磁盤 I/O 不夠有利。 這回是這樣的：
1) 計算内關系和外關系雙方的哈希表
2) 儲存哈希表到磁盤
3) 然後逐個哈希桶比較（其中一個讀入記憶體，另一個逐行讀取）。
合并聯接
合并聯接是唯一産生排序的聯接算法。
注：這個簡化的合并聯接不區分内表或外表；兩個表扮演同樣的角色。但是真實的實作方式是不同的，比如當處理重複值時。
1.（可選）排序聯接運算：兩個輸入源都按照聯接關鍵字排序。
2.合并聯接運算：排序後的輸入源合并到一起。
我們已經談到過合并排序，在這裡合并排序是個很好的算法（但是并非最好的，如果記憶體足夠用的話，還是哈希聯接更好）。
然而有時資料集已經排序了，比如：
1 如果表内部就是有序的，比如聯接條件裡一個索引組織表
2 如果關系是聯接條件裡的一個索引
3 如果聯接應用在一個查詢中已經排序的中間結果
這部分與我們研究過的合并排序中的合并運算非常相似。不過這一次呢，我們不是從兩個關系裡挑選所有元素，而是隻挑選相同的元素。道理如下：
1) 在兩個關系中，比較目前元素（目前=頭一次出現的第一個）
2) 如果相同，就把兩個元素都放入結果，再比較兩個關系裡的下一個元素
3) 如果不同，就去帶有最小元素的關系裡找下一個元素（因為下一個元素可能會比對）
4) 重複 1、2、3步驟直到其中一個關系的最後一個元素。
因為兩個關系都是已排序的，你不需要『回頭去找』，是以這個方法是有效的。
該算法是個簡化版，因為它沒有處理兩個序列中相同資料出現多次的情況（即多重比對）。真實版本『僅僅』針對本例就更加複雜，是以我才選擇簡化版。
1 如果兩個關系都已經排序，時間複雜度是 O(N+M)
2 如果兩個關系需要排序，時間複雜度是對兩個關系排序的成本：O(N*Log(N) + M*Log(M))
哪個算法最好？
如果有最好的，就沒必要弄那麼多種類型了。這個問題很難，因為很多因素都要考慮，比如：
1 空閑記憶體：沒有足夠的記憶體的話就跟強大的哈希聯接拜拜吧（至少是完全記憶體中哈希聯接）。
2 兩個資料集的大小。比如，如果一個大表聯接一個很小的表，那麼嵌套循環聯接就比哈希聯接快，因為後者有建立哈希的高昂成本；如果兩個表都非常大，那麼嵌套循環聯接CPU成本就很高昂。
3 是否有索引：有兩個 B+樹索引的話，聰明的選擇似乎是合并聯接。
4 結果是否需要排序：即使你用到的是未排序的資料集，你也可能想用成本較高的合并聯接（帶排序的），因為最終得到排序的結果後，你可以把它和另一個合并聯接串起來（或者也許因為查詢用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或顯式地要求一個排序結果）。
5 關系是否已經排序：這時候合并聯接是最好的候選項。
6 聯接的類型：是等值聯接（比如 tableA.col1 = tableB.col2 ）？ 還是内聯接？外聯接？笛卡爾乘積？或者自聯接？有些聯接在特定環境下是無法工作的。
7 資料的分布：如果聯接條件的資料是傾斜的（比如根據姓氏來聯接人，但是很多人同姓），用哈希聯接将是個災難，原因是哈希函數将産生分布極不均勻的哈希桶。
8 如果你希望聯接操作使用多線程或多程序。