Calcite原理和代碼講解(一)

1.Calcite介紹

(1)簡介

• Apache Calcite 是面向 Hadoop 新的查詢引擎，它提供了标準的 SQL 語言、多種查詢優化和連接配接各種資料源的能力。
• Calcite 的目标是“ one size fits all （一種方案适應所有需求場景）”， 希望能為不同計算平台和資料源提供統一的查詢引擎，并以類似傳統資料庫的通路方式（SQL 和進階查詢優化）來通路Hadoop 上的資料。
• Calcite 之前的名稱叫做 optiq ，optiq 起初在 Hive 項目中，為 Hive 提供基于成本模型的優化，即 CBO（Cost Based Optimizatio）。2014 年 5 月 optiq 獨立出來，成為 Apache 社群的孵化項目，2014 年 9 月正式更名為 Calcite。

(2)技術特性

• 支援标準 SQL 語言；
• 獨立于程式設計語言和資料源， 可以支援不同的前端和後端（後面再補充解釋）；
• 支援 關系代數、可定制的邏輯規劃規則和基于成本模型優化的查詢引擎；
• 支援物化視圖（ materialized view）的管理（建立、丢棄、持久化和自動識别）
• 個人了解：flexible, embeddable, and extensible（靈活性、元件可插拔、可擴充）。它的 SQL Parser 層、Optimizer 層等都可以單獨使用。

2.關系代數

• 關系代數是關系型資料庫操作的理論基礎，關系代數支援 并、差、笛卡爾積、投影和選擇等基本運算。
• 關系代數也是 Calcite 的核心， 任何一個查詢都可以表示成由關系運算符組成的樹。 在 Calcite 中，它會先将 SQL 轉換成關系表達式（relational expression），然後通過規則比對（rules match）進行相應的優化，優化會有一個成本（cost）模型為參考。

3.Calcite架構

• calcite架構與傳統資料庫管理系統有一些相似之處，相比而言， 它将資料存儲、資料處理算法和中繼資料存儲這些部分忽略掉了。
• 好處是：對于涉及多種資料源和多種計算引擎的應用而言，Calcite 因為可以相容多種存儲和計算引擎，使得 Calcite 可以提供統一查詢服務。
• Calcite 架構中，最核心地方就是 Optimizer，也就是優化器，一個 Optimization Engine 包含三個組成部分
  • Rules：也就是 比對規則，Calcite 内置上百種 Rules 來優化 relational expression，當然也支援自定義 rules；
  • metadata providers：主要是向優化器提供資訊，這些資訊會有助于指導優化器向着目标（減少整體 cost）進行優化， 資訊可以包括行數、table 哪一列是唯一列等，也包括計算 RelNode 樹中執行 subexpression cost 的函數。
  • planner engines：它的主要目标是進行觸發 rules 來達到指定目标，比如像 cost-based optimizer（CBO）的目标是減少cost （Cost 包括處理的資料行數、CPU cost、IO cost 等）

4.Calcite核心概念

• RelOptRule：根據傳遞給它的 RelOptRuleOperand 來對目标 RelNode 樹進行 規則比對，比對成功後，會再次調用 matches() 方法進行進一步檢查。如果 mathes結果為真，則調用 onMatch() 進行轉換。
• ConverterRule：它是 RelOptRule 的子類，專門用來做 資料源之間的轉換（Calling convention），ConverterRule 一般會調用對應的 Converter 來完成工作，比如說：JdbcToSparkConverterRule 調用 JdbcToSparkConverter 來完成對 JDBC Table 到 Spark RDD 的轉換。

• RelNode：relational expression，which contains input RelNode。代表了對資料的一個處理操作，常見的操作有 Sort、Join、Project、Filter、Scan 等。它蘊含的是對整個 Relation 的操作，而不是對具體資料的處理邏輯。
• Converter： 用來把一種 RelTrait 轉換為另一種 RelTrait 的 RelNode。如 JdbcToSparkConverter 可以把 JDBC 裡的 table 轉換為 Spark RDD。如果需要在一個 RelNode 中處理來源于異構系統的邏輯表，Calcite 要求先用 Converter 把異構系統的邏輯表轉換為同一種 Convention。

• RexNode： 行表達式（标量表達式），蘊含的是對一行資料的處理邏輯。每個行表達式都有資料的類型。這是因為在 Valdiation 的過程中，編譯器會推導出表達式的結果類型。常見的行表達式包括字面量 RexLiteral， 變量 RexVariable， 函數或操作符調用 RexCall 等。 RexNode 通過 RexBuilder 進行建構。
• RelTrait： 用來定義邏輯表的實體相關屬性（physical property），三種主要的 trait 類型是：Convention、RelCollation、RelDistribution；

• Convention：繼承自 RelTrait，類型很少，代表一個單一的資料源，一個 relational expression 必須在同一個 convention 中；
• RelTraitDef：主要有三種： ConventionTraitDef：用來代表資料源。 RelCollationTraitDef：用來定義參與排序的字段。 RelDistributionTraitDef：用來定義資料在實體存儲上的分布方式（比如：single、hash、range、random 等）；
• RelOptCluster： palnner 運作時的環境，儲存上下文資訊；

• RelOptPlanner：也就是 優化器，Calcite 支援 RBO（Rule-Based Optimizer） 和 CBO（Cost-Based Optimizer）。Calcite 的 RBO （HepPlanner）稱為 啟發式優化器（heuristic implementation ）， 它簡單地按 AST 樹結構比對所有已知規則，直到沒有規則能夠比對為止；Calcite 的 CBO 稱為 火山式優化器（VolcanoPlanner）成本優化器也會比對并應用規則，當整棵樹的成本降低趨于穩定後，優化完成，成本優化器依賴于比較準确的成本估算。RelOptCost 和 Statistic 與成本估算相關；
• RelOptCost： 優化器成本模型會依賴。

5.Calcite處理SQL流程

    sql執行流程（目前看來基本上所有SQL編譯器 都是相似流程，隻是細節不同）：

• 解析 SQL： 把 SQL 轉換成為 AST （抽象文法樹），在 Calcite 中用 SqlNode 來表示；
• 文法檢查： 根據資料庫的中繼資料資訊進行文法驗證，驗證之後還是用 SqlNode 表示 AST 文法樹 (标準化修改：比如隻寫join會變成inner join)；
• 語義分析：根據 SqlNode 及元資訊建構 RelNode 樹，也就是 最初版本的邏輯計劃（Logical Plan）；
• 邏輯計劃優化：優化器的核心， 根據前面生成的邏輯計劃按照相應的規則（Rule）進行優化(邏輯計劃調整)；
• 實體執行：生成實體計劃，實體執行計劃執行 (具體執行計劃就要看存儲引擎如何設計，比較Mysql有Innodb，Hive預設使用HDFS存儲)。

（1）Step1: SQL 解析階段（SQL–>SqlNode）

• Calcite 進行 Sql 解析的代碼如下：
  • SqlParser parser = SqlParser.create(sql, SqlParser.Config.DEFAULT);
  • SqlNode sqlNode = parser.parseStmt();
• Calcite 使用 JavaCC( Java Compiler Compiler ) 做 SQL 解析，JavaCC 根據 Calcite 中定義的 Parser.jj 檔案，生成一系列的 java 代碼，生成的 Java 代碼會把 SQL 轉換成 AST 的資料結構（ 這裡是 SqlNode 類型）。
• 與 Javacc 相似的工具還有 ANTLR，JavaCC 中的 jj 檔案也跟 ANTLR 中的 G4檔案類似，Apache Spark（Inceptor）中使用這個工具做類似的事情。
• Javacc實作了一個 SQL Parser，它的功能有以下兩個（ 這裡都是需要在 jj 檔案中定義的）：
  • 設計 詞法和語義，定義 SQL 中具體的元素；
  • 實作 詞法分析器（Lexer）和文法分析器（Parser），完成對 SQL 的解析，完成相應的轉換。

  【SQL案例】         

    解析sqlNode結果：

（2）Step2: SQL 驗證階段（SqlNode–>SqlNode）

• 經過上一步，會生成一個 SqlNode 對象，它是一個未經驗證的抽象文法樹，下面就進入了一個文法檢查階段， 文法檢查前需要知道中繼資料資訊，這個檢查會包括 表名、字段名、函數名、資料類型的檢查。

• Calcite 本身是不管理和存儲中繼資料的，在檢查之前， 需要先把元資訊注冊到 Calcite 中，一般的操作方法是實作 SchemaFactory， 由它去建立相應的 Schema，在 Schema 中可以注冊相應的中繼資料資訊。

• SqlValidatorImpl 檢查過程
  1. rewrite expression， 将其标準化，便于後面的邏輯計劃優化；
  2. 注冊這個 relational expression 的 scopes 和 namespaces （這兩個對象代表了其元資訊）；
  3. 進行相應的驗證，這裡會依賴第二步注冊的 scopes 和 namespaces 資訊。

（3）Step3: SQL 語義分析階段（ SqlNode –>RelNode/RexNode）

• 主要步驟：

1. 初始化 RexBuilder；
2. 初始化 RelOptPlanner;
3. 初始化 RelOptCluster；
4. 初始化 SqlToRelConverter；
5. 進行轉換；

• 轉換部分
  • SqlToRelConverter 中的 convertQuery() 将 SqlNode 轉換為 RelRoot
  • 真正實作部分：convertQueryRecursive

（4）Step4: 優化階段（ RelNode –>RelNode）

• 提供了兩種 planner：HepPlanner 和 VolcanoPlanner
• HepPlanner：
  • HepPlanner is a heuristic optimizer similar to Spark’s optimizer： 與 spark 的優化器相似，HepPlanner 是一個 heuristic 優化器；
  • Applies all matching rules until none can be applied： 将會比對所有的 rules 直到某個 rule 被滿足；
  • Heuristic optimization is faster than cost- based optimization：它比 CBO 更快；
  • Risk of infinite recursion if rules make opposing changes to the plan： 如果沒有每次都不比對規則，可能會有無限遞歸風險；
• VolcanoPlanner：
  • VolcanoPlanner is a cost-based optimizer：VolcanoPlanner是一個CBO優化器；
  • Applies matching rules iteratively, selecting the plan with the cheapest cost on each iteration： 疊代地應用 rules，直到找到cost最小的plan；
  • Costs are provided by relational expressions；
  • Not all possible plans can be computed： 不會計算所有可能的計劃(如何判斷？有時間再補充...)；
  • Stops optimization when the cost does not significantly improve through a determinable number of iterations：根據已知的情況， 如果下面的疊代不能帶來提升時，這些計劃将會停止優化（類似與機器學習中損失函數，隻不過early_stop為1個epoch）；

• 簡單的優化 （過濾條件下壓，也稱為謂詞下推）
  • 關于filter 操作下壓，在 Calcite 中已經有相應的 Rule 實作，就是 FilterJoinRule.FilterIntoJoinRule.FILTER_ON_JOIN
  • 這裡使用 HepPlanner 作為示例的 planer，并注冊 FilterIntoJoinRule 規則進行相應的優化（這裡可以看到where u.age>10 and j.id>0被下推到掃表操作上面，也就是說SQL引擎掃描一遍表時如果發現表中某行滿足過濾條件則拿取出來，否則跳過）

    

    

    參考資料

    https://www.cnblogs.com/wcgstudy/p/11795886.html

    https://www.infoq.cn/article/new-big-data-hadoop-query-engine-apache-calcite

    https://www.jianshu.com/p/2dfbd71b7f0f

    https://www.slideshare.net/JordanHalterman/introduction-to-apache-calcite