作者 | 劉垚

編輯 | 爾悅

小 T 導(dǎo)讀：在使用或者實(shí)現(xiàn)分布式數(shù)據(jù)庫(kù)（Distributed Database）時(shí)，會(huì)面臨把一個(gè)表的數(shù)據(jù)按照一定的策略分散到各個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)上的情況，隨之而來的是多節(jié)點(diǎn)數(shù)據(jù)查詢復(fù)雜性的問題，例如 Join 和子查詢。本文將會(huì)為你解讀分布式數(shù)據(jù)庫(kù)下子查詢和 Join 等復(fù)雜 SQL 如何實(shí)現(xiàn)，來幫助你更好地解決上述問題。

首先簡(jiǎn)單講一下 SQL 的執(zhí)行過程：

SQL ==> Parser ==> Translate & Semantic Check ==> Optimizer ==> Coordinator ==> Executer

• Parser 產(chǎn)生的是語法樹，即 Abstract Syntax Tree；
• Translate & Semantic Check，這一步會(huì)從 Catalog 讀取元數(shù)據(jù)，用元數(shù)據(jù)完善語法樹，便于 Optimizer 使用。例如：常見的 select * from tableA，一般會(huì)在這一步把“*”換成 tableA 的列；
• Optimizer 產(chǎn)生的是優(yōu)化之后的邏輯執(zhí)行計(jì)劃，即 Optimized Logical Plan，執(zhí)行計(jì)劃是個(gè)有向無環(huán)圖，即 DAG；
• Coordinator 負(fù)責(zé)分發(fā)邏輯執(zhí)行計(jì)劃給各個(gè)節(jié)點(diǎn)去計(jì)算；
• Executer 會(huì)把邏輯執(zhí)行計(jì)劃轉(zhuǎn)成物理執(zhí)行計(jì)劃，即 Physical Plan。

開源的數(shù)據(jù)庫(kù)有很多，我們可以結(jié)合一些主流數(shù)據(jù)庫(kù)的源代碼來理解子查詢和 Join 的實(shí)現(xiàn)方式，比如關(guān)系型數(shù)據(jù)庫(kù) ：Impala、Presto、ClickHouse，時(shí)序數(shù)據(jù)庫(kù)（Time- Series Database）： TDengine 等。下面從子查詢和 Join 兩部分進(jìn)行分析。

子查詢部分

邏輯執(zhí)行計(jì)劃有多種 Node，分別對(duì)應(yīng)著 SQL 中的各種計(jì)算，包括 Scan Node、Join Node、Aggregate Node、Sort Node、Project Node 等等，相應(yīng)的物理執(zhí)行計(jì)劃的算子為 Scan Operator 、Join Operator、Aggregate Operator、Sort Operator、Project Operator 等等。而數(shù)據(jù)庫(kù)一般沒有計(jì)算子查詢的算子，這是因?yàn)閷⒊橄笳Z法樹轉(zhuǎn)成邏輯執(zhí)行計(jì)劃之后，就已經(jīng)沒有子查詢的概念了，其運(yùn)行邏輯是數(shù)據(jù)算子之間自下而上逐層傳遞，并逐層計(jì)算，并不特別計(jì)算子查詢。下面講一下分布式數(shù)據(jù)庫(kù)針對(duì)子查詢的一些相關(guān)處理。

首先，分布式數(shù)據(jù)庫(kù)的優(yōu)化器會(huì)將子查詢扁平化處理，這種方式一般分為兩種，一種是直接在語法樹（AST）上做子查詢扁平化（Subquery Flatten），另外一種是在生成邏輯執(zhí)行計(jì)劃時(shí)進(jìn)行扁平化。這兩種方式本質(zhì)上大同小異，都要保證語義的等價(jià)性。但也并不是所有的子查詢都能扁平化，有如下幾種特殊情況：

• 子查詢和父查詢都有聚集函數(shù)
• 子查詢有聚集函數(shù)，并且父查詢有分組計(jì)算（Group By）
• 子查詢有聚集函數(shù)，并且用子查詢聚集函數(shù)的結(jié)果關(guān)聯(lián)（Join）父查詢的表
• 父查詢有聚集函數(shù)，并且子查詢有分組計(jì)算（Group By）
• 子查詢有 Limit（限制返回結(jié)果的行數(shù)），并且父查詢有過濾條件（Where）或者分組計(jì)算、排序（Order By）
• 其他

基于 AST 進(jìn)行子查詢扁平化時(shí)，需要先遍歷語法數(shù)據(jù)，并按規(guī)則進(jìn)行判斷，進(jìn)而去除不必要的子查詢。對(duì)于生成邏輯執(zhí)行計(jì)劃時(shí)的子查詢扁平化，在生成 Plan Node 時(shí)需要先去除冗余的 Node，舉個(gè)例子，SQL：select colA from (select * from tA) group by colA;

一般來說，邏輯執(zhí)行計(jì)劃會(huì)有多個(gè)子計(jì)劃，通常在需要網(wǎng)絡(luò)傳輸時(shí)才會(huì)產(chǎn)生子計(jì)劃，需要注意的是子計(jì)劃和子查詢之間并沒有必然的聯(lián)系，即有子查詢不一定對(duì)應(yīng)一個(gè)子計(jì)劃。

Join 部分

