calcite 概念和架構
1. 前言
Flink使用Calcite構造SQL引擎，那麼他們 是怎麼合作的？ drill, hive，storm 和其他的一干apache 大數據引擎也用calcite ， 那麼對於同一個sql 語句（statement) , 無論複雜簡單與否，他們和Flink產生的執行計劃是不是一樣的? 如果不一樣, 區別是怎麼產生的？ 應該在哪裡實施優化和發力？優化的手段和原則有那些，等等？ 本文不會對calcite 面面做具到的介紹，重點是SQL執行計劃的優化框架，流程和策略， 對執行計划進行優化是calcite 的主要業務。為了有助於理解優化框架，對於必要的概念會有介紹， 比如關係，關係代數，關係演算，等價原理，謂詞邏輯等。
2. calcite 架構
圖-1 calcite 使用場景
如Calcite的官方論文 （見引用1， 發表于于 SIGMOD』18, June 10–15, 2018, Houston, TX, USA）所定義， calcite 是一個能夠連接異構數據源，並運行優化的查詢計劃的基礎框架 。Cacite 提供查詢處理需要的三大功能：查詢語言，查詢優化和查詢執行。 但是calcite 並不想做這樣「one size fit all ” 的框架， 它提供足夠靈活適配介面， 使外部系統 （數據源（或稱存儲系統），或查詢處理系統）能夠選擇合適的場景與它適配 。calcite 支援的場景主要有兩種， 如上圖描述。
在場景1中，calcite 作為獨立運行的進程，後台通過適配器與外部的存儲系統連接，前台通過JDBC 介面 使用SQL 語言通用戶交互 。在這個場景里，calcite 作為一個中間件，為一些沒有或缺乏友好的查詢語言的存儲系統（比如HBase, Cassandra, Kafka, ES, Redis） 提供查詢語言（比如SQL）。 calcite在 內部將用戶提交的查詢優化並運行再自己的進程里，並在優化的過程中將適當的部分下推給存儲系統 。比如Cassandra 有部分關係掃描（tableScan), 過濾（Filter), 投影（Proction) 和聚合（Aggregation）的能力， calcite 能將相應關係表達式翻譯成Cassandra 的語言發送給它並返回結果。對於 Cassandra 不具備的能力，比如連接（ join），這部分關係表達式在calcite 里運行 。當然這兒場景並不是calcite 擅長的，因為query 執行不是它所擅長的。
在場景2中，calcite 作為嵌入式的組件運行在一個查詢引擎里。這些查詢引擎用自己的方式連接後台數據源，並使用自己的集群用分布的方式執行查詢。 查詢引擎善於獲取數據和執行查詢，需要calcite 提供查詢語言和優化查詢的能力 。 這個場景的例子有Hive , Flink, Drill , Storm 。 以 Flink 為例， 它的框架里有運算元連接各樣的異構數據源用於數據的獲取和發布，無論是數據流還是數據集。 它也有豐富的運算元將講這些數據過濾、放大、縮小和變形用於各種各樣計算需求。他需要一種對用戶友好的， 對於批流數據語義統一的查詢語言，以便於用戶編排查詢作業流程，經過優化器後後， 作業能夠最小的代價運行在Flink集群中。 場景2是calcite 最受歡迎的和最擅長的場景， 相比查詢執行, 連接數據源， calcite 更擅長的是製造查詢語言，解析查詢， 和查詢優化 。為什麼這麼說呢 , 那就要看看 它的架構了。
圖-2 引用1中calcite 官方論文中的架構圖。
綠色框框QueryOptimizer （優化器， 也稱Planner, 比如HepPlanner, VolcanoPlanner)是calcite 的心臟和大腦，它接受查詢計劃，輸出優化的查詢計劃 。
藍色的框框是優化器的輸入和輸出和各種適配器，包括Opeator Expressions (輸入的原始計劃，中間結果和最後輸出的計劃）, MetadataProvider(提供元數據的組件，比如對優化規則用的統計資訊（RowCount of table, Distinct RowCout/min/max of a column , etc ) 還有pluggable Rules (優化規則, 利用關係代數或關係演算的等價關係，優化執行計劃，使之更夠最快速的執行)。這三個組件是calcite 可擴展部分，因此與外部系統有連接 。
黃色框框（Data Processing System， 簡稱DPS)與藍色框框有虛線連接，是DPS 對calcite 的擴展部分。 這裡的Data Processing System所指的就是場景2里的查詢引擎。它通過擴展metadata provider 和 pluggable rules , 向優化器提供更準確的元數據資訊，更適合的代價模型， 更高效的優化規則， 利用calcite 優化器產生最優化查詢計劃。SQL parser and validator, 是Calcite的SQL 語言的解釋器， 它將用用戶用SQL語言編寫的查詢解析稱Opeator Expressions ， 並驗證它的合法性 。
Opeator Expressions是一種用於表示關係代數表達式的樹狀數據結構。解釋器將SQL 查詢解釋成關係代數表達式， 之後優化器調用規則將其修改為最優表達式。優化規則會根據有關係代數的等價原理將表達式變形從而使表達式的代價降低。但如何判斷代價是否降低？ 辦法有兩種：一種是根據經驗，一種是根據代價模型。根據經驗學名稱做啟發式（Heuristic )模型, 根據代價模型估計的，學名叫火山模型。 相應的優化器也被稱作啟發式優化器和火山優化器（HepPlanner, VocanoPlanner)。 代價模型的量化計算是根據從metadata provider獲取關係及關係運算的元數據，再輔以量化模型的計算。元數據通常指的是一個關係（table）和關係運算(projection, filter, join, aggregation, etc)產生關係的統計數據：如關係的row count, 某個分量的 distinct count， min, max 等 。DPS 會擴展Calcite 邏輯關係表達式產生「物理」關係表達式, 而這些擴展的表達式也會輸入給優化器， 利用規則繼續優化 。
Expression Builder 是一種繞過SQL解析，直接生成關係表達式的工具。 這種方式適用於單元測試，就不做展開展開介紹了。
圖-3 calcite 交互數據流
用數據流圖的方式描述一下calcite 和Data Processing System 的交互， 如上圖所示， 應該更容易理解 ， 為什麼一個大數據處理系統更喜歡在場景1裡面使用calcite 。優化器是從calcite的核心是不變的地方。 Rules, metadata, 和operator 是優化器依賴的幫手， 但都是可擴展的部分 。 回答在前言里的問題， 有那麼多的大數據系統使用calcite， 相同的sql 查詢經過calcide 優化器產生的計劃會一樣嗎 ？ 答案是否定的。 原因是要看各個大數據系統里擴展的Operators, metadata provider , 還有新的規則和應用的順序 是否相同等等 。不同的擴展，產生的關係表達式肯定不一樣。 擴展做的更優秀， 優化的結果就更優秀。 比如Metadata Provider提供的關係運算統計數據是一種估計， 除了最底層的TableScan的代價估計是相對準確的， 別的運算的估計都是有誤差的 。 誤差越小，規則運行的越準確， 反之則不然 。
3. 一些關係的概念
Calcite 只支援於關係型數據模型（不支援層次，網狀，對象資料庫的模型）， 那麼什麼是關係型資料庫呢 ？ 建議讀一下引用5中的那本書 ，雖然我也沒讀完 。下面解釋一下一些比較容易混淆的概念 。
關係：關係一詞來自離散數學裡的集合論，根據維基百科的的定義，給定任意集合A和B，若
（笛卡爾乘積），則稱R為從A到B的二元關係，特別在A=B時，稱R為A上的二元關係。如果一個有N列的二維表， 每一列的取值範圍為Ai 則該表是定義在A1x..Ai..xAn上的N元關係。可見，關係（Relation)是N元有序序列的集合。關係在資料庫的概念里稱作表（Table），關係的每一個有序序列叫做元組或行（Row), 元組的每一個量叫分量或列(Column)。
關係模式（Schema）：是對關係或表的描述。包括關係名稱（Table Name），列名以及列的定義域（Domain)。
關係模型（Model)：指的是一系列關係模式的集合， 概念上對應資料庫。
維度（Dimension)：通常是指列離散定義域的列。定義域上的每一個值稱為基（cardinality), 一個關係已經使用的所有的基的個數成為基數 （cardinal number) , 也就是 distinct count , 也成 NDV （Number of Distinct Value) 。
關係代數：是由 Edgar F. Codd提出一種利用具有良好語義的代數結構用於對數據建模和定義查詢的理論。代數結構是在一種或多種運算下封閉的一個或多個集合，那麼關係代數在閉合關係上的良好語義的運算的集合。通俗的說，關係代數是一種通過由代數運算和輸入關係組成的表達式來表達輸出關係的理論。 比如 圖-3中，SQL 產生的關係可以多個樹形的表達式表示，樹的形狀和節點的排列順序代表運算的過程（從下到上） 。關係代數是面向過程的。
關係演算，是另外一鐘錶達關係的理論， 他是以數理邏輯中的謂詞演算為基礎，用描述和聲明的方式表達關係 。比如關係代數表達式用一系列代數運算來表示最終的產生關係，而關係演算則用聲明形式的表達式描述一下最終的關係定義 。每一個關係代數的表達式，都有對應的等價的關係演算表達式（Codd定理）， 但反之則不然。關係演算和關係代數都來自關係模型理論。
SQL語言：是關係代數和關係演算的實現。 比如運算都來自關係代數， 運算里謂詞都來自關係演算 。 現在大多數人都說SQL是一種聲明式的語言，有點道理但也不全對。演算部分是聲明的，代數部分是過程的。 比如一個equal join , join 是代數規定結果是一個笛卡爾乘積。 equal 是演算定義了目標關係里保留的是雙方的鍵值要相等。 這個聲明給了關係表達式的實現者可以通過hash join, 或sort merge join 優化 這個equal 。
Operator Expression : 指的是表達關係代數和關係演算的表達式， 在calcite 中由一種樹狀結構來表示 。它取這個名字的原因是樹中所有的節點都有相應的操作符來表示， 包括輸入和輸出關係（TableScan， Sink )。我更喜歡把它叫做關係表達式：表達關係代數和演算的表達式 ，或由作用在關係上的運算組成的表達式。在優化的過程中，最原始的樹狀的數據結構會轉化成一個圖， 因為一些子計劃可以重用的，重用的子計劃和原計劃會使用相同的節點實例，就像一個可以重入的函數可以被調用多次，但返回的數據是相同的。一個節點有多個parent, 就變成了不在是一棵樹了。 比如SQL中的CTE， 如果上游的謂詞沒有下推，它是一個非常獨立的存在，可以單獨優化，形成一個比較獨立的子計劃和子表達式。 如果該子表達式被使用多次，他在圖中就會成為多個上游節點的子計劃。物化視圖也是一個例子。 計劃圖是一個有向無環圖(DAG)，也就是一個關係只能作為另外一個關係的輸入，不能作為自身的直接或間接輸入，樹是有向無環圖的特殊性形式，所以把優化後關係表達式稱為計劃圖比較合適 。
還有一點要注意，當我們談論計劃的時候， 計劃圖是一個向下生長的DAG, 根節點是Sink, 葉結點是TableScan 。 上游，下游， 上推， 下推， 是對應從根節點先下的方向。當我們談論作業流（jobGraph)的是，上游，下游對應的是數據流向。
4. calcite的概念
上一章的概念說了這麼多， 感覺就是為了解釋什麼是Operator Expression（關係表達式） 。這個概念很關鍵， 它是優化器操作的數據結構， 它經過優化規則的修剪和雕琢， 和元數據提供者營養的滋潤，成為最終的最優（代價最小）結構。如果還是不好理解， 那就先拋去那些雖嚴謹但晦澀的數學概念， 可以把一個關係表達式想像成一個作戰計劃， 比如著名的官渡之戰。 如果曹操在官渡和袁紹死磕, 作為原始的作戰計劃，也有可能也會獲勝，畢竟有官渡河天險可守。但是代價會很高，畢竟袁紹的兵力數倍於曹操，正面作戰勝率較低。於是曹操優化了原始計劃，首先不主動出擊，堅守官渡，然後 偷襲烏巢，燒了袁軍的糧草，導致袁軍軍心大亂，倉促攻曹，最後致敗。曹操用最小的代價大敗袁紹於官渡，他的作戰計劃里的關鍵步驟是奇襲烏巢和堅守官渡。可惜袁紹白白擁有10萬大軍，和五子良將張頜，佔盡優勢，但卻一敗塗地。袁紹最大的錯誤就是使用了錯誤的計劃， 信任千古奸人 郭圖，這個人不僅害袁紹， 袁的兩個兒子也都被他害死，最後被曹操斬殺 。不得不說，曹操無論是對官渡之站的計劃，還是對郭圖的計劃都是最優的。
如果做一個粗糙的類比，曹操的大腦在相當於calcite 的啟發式優化器，他手下謀士的計策就是Plugable rules ，比如荀攸的突襲白馬，荀彧的堅守官渡，許攸的奇襲烏巢，進攻、退守是關係代數里的運算符， 白馬，烏巢，官渡這些地名相當於關係，那麼行軍路線就構成了一個計劃圖，如同關係表達式的計劃圖一樣。作戰計劃依賴主將的智商和經驗判斷來計劃的優劣，曹操雄才大略是不世的英雄豪傑，比起袁紹要聰明數倍， 他的判斷自然準確率比較高。但是也有判斷失誤的時候啊，比如赤壁之戰，依賴智商並不總是一個好辦法。Calcite 的優化器要依靠元數據提供者的數據和代價模型用量化的指標來判斷不同計劃的優劣，在統計上應該是更準確的。那麼回到一個程式設計師的思維里，優化器具體是怎麼工作的呢 ？
先看下callcite 對外開放的介面。
圖-4 來自引用7中， Calcite API and SPIs
概念比較多， 用一個表來解釋一下吧。
| 概念 | 解釋 | 例子 |
| RelNode | 關係代數中的關係和運算的基類。RelNode 有很多繼承者， 見舉例。 | TableScan對應一個數據源的一個關係，Filter對應Filter運算 。Filter有一些系列的繼承者， 每一個繼承者對應一個CallingConvention, 也對應一個優化階段的使用的數據結構 。 比如Join<-LogicalJoin<-FlinkLocalJoin<-FlinkBatchExecJoin, FlinkExecStreamJoin 。 |
| RelDataType | 代表域，是關係中列的定義域 | 整數，日期，浮點數，定點數，字元串 |
| RexNode | 代表Project里Filter中表達式 | 比如下面關係里一個分量（InputRef)，一個常量值(Literal)，一個或多個分量函數(RexCall, 加、減、乘、除、CAST 等) |
| RelTrait | 代表關係運算的物理特性，這個應該是calcite 里最讓人迷惑的概念了。但Trait， set， subset 是 volcanoPlanner 最依賴的概念。 關係的物理特性是跟關係代數沒有關係的一些特性，所以只有跟物理執行系統比較臨近的關係運算才會有物理特性，比如FlinkBatchExecFilter 有物理特性， 它是被翻譯成FlinkJobGraph的輸入計劃的節點類型。而LogicalFilter觀完全邏輯上的關係觀念，因此不會有任何物理特性。 Calcite 有三種類型的特性， 類型叫做TraitDef 。
|
比如Flink中的節點BatchExecJoin在BATCH_PHYSICAL 調用習慣中的運算節點。 |
| AbstractConverter | 當關係表達式的 Convention 發生變化的時候， VolcanoPlanner 會在Relset 里創建Relsubset 代表這種traits, 隨後創建AbstractConverter用於轉化成真正的表達式。 ExpendConventionRule 配備AbstractConverter， 將它轉化成合適的節點， 比如 BroadcastExchange, Sort 等 。 | 參考FlinkExpandConversionRule, calcite: AbstractConverter, Relset.addAbstractConverter。 |
| RelOptRule | 所有的優化規則的基類， 它構造函數第一個參數就是關係運算的類型（比如， Join， Filter 等），（還有一些別的， 不展開了）。當Planner 遍歷表達式圖的每一個節點時，他會調用匹配這個節點類型的規則 。除了匹配類型，VolcanoPlanner 還會給規則設置優先順序，級別高的會別先調用。每一個規則有兩個函數： matches() 繼續深度判斷改規則是否真的應該調用。 onMatch 執行規則實際的動作：根據測量增、減、改變、升級表達式的節點。 優化規則有的會通過元數據提供者查詢元數據資訊，從而做相應的措施。有的不會。從規則的角度來看，planner 都是無區別的。 所以除了少量的例外（比如前面提到的ExpendConvensionRule)，大部分都可以被HepPlanner 和 VocanoPlanner 調用的。 |
例子有很多， 比如有名的謂詞下推，子查詢替換，join-recorder， 常量替換等。google里搜索一下， 會很多介紹 。 想看全面的， 請參考 org.apache.calcite.rel.rules裡面的規則， 或 FlinkBatchRuleSets.scala裡面的使用的規則。 |
| RelMetadataProvider RelOptCost |
前文多次提到的統計數據提供者，他是一個能handle不同統計類型數據的handler的集合。比如 RelMdRowCount是提供關係運算產生的rowCount估計, RelMdDistinctRowCount 提供某個列的cardinal number 估計 。RelMdSelectivity 提供關係運算後的rowcount 原來的比例 估計。 RelOptCost是代價模型， calcite 的代價模型是對關係的行數，通常是考慮IO(disk IO + network IO) 和CPU使用率， memory, 和 關係規模（rowcount)的一個綜合衡量。 |
Calcite 里有DefaultRelMetadataProvider 提供了各種Handle 預設計算方法。ReflectiveRelMetadataProvider 由於接受DPS端實現的Provider , 比如 Flink里實現的FlinkDefaultRelMetadataProvider . 還有一個JaninoRelMetadataProvider, 看起來是通過動態編譯的生成Provider ? Handler的元數據的估計演算法請閱引用5的第13章。 |
| Schema Table Lattice ，Tile |
Schema和table的概念全面說過。 Lattice（格） 是除了關係、關係代數之外，另一個來自於數學領域的名詞。看起來calcite 是真的很想提升廣大數據程式設計師的數學格調。 格同關係代數一樣是一種代數結構（集合+一種二元關係），集合的成員的二元關係是反自反， 和傳遞的， 而且這個關係有明確的上下界， 則稱這種代數結構為格。 很抽象， 可以看引用8中的哈斯圖理解 。{ x, y, z }的冪集按包含偏序排序就是一個格。 這個和多維cube聚合計算的物化視圖的結構很像。 物化視圖裡的每一個頂點都是一個tile , 最上面的tile 包含了所有的維度， 最下面的維度為空， 維度集合以及包含關係組成了一個格。 格從上到下是是降維的過程，則低維聚合計算可由高維聚合導出 。所以lattice , Tile 是為 物化視圖引入的， 只不過換了一個文藝的名字而已 。 物化視圖是一個預計算的結果，物化在硬碟或記憶體里，如果把查詢計劃里能夠利用物化視圖，執行的很定會飛快 。 |
來自引用8 |
| HepVertex HepProgram HepPlanner |
HepVertex是HepProgram里用於組成計劃圖的頂點。HepProgram 是一些優化規則的集合，HepPlanner 利用HepVertex建立將計劃樹轉化成計劃圖， 然後利用HepProgram按照一定順序遍歷其中的優化規則。 HepPlanner 調用流程如右側程式碼所示。
HepPlanner的尋優 是一個一種貪心的演算法，就是當前迭代步會用上一次迭代結果的作為當前最優結果繼續優化，如果上一步做錯了，下一步也會錯下去。只有將迭代運行多次，才有可能避免改正錯誤。 |
//build program val builder = new HepProgramBuilder() builder .addMatchLimit(10) .addRuleInstance(SubQueryRemoveRule.FILTER) .addRuleInstance(SubQueryRemoveRule.JOIN) .addMatchOrder(HepMatchOrder.BOTTOM_UP) val hepProgram = builder.build() //create planner val planner = new HepPlanner(hepProgram, ...) //build new operator expression graph planner.setRoot(root) planner.changeTraits(desiredTraits) //apply rules in programs to optimize the operator expression planner.findBestExp
|
| Relset RelSubset VolcanoProgram ValcanoPlanner |
RelSubset 代表一個目標物理特性， 比如BATCH_PHYSICAL.Broadcast.ANY, 代表一個BATCH_PHYSICAL convention 等價 子計劃，行發布方式是廣播， 列排序方式為任意。BATCH_PHYSICAL.Hash.ANY,是另為一個subet 。 Relset 是所有具有不同物理特性的等價的RelSubset的集合這些， 比如BATCH_PHYSICAL.Broadcast.[]和 BATCH_PHYSICAL.Hash.[]是等價的。 Relset 還是所有等價關係的集合，比如HashExchange+SortMergeJoin，HashExchange+HashJoin, BroadcastExchange+Hash, ASC sort + SingleExchange+Hash 都是等價關係表達式。 RelSubset 會在從等價關係集合里選擇符合自身trait的最便宜的作為他的best 。從上到下的best組成最終的計劃圖 。
|
5. 優化器流程
HepPlanner 的尋優流程很簡單，setRoot重建planGraph, findBestExp 就是按照指定的順序將HelpProgram里的規則觸發一遍。 如果擔心有問題貪心演算法的問題，可以將這兩步多做幾次。
VocanoPlanner 的尋優流程如前所述。 TraitSet 通常包含了 Convension, distribution, collation 三個維度 ， 這三個維度不同的基的組成的組合（subset)都是等價的但是cost不相等，但並不是代價把最低的subset 輸入給上游總代價就會最低的。最低的代價需要綜合考把慮上游和下游的情況，尋找最搭配的搭檔。所以這個尋優過程需要一個動態規劃的方式來求解。在使用動態規劃（也就是遞歸的方法, volcanoPlanner 的命名就來自這裡吧 ）求解之前， 我們需要把各種可能的計劃的每一層的滿足需要trait的subset， 以及對應關係求出來。 而滿足要求的subset, 而且在考慮到輸入的組合，狀態轉移公式大概如下。
BestExp(subset)) = argmin( cost(rel1 ), cost(rel2), ... ) cost (rel ) = algoCost(rel.self) + cost(BestExp(rel.input1)) + cost(BestExp(rel.input2))
第一行中，rel1, rel2 是滿足traits 的等價表達式，表示當前subet的最佳表達式是他們之中里cost最低的表達式。
第二行中， 表示表達式的cost 等於最上層節點自身演算法代價估計 和下層輸入subset的最佳表達式向上輸入的累計的綜合代價 。TableScan 的下層輸入就是磁碟IO的代價，底層關係的RowCount相關 。這裡的加號代表代價計算要綜合考慮的因素並不是簡單的算數相加 。比如hashJion和sortMergeJoin自身演算法的代價不一樣（CPU， 記憶體代價）， join的兩路輸入方式不同代價不一樣（IO代價）。
舉個例子 ：
SELECT * from store_sales join date_dim on store_sales.ss_sold_date_sk = date_dim.d_date_sk and date_dim.d_year=2002
1 |
這個表達式里主要有一個HashJoin 和兩個TableScan 組成， 如果對HashJoin 的 requriedTraits 是 BATCH_PHYSICAL.ANY.[], HashJoin 對store_sales 和 date_dim的要求分別是BATCH_PYSICAL.forward.[] 和 BATCH_PYSICAL.broadcast.[], 那麼上面的公式以下的形式 。
BestExp(join.BATCH_PHYSICAL.ANY.[]) = argmin( cost(shuffledHashjoin), cost(broadcastHashJoin), cost(shuffledSortMergeJoin)，... ) cost(broadcastHashJoin)= cost(BestExp(tablenscan_store_sales.BATCH_PHYSICAL.forward.[])) + cost(BestExp(tablenscan_date_dim.BATCH_PHYSICAL.broadcast.[])) + algoCost(HashJoin)
類似的過程可以求出 cost(broadcastHashJoin), cost(shuffledSortMergeJoin) 。
Broadcast join 極大的減少了網路和磁碟IO， cost 肯定是最低的 ， 最終Broadcast join表達式會選為join 層滿足要求的subset 的最佳關係表達式 。
從上面的轉移公式可以看到， required traits 是從通常從上向下傳遞的（也有自我要求的) ，比如join對下游的廣播方式的要求， 全局排序要求下游以single 方式發布數據的要求等。 cost是從下先上傳遞的， 沒有下游已經確定的關係，上游是無法計算代價的 。在向下傳遞traits 的過程中， calcite 創建AbstractConverter代表 目標traits 臨時節點， 之後再ConventionExpansionRule 將AbstractConverter 轉化成實際的關係。比如AbstractConverter.Broastcast.[] 建在TableScan上面， 目的是想讓tableScan以廣播方式輸出， ConventionExpansionRule最終會將這個表達式變成BroadcastExchange+TableScan 。當TableScan的代價估計會沿著Exchange向上傳遞， 上游關係的代價也得以計算， 以此類推 。
VolcanoPlanner 將與節點匹配上的 ConventionExpansionRule 和其他的ConverterRule 都放在優先隊列里。由於新的relSubset創建時， AbstractConverter才會創建，之後觸發ConventionExpansionRule 與之匹配和放入隊列， 用以之後創建Exchange 和 sort 節點。這個和其他的ConverterRule 不同， ConverterRule 是匹配舊的Convention 的結點（比如LogicalXxxxx), 他們在節點註冊的時候（setRoot)就已經入隊。優先隊列里的成員都有優先順序，級別高的先被調用， 這樣能保證那些ConverterRule 先於ConventionExpansionRule 調用。
圖-5 VolcanoPlanner
畫個圖表示一下 relSet, relSubset, 和besExp 還有trait之間的關係吧， 還有這個類似火山噴發的形狀。
7. 引用
| 序號 | 描述 | 鏈接 |
| 1 | Calcite 論文 | dl.acm.org/doi/10.1145/3183713.3190662 |
| 2 | Calcite 官方文檔 | calcite.apache.org/docs/ |
| 3 | 關係代數 | en.wikipedia.org/wiki/Relational_algebra |
| 4 | 關係演算 | //en.wikipedia.org/wiki/Relational_calculus |
| 5 | 資料庫系統概念第6版 Abraham Silberschatz 等著 | |
| 6 | 官渡之戰 | //zh.wikipedia.org/wiki/%E5%AE%98%E6%B8%A1%E4%B9%8B%E6%88%98 |
| 7 | SQL on everything, in memory by Julian Hyde | www.slideshare.net/julianhyde/calcite-stratany2014 |
| 8 | 哈斯圖 | zh.wikipedia.org/wiki/%E5%93%88%E6%96%AF%E5%9C%96 |
