背景

Apache Calcite 作為一款開源的動態(tài)數據管理框架搏恤，由于其模塊化、可擴展萧豆、以及不和任何計算引擎綁定的特性潭陪，目前在開源項目和商業(yè)化產品中已得到廣泛的應用雄妥。不僅 Apache Flink、Apache Druid依溯、Apache Hive 等明星開源項目在使用 Calcite，騰訊天穹 Super SQL瘟则、阿里 MaxCompute黎炉、Dremio 等商業(yè)化產品的 SQL Planner 也都基于 Calcite 實現。Apache Calcite 儼然成為了 SQL Planner 層的黃金標準醋拧、事實趨勢慷嗜。

隨著近些年大數據基礎設施的不斷發(fā)展成熟，SQL 已經無可爭議地成為大數據計算引擎的主流語言丹壕，但與此同時庆械，大量新興計算引擎、數據庫項目的出現菌赖，也產生了大量 SQL 方言缭乘，運維一個企業(yè)級大數據平臺需要處理 SQL 的場景越來越多。學習和了解 Apache Calcite琉用，既能幫助我們快速理解 SQL Planner 的原理機制堕绩，又能有助于我們利用 Calcite 快速解決以處理 SQL 為中心的各類日常問題（如實現一個SQL Parser、SQL Gateway邑时、SQL Planner 等）奴紧。

我們計劃從技術實戰(zhàn)、原理講解晶丘、源碼分析等角度推出系列文章黍氮，來介紹如何利用 Apache Calcite 解決一些常見的具體問題唐含，希望對數據平臺工具研發(fā)的同學有一些幫助。本文是系列文章的第一篇沫浆，將首先介紹 Apache Calcite 的架構設計捷枯，同時以一條 SQL 在 Calcite 中的處理流程為主線，對 SQL 解析件缸、元數據驗證铜靶、執(zhí)行計劃生成及優(yōu)化、SQL 方言轉換等模塊的關鍵原理進行闡述他炊，讓讀者對 Apache Calcite 有一個初步印象争剿。關于各模塊更深入的原理講解和源碼實戰(zhàn)，會在后面的系列文章中分篇進行展開痊末。

目標和收益

本文主要講解 Apache Calcite 的架構設計以及 Calcite 內部 SQL 優(yōu)化方式蚕苇，閱讀本文，能夠從以下幾點幫助到你：

整體了解 Apache Calcite 凿叠，包括架構設計和核心模塊涩笤。

從一條 SQL 處理流程視角出發(fā)，通過對 Calcite SQL 解析盒件、校驗蹬碧、關系代數轉換、RBO 和 CBO炒刁、物化視圖改寫和方言轉換整體流程的講解恩沽，帶你了解一條 SQL 的 Calcite 之旅。

了解 Calcite 物化視圖改寫的兩種方式及各自優(yōu)缺點翔始。

了解 Calcite 中優(yōu)化器設計的關鍵細節(jié)罗心，以及如何實現對 SQL 方言的改寫。

希望閱讀完本篇文章后城瞎，你能夠對 Calcite 整體使用流程有一個初步的認識渤闷，下面我們進入正文。

一脖镀、Apache Calcite 架構概述

1.1 Apache Calcite 誕生背景

Apache Calcite 自 2013 年 11 月首次在 Github 上進行代碼倉庫初始化飒箭，距今已有 9 年時間。Apache Calcite 前身其實是 optiq认然。optiq 最開始則是在 Hive 項目中進行使用补憾，其主要目的是為 Hive 提供基于成本模型的優(yōu)化器。2014 年 5 月 optiq 獨立出來卷员，成為 Apache 社區(qū)的孵化項目盈匾，同年 9 月正式更名為 Apache Calcite。Calcite 的作者是 Julian Hyde毕骡，他早期還寫過 Mondrian OLAP Engine 和 olap4j API削饵，目前他不僅是 Calcite 的 VP岩瘦，同時也是 Apache Arrow、Apache Drill窿撬、Apache Druid启昧、Apache Kylin 等開源項目的 PMC。

Apache Calcite 設計的核心目標：“One planner fits all”劈伴，它期望在異構引擎密末、異構存儲之上，提供統(tǒng)一的數據管理能力跛璧，同時還提供基于關系代數的優(yōu)化器严里，它的內部各個模塊都是可擴展的，也正是因為這種設計理念追城，Apache Calcite 才會被眾多其他開源項目所使用刹碾。

1.2 Apache Calcite 架構設計

