2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

什么是 Sort Merge Join

在開(kāi)始閱讀源碼之前, 我們來(lái)看看什么是 Sort Merge Join (SMJ)，定義可以看 wikipedia。簡(jiǎn)單說(shuō)來(lái)就是將 Join 的兩個(gè)表，首先根據(jù)連接屬性進(jìn)行排序，然后進(jìn)行一次掃描歸并, 進(jìn)而就可以得出最后的結(jié)果。這個(gè)算法最大的消耗在于對(duì)內(nèi)外表數(shù)據(jù)進(jìn)行排序，而當(dāng)連接列為索引列時(shí)，我們可以利用索引的有序性避免排序帶來(lái)的消耗, 所以通常在查詢優(yōu)化器中，連接列為索引列的情況下可以考慮選擇使用 SMJ。

TiDB Sort Merge Join 實(shí)現(xiàn)

執(zhí)行過(guò)程

TiDB 的實(shí)現(xiàn)代碼在 tidb/executor/merge_join.go 中 MergeJoinExec.NextChunk 是這個(gè)算子的入口。下面以 SELECT * FROM A JOIN B ON A.a = B.a 為例，對(duì) SMJ 執(zhí)行過(guò)程進(jìn)行簡(jiǎn)述，假設(shè)此時(shí)外表為 A，內(nèi)表為 B，join-keys 為 a，A，B 表的 a 列上都有索引：

順序讀取外表 A 直到 join-keys 中出現(xiàn)另外的值，把相同 keys 的行放入數(shù)組 a1，同樣的規(guī)則讀取內(nèi)表 B，把相同 keys 的行放入數(shù)組 a2。如果外表數(shù)據(jù)或者內(nèi)表數(shù)據(jù)讀取結(jié)束，退出。

從 a1 中讀取當(dāng)前第一行數(shù)據(jù)，設(shè)為 v1。從 a2 中讀取當(dāng)前第一行數(shù)據(jù)，設(shè)為 v2。

根據(jù) join-keys 比較 v1，v2，結(jié)果分為幾種情況：

• cmpResult > 0, 表示 v1 大于 v2，把當(dāng)前 a2 的數(shù)據(jù)丟棄，從內(nèi)表讀取下一批數(shù)據(jù)，讀取方法同 1。重復(fù) 2。
• cmpResult < 0, 表示 v1 小于 v2，說(shuō)明外表的 v1 沒(méi)有內(nèi)表的值與之相同，把外表數(shù)據(jù)輸出給 resultGenerator（不同的連接類型會(huì)有不同的結(jié)果輸出，例如外連接會(huì)把不匹配的外表數(shù)據(jù)輸出）。
• cmpResult == 0, 表示 v1 等于 v2。那么遍歷 a1 里面的數(shù)據(jù)，跟 a2 的數(shù)據(jù)，輸出給 resultGenerator 作一次連接。

回到步驟 1。

下面的圖展示了 SMJ 的過(guò)程：

讀取內(nèi)表 / 外表數(shù)據(jù)

我們分別通過(guò) fetchNextInnerRows 或者 fetchNextOuterRows 讀取內(nèi)表和外表的數(shù)據(jù)。這兩個(gè)函數(shù)實(shí)現(xiàn)的功能類似，這里只詳述函數(shù) fetchNextInnerRows 的實(shí)現(xiàn)。

MergeSortExec 算子讀取數(shù)據(jù)，是通過(guò)迭代器 readerIterator 完成，readerIterator 可以順序讀取數(shù)據(jù)。MergeSortExec 算子維護(hù)兩個(gè) readerIterator：outerIter 和 innerIter，它們?cè)?buildMergeJoin 函數(shù)中被構(gòu)造。

真正讀取數(shù)據(jù)的操作是在 readerIterator.nextSelectedRow 中完成, 這里會(huì)通過(guò) ri.reader.NextChunk 每次讀取一個(gè) Chunk 的數(shù)據(jù)，關(guān)于 Chunk 的相關(guān)內(nèi)容，可以查看我們之前的文章 TiDB 源碼閱讀系列文章（十）Chunk 和執(zhí)行框架簡(jiǎn)介 。

這里值得注意的是，我們通過(guò) expression.VectorizedFilter 對(duì)外表數(shù)據(jù)進(jìn)行過(guò)濾，返回一個(gè) curSelected 布爾數(shù)組，用于外表的每一行數(shù)據(jù)是否是滿足 filter 過(guò)濾條件。以 select * from t1 left outer join t2 on t1.a=100; 為例, 這里的 filter 是 t1.a=100, 對(duì)于沒(méi)有通過(guò)這個(gè)過(guò)濾條件的行，我們通過(guò) ri.joinResultGenerator.emitToChunk 函數(shù)發(fā)送給 resultGenerator, 這個(gè) resultGenerator 是一個(gè) interface，具體是否輸出這行數(shù)據(jù)，會(huì)由 join 的類型決定，比如外連接則會(huì)輸出，內(nèi)連接則會(huì)忽略。具體關(guān)于 resultGenerator, 可以參考之前的文章：TiDB 源碼閱讀系列文章（九）Hash Join

