相信大家都對(duì)大名鼎鼎的ClickHouse有一定的了解了，它強(qiáng)大的數(shù)據(jù)分析性能讓人印象深刻。但在字節(jié)大量生產(chǎn)使用中，發(fā)現(xiàn)了ClickHouse依然存在了一定的限制。例如：

缺少完整的upsert和delete操作

多表關(guān)聯(lián)查詢能力弱

集群規(guī)模較大時(shí)可用性下降（對(duì)字節(jié)尤其如此）

沒(méi)有資源隔離能力

因此，我們決定將ClickHouse能力進(jìn)行全方位加強(qiáng)，打造一款更強(qiáng)大的數(shù)據(jù)分析平臺(tái)。后面我們將從五個(gè)方面來(lái)和大家分享，此前兩篇內(nèi)容分別為大家介紹了“更新刪除”和“多表關(guān)聯(lián)查詢”，本篇將詳細(xì)介紹我們是如何構(gòu)建ClickHouse的查詢優(yōu)化器。

查詢優(yōu)化器有多重要？

在傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)中，如Oracle、DB2、MySQL，查詢優(yōu)化器都是作為幾個(gè)最重要的核心組件之一?？梢哉f(shuō)，沒(méi)有查詢優(yōu)化器的數(shù)據(jù)庫(kù)是不完整的。相對(duì) OLTP 而言在OLAP領(lǐng)域中更是如此；對(duì)于分析類場(chǎng)景，查詢更為復(fù)雜，計(jì)劃好壞的差異更大。一個(gè)優(yōu)秀的查詢優(yōu)化器可以防止用戶寫出不好的SQL導(dǎo)致執(zhí)行速度慢，能夠準(zhǔn)確的選擇出一條效率最高的執(zhí)行路徑，大幅度降低查詢時(shí)間。相應(yīng)的，一個(gè)不好的查詢優(yōu)化器，甚至?xí)尣樵冏兟?/p>

常見(jiàn)的優(yōu)化器邏輯分為兩類，一類叫“基于規(guī)則的優(yōu)化（RBO）”，另一類稱為“基于代價(jià)的優(yōu)化（CBO）”，實(shí)際應(yīng)用過(guò)程中應(yīng)當(dāng)兩類兼顧才能取得最佳效果。

基于規(guī)則的優(yōu)化

根據(jù)優(yōu)化規(guī)則對(duì)關(guān)系表達(dá)式進(jìn)行轉(zhuǎn)換，這里的轉(zhuǎn)換是說(shuō)一個(gè)關(guān)系表達(dá)式經(jīng)過(guò)優(yōu)化規(guī)則后會(huì)變成另外一個(gè)關(guān)系表達(dá)式，同時(shí)原有表達(dá)式會(huì)被裁剪掉，經(jīng)過(guò)一系列轉(zhuǎn)換后生成最終的執(zhí)行計(jì)劃。RBO中包含了一套有著嚴(yán)格順序的優(yōu)化規(guī)則，同樣一條SQL，無(wú)論讀取的表中數(shù)據(jù)是怎么樣的，最后生成的執(zhí)行計(jì)劃都是一樣的。同時(shí)，在RBO中SQL寫法的不同很有可能影響最終的執(zhí)行計(jì)劃，從而影響腳本性能。

基于代價(jià)的優(yōu)化

根據(jù)優(yōu)化規(guī)則對(duì)關(guān)系表達(dá)式進(jìn)行轉(zhuǎn)換，這里的轉(zhuǎn)換是說(shuō)一個(gè)關(guān)系表達(dá)式經(jīng)過(guò)優(yōu)化規(guī)則后會(huì)生成另外一個(gè)關(guān)系表達(dá)式，同時(shí)原有表達(dá)式也會(huì)保留，經(jīng)過(guò)一系列轉(zhuǎn)換后會(huì)生成多個(gè)執(zhí)行計(jì)劃，然后CBO會(huì)根據(jù)統(tǒng)計(jì)信息和代價(jià)模型(Cost Model)計(jì)算每個(gè)執(zhí)行計(jì)劃的Cost，從中挑選Cost最小的執(zhí)行計(jì)劃。

ByteHouse的查詢優(yōu)化器

目前主流的OLAP的引擎在查詢優(yōu)化器方面做的并不夠好，尤其是ClickHouse。眾所周知ClickHouse以快著稱，但是它的快是采用了力大飛磚的方式，需要用戶將數(shù)據(jù)預(yù)先生成大寬表，以避免過(guò)于復(fù)雜的多表查詢從而獲得高性能。而代價(jià)是，每次維度變化或新需求都需要大量操作，以及在必須使用多表關(guān)聯(lián)進(jìn)行分析的場(chǎng)景中顯得十分無(wú)力。