首先，分布式數(shù)據(jù)庫(kù)會(huì)對(duì) Join 進(jìn)行優(yōu)化，包括 Join 消除（例如基于主鍵外鍵去除不必要的 Join）、外連接消除（Outer Join 轉(zhuǎn)成 Inner Join）、Join Order 優(yōu)化（基于數(shù)據(jù)的統(tǒng)計(jì)信息，用動(dòng)態(tài)規(guī)劃算法、貪心算法或遺傳算法等優(yōu)化 Table 的 Join 順序）等等。

再講一下 Join 的三種基本算法：Hash Join（必須要有等值連接條件，例如 t1.colA = t2.colB）、Merge Join（左表和右表的數(shù)據(jù)都是有序的，按連接條件中的列有序）、Nestloop Join（含有非等值連接條件并且數(shù)據(jù)無序）。在實(shí)際當(dāng)中，會(huì)把三種算法進(jìn)行混合使用，這是因?yàn)?Join 條件可以同時(shí)包含等值連接和非等值連接，例如 t1.colA = t2.colB AND t1.colC > t2.colC

Hash Join

在進(jìn)行 Join Order 優(yōu)化時(shí)，優(yōu)化器會(huì)調(diào)整左表和右表的順序，一般把小表放右邊，大表放左邊，并且選擇 Join 模式：Shuffle Join（按照關(guān)聯(lián)條件，同時(shí) shuffle 左表和右表，然后再計(jì)算 Join） 或 Boradcast Join（把右表廣播到左表所在的節(jié)點(diǎn)，注意左表不動(dòng)，然后再計(jì)算 Join）。一般是基于代價(jià)去選擇 Join Order 優(yōu)化，但考慮到統(tǒng)計(jì)信息可能會(huì)存在誤差，因此很多數(shù)據(jù)庫(kù)可以通過 Hint、Query Option 等方式，由用戶來指定 Join 順序、Join 模式等。

Hash Join 是目前最常用的 Join 算法，大部分?jǐn)?shù)據(jù)庫(kù)都實(shí)現(xiàn)了 Hash Join。這種算法會(huì)先讀取右表，并把右表的數(shù)據(jù)放入 Hash Map 里，如果存不下就會(huì)放入外存。通常情況下，各個(gè)數(shù)據(jù)庫(kù)都會(huì)實(shí)現(xiàn)自己的 Hash Map，很少直接使用 STL 或 Boost 等第三方庫(kù)中的 Hash Map，原因主要有兩點(diǎn)：

• 定制化 Hash Map 會(huì)提升 Join 計(jì)算速度。
• 定制化 Hash Map 能更準(zhǔn)確地控制內(nèi)存使用，當(dāng)內(nèi)存不足時(shí)，會(huì)使用外存，定制化 Hash Map 可以根據(jù) Join 算法，優(yōu)化 Swap 機(jī)制，減少 Swap 的數(shù)據(jù)量。Hash Map 的結(jié)構(gòu)如下：

右表可能含有重復(fù)的數(shù)據(jù)，所以會(huì)有 Duplicate Node。這里的重復(fù)數(shù)據(jù)是指 Join Key（Join 條件對(duì)應(yīng)的列）的數(shù)據(jù)重復(fù)，并且其他列不重復(fù)，所以要分別緩存。注意上述圖中，是通過 Hash 算法解決 Hash 沖突的問題，即不會(huì)把不同的 Join Key 放在同一個(gè)桶中。當(dāng)然，現(xiàn)實(shí)操作中也有把不同的 Join Key 放在同一個(gè)桶中的情況，那需要遍歷 List 才能確定查找的 Join Key 是否存在。

Merge Join

Merge Join 一般是在左表和右表的數(shù)據(jù)是有序的情況下使用。例如時(shí)序數(shù)據(jù)庫(kù) TDengine，數(shù)據(jù)按時(shí)間戳列有序，那么用時(shí)間戳列做 Join 時(shí)，TDengine database 會(huì)用 Merge Join 來計(jì)算，這樣的一個(gè)好處是處理速度非?？?，并且占用內(nèi)存非常小。

Nestloop Join

這種 Join 算法速度非常慢，但對(duì)于全功能數(shù)據(jù)庫(kù)而言是不可缺少的。使用這種算法時(shí)，可以結(jié)合索引來提速。

總結(jié)而言，Hash Join 使用最廣，適用于很多數(shù)據(jù)分析的場(chǎng)景，并且大部分?jǐn)?shù)據(jù)庫(kù)都支持；Merge Join 一般是在左右表數(shù)據(jù)有序時(shí)才會(huì)使用，不需要緩存數(shù)據(jù)，所以使用內(nèi)存非常少，計(jì)算速度是三種 Join 算法中最快的；Nestloop Join 性能很差，分布式數(shù)據(jù)庫(kù)一般很少使用，有些分布式數(shù)據(jù)庫(kù)就不支持，可以通過索引來加速 Nestloop Join。

寫在最后

上面我們對(duì)子查詢和 Join 兩種復(fù)雜 SQL 的實(shí)現(xiàn)方式做了具體解讀，大家可以結(jié)合一些開源數(shù)據(jù)庫(kù)的源代碼來理解，像 TDengine 的源代碼都可以在 GitHub 上看到，如果你對(duì)時(shí)序數(shù)據(jù)庫(kù)的復(fù)雜 SQL 實(shí)現(xiàn)有興趣，這就是一個(gè)不錯(cuò)的觀摩對(duì)象。也歡迎大家在下方評(píng)論區(qū)進(jìn)行交流。