我們?cè)谧鯯QL查詢(xún)的時(shí)候，經(jīng)常會(huì)用到各各種關(guān)聯(lián)查詢(xún)，對(duì)于不同的聯(lián)接，效率還是有差別的，具體該用哪種呢?雖說(shuō)數(shù)據(jù)庫(kù)會(huì)做一些查詢(xún)的優(yōu)化，但了解原理，能有助我們直指核心。

開(kāi)始join吧。

[[339944]]

我們分析三種常見(jiàn)的join: Merge join，Hash join 和 NestedLoop Join。在此之前，我們先介紹一些關(guān)鍵詞：

Inner ralation 和 outer relation。

一個(gè) relation 可以是：

• 一張表
• 一個(gè)索引
• 一個(gè)前面操作的中間結(jié)果

當(dāng)你在對(duì)兩個(gè) relation 進(jìn)行 Join 的時(shí)候，join 算法對(duì)inner 和 outer relation 的方式是有區(qū)別的。outer relation 是左數(shù)據(jù)集， inner relation 是右數(shù)據(jù)集。

比如說(shuō) A JOIN B，此時(shí) A 是 outer relation，B 是 inner relation。而且一般 A JOIN B 和 B JOIN A 用時(shí)是不一樣的。

后面我們假設(shè) outer relation 有 N 個(gè)元素， inner relation 有 M個(gè)元素。不過(guò)實(shí)際的優(yōu)化器里，可以從統(tǒng)計(jì)信息中拿到確切的值。

Nested loop join

嵌套關(guān)聯(lián)是最容易的一個(gè)。過(guò)程大概是：

遍歷 outer relation 的每一行

然后去查找inner relation 的每一行是否匹配

寫(xiě)成偽代碼是這樣：

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 

因?yàn)閮芍乇闅v，所以復(fù)雜度是 O(N*M)。對(duì)應(yīng)到磁盤(pán)的I/O，在outer relation中，N 行中的每一行，都需要從inner relation 中循環(huán)讀取M行數(shù)據(jù)。

所以這個(gè)算法需要從磁盤(pán)讀 N + N*M行數(shù)據(jù)。但是，如果 inner relation 足夠小，可以放到內(nèi)存里的話(huà)，就只需要讀 M + N 次了。雖然說(shuō)在時(shí)間復(fù)雜度上沒(méi)什么變化，但在磁盤(pán)I/O上這個(gè)方式還不錯(cuò)，因此， inner relation 可以被索引替代，磁盤(pán)I/O也更有利。

Hash join

哈希連接更復(fù)雜，不過(guò)很多時(shí)候也比循環(huán)嵌套連接成本要低

哈希連接的原理是：

• 從 inner relation 中獲取所有元素
• 保存哈希表到磁盤(pán)
• 在內(nèi)存中建立一個(gè)哈希表
• 逐條讀取outer relation 的所有元素
• (用哈希表的哈希函數(shù))計(jì)算每個(gè)元素的哈希值，來(lái)查找inner relation 關(guān)聯(lián)的哈希桶
• 查看 outer relation 的元素是否有哈希桶內(nèi)的匹配。

在時(shí)間復(fù)雜度方面我們需要做點(diǎn)假設(shè)簡(jiǎn)化問(wèn)題：

• inner relation 被劃分成 X 個(gè)哈希桶
• 哈希函數(shù)接近均勻地分布每個(gè) relation 內(nèi)數(shù)據(jù)的哈希值，相當(dāng)于說(shuō)哈希桶大小是一致的。
• outer relation 的元素與哈希桶內(nèi)的所有元素的匹配，成本是哈希桶內(nèi)元素的數(shù)量。

時(shí)間復(fù)雜度是 (M/X) * N + cost_to_create_hash_table(M) + cost_of_hash_function*N。如果哈希函數(shù)創(chuàng)建了足夠小規(guī)模的哈希桶，那么復(fù)雜度就是 O(M+N)。

還有個(gè)哈希聯(lián)接的版本，對(duì)內(nèi)存更友好，但是對(duì)磁盤(pán) I/O 不夠有利。情況是這樣的：

• 計(jì)算outer relation 和 inner relation 雙方的哈希表
• 保存哈希表到磁盤(pán)
• 然后逐個(gè)比較兩個(gè) relation 的哈希桶(一個(gè)關(guān)系讀到內(nèi)存里，另一個(gè)逐行讀取)

Merge join

合并聯(lián)接是唯一產(chǎn)生排序的聯(lián)接算法。

注：這個(gè)簡(jiǎn)化的合并聯(lián)接不區(qū)分內(nèi)表或外表;兩個(gè)表扮演同樣的角色。但實(shí)際實(shí)現(xiàn)方式是不同的，比如當(dāng)處理重復(fù)值時(shí)。

• (可選)排序聯(lián)接運(yùn)算：兩個(gè)輸入源都按照聯(lián)接關(guān)鍵字排序。
• 合并聯(lián)接運(yùn)算：排序后的輸入源合并到一起。

(1) 排序

我們已經(jīng)說(shuō)過(guò)合并排序，在這里合并排序是個(gè)很好的算法。

有些時(shí)候數(shù)據(jù)集已經(jīng)排序了，比如：

• 如果表內(nèi)部就是有序的，比如聯(lián)接條件里有一個(gè)索引組織表
• 如果 relation 是聯(lián)接條件里的一個(gè)索引
• 如果聯(lián)接是作用在一個(gè)已經(jīng)排序的查詢(xún)的中間結(jié)果

(2) 合并聯(lián)接

這部分與我們說(shuō)過(guò)的合并排序中的合并運(yùn)算非常相似。區(qū)別只在于我們不從兩個(gè)關(guān)系里挑選所有元素，只選相同的元素。

大致原理如下：

• 在兩個(gè) relation 里，比較當(dāng)前元素(當(dāng)前的等號(hào)第一次出現(xiàn))
• 相同的時(shí)候，就把兩個(gè)元素都放到結(jié)果里，再比較兩個(gè)關(guān)系里的下一個(gè)元素
• 不相同的話(huà)，就去帶有最小元素的關(guān)系里找下一個(gè)元素
• 重復(fù) 1、2、3步驟直到其中一個(gè)關(guān)系的最后一個(gè)元素。

因?yàn)閮蓚€(gè)關(guān)系都是已排序的，你不再需要「回過(guò)頭找」，所以這個(gè)方法很有效。

這個(gè)算法是個(gè)簡(jiǎn)化版本，它沒(méi)有處理兩組數(shù)據(jù)中相同數(shù)據(jù)出現(xiàn)多次的情況。

哪個(gè)連接算法最好?

如果有最好的，就沒(méi)必要弄那么多種類(lèi)型了。由于很多因素要考慮，所以不會(huì)有一個(gè)簡(jiǎn)單的答案，需要考慮的因素例如這些：

• 空閑內(nèi)存大小：沒(méi)有足夠的內(nèi)存的話(huà)，就和有力的哈希聯(lián)接，至少是完全內(nèi)存中哈希聯(lián)接 說(shuō)bye bye吧。
• 兩個(gè)數(shù)據(jù)集的大小：如果一個(gè)大表聯(lián)接一個(gè)很小的表，嵌套循環(huán)聯(lián)接就比哈希聯(lián)接要快，因?yàn)楹笳哂袆?chuàng)建哈希的成本;如果兩個(gè)表都非常大，那么嵌套循環(huán)聯(lián)接CPU成本就很高。
• 是否有索引：有兩個(gè) B+樹(shù)索引的話(huà)，合并聯(lián)接似乎是更聰明的選擇。
• 結(jié)果集是否需要排序：即使你用到的是無(wú)序的數(shù)據(jù)集，你也可能想用成本較高的合并聯(lián)接(帶排序的)，因?yàn)樽罱K的結(jié)果是有序的，你可以把它和另一個(gè)結(jié)果集通過(guò)合并聯(lián)接合起來(lái)(也可能查詢(xún)用的 ORDER BY/GROUP BY/DISTINCT 等操作符隱式或顯式地要求一個(gè)排序結(jié)果)。
• 關(guān)系是否已經(jīng)排序：這時(shí)候合并聯(lián)接是最佳的選擇。
• 聯(lián)接的類(lèi)型：是等值聯(lián)接(比如 tableA.col1 = tableB.col2 )還是內(nèi)聯(lián)接?外聯(lián)接?笛卡爾乘積?或者自聯(lián)接?有些聯(lián)接在特定環(huán)境下是無(wú)法工作的。
• 數(shù)據(jù)的分布：假如聯(lián)接條件的數(shù)據(jù)是傾斜的(比如根據(jù)姓氏來(lái)聯(lián)接人，會(huì)有很多同姓的人)，用哈希聯(lián)接將是個(gè)災(zāi)難，因?yàn)槭枪：瘮?shù)將產(chǎn)生分布極不均勻的哈希桶。
• 如果你希望聯(lián)接操作使用多線(xiàn)程或多進(jìn)程。

【本文為51CTO專(zhuān)欄作者“侯樹(shù)成”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過(guò)作者微信公眾號(hào)『Tomcat那些事兒』獲取授權(quán)】

戳這里，看該作者更多好文