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

缺少完整的upsert和delete操作

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

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

沒有資源隔離能力

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

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

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

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

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

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

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

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

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

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

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

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

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

主要功能模塊

Analyzers

Analyzers 目錄包括兩部分功能：

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

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

QueryRewriter 針對 ANSI SQL 的改寫主要有：

With CTE/view 展開；

UDF 展開；

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

QueryRewriter 針對 Clickhouse SQL 的改寫主要有：

With CTE/view 展開；

UDF 展開；

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

JoinToSubquery 展開，對應(yīng)于 Interpreter 鏈路下的 JoinToSubqueryTransformVisitor；

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

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

QueryAnalyzer 查詢語義進(jì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ū)分，一套代碼同時兼容兩種語義。

QueryPlan

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

Optimizer

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

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

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

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

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

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

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

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

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

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

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

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

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

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