作者 | 劉垚

編輯 | 爾悅

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

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

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

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

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

子查詢部分

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

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

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

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

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

Join 部分

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

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

Hash Join

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

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

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

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

Merge Join

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

Nestloop Join

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

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

寫在最后

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