歡迎閱讀數(shù)據(jù)庫內(nèi)核雜談！這期我們重新回歸主線劇情棺榔，繼續(xù)討論執(zhí)行算子的實現(xiàn)彪标。相對簡單的算子如limit或者是projection，在內(nèi)核雜談的第一期(一小時數(shù)據(jù)庫實現(xiàn))就已經(jīng)討論過掷豺，不再贅述捞烟。繼上節(jié)討論了排序和聚合的實現(xiàn)薄声，我們對單個表的大部分操作都覆蓋了。但數(shù)據(jù)庫強大的地方在于题画，它能夠把現(xiàn)實中的某一塊業(yè)務(wù)默辨，映射地表達(dá)成一系列的表的集合，并且其查詢語句SQL支持多個表相關(guān)聯(lián)的查詢操作苍息。這種連接多表的查詢使得數(shù)據(jù)庫的功能得到了一個質(zhì)的飛躍缩幸。對應(yīng)用開發(fā)者而言，相當(dāng)于打開了一個新世界的大門竞思。原本一個個獨立的表表谊，因為連接而產(chǎn)生了無窮多種可能。這期盖喷，咱們就來細(xì)聊一下表與表之間的JOIN(連接)算子的實現(xiàn)爆办。
為什么需要JOIN?
在說具體實現(xiàn)前，咱們先細(xì)聊一下為什么數(shù)據(jù)庫需要支持JOIN课梳。這個問題距辆，甚至可以再退一步到為什么數(shù)據(jù)庫需要有多個表？其實答案很簡單暮刃，上文都提到了：因為現(xiàn)實中的事物就是復(fù)雜跨算，多樣的。多個表之間的關(guān)系能方便地和現(xiàn)實世界的事物映射起來椭懊，并且這種映射更直觀诸蚕，更能夠讓人接受。就像面向?qū)ο缶幊桃粯友踱峙挛覀兌疾荒芟胂笕绻嫦驅(qū)ο缶幊讨荒軇?chuàng)建一種類型的對象吧背犯。
除了方便映射實物，業(yè)務(wù)邏輯同樣需要JOIN狂窑。舉個例子，假設(shè)現(xiàn)在有個簡單的電商系統(tǒng)有買家桑腮，賣家和訂單三張表泉哈，數(shù)據(jù)科學(xué)家想要查詢2018年，對于上浩铺郑客戶的銷售額最高的前3位賣家信息丛晦。這么一個簡單的查詢其實就用到了每個表里的信息，需要從買家表里得到賣家信息提陶，從買家表里得到地址是上海的買家ID烫沙，然后對訂單表以賣家ID做組隊聚合，最后對銷售總額進(jìn)行排序并取前3隙笆。讀者可能想到锌蓄，這些業(yè)務(wù)邏輯其實也可以放在應(yīng)用層做升筏，的確如此(并且，如果是使用某些NoSQL的用戶瘸爽，因為還不支持JOIN您访，應(yīng)用層實現(xiàn)是唯一的選擇)。放在應(yīng)用層有下面這些短處剪决，一是執(zhí)行效率方面肯定不如在數(shù)據(jù)庫高效灵汪；二是數(shù)據(jù)一致性和正確性得不到保證。假設(shè)在多用戶的情形下柑潦，有多個用戶同時在更新數(shù)據(jù)和查詢數(shù)據(jù)享言，如何保證查詢數(shù)據(jù)的正確性。由于應(yīng)用層沒有數(shù)據(jù)庫系統(tǒng)的全局觀渗鬼，在保證對多用戶的支持上實現(xiàn)會更加復(fù)雜览露。業(yè)務(wù)驅(qū)動實現(xiàn)，數(shù)據(jù)庫系統(tǒng)就推出了SQL查詢語句讓實現(xiàn)業(yè)務(wù)的程序員通過構(gòu)建不同的SQL語句就能得到相應(yīng)的信息乍钻，而把復(fù)雜的執(zhí)行邏輯肛循，資源管理，多用戶協(xié)調(diào)等等都封裝進(jìn)了數(shù)據(jù)庫內(nèi)部银择。這樣不僅提高了整體執(zhí)行效率多糠，也大大簡化了業(yè)務(wù)邏輯的開發(fā)工作。 這里插個題外話浩考，現(xiàn)在很多互聯(lián)網(wǎng)公司開始推出數(shù)據(jù)中臺夹孔，我覺得和數(shù)據(jù)庫系統(tǒng)提供SQL查詢語句的封裝是類似的概念：由于業(yè)務(wù)更加復(fù)雜，但迭代需求更快析孽，如果每次實現(xiàn)新的業(yè)務(wù)或報表都需要寫很復(fù)雜的查詢語句搭伤，那豈不是效率很低。如何能夠根據(jù)業(yè)務(wù)邏輯需求袜瞬，把數(shù)據(jù)標(biāo)準(zhǔn)化怜俐，接口化，提供比SQL語句更高層次的API來方便上層開發(fā)邓尤。除了更進(jìn)一步提高效率拍鲤，還能提高安全性和對數(shù)據(jù)的控制性。未準(zhǔn)就出現(xiàn)一套新的數(shù)據(jù)操作的標(biāo)準(zhǔn)汞扎，值得期待季稳。
鋪墊做好了，進(jìn)入正題環(huán)節(jié)澈魄。在查詢語句中經(jīng)尘笆螅可能涉及多個表的JOIN，比如我們示例中的訂單痹扇，賣家和買家铛漓。在實現(xiàn)過程中溯香，我們可以選擇兩個表先JOIN變成一個暫存的中間表然后再和下一個表JOIN來獲得最終結(jié)果（當(dāng)然也有一些高級的支持多表同時JOIN的算子操作，就不在這篇進(jìn)行深入了）因此票渠，只要提供兩個表JOIN的算子操作逐哈，就能依次實現(xiàn)多表JOIN，得到最終結(jié)果问顷。今天討論的實現(xiàn)都針對兩個表昂秃。
其次，和討論排序以及聚合一樣杜窄，為了估計和比較時間復(fù)雜度肠骆，我們假設(shè)有兩個表，表A和表B塞耕；分別有M個block(頁)蚀腿，m個row以及N個Block和n個row的數(shù)據(jù)，并且假設(shè)M < N 和 m < n扫外。最后莉钙，因為絕大部分的JOIN都涉及equality join，也就是JOIN的where condition里面是等式比如（WHERE A.id = B.id）筛谚，今天討論的JOIN實現(xiàn)都是基于equality join磁玉。
NestedLoopJoin：看似暴力的兩層for循環(huán)
如果有兩個表，讓你在應(yīng)用層做join驾讲，最容易想到的是什么方法蚊伞？你可能應(yīng)口而出，可以用兩層for循環(huán)：第一層for循環(huán)表A的每一個row吮铭，然后嵌套內(nèi)部另一層表B的for循環(huán)时迫，循環(huán)體內(nèi)做具體的join邏輯，如果滿足條件谓晌，就輸出一個joint的結(jié)果掠拳，代碼示例如下圖所示：
這就是我們今天介紹的第一個JOIN算子實現(xiàn)，NestedLoopJoin纸肉；名副其實的兩層for循環(huán)溺欧。如果表A和表B都能放進(jìn)內(nèi)存里，那總共的IO時間復(fù)雜度就是M + N：只需要讀取M + N個page毁靶。那如果內(nèi)存有限胧奔，每次每個表只能讀取一個page逊移，又該怎么改進(jìn)呢预吆？改進(jìn)的代碼如下圖所示：
如代碼所示，先讀取一個外層表的block胳泉，然后依次讀取內(nèi)層表的block拐叉，比較結(jié)束后再讀取下一個岩遗。這種時間下的IO cost是多少？應(yīng)該是 M + M * N凤瘦。由此也可見宿礁，在運行NestedLoopJoin時，應(yīng)該盡量把小的表放在外層循環(huán)中來減少IO次數(shù)蔬芥。
這里梆靖，給大家出一道思考題，現(xiàn)在假設(shè)系統(tǒng)允許分配B個page給這個join算子笔诵，應(yīng)該怎么分配讀取才能最優(yōu)返吻，最后IO時間復(fù)雜度又是多少呢？
有同學(xué)問乎婿，還能不能進(jìn)一步優(yōu)化测僵，答案是可以的。時間復(fù)雜度的大頭主要在M * N谢翎， 有什么辦法可以優(yōu)化這一塊捍靠？要想辦法避免對表B進(jìn)行全表掃描。優(yōu)化方法就是森逮，如果表B在對應(yīng)的join鍵上建立索引榨婆，那我們就能用Index Scan來取代全表掃描。這就是NestedLoopIndexJoin吊宋。假設(shè)每次Index Scan的時間是常數(shù)C纲辽，它的時間復(fù)雜度就是 M + m * C。相較于前面 block-based NestedLoopJoin又提高了不少璃搜。
總結(jié)一下拖吼，我們第一個介紹的Join實現(xiàn)就是NestedLoopJoin，看似暴力的2層for循環(huán)这吻。同時吊档，也引出了block-based和內(nèi)層循環(huán)用IndexScan替代的優(yōu)化。
SortMergeJoin：Merge 2 sorted List
做過LeetCode的同學(xué)肯定都知道這題唾糯，Merge 2 sorted list怠硼。只要對每個list維護(hù)一個指針，然后相互比較后移即可移怯。其實這個思路同樣可以應(yīng)用到表的JOIN上香璃，只要對兩個表分別根據(jù)JOIN鍵做排序，然后在JOIN時舟误，對每個表維護(hù)一個指針葡秒，當(dāng)兩邊指針的鍵值相同，就可以輸出JOIN的row。指針不斷后移眯牧，直到一方終止為止蹋岩。代碼如下圖所示：
從IO的時間復(fù)雜度來看，又是多少呢学少？在講排序那章的時候我們已經(jīng)討論過剪个，對M個page的表做排序，復(fù)雜度是2M * (log2M)版确。因此扣囊，總共的時間復(fù)雜度是M + N + 2M * (log2M) + 2N * (log2N)。因為沒有M*N這一項绒疗，因此當(dāng)兩個表都比較大的情況下如暖，性能是優(yōu)于NestedLoopJoin的。
除了性能進(jìn)步忌堂，SortMergeJoin還有什么好的特性盒至？和BTreeIndexScan一樣，SortMergeJoin后輸出的tuples是已經(jīng)排過序的士修。因此枷遂，如果上層的SQL語句還有對應(yīng)鍵排序的需求，就不再需要額外排序了棋嘲。并且排序的需求不單單指ORDER BY語句酒唉，上一期提到過的，作組隊聚合(group aggregation)的時候沸移，有序的tuple就不需要額外建立Hash表痪伦，可以直接用SortGroupByAgg來實現(xiàn)。另外雹锣，如果系統(tǒng)在JOIN前發(fā)現(xiàn)一方或者兩方都已經(jīng)排序過网沾，同樣在JOIN時就可以直接使用MERGE JOIN。很多情況下蕊爵，排序是一個一勞永逸的過程辉哥，一旦排序后，上層的語句可能都能獲益攒射。
總結(jié)一下醋旦，本章介紹的第二個JOIN算子實現(xiàn)是SortMergeJoin，分別對兩張表根據(jù)JOIN鍵排序然后合并会放。
HashJoin：最高效的Join
說完了利用排序來作JOIN饲齐，結(jié)合上一節(jié)篇章中我們提過的，實現(xiàn)聚類可以用排序或者哈希表咧最。排序和哈希表在數(shù)據(jù)庫算子里有那么些既生瑜何生亮的即視感捂人。你是不是也預(yù)料到了甩骏，在表JOIN的時候，哈希表依然作為排序的對手出現(xiàn)先慷。這正是我們要介紹的最后一種實現(xiàn)HashJoin，并且HashJoin再一次扮演了亮的角色咨察。HashJoin算法很直觀论熙，對相對較小的表表A，根據(jù)join condition來建立哈希表摄狱。然后對表B脓诡，只要依次讀入數(shù)據(jù)去和哈希表里的值去匹配，如果匹配媒役，那就生成一個新的tuple祝谚。代碼如下圖所示：
下面來計算IO時間復(fù)雜度，如果假設(shè)較小的表A建立的哈希表能夠全部放進(jìn)內(nèi)存的話酣衷，IO時間復(fù)雜度只有 M+N交惯。
按照這種方式，假設(shè)將較小的外部表M建立哈希表穿仪，如果能全部放進(jìn)內(nèi)存的話席爽，然后對N表進(jìn)行全表掃描并且對比hash。IO時間復(fù)雜度只有 M + N啊片。如果表A比較大只锻，不能全部放進(jìn)內(nèi)存的話，我們又要借助外部哈希表的算法來分而治之紫谷。首先齐饮，我們用一個哈希函數(shù)把表A和表B分別劃分到x個bucket，如果在劃分的過程中發(fā)現(xiàn)某個bucket依然很大笤昨，可以借助遞歸思想祖驱，繼續(xù)劃分。我們稱之為partition phase瞒窒。Partition phase的IO復(fù)雜度是2 * (M + N)羹膳，因為需要把所有的表A和表B讀取到內(nèi)存在寫回文件系統(tǒng)。第二階段就是對于每個bucket根竿，分別讀取表A和表B然后建立哈希表做JOIN陵像，稱之為probing phase。這個階段會再次讀取所有表A和表B的數(shù)據(jù)寇壳，因此是 M + N醒颖。因此，HASH JOIN的時間復(fù)雜度壳炎，在即使需要依賴外部哈希表的情況下泞歉，依然是線性的 3*(M+N)逼侦。所以在絕大多數(shù)的情況下，性能都是最優(yōu)的腰耙。
總結(jié)一下榛丢，本章介紹的最后一個JOIN實現(xiàn)是HashJoin，通過對相對較小的表建立哈希表挺庞，然后讀取另一個表來匹配生成join rows晰赞。
總結(jié)
總結(jié)時刻，本章我們詳細(xì)介紹了三種JOIN算子的實現(xiàn)选侨，分析了它們的適用場景和時間復(fù)雜度掖鱼。至此，數(shù)據(jù)庫內(nèi)和雜談覆蓋了常見算子的實現(xiàn)援制。各位讀者可以回想一下寫過的SQL戏挡，是否能能夠使用我們討論過的算子組合成算子樹來實現(xiàn)這些查詢語句。
說了那么多種JOIN晨仑，讀者可能會想褐墅，即然已經(jīng)說了HashJoin普遍情況下性能最優(yōu)，為什么還需要實現(xiàn)其他JOIN呢洪己？因為在特定的情況下掌栅，NestedLoopIndexScan可能會比HashJoin更快，或者在需要排序的情況下码泛，SortMergeJoin也可能更有優(yōu)勢猾封。影響因素有具體的查詢語句，表A和表B的大小噪珊，join鍵值的分布晌缘，以及是否對join鍵值有index等等。數(shù)據(jù)庫在執(zhí)行語句的時候痢站，需要通盤考慮這些影響因素來決定最后具體使用哪種JOIN算子磷箕。而做這個決定的就是咱們下一期要講的內(nèi)容：數(shù)據(jù)庫的大腦 -- 優(yōu)化器。盡情期待阵难。
