本文我們來看幾個 Calcite 的關鍵參與對象。

抽象語法樹(SqlNode)

SQL 到達 Calcite 後首先會被轉換為 SqlNode, 對於語法樹的訪問我們多依靠 SqlVistor 來進行檢查和後續轉處理。

sql 到語法樹的轉換是 parser 的處理邏輯， 而 SqlNode 自身相對比較簡單這裡不多介紹。

關係表達式(RelNode)

SqlNode 會被轉換為 RelNode 關係表達式來進行後續 Planner 邏輯.

1) RelOptNode

RelOptNode 介面, 它代表的是能被 planner 操作的 expression node。

  • getId(): 表達式唯一數字 ID (進程啟動後維度)
  • getDigest(): 簡潔的描述關係表達式定義唯一性(不會包含當前運算元ID但會包含子運算元ID)
  • getDescription/toString: 通常是 rel#{id}:{digest} 但多帶 ID 信息
  • getTraitSet(): 獲取關係表達式的 traits, 這個馬上後面會介紹.
  • getInput(): 獲取當前關係表達式的 input 表達式們
  • getCluster(): 獲取當前關係表達式所屬的 cluster

2) RelNode

RelNode 代表一個 relation expression 的 node，他實現了 RelOptNode, 我們熟悉的 sort，join，projection 等都是 RelNode。

前面幾篇文章中有提到過， 關係表達式可以選擇在自己"出現"時註冊新的 Rule, 即實現 register 方法(e.g. Cassandra 的 tableScan 出現時再註冊 c* 相關的轉換規則)。

每個可被實現的關係表達式都會有有對應的 RelTraitSet 來描述他的物理特性， 每個 TraitSet 中必有一個 Convention 的用於定義當前 Rel 如何將數據傳遞給消費 Rel, 另外還有一些其他 Trait。

關係表達式特性(RelTrait)

1) RelTraitDef

RelTraitDef 用於定義一類 RelTrait, 後面的幾篇文章中會看到對於一個 TraitSet 中是根據 TraitDef 做的去重(也就是在 set 中同一種 TraitDef 只會有一個 Trait) 。

具體的 TraitDef 實現有幾個需要關注的待實現方法:

  • convert(): 轉換 Rel 為目標 Trait 的表達式(可以修改 Rel)， 其實這個方法正想提交者所說更應該叫 shouldConvert
  • canConvert(): 檢查當前關係節點的 Trait 是否能直接轉換為目標 Trait(不改變 Rel 的情況下)

Calcite 默認實現的 Trait 有: Convention, Collation(排序), Distribution(分布)

這裡先用 Collation 作為 RelTraitDef 的簡單實現來看看(Distribution 和 Collation 非常像， Convention 稍微有些複雜本文後面有專門一小節說明)， CollationTraitDef 代碼位於這裡

  • Collation 的 canConvert 實現是檢查原始排序是否能覆蓋目標排序, e.g. 原始 Trait 是"按照a , b 排序", 那可以直接將 Trait 變為"按照 a 排序"也是等價的, 所以如果需要可以直接轉。
  • Collation 的 convert 實現則是添加一個 LogicalSort 的 Rel 來替換原始 Rel 達到替換輸出 trait 的目的

2) RelTrait

RelTrait 是對應 TraitDef 的具體實例, 需要關注的是可以 register 方法來添加註冊相關的 Rule。

Trait 對應的也定義自帶有: Convention, Collation, Distribution 三個已有 Trait.

關係表達式等價集(RelSet)

1) RelSet

RelSet 是一組等價關係表達式的集合，集合中的表達式都有相同的語義, 但其中的 Rel 各自會有不同的 Trait。

RelSet 中除了一組等價關係表達式(rels)外， 還維護了:

  • 引用了當前集合中 RelNode 的其他外部 RelNode;
  • 待滿足的 Converter
  • 和邏輯上對當前等價集根據不同 TraitSet 進行劃分的 RelSubSet。

2) RelSubSet