作為一個(gè)企業(yè)級(jí)的OLAP數(shù)據(jù)庫(kù)來(lái)說(shuō)一個(gè)完善且強(qiáng)大的優(yōu)化器是必不可少的，因此，ByteHouse從零開(kāi)始自研的了查詢優(yōu)化器。

查詢優(yōu)化的完整流程

上圖描述了整個(gè)查詢的執(zhí)行流程，從 SQL parse 到執(zhí)行期間所有內(nèi)容全部進(jìn)行了重新實(shí)現(xiàn)（其中紫色模塊），構(gòu)建了一套完整的且規(guī)范的查詢優(yōu)化器。

主要功能模塊

Analyzers

Analyzers 目錄包括兩部分功能：

一個(gè)是 QueryRewriter，一方面是通過(guò) AST 改寫的方式實(shí)現(xiàn)一些語(yǔ)法特性；我們同時(shí)支持 Clickhouse SQL 和標(biāo)準(zhǔn) SQL，所以另一方面是確保在 Clickhouse SQL 模式下 SQL 語(yǔ)義能和原生 Interpreter 執(zhí)行模式一致。

另一個(gè)是 QueryAnalyzer，用于對(duì)改寫完的 AST 進(jìn)行語(yǔ)義的分析和驗(yàn)證。Analyzer 區(qū)分 ANSI SQL 和 Clickhouse SQL 兩種模式。

QueryRewriter 針對(duì) ANSI SQL 的改寫主要有：

With CTE/view 展開(kāi)；

UDF 展開(kāi)；

特定函數(shù)的改寫，比如將 count(*) 改寫為 count()，將 countDistinct(...) 改寫為 uniqExact(...)；

QueryRewriter 針對(duì) Clickhouse SQL 的改寫主要有：

With CTE/view 展開(kāi)；

UDF 展開(kāi)；

特定函數(shù)的改寫；

JoinToSubquery 展開(kāi)，對(duì)應(yīng)于 Interpreter 鏈路下的 JoinToSubqueryTransformVisitor；

Qualified name 歸一化，對(duì)應(yīng)于 Interpreter 鏈路下的 TranslateQualifiedNamesVisitor；

Alias 改寫，對(duì)應(yīng)于 Interpreter 鏈路下的 QueryNormalizer；

QueryAnalyzer 查詢語(yǔ)義進(jìn)行分析和校驗(yàn)，將 AST 抽象成出結(jié)構(gòu)化的數(shù)據(jù)結(jié)構(gòu)，為下一步構(gòu)建 plan 提供數(shù)據(jù)。在該模塊中標(biāo)準(zhǔn) SQL 和 Clickhouse SQL 進(jìn)行了區(qū)分，一套代碼同時(shí)兼容兩種語(yǔ)義。

QueryPlan

在 Analyze 之后則是利用 Analyze 出的數(shù)據(jù)結(jié)構(gòu)構(gòu)建初始的查詢計(jì)劃。QueryPlan 是在社區(qū)的 QueryPlanStep 基礎(chǔ)上改進(jìn)而來(lái)，一方面增加了序列化/反序列化方法，為了計(jì)劃下發(fā)執(zhí)行基于 QueryPlan 并非 AST 或者 SQL 文本。另一方面是對(duì)社區(qū)中不合理的 Step 進(jìn)行更改，讓每個(gè) Step 僅僅表達(dá)關(guān)系代數(shù)的語(yǔ)義而非很多執(zhí)行相關(guān)的內(nèi)容和參數(shù)，而這些執(zhí)行相關(guān)的信息則是在每個(gè)執(zhí)行的 server 上構(gòu)建執(zhí)行 pipeline 時(shí)才真正進(jìn)行獲得。

Optimizer

構(gòu)建完執(zhí)行計(jì)劃后則是最為關(guān)鍵最后為核心的優(yōu)化器模塊。PlanOptimizer 類是查詢優(yōu)化的入口類，首先會(huì)基于 PlanPattern 對(duì) SQL的查詢做一次粗粒度的分類，不同復(fù)雜度的查詢使用不同的規(guī)則集合，提升效率。

優(yōu)化器不管是 RBO 還是 CBO 本質(zhì)上都是對(duì)查詢做改寫，只是改寫的思路以及改寫框架有不同的取舍。我們實(shí)現(xiàn)了三種改寫框架，用于處理不同的場(chǎng)景：