rowsWithSameKey 通過(guò) nextSelectedRow 不斷讀取下一行數(shù)據(jù)，并通過(guò)對(duì)每行數(shù)據(jù)的 join-keys 進(jìn)行判斷是不是屬于同一個(gè) join-keys，如果是，會(huì)把相同 join-keys 的行分別放入到 innerChunkRows 和 outerIter4Row 數(shù)組中。然后對(duì)其分別建立迭代器 innerIter4Row 和 outerIter4Row。在 SMJ 中的執(zhí)行過(guò)程中，會(huì)利用這兩個(gè)迭代器來(lái)獲取數(shù)據(jù)進(jìn)行真正的比較得出 join result。

Merge-Join

實(shí)現(xiàn) Merge-Join 邏輯的代碼在函數(shù) MergeJoinExec.joinToChunk, 對(duì)內(nèi)外表迭代器的當(dāng)前數(shù)據(jù)根據(jù)各自的 join-keys 作對(duì)比，有如下幾個(gè)結(jié)果：

• cmpResult > 0，代表外表當(dāng)前數(shù)據(jù)大于內(nèi)表數(shù)據(jù)，那么通過(guò) fetchNextInnerRows 直接讀取下一個(gè)內(nèi)表數(shù)據(jù)，然后重新比較即可。

• cmpResult < 0，代表外表當(dāng)前數(shù)據(jù)小于內(nèi)表數(shù)據(jù)，這個(gè)時(shí)候就分幾種情況了，如果是外連接，那么需要輸出外表數(shù)據(jù) + NULL，如果是內(nèi)連接，那么這個(gè)外表數(shù)據(jù)就被忽略，對(duì)于這個(gè)不同邏輯的處理，統(tǒng)一由 e.resultGenerator 來(lái)控制，我們只需要把外表數(shù)據(jù)通過(guò) e.resultGenerator.emitToChunk 調(diào)用它即可。然后通過(guò) fetchNextOuterRows 讀取下一個(gè)外表數(shù)據(jù)，重新比較。

• cmpResult == 0，代表外表當(dāng)前數(shù)據(jù)等于內(nèi)表當(dāng)前數(shù)據(jù)，這個(gè)時(shí)候就把外表數(shù)據(jù)跟內(nèi)表當(dāng)前數(shù)據(jù)做一次連接，通過(guò) e.resultGenerator.emitToChunk 生成結(jié)果。之后外表跟內(nèi)表分別獲取下一個(gè)數(shù)據(jù)，重新開(kāi)始比較。

重復(fù)上面的過(guò)程，直到外表或者內(nèi)表數(shù)據(jù)被遍歷完，退出 Merge-Join 的過(guò)程。

更多

我們上面的分析代碼基于 Source-code 分支，可能大家已經(jīng)發(fā)現(xiàn)了一些問(wèn)題，比如我們會(huì)一次性讀取內(nèi)外表的 Join group（相同的 key）。這里如果相同的 key 比較多，是有內(nèi)存 OOM 的風(fēng)險(xiǎn)的。針對(duì)這個(gè)問(wèn)題，我們?cè)谧钚碌?master 分支做了幾個(gè)事情來(lái)優(yōu)化：

外表其實(shí)不需要把相同的 keys 一次性都讀取上來(lái)， 它只需要按次迭代外表數(shù)據(jù)，再跟內(nèi)表逐一對(duì)比作連接即可。這里至少可以減少外表發(fā)生 OOM 的問(wèn)題，可以大大減少 OOM 的概率。

對(duì)于內(nèi)表，我們對(duì) OOM 也不是沒(méi)有辦法，我們用 memory.Tracker 這個(gè)內(nèi)存追蹤器來(lái)記錄當(dāng)前內(nèi)表已經(jīng)使用的中間結(jié)果的內(nèi)存大小，如果它超過(guò)我們?cè)O(shè)置的閾值，我們會(huì)采取輸出日志或者終止 SQL 繼續(xù)運(yùn)行的方法來(lái)規(guī)避 OOM 的發(fā)生。關(guān)于 memory.Tracker 我們不在此展開(kāi)，可以留意我們后續(xù)的源碼分析文章。

后續(xù)我們還會(huì)在 Merge-Join 方面做一些優(yōu)化， 比如我們可以做多路歸并，中間結(jié)果存外存等等，敬請(qǐng)期待。

作者：姚維

轉(zhuǎn)載于:https://my.oschina.net/zhaiyuan/blog/1924293

總結(jié)

以上是生活随笔為你收集整理的TiDB 源码阅读系列文章（十五）Sort Merge Join的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。