歡迎閱讀數(shù)據(jù)庫(kù)內(nèi)核雜談！這期我們重新回歸主線劇情，繼續(xù)討論執(zhí)行算子的實(shí)現(xiàn)。相對(duì)簡(jiǎn)單的算子如limit或者是projection，在內(nèi)核雜談的第一期(一小時(shí)數(shù)據(jù)庫(kù)實(shí)現(xiàn))就已經(jīng)討論過(guò)，不再贅述。繼上節(jié)討論了排序和聚合的實(shí)現(xiàn)，我們對(duì)單個(gè)表的大部分操作都覆蓋了。但數(shù)據(jù)庫(kù)強(qiáng)大的地方在于，它能夠把現(xiàn)實(shí)中的某一塊業(yè)務(wù)，映射地表達(dá)成一系列的表的集合，并且其查詢語(yǔ)句SQL支持多個(gè)表相關(guān)聯(lián)的查詢操作。這種連接多表的查詢使得數(shù)據(jù)庫(kù)的功能得到了一個(gè)質(zhì)的飛躍。對(duì)應(yīng)用開(kāi)發(fā)者而言，相當(dāng)于打開(kāi)了一個(gè)新世界的大門(mén)。原本一個(gè)個(gè)獨(dú)立的表，因?yàn)檫B接而產(chǎn)生了無(wú)窮多種可能。這期，咱們就來(lái)細(xì)聊一下表與表之間的JOIN(連接)算子的實(shí)現(xiàn)。
為什么需要JOIN?
在說(shuō)具體實(shí)現(xiàn)前，咱們先細(xì)聊一下為什么數(shù)據(jù)庫(kù)需要支持JOIN。這個(gè)問(wèn)題，甚至可以再退一步到為什么數(shù)據(jù)庫(kù)需要有多個(gè)表？其實(shí)答案很簡(jiǎn)單，上文都提到了：因?yàn)楝F(xiàn)實(shí)中的事物就是復(fù)雜，多樣的。多個(gè)表之間的關(guān)系能方便地和現(xiàn)實(shí)世界的事物映射起來(lái)，并且這種映射更直觀，更能夠讓人接受。就像面向?qū)ο缶幊桃粯?，恐怕我們都不能想象如果面向?qū)ο缶幊讨荒軇?chuàng)建一種類(lèi)型的對(duì)象吧。
除了方便映射實(shí)物，業(yè)務(wù)邏輯同樣需要JOIN。舉個(gè)例子，假設(shè)現(xiàn)在有個(gè)簡(jiǎn)單的電商系統(tǒng)有買(mǎi)家，賣(mài)家和訂單三張表，數(shù)據(jù)科學(xué)家想要查詢2018年，對(duì)于上海客戶的銷(xiāo)售額最高的前3位賣(mài)家信息。這么一個(gè)簡(jiǎn)單的查詢其實(shí)就用到了每個(gè)表里的信息，需要從買(mǎi)家表里得到賣(mài)家信息，從買(mǎi)家表里得到地址是上海的買(mǎi)家ID，然后對(duì)訂單表以賣(mài)家ID做組隊(duì)聚合，最后對(duì)銷(xiāo)售總額進(jìn)行排序并取前3。讀者可能想到，這些業(yè)務(wù)邏輯其實(shí)也可以放在應(yīng)用層做，的確如此(并且，如果是使用某些NoSQL的用戶，因?yàn)檫€不支持JOIN，應(yīng)用層實(shí)現(xiàn)是唯一的選擇)。放在應(yīng)用層有下面這些短處，一是執(zhí)行效率方面肯定不如在數(shù)據(jù)庫(kù)高效；二是數(shù)據(jù)一致性和正確性得不到保證。假設(shè)在多用戶的情形下，有多個(gè)用戶同時(shí)在更新數(shù)據(jù)和查詢數(shù)據(jù)，如何保證查詢數(shù)據(jù)的正確性。由于應(yīng)用層沒(méi)有數(shù)據(jù)庫(kù)系統(tǒng)的全局觀，在保證對(duì)多用戶的支持上實(shí)現(xiàn)會(huì)更加復(fù)雜。業(yè)務(wù)驅(qū)動(dòng)實(shí)現(xiàn)，數(shù)據(jù)庫(kù)系統(tǒng)就推出了SQL查詢語(yǔ)句讓實(shí)現(xiàn)業(yè)務(wù)的程序員通過(guò)構(gòu)建不同的SQL語(yǔ)句就能得到相應(yīng)的信息，而把復(fù)雜的執(zhí)行邏輯，資源管理，多用戶協(xié)調(diào)等等都封裝進(jìn)了數(shù)據(jù)庫(kù)內(nèi)部。這樣不僅提高了整體執(zhí)行效率，也大大簡(jiǎn)化了業(yè)務(wù)邏輯的開(kāi)發(fā)工作。 這里插個(gè)題外話，現(xiàn)在很多互聯(lián)網(wǎng)公司開(kāi)始推出數(shù)據(jù)中臺(tái)，我覺(jué)得和數(shù)據(jù)庫(kù)系統(tǒng)提供SQL查詢語(yǔ)句的封裝是類(lèi)似的概念：由于業(yè)務(wù)更加復(fù)雜，但迭代需求更快，如果每次實(shí)現(xiàn)新的業(yè)務(wù)或報(bào)表都需要寫(xiě)很復(fù)雜的查詢語(yǔ)句，那豈不是效率很低。如何能夠根據(jù)業(yè)務(wù)邏輯需求，把數(shù)據(jù)標(biāo)準(zhǔn)化，接口化，提供比SQL語(yǔ)句更高層次的API來(lái)方便上層開(kāi)發(fā)。除了更進(jìn)一步提高效率，還能提高安全性和對(duì)數(shù)據(jù)的控制性。未準(zhǔn)就出現(xiàn)一套新的數(shù)據(jù)操作的標(biāo)準(zhǔn)，值得期待。
鋪墊做好了，進(jìn)入正題環(huán)節(jié)。在查詢語(yǔ)句中經(jīng)?？赡苌婕岸鄠€(gè)表的JOIN，比如我們示例中的訂單，賣(mài)家和買(mǎi)家。在實(shí)現(xiàn)過(guò)程中，我們可以選擇兩個(gè)表先JOIN變成一個(gè)暫存的中間表然后再和下一個(gè)表JOIN來(lái)獲得最終結(jié)果（當(dāng)然也有一些高級(jí)的支持多表同時(shí)JOIN的算子操作，就不在這篇進(jìn)行深入了）因此，只要提供兩個(gè)表JOIN的算子操作，就能依次實(shí)現(xiàn)多表JOIN，得到最終結(jié)果。今天討論的實(shí)現(xiàn)都針對(duì)兩個(gè)表。
其次，和討論排序以及聚合一樣，為了估計(jì)和比較時(shí)間復(fù)雜度，我們假設(shè)有兩個(gè)表，表A和表B；分別有M個(gè)block(頁(yè))，m個(gè)row以及N個(gè)Block和n個(gè)row的數(shù)據(jù)，并且假設(shè)M < N 和 m < n。最后，因?yàn)榻^大部分的JOIN都涉及equality join，也就是JOIN的where condition里面是等式比如（WHERE A.id = B.id），今天討論的JOIN實(shí)現(xiàn)都是基于equality join。
NestedLoopJoin：看似暴力的兩層for循環(huán)
如果有兩個(gè)表，讓你在應(yīng)用層做join，最容易想到的是什么方法？你可能應(yīng)口而出，可以用兩層for循環(huán)：第一層for循環(huán)表A的每一個(gè)row，然后嵌套內(nèi)部另一層表B的for循環(huán)，循環(huán)體內(nèi)做具體的join邏輯，如果滿足條件，就輸出一個(gè)joint的結(jié)果，代碼示例如下圖所示：
這就是我們今天介紹的第一個(gè)JOIN算子實(shí)現(xiàn)，NestedLoopJoin；名副其實(shí)的兩層for循環(huán)。如果表A和表B都能放進(jìn)內(nèi)存里，那總共的IO時(shí)間復(fù)雜度就是M + N：只需要讀取M + N個(gè)page。那如果內(nèi)存有限，每次每個(gè)表只能讀取一個(gè)page，又該怎么改進(jìn)呢？改進(jìn)的代碼如下圖所示：
如代碼所示，先讀取一個(gè)外層表的block，然后依次讀取內(nèi)層表的block，比較結(jié)束后再讀取下一個(gè)。這種時(shí)間下的IO cost是多少？應(yīng)該是 M + M * N。由此也可見(jiàn)，在運(yùn)行NestedLoopJoin時(shí)，應(yīng)該盡量把小的表放在外層循環(huán)中來(lái)減少I(mǎi)O次數(shù)。
這里，給大家出一道思考題，現(xiàn)在假設(shè)系統(tǒng)允許分配B個(gè)page給這個(gè)join算子，應(yīng)該怎么分配讀取才能最優(yōu)，最后IO時(shí)間復(fù)雜度又是多少呢？
有同學(xué)問(wèn)，還能不能進(jìn)一步優(yōu)化，答案是可以的。時(shí)間復(fù)雜度的大頭主要在M * N， 有什么辦法可以優(yōu)化這一塊？要想辦法避免對(duì)表B進(jìn)行全表掃描。優(yōu)化方法就是，如果表B在對(duì)應(yīng)的join鍵上建立索引，那我們就能用Index Scan來(lái)取代全表掃描。這就是NestedLoopIndexJoin。假設(shè)每次Index Scan的時(shí)間是常數(shù)C，它的時(shí)間復(fù)雜度就是 M + m * C。相較于前面 block-based NestedLoopJoin又提高了不少。
總結(jié)一下，我們第一個(gè)介紹的Join實(shí)現(xiàn)就是NestedLoopJoin，看似暴力的2層for循環(huán)。同時(shí)，也引出了block-based和內(nèi)層循環(huán)用IndexScan替代的優(yōu)化。
SortMergeJoin：Merge 2 sorted List
做過(guò)LeetCode的同學(xué)肯定都知道這題，Merge 2 sorted list。只要對(duì)每個(gè)list維護(hù)一個(gè)指針，然后相互比較后移即可。其實(shí)這個(gè)思路同樣可以應(yīng)用到表的JOIN上，只要對(duì)兩個(gè)表分別根據(jù)JOIN鍵做排序，然后在JOIN時(shí)，對(duì)每個(gè)表維護(hù)一個(gè)指針，當(dāng)兩邊指針的鍵值相同，就可以輸出JOIN的row。指針不斷后移，直到一方終止為止。代碼如下圖所示：
從IO的時(shí)間復(fù)雜度來(lái)看，又是多少呢？在講排序那章的時(shí)候我們已經(jīng)討論過(guò)，對(duì)M個(gè)page的表做排序，復(fù)雜度是2M * (log2M)。因此，總共的時(shí)間復(fù)雜度是M + N + 2M * (log2M) + 2N * (log2N)。因?yàn)闆](méi)有M*N這一項(xiàng)，因此當(dāng)兩個(gè)表都比較大的情況下，性能是優(yōu)于NestedLoopJoin的。
除了性能進(jìn)步，SortMergeJoin還有什么好的特性？和BTreeIndexScan一樣，SortMergeJoin后輸出的tuples是已經(jīng)排過(guò)序的。因此，如果上層的SQL語(yǔ)句還有對(duì)應(yīng)鍵排序的需求，就不再需要額外排序了。并且排序的需求不單單指ORDER BY語(yǔ)句，上一期提到過(guò)的，作組隊(duì)聚合(group aggregation)的時(shí)候，有序的tuple就不需要額外建立Hash表，可以直接用SortGroupByAgg來(lái)實(shí)現(xiàn)。另外，如果系統(tǒng)在JOIN前發(fā)現(xiàn)一方或者兩方都已經(jīng)排序過(guò)，同樣在JOIN時(shí)就可以直接使用MERGE JOIN。很多情況下，排序是一個(gè)一勞永逸的過(guò)程，一旦排序后，上層的語(yǔ)句可能都能獲益。
總結(jié)一下，本章介紹的第二個(gè)JOIN算子實(shí)現(xiàn)是SortMergeJoin，分別對(duì)兩張表根據(jù)JOIN鍵排序然后合并。
HashJoin：最高效的Join
說(shuō)完了利用排序來(lái)作JOIN，結(jié)合上一節(jié)篇章中我們提過(guò)的，實(shí)現(xiàn)聚類(lèi)可以用排序或者哈希表。排序和哈希表在數(shù)據(jù)庫(kù)算子里有那么些既生瑜何生亮的即視感。你是不是也預(yù)料到了，在表JOIN的時(shí)候，哈希表依然作為排序的對(duì)手出現(xiàn)。這正是我們要介紹的最后一種實(shí)現(xiàn)HashJoin，并且HashJoin再一次扮演了亮的角色。HashJoin算法很直觀，對(duì)相對(duì)較小的表表A，根據(jù)join condition來(lái)建立哈希表。然后對(duì)表B，只要依次讀入數(shù)據(jù)去和哈希表里的值去匹配，如果匹配，那就生成一個(gè)新的tuple。代碼如下圖所示：
下面來(lái)計(jì)算IO時(shí)間復(fù)雜度，如果假設(shè)較小的表A建立的哈希表能夠全部放進(jìn)內(nèi)存的話，IO時(shí)間復(fù)雜度只有 M+N。
按照這種方式，假設(shè)將較小的外部表M建立哈希表，如果能全部放進(jìn)內(nèi)存的話，然后對(duì)N表進(jìn)行全表掃描并且對(duì)比hash。IO時(shí)間復(fù)雜度只有 M + N。如果表A比較大，不能全部放進(jìn)內(nèi)存的話，我們又要借助外部哈希表的算法來(lái)分而治之。首先，我們用一個(gè)哈希函數(shù)把表A和表B分別劃分到x個(gè)bucket，如果在劃分的過(guò)程中發(fā)現(xiàn)某個(gè)bucket依然很大，可以借助遞歸思想，繼續(xù)劃分。我們稱(chēng)之為partition phase。Partition phase的IO復(fù)雜度是2 * (M + N)，因?yàn)樾枰阉械谋鞟和表B讀取到內(nèi)存在寫(xiě)回文件系統(tǒng)。第二階段就是對(duì)于每個(gè)bucket，分別讀取表A和表B然后建立哈希表做JOIN，稱(chēng)之為probing phase。這個(gè)階段會(huì)再次讀取所有表A和表B的數(shù)據(jù)，因此是 M + N。因此，HASH JOIN的時(shí)間復(fù)雜度，在即使需要依賴外部哈希表的情況下，依然是線性的 3*(M+N)。所以在絕大多數(shù)的情況下，性能都是最優(yōu)的。
總結(jié)一下，本章介紹的最后一個(gè)JOIN實(shí)現(xiàn)是HashJoin，通過(guò)對(duì)相對(duì)較小的表建立哈希表，然后讀取另一個(gè)表來(lái)匹配生成join rows。
總結(jié)
總結(jié)時(shí)刻，本章我們?cè)敿?xì)介紹了三種JOIN算子的實(shí)現(xiàn)，分析了它們的適用場(chǎng)景和時(shí)間復(fù)雜度。至此，數(shù)據(jù)庫(kù)內(nèi)和雜談覆蓋了常見(jiàn)算子的實(shí)現(xiàn)。各位讀者可以回想一下寫(xiě)過(guò)的SQL，是否能能夠使用我們討論過(guò)的算子組合成算子樹(shù)來(lái)實(shí)現(xiàn)這些查詢語(yǔ)句。
說(shuō)了那么多種JOIN，讀者可能會(huì)想，即然已經(jīng)說(shuō)了HashJoin普遍情況下性能最優(yōu)，為什么還需要實(shí)現(xiàn)其他JOIN呢？因?yàn)樵谔囟ǖ那闆r下，NestedLoopIndexScan可能會(huì)比HashJoin更快，或者在需要排序的情況下，SortMergeJoin也可能更有優(yōu)勢(shì)。影響因素有具體的查詢語(yǔ)句，表A和表B的大小，join鍵值的分布，以及是否對(duì)join鍵值有index等等。數(shù)據(jù)庫(kù)在執(zhí)行語(yǔ)句的時(shí)候，需要通盤(pán)考慮這些影響因素來(lái)決定最后具體使用哪種JOIN算子。而做這個(gè)決定的就是咱們下一期要講的內(nèi)容：數(shù)據(jù)庫(kù)的大腦 -- 優(yōu)化器。盡情期待。