基于 visitor 的改寫框架：可以 Top-Down，也可以 Botton-Up 的 方式對(duì)一個(gè) QueryPlan 做改寫，它比較適合于帶有上下文依賴的優(yōu)化規(guī)則，例如 PredicatePushDown，需要把 Predicate 一層層的往下推。

基于 pattern-match 的改寫框架：這種適合簡(jiǎn)單、通用的改寫規(guī)則，例如對(duì)于兩個(gè)連續(xù)的 Filter 做合并的動(dòng)作，只要 QueryPlan 里面的 Sub Plan 符合 Filter-Filter 這樣的 pattern，就可以 match 對(duì)應(yīng)的優(yōu)化規(guī)則，進(jìn)行改寫。

基于 Cascade 的改寫框架：通過(guò)遍歷等價(jià)計(jì)劃，并將所有的等價(jià)計(jì)劃存儲(chǔ)在一個(gè)內(nèi)存空間中，然后評(píng)估每種等價(jià)計(jì)劃的代價(jià)，進(jìn)而選擇一種最優(yōu)解。

查詢優(yōu)化器帶來(lái)了什么

在性能方面，原生Clickhouse受限于缺少查詢優(yōu)化器，對(duì)于 TPC-DS測(cè)試集的99個(gè)SQL用例僅能正常運(yùn)行很少一部分查詢，即使通過(guò)手動(dòng)改寫 SQL 也僅能成功運(yùn)行 80%的查詢。在實(shí)現(xiàn)了完善的優(yōu)化器之后可以直接運(yùn)行全部 TPC-DS 原始 SQL，改進(jìn)后的 Clickhouse 才這正可以算是可用的 OLAP 數(shù)據(jù)庫(kù)。不僅僅是可以正常執(zhí)行這些復(fù)雜查詢，而且效率也得到了很大的提升，相對(duì)在沒(méi)優(yōu)化器的情況下手動(dòng)改寫的 SQL ，性能提升 6 倍以上。在內(nèi)部的一些業(yè)務(wù)場(chǎng)景中性能也有近10倍的提升。

優(yōu)化器的能力方面：

RBO：支持：列裁剪、分區(qū)裁剪、表達(dá)式簡(jiǎn)化、子查詢解關(guān)聯(lián)、謂詞下推、冗余算子消除、Outer-JOIN 轉(zhuǎn) INNER-JOIN、算子下推存儲(chǔ)、分布式算子拆分等常見(jiàn)的啟發(fā)式優(yōu)化能力。

CBO：基于 Cascade 搜索框架，實(shí)現(xiàn)了高效的 Join 枚舉算法，以及基于 Histogram 的代價(jià)估算，對(duì) 10 表全連接級(jí)別規(guī)模的 Join Reorder 問(wèn)題，能夠全量枚舉并尋求最優(yōu)解，同時(shí)針對(duì)大于10表規(guī)模的 Join Reorder 支持啟發(fā)式枚舉并尋求最優(yōu)解。CBO 支持基于規(guī)則擴(kuò)展搜索空間，除了常見(jiàn)的 Join Reorder 問(wèn)題以外，還支持 Outer-Join/Join Reorder，Magic Set Placement 等相關(guān)優(yōu)化能力。

分布式計(jì)劃優(yōu)化：面向分布式MPP數(shù)據(jù)庫(kù)，生成分布式查詢計(jì)劃，并且和 CBO 結(jié)合在一起。相對(duì)業(yè)界主流實(shí)現(xiàn)：分為兩個(gè)階段，首先尋求最優(yōu)的單機(jī)版計(jì)劃，然后將其分布式化。我們的方案則是將這兩個(gè)階段融合在一起，在整個(gè) CBO 尋求最優(yōu)解的過(guò)程中，會(huì)結(jié)合分布式計(jì)劃的訴求，從代價(jià)的角度選擇最優(yōu)的分布式計(jì)劃。對(duì)于 Join/Aggregate 的還支持 Partition 屬性展開(kāi)。

高階優(yōu)化能力：實(shí)現(xiàn)了 Dynamic Filter pushdown、單表物化視圖改寫、基于代價(jià)的 CTE （公共表達(dá)式共享）。

下面我們用TPC-DS標(biāo)準(zhǔn)測(cè)試集，來(lái)為大家展現(xiàn)一下添加優(yōu)化器前后的差別：

在沒(méi)有優(yōu)化器時(shí)，僅能完成26個(gè)SQL的查詢。而添加了優(yōu)化器后，能夠完整跑完TPC-DS的全部99個(gè)SQL，并且在此前能完成的查詢中，性能也得到了極大的提升。