Apache Calcite 整體是按模塊化進行設計，各個模塊支持可擴展座柱，比如 SQL 語法文件迷帜、元數據、Transformation Rule（邏輯轉換規(guī)則）和 Implementation Rule（物理轉換規(guī)則）色洞、CBO 元數據獲取的 Metadata Handler戏锹、自定義RelNode 和 SqlNode類型等等，同時 Calcite 底層也支持不同引擎的 SQL 方言轉換火诸。對于 SQL Planner 的優(yōu)化框架景用，整體上 Calcite 已經搭建好，我們可以直接自定義擴展需要的差異化特性惭蹂。下面是 Calcite 各模塊的架構設計示意圖：

上圖中的所有模塊都可自定義實現，接下來讓我們對各模塊一一進行說明：

1割粮、JDBC Client 和 JDBC Server盾碗，主要負責一個 SQL 的請求響應和結果返回，可以基于 Calcite 子項目 Avatica 框架來進行實現舀瓢。

2廷雅、SQL Parser 和 Validator，Parser 主要負責對一個 SQL 進行解析京髓，生成 AST 樹航缀。Validator 主要是驗證 SQL 的元數據合法性。

3堰怨、Operator Expressions芥玉，則是將一棵 AST Tree 轉換為 RelNode關系代數的計劃樹，這樣優(yōu)化器才能識別和優(yōu)化备图。

4灿巧、Query Optimizer赶袄，Calcite 優(yōu)化器模塊，有 RBO 和 CBO 優(yōu)化器抠藕，即對 Query 的關系代數計劃樹做優(yōu)化

5饿肺、Metadata Providers，CBO 優(yōu)化器計算 Cost 時盾似，所需元數據的提供者敬辣，包括：Selectivity（選擇率）、RowCount零院、DistinctRowCount 等等溉跃。

6、Pluggable Rules门粪，Calcite 優(yōu)化規(guī)則模塊喊积，Calcite 主要有：Transformation Rule（邏輯優(yōu)化規(guī)則）和 ConverterRule（Implementation Rule），用戶可以自定義可擴展玄妈。

以上我們是從 Calcite 模塊組成視角來進行理解的乾吻，那么下面從 Calcite 底層核心源代碼類調用流轉邏輯來看：

一個 SQL 的處理邏輯，會使用SqlParser 將 SQL 解析為 SqlNode拟蜻，使SqlValidator來進行 SQL 校驗绎签，使用SqlToRelConverter來將SqlNode 轉換為RelNode關系代數，使用 RelOptPlanner（具體有HepPlanner 和VolcanoPlanner ）來進行計劃優(yōu)化酝锅，同時可以通過擴展RelOptRule 诡必、BuiltInMetadata 的實現，來自定義 SQL 優(yōu)化器的邏輯搔扁。CalCite 這種可擴展的設計邏輯爸舒，極大的方便開發(fā)同學去自定義 SQL 引擎 Planner 邏輯，同時避免大家重復造輪子稿蹲。

下圖為 Calcite 底層核心代碼調用流轉示意：

二扭勉、SQL 查詢優(yōu)化器概述

2.1 SQL 查詢優(yōu)化器的用途

SQL 作為一種聲明式的查詢語言，能夠讓很多技術以及非技術人員快速入門和掌握苛聘，用戶能夠使用 SQL 快速完成業(yè)務層的查詢語義邏輯的編寫涂炎。但單純的 SQL 語言，是無法直接讓底層的計算引擎識別和運行的设哗。當 SQL 查詢請求發(fā)送到底層數據庫時唱捣，需要將 SQL 查詢語句轉換為底層數據庫的計算引擎能夠識別的模型約定定義（比如執(zhí)行計劃描述），最終讓底層計算引擎按照預定的計算邏輯執(zhí)行并返回結果网梢。

對于 SQL 優(yōu)化器的核心用途：即對用戶輸入的 SQL 查詢語句震缭，將其轉換為計算引擎能夠識別和計算的執(zhí)行計劃，由于最終轉換的可以運行計劃有很多種情形澎粟，所以優(yōu)化器需要從中選取一個最優(yōu)的執(zhí)行計劃蛀序，下發(fā)到計算引擎執(zhí)行欢瞪。這里最優(yōu)既可以結合我們的先驗經驗來判定，同時也可以從一個執(zhí)行計劃使用到的物理資源進行考量徐裸，比如使用的 CPU遣鼓、內存、磁盤 IO重贺、網絡 IO骑祟、CPU LRU Cache 等等。SQL 優(yōu)化器的核心邏輯：就是對關系代數計劃做等價轉換气笙，在不改變計劃語義的情況下次企，盡可能最大化的對關系代數計劃做優(yōu)化。

2.2 SQL 查詢優(yōu)化器的優(yōu)化方式

常見的 SQL 優(yōu)化有兩種方式：RBO 優(yōu)化（基于先驗經驗的啟發(fā)式規(guī)則優(yōu)化）和 CBO 優(yōu)化（基于計算成本的優(yōu)化）潜圃。RBO 主要是使用一些預定義的先驗且有收益的優(yōu)化規(guī)則集合缸棵，來對 SQL 進行優(yōu)化，常見的有：常量折疊谭期、謂詞下推堵第、列裁剪、關聯子查詢消除等優(yōu)化規(guī)則隧出。下圖以謂詞下推優(yōu)化舉例：

上圖左邊是原始 SQL 計劃踏志，可以看到，通過 Filter 謂詞下推規(guī)則優(yōu)化后胀瞪，Filter 節(jié)點已經下推到了 Join 節(jié)點之下针余，這樣能夠提前對 Scan 節(jié)點的數據進行過濾，最終減少進入到 Join 算子的數據量凄诞，減少 Join 節(jié)點的計算成本圆雁。

當然，根據先驗經驗主義的優(yōu)化方式也存在缺陷帆谍，可能在部分場景摸柄，由于沒有考慮到 SQL 在真實環(huán)境下的實際運行情況，其執(zhí)行效率并不是最優(yōu)的既忆，所以就有了基于 Cost 的優(yōu)化方式（CBO）。CBO 優(yōu)化嗦玖，則是在期望的物理特質下患雇，通過對不同物理計劃運行所需要的成本進行估算，使用動態(tài)規(guī)劃宇挫，來選擇一個計算成本最優(yōu)的物理計劃苛吱。一般 Cost 包括：CPU、內存器瘪、磁盤 IO翠储、網絡 IO 等等绘雁。

當然，隨著技術的演進援所，現在在 RBO 優(yōu)化階段庐舟，其實也可以基于 Cost 來評估某些優(yōu)化規(guī)則是否應該使用。這里以 Group By（聚合） 下推舉例：

在上圖中住拭，如果 LogicalJoin 之后的基數（輸出的行數）如果比 LogicalTableScan[A] 后的基數要小的話挪略，Aggregate 不下推，其實會比下推更節(jié)約資源滔岳。但完全進入 CBO 階段杠娱，如果計劃搜索空間過大的話，CBO 找出最優(yōu)計劃的耗時可能又很久谱煤。所以在使用 RBO 優(yōu)化規(guī)則時摊求，某些規(guī)則可以比較轉換前后的計劃的 Cost ，來決定是否應用該規(guī)則刘离。目前業(yè)界像 Oracle 和 MemSQL（SingStoreDB）在它們的優(yōu)化器都已經這樣進行實現室叉。

2.3 SQL 查詢優(yōu)化器的框架類型

目前業(yè)界的 SQL 優(yōu)化器框架類型有：Volcano、Cascades寥闪、Columbia太惠、Orca 等優(yōu)化器框架，比較主流的優(yōu)化器框架為 Cascades疲憋，像微軟的 SQL Server凿渊、阿里 ADB、PingCAP 的 TIDB缚柳、CockroachDB埃脏、StarRocks 這些商業(yè)化產品，其 SQL 優(yōu)化器都是基于 Cascades 優(yōu)化器框架的秋忙。

Columbia彩掐、Orca 這兩款優(yōu)化器框架都是在 Cascades 優(yōu)化器基礎上，做了部分改良和優(yōu)化灰追。以 Columbia 優(yōu)化器框架舉例堵幽，其在 Cascades 優(yōu)化器基礎上，對于搜索計劃空間剪枝做得更好弹澎，不僅能夠基于 Group 空間計劃剪枝朴下，同時也能夠做全局計劃剪枝，這樣在一個可以接收并近似最優(yōu)計劃的前提下苦蒿，通過剪枝來減少 Plan 空間搜索的時間殴胧，提升查詢性能。Orca 則是能夠作為獨立的優(yōu)化器在數據庫系統(tǒng)之外運行，這樣的好處在于優(yōu)化器不需要和數據庫系統(tǒng)緊密耦合在一起团滥，但需要提供一種能夠和數據庫系統(tǒng)的交互通信機制來處理查詢竿屹。

Cascades 優(yōu)化器相對于 Volcano 優(yōu)化器最大的區(qū)別在于：Volcano 優(yōu)化器會先盡可能枚舉所有的執(zhí)行計劃空間，然后再從中找出最優(yōu)的執(zhí)行計劃灸姊。而 Cascades 優(yōu)化器能夠在搜索過程中拱燃，對空間搜索計劃進行剪枝，使得搜索的執(zhí)行計劃空間不會像 Vocano 那么大厨钻，但也可以獲得一個相對較好的執(zhí)行計劃扼雏，這樣通過減少空間計劃的搜索時間，來降低 SQL Planning 的耗時夯膀，從而提升查詢性能诗充。

2.4 一條 SQL 在 Apache Calcite 的優(yōu)化旅程

在一個典型的 SQL 查詢服務中，從用戶輸入一條 SQL 語句開始诱建，到最終結果返回到 Client蝴蜓，一般會經過：Client 端 SQL 查詢請求、服務端接收到 SQL 請求和內部作業(yè)構建俺猿、SQL 解析茎匠、SQL 校驗、SQL 優(yōu)化押袍，繼而形成物理計劃诵冒。如果底層有自己的計算引擎，還可以將物理計劃轉換為執(zhí)行計劃谊惭，下發(fā)到計算節(jié)點并執(zhí)行汽馋。如果底層計算引擎是其他引擎的話，可以將物理計劃翻譯成對應引擎的 SQL 方言圈盔，然后提交到對應引擎執(zhí)行豹芯。

為了方便讀者更具象地理解Aapche Calcite的每個模塊的運作細節(jié)，本文選擇了從第二種方式出發(fā)驱敲，以實現一個SQL優(yōu)化改寫器為例铁蹈，來展開介紹一條SQL在 Apache Calcite是如何完成解析、優(yōu)化與改寫的众眨。

如上圖所示握牧，一條 SQL 整體處理流程分為以下幾個步驟：

當 Client 層發(fā)起一條 SQL 請求時，請求會到 JDBC Server 端娩梨，JDBC Server 端底層一般可以是 GRPC 服務或者 HTTP 服務我碟，在 Calcite 中，也可以使用 Calcite Avatica 來做 JDBC 服務端和 Driver 層的代碼開發(fā)姚建。

服務端接收到 SQL 請求后，會在內部構建出一個 Job 作業(yè)請求吱殉，同時提交到內部作業(yè)服務掸冤，之后會進入到 SQL 鏈路處理流程中厘托。

在 SQL 處理流程中，第一步則是將 SQL 解析成一棵 SqlNode 的 AST 抽象語法樹稿湿，這個過程中會做 SQL 詞法和語法的校驗铅匹。之后會進入到 SQL 驗證階段，SQL 驗證階段主要對 SQL 的語義進行驗證饺藤，比如查詢的數據表是否存在包斑、函數是否存在、函數參數數據類型是否匹配等等涕俗。元數據驗證完之后罗丰，其輸出本質還是一棵 SqlNode 樹，接下來會將 SqlNode Tree 轉換為一棵RelNode 關系代數 Tree再姑，同時進入到 SQL 優(yōu)化階段萌抵。

在 Calcite 中，RBO 優(yōu)化主要使用HepPlanner類來進行實現元镀。CBO 優(yōu)化绍填，則是使用 VolcanoPlanner來進行實現，RBO 規(guī)則和 CBO 規(guī)則都支持自定義擴展栖疑。

經過 SQL 優(yōu)化器的優(yōu)化讨永，會產出最優(yōu)的物理計劃。但這還無法最終運行遇革，還需要將物理計劃轉化為底層計算引擎的 SQL 方言卿闹，進行作業(yè)的提交和計算。

本次先分享到這里澳淑，下一篇比原，我們將進入 Apache Calcite 各組件模塊關鍵原理解析。最后杠巡，如果你對數據虛擬化量窘、Calcite 原理技術、湖倉平臺氢拥、SQL 優(yōu)化器感興趣的話蚌铜，歡迎關注“Aloudata技術團隊”公眾號。

??本文作者/?沈浪嫩海，Aloudata OLAP 引擎研發(fā)專家, 畢業(yè)于電子科技大學冬殃，曾就職于阿里、有贊叁怪、字節(jié)的基礎設施團隊审葬，參與數據倉庫、實時計算、數據湖核心研發(fā)涣觉，現負責Aloudata 湖倉查詢引擎 SQL 查詢優(yōu)化器的研發(fā)工作痴荐。

Aloudata浙江大應科技-技術部誠聘Java技術專家/高級技術專家，高級數據庫內核研發(fā)專家官册，Base杭州生兆。同時，我們針對24屆實習生招聘已經開始啦膝宁，歡迎有興趣的同學投遞簡歷至：wuque.hua@aloudata.com鸦难。積蓄星火，以待磅礴员淫，Aloudata技術團隊期待與你共同探索NoETL新世界合蔽，領跑數據智能新未來！