RelSubSet 引用一個 RelSet，並從 Set 中根據 TraitSet 劃分出邏輯上的子集(都是在getRels 才去 lazy 取子集), 此外RelSubSet本身也是一種 RelNode 。

所以在一個 RelSet 中相同的 RelTraitSet 的 RelNode 會在同一個 RelSubSet 內。

添加一個 Rel 到 RelSubSet 會添加 rel 到對應的 RelSet 中。

調用約定 ConventionTraitDef/Convention/Converter/ConverterRule

本節對 Convention 相關的幾個概念進行梳理:

0) ConventionTraitDef

Convention 是一種 RelTrait 用於表示 Rel 的調用約定(calling convention)，即， Rel 最後應該被如何調用； 而 ConventionTraitDef 則是 Convention 的分類定義(表現在一個 TraitSet 中只會有一個 Convention, 因為 Def 都相同) 。

前面提到過所有 TraitDef 都會實現 canConvert 和 convert來支持不同 Trait(這裡是 Convention) 之間的轉換，Convention 的轉換相對複雜和之前 Collation 不同, Collation 的轉換和判斷邏輯都在 TraitDef 中實現(並通過abstractConverter + ExpandConversionRule 驅動執行), 而 Convention 的具體轉換是 通過 ConverterRule 來實現， ConventionTraitDef 中的 canConvert 和 convert 用於支持 rule 的 isGuaranteed 返回 true 是支持連續轉換(e.g. 當前是 A 但希望轉換成 D， 中間用 a->b, b->c, c->d 三個 ConventerRule), 所以 ConventionTraitDef 會在 Planner 維度維護一個支持轉換的的 Graph --- ConversionData 來尋找最短轉換路徑， 不過從 calcite 倉庫的代碼看並沒有 conveterRule 用的 isGuaranteed 返回 true, 所以從代碼看所有 Convention 的轉換都是走的正常 rule 匹配的方式, 不過可能有別的項目用了(看 calcite 會發現比較多看上去 dead code 的東西，作為一個被其他項目用的框架有很多未知)

1) Convention

相比普通的 Trait, Convention 多了 2 個需要提供的信息:

  • Class getInterface(): 實現該 Trait 的 rel 需要遵循的介面
  • String getName(): Convention 的名字

所以我們看下幾個 Convention 實現:

  • Convention#Impl: 默認的 Convention 實現, 只是提供了介面信息和名稱信息, JdbcConvention, 和上篇文章中介紹的 Drill 轉換 logic 和 physical rel 都是使用這個默認實現。
  • EnumerableConvention: 能返回 Enumerable 的 Convention 實現, 默認一般用這個。會對實現了 EnumerableRel介面的 rel 執行 impl, 一般是通過 codegen 方式來實現 enumerable 的關係表達式。
  • InterpretableConvention: 能返回 Enumerable 的對象數組， 同樣會實現 EnumerableRel 介面和上一個相比通常不依賴於 codegen 而是 interpret 執行。
  • BindableConvention: 也是能返回 Enumerable 的對象數組， 會實現 BindableRel 介面

總結下： Convention 是一種特殊的 trait 定義了，相關 rel 必須實現的介面， 後面會利用這個介面來做 calling.

2) ConverterRule 轉換規則

ConverterRule 則是可以用於將一種 Convention 轉換為另一種 Convention 的 rule。

相比普通的 rule 他會檢查 in/out trait 約束並且實現只需要實現轉換的convert方法即可。

3) Converter 轉換器

Converter 是一種特殊的 RelNode(注意是Node不是rule)， 所以 Converter 理解更像一個 Adaptor 作為一個 RelNode 實現了從 input rel + trait 到 output traitSet 的轉換， converter 通常作為 converterRule 的中間結果，之後被進一步 impl。

舉個例子: CassandraToEnumerableConverterRule 實現了 CassandraRel#CONVENTION到轉 EnumerableConvention的轉換，生成了converter CassandraToEnumerableConverter 來充當 EnumerableConvention 的 rel， 後續他會被 impl 並 codegen 出實際執行的 Enumerable。

ps: Converter#getTraitDef會被設置為被轉換的 Trait，之後在 ConverterRule 不會重複操作這些是 Converter 類型的 Rel。

4) AbstractConverter

Converter 中有個叫 AbstractConverter 的 Converter 比較奇特，在一些場景比如 root RelSet 中的 input 並不確定， 會先添加一個 AbstractConverter 的 Rel， 然後等待後續用 ExpandConversionRule 來調用 TraitDef 的 convert 來做轉換， 根據前面的描述，一般沒有 isGuaranteed 為 true 所以 Convention 相關的 rule 並不會被這個觸發執行， 但類似 collation 的邏輯會就會被這個先 AbstractConverter + ExpandConversionRule 給執行。

關係表達式變換規則 RelOptRule

Calcite 中存在大量的 rule，Rule 通過指定 RelClass, Trait, Rel Predicate 和RelOptRuleOperand樹, 來定義規則匹配的 RelNode， 並可以通過自定義 matches 方法來添加一些匹配附加條件， 最後會調用 onMatch 方法進行具體匹配後的規則變換操作。

具體的規則後續文章會針對不同場景分別介紹～

行表達式 RexNode

SqlToRelConverter 在轉換 SqlNode 到 RelNode 的同時， 對於行表達式(SqlOperator)需要轉換為 RexNode，每個 Row-Expression 都有一種特定的類型：

  • RexLiteral 普通的 Literal 類型.
  • RexVariable 有一些子類型:
  • RexCorrelVariable nested-loop joins 的關聯變數
  • RexInputRef引用輸入關係表達式中的一個欄位
  • RexCall 對表達式或函數的調用，會被用於表示樹中的非葉子節點
  • RexRangeRef引用輸入關係表達式中的聯繫的多個欄位(通常只用於 translation 中)

Rex 通常通過 RexBuilder 來構建， 並且同樣通過 RexVisitor 和 RexShuttle 來進行操作訪問。

元數據信息

Calcite 在查詢優化階段依賴於 RelMetadataQuery 和 RelMetadataProvider 來查詢獲取統計信息 (如何收集？後面會繼續研究哈- -), DefaultRelMetadataProvider 定義了一組各類 RelMd*的 Meta 信息，meta 信息使用者 RelMetadataQuery 來查詢特定類型的信息， 這個 query 實現是通過代碼生成對 RelMd* 的調用來實現

ps: RelationalExpressionMetadata(Wiki) 值得一看

優化環境信息 RelOptCluster

RelOptCluster 彙集了 Planner, RexBuilder, MetadataQuery 等上面介紹的各種信息， 在 SqlNode 轉換 RelNode 前創建，後面一直充當類似上下文的作用。

Planner

RelOptPlanner 通過合理運用 Rule 和 cost 對 RelNode 做語義等價轉換，Calcite 中有 Hep 和 Volcano 兩個 Planner 實現， 這部分後面會重點介紹～

Program

Program 用來將 planner 和 TraitSet 組合來轉換 rel， 另外 Program 自己也是可以通過 Program 組合 Program 來實現對 rel 用不同 planner 不同 traitSet 的多輪處理.

總結下

  • SQL 文本會被 Parse 為 SqlNode
  • SqlNode 轉換為 RelNode 和 RexNode
  • RelNode 會有 RelTraitSet, 其中的Trait由 TraitDef 定義
  • RelNode 會被 RelOptRule 匹配並轉換
  • 相同語義的 RelNode 會組成 RelSet, set 中 TraitSet 相同的 rel 會歸為 RelSubSet, subSet 作為一個 RelNode 會被其他 RelNode 做 input
  • Convention 是一種特殊的 Trait 規定了如何被 impl, ConverterRule 可以用於不同 Convention 的轉換, 轉換過程中會用特殊的 RelNode --- Converter 來協助
  • 有不同的 Planner 實現， 通過 Program 可以協調組合

本文介紹的概念比較多， 梳理下主要為了後續進一步研究哈，有問題歡迎討論~~


推薦閱讀：
相关文章