更多技術交流、求職機會，歡迎關注位元組跳動資料平台微信公衆号，回複【1】進入官方交流群
相信大家都對大名鼎鼎的 ClickHouse 有一定的了解了，它強大的資料分析性能讓人印象深刻。但在位元組大量生産使用中，發現了 ClickHouse 依然存在了一定的限制。例如：
- 缺少完整的 upsert 和 delete 操作
- 多表關聯查詢能力弱
- 叢集規模較大時可用性下降（對位元組尤其如此）
- 沒有資源隔離能力
是以，我們決定将 ClickHouse 能力進行全方位加強，打造一款更強大的資料分析平台。本篇将詳細介紹我們是如何建構ClickHouse的查詢優化器。
查詢優化器有多重要？
在傳統的關系型資料庫中，如Oracle、DB2、MySQL，查詢優化器都是作為幾個最重要的核心元件之一。可以說，沒有查詢優化器的資料庫是不完整的。相對 OLTP 而言在OLAP領域中更是如此；對于分析類場景，查詢更為複雜，計劃好壞的差異更大。一個優秀的查詢優化器可以防止使用者寫出不好的SQL導緻執行速度慢，能夠準确的選擇出一條效率最高的執行路徑，大幅度降低查詢時間。相應的，一個不好的查詢優化器，甚至會讓查詢變慢。
常見的優化器邏輯分為兩類，一類叫“基于規則的優化（RBO）”，另一類稱為“基于代價的優化（CBO）”，實際應用過程中應當兩類兼顧才能取得最佳效果。
基于規則的優化
根據優化規則對關系表達式進行轉換，這裡的轉換是說一個關系表達式經過優化規則後會變成另外一個關系表達式，同時原有表達式會被裁剪掉，經過一系列轉換後生成最終的執行計劃。RBO中包含了一套有着嚴格順序的優化規則，同樣一條SQL，無論讀取的表中資料是怎麼樣的，最後生成的執行計劃都是一樣的。同時，在RBO中SQL寫法的不同很有可能影響最終的執行計劃，進而影響腳本性能。
基于代價的優化
根據優化規則對關系表達式進行轉換，這裡的轉換是說一個關系表達式經過優化規則後會生成另外一個關系表達式，同時原有表達式也會保留，經過一系列轉換後會生成多個執行計劃，然後CBO會根據統計資訊和代價模型(Cost Model)計算每個執行計劃的Cost，從中挑選Cost最小的執行計劃。
ByteHouse的查詢優化器
目前主流的OLAP的引擎在查詢優化器方面做的并不夠好，尤其是ClickHouse。衆所周知ClickHouse以快著稱，但是它的快是采用了力大飛磚的方式，需要使用者将資料預先生成大寬表，以避免過于複雜的多表查詢進而獲得高性能。而代價是，每次次元變化或新需求都需要大量操作，以及在必須使用多表關聯進行分析的場景中顯得十分無力。
作為一個企業級的OLAP資料庫來說一個完善且強大的優化器是必不可少的，是以，ByteHouse從零開始自研的了查詢優化器。
查詢優化的完整流程
上圖描述了整個查詢的執行流程，從 SQL parse 到執行期間所有内容全部進行了重新實作（其中紫色子產品），建構了一套完整的且規範的查詢優化器。
主要功能子產品
Analyzers
Analyzers 目錄包括兩部分功能：
- 一個是 QueryRewriter，一方面是通過 AST 改寫的方式實作一些文法特性；我們同時支援 Clickhouse SQL 和标準 SQL，是以另一方面是確定在 Clickhouse SQL 模式下 SQL 語義能和原生 Interpreter 執行模式一緻。
- 另一個是 QueryAnalyzer，用于對改寫完的 AST 進行語義的分析和驗證。Analyzer 區分 ANSI SQL 和 Clickhouse SQL 兩種模式。
QueryRewriter 針對 ANSI SQL 的改寫主要有：
- With CTE/view 展開；
- UDF 展開；
- 特定函數的改寫，比如将 count(*) 改寫為 count()，将 countDistinct(...) 改寫為 uniqExact(...)；
QueryRewriter 針對 Clickhouse SQL 的改寫主要有：
- With CTE/view 展開；
- UDF 展開；
- 特定函數的改寫；
- JoinToSubquery 展開，對應于 Interpreter 鍊路下的 JoinToSubqueryTransformVisitor；
- Qualified name 歸一化，對應于 Interpreter 鍊路下的 TranslateQualifiedNamesVisitor；
- Alias 改寫，對應于 Interpreter 鍊路下的 QueryNormalizer；
QueryAnalyzer 查詢語義進行分析和校驗，将 AST 抽象成出結構化的資料結構，為下一步建構 plan 提供資料。在該子產品中标準 SQL 和 Clickhouse SQL 進行了區分，一套代碼同時相容兩種語義。
QueryPlan
在 Analyze 之後則是利用 Analyze 出的資料結構建構初始的查詢計劃。QueryPlan 是在社群的 QueryPlanStep 基礎上改進而來，一方面增加了序列化/反序列化方法，為了計劃下發執行基于 QueryPlan 并非 AST 或者 SQL 文本。另一方面是對社群中不合理的 Step 進行更改，讓每個 Step 僅僅表達關系代數的語義而非很多執行相關的内容和參數，而這些執行相關的資訊則是在每個執行的 server 上建構執行 pipeline 時才真正進行獲得。
Optimizer
建構完執行計劃後則是最為關鍵最後為核心的優化器子產品。 PlanOptimizer 類是查詢優化的入口類，首先會基于 PlanPattern 對 SQL的查詢做一次粗粒度的分類，不同複雜度的查詢使用不同的規則集合，提升效率。
優化器不管是 RBO 還是 CBO 本質上都是對查詢做改寫，隻是改寫的思路以及改寫架構有不同的取舍。我們實作了三種改寫架構，用于處理不同的場景：
- 基于 visitor 的改寫架構：可以 Top-Down，也可以 Botton-Up 的 方式對一個 QueryPlan 做改寫，它比較适合于帶有上下文依賴的優化規則，例如 PredicatePushDown，需要把 Predicate 一層層的往下推。
- 基于 pattern-match 的改寫架構：這種适合簡單、通用的改寫規則，例如對于兩個連續的 Filter 做合并的動作，隻要 QueryPlan 裡面的 Sub Plan 符合 Filter-Filter 這樣的 pattern，就可以 match 對應的優化規則，進行改寫。
- 基于 Cascade 的改寫架構：通過周遊等價計劃，并将所有的等價計劃存儲在一個記憶體空間中，然後評估每種等價計劃的代價，進而選擇一種最優解。
查詢優化器帶來了什麼
在性能方面，原生Clickhouse受限于缺少查詢優化器，對于 TPC-DS測試集的99個SQL用例僅能正常運作很少一部分查詢，即使通過手動改寫 SQL 也僅能成功運作 80%的查詢。在實作了完善的優化器之後可以直接運作全部 TPC-DS 原始 SQL，改進後的 Clickhouse 才這正可以算是可用的 OLAP 資料庫。不僅僅是可以正常執行這些複雜查詢，而且效率也得到了很大的提升，相對在沒優化器的情況下手動改寫的 SQL ，性能提升 6 倍以上。在内部的一些業務場景中性能也有近10倍的提升。
優化器的能力方面：
- RBO：支援：列裁剪、分區裁剪、表達式簡化、子查詢解關聯、謂詞下推、備援算子消除、Outer-JOIN 轉 INNER-JOIN、算子下推存儲、分布式算子拆分等常見的啟發式優化能力。
- CBO：基于 Cascade 搜尋架構，實作了高效的 Join 枚舉算法，以及基于 Histogram 的代價估算，對 10 表全連接配接級别規模的 Join Reorder 問題，能夠全量枚舉并尋求最優解，同時針對大于10表規模的 Join Reorder 支援啟發式枚舉并尋求最優解。CBO 支援基于規則擴充搜尋空間，除了常見的 Join Reorder 問題以外，還支援 Outer-Join/Join Reorder，Magic Set Placement 等相關優化能力。
- 分布式計劃優化：面向分布式MPP資料庫，生成分布式查詢計劃，并且和 CBO 結合在一起。相對業界主流實作：分為兩個階段，首先尋求最優的單機版計劃，然後将其分布式化。我們的方案則是将這兩個階段融合在一起，在整個 CBO 尋求最優解的過程中，會結合分布式計劃的訴求，從代價的角度選擇最優的分布式計劃。對于 Join/Aggregate 的還支援 Partition 屬性展開。
- 高階優化能力：實作了 Dynamic Filter pushdown、單表物化視圖改寫、基于代價的 CTE （公共表達式共享）。
下面我們用TPC-DS标準測試集，來為大家展現一下添加優化器前後的差别：
在沒有優化器時，僅能完成26個SQL的查詢。而添加了優化器後，能夠完整跑完TPC-DS的全部99個SQL，并且在此前能完成的查詢中，性能也得到了極大的提升。
立即跳轉火山引擎BytHouse官網了解詳情！