之前幾篇文章有在 Planner 部分主要關注了 calcite 的"瑰寶" VolcanoPlanner 的處理流程，並跳過了幾處用 HepPlanner 的地方， 這裡我們回過頭看下 calcite 中的另一個 Planner 實現 --- HepPlanner。

啟發式 Planner 的意思就是"基於規則的Planner" , 而前面我們看到 Volcano 的強項是基於代價求解多種規則組合最優的情況，但也存在其他一些優化只要滿足規則轉換一定比不轉換更優，另外，一些規則通過明顯的指定應用順序比 importance 控制順序明顯更好， 所以除了 Volcano, Calcite 還提供了 Hep，並結合使用 Hep 處理一些 Volcano 不適用的場景。

HepPlanner 和 VolcanoPlanner 一樣實現了 RelOptPlanner, 所以我們一樣通過三步: 創建Planner， SetRoot, FindBest 來看下；雖然說就是簡單的應用規則， HepPlanner 做了一些通用封裝: 封裝了可選的規則應用規則(自頂下下或...), 可以分組分子程序應用規則， 可以選擇對 Rel 做 DAG 或 Tree...

另外本文我們會看到， HepPlanner 並非想像中完全的 RBO， 如果規則規則匹配輸出多個 rel 還是能根據 cost 來選一個。

創建Planner

HepPlanner 的創建需要主要需要制定 HepProgram 和 noDag 開關， 其實 new 出來後的 HepPlanner 邏輯上主要有2個東西: 執行的 rule 和如何執行，要被優化的 rel。 實現上 calcite, 將rule 執行過程封裝成了 HepProgram 來控制 rule 執行(注意這個和之前 Program 沒關係), 並將 rel 封裝組織成一個 DirectGraph 方便規則匹配， 這裡我們先看下 program。

HepProgram 中主要維護了各種 HepInstruction:

  • BeginGroup, EndGroup: 開始和結束一組指令組
  • SubProgram: 用來執行子 HepProgram 的指令
  • MatchOrder: 修改當前 Program 匹配次序的指令
  • MatchLimit: 修改當前 Program 匹配 limit 的指令
  • RuleInstance: 執行一個 rule 的指令(不必在 allRules 中)
  • RuleCollection: 執行多個 rules 的指令(不必在 allRules 中)
  • RuleClass: 執行 rules 中符合指定規則類型 allRules 的規則的指令(對 allRules 的過濾)
  • CommonRelSubExprRels: 尋找公共子關係表達式的指令

其中的 RuleClass 執行的規則需要通過 HepPlanner 的 AddRule 方法添加到 allRules 後面才能執行。

創建 HepProgram 一般使用 HepProgramBuilder 來協助， 過程就是創建上面提到的這些 Instruction。

所以在 HepPlanner 創建好之後內部已經有一個 HepProgram 維護了要執行的 Instruction(後面會看到 FindBest 就是執行這些 Instruction), 不過有了執行指令外 HepPlanner 還需要 rel。

setRoot

HepPlanner 的 setRoot 就是將 rel 樹節點包裝為 HepRelVertex 節點和 Edge 邊信息， 組成 Graph 的過程。

addRelToGraph 的實現邏輯是自底向上將 rel 節點用 HepRelVertex 包起來， 並且 copy rel 節點 將之前是 rel 的 input 替換為 relVertex(e.g. 之前是 project 指向 filter, addRelToGraph 後變為 project 指向 包裹了 filter 的 relVertex), 並且根據 HepPlanner 創建時指定的 noDag 參數決定是否將等價 rel 復用節點，復用就是 DAG，不復用 Graph 就是一顆 Tree, calcite 是根據不同的場景選擇 noDag 的值, 簡單總結下:

  • noDag = false: Materialization, Interpreter 對 rel 的優化, 啟發 Join reorder 等使用..
  • 其他的大量 hep 規則都是使用 tree 而不是 dag: CalRule, Decorrelator, 子查詢消除，Lattice

和之前 VolcanoPlanner 中用的 rel 一樣, relVertex 也通過 Digest 字元串來確定唯一和等價， 所以會維護 mapDigestToVertex 來維護所有的 digest 到節點的信息映射。

對於 Edge 邊信息， 在 graph 中維護邊的方向都是從 父節點指向 input 節點(e.g. filter -> tableScan), 因為是有向圖所以只會維護 vertex 的 output 信息。

FindBest

setRoot 之後就是調用 FindBest 來對準備好的 Graph 執行 HepProgram 中的 Instruction 了， 執行就是對每個 Instruction 調用 execute , 並通過重載做邏輯分發， 在運行一定 instruction 後會對 graph 做一次 gc。

最常見的規則類 Instruction 在這實現都是找到一組(個)規則並通過 applyRules 對 graph 應用規則。

MatchOrder

applyRules 是一個以 Vertex 做外循環的的規則匹配過程(對所 rel 分別嘗試應用 rule), 所以自然需要考慮規則應用次序問題, 是自頂向下?還是自頂向下?.... calcite HepPlanner 的選擇是根據不同規則和場景使用選擇不同的匹配次序(PS: 回憶下之前 volcano 也並非純粹的自頂向下，而是 importance 驅動的執行)。

在 getGraphIterator 中根據當前的 Program 的 matchOrder 屬性來選擇不同的迭代器:

  • ARBITRARY, DEPTH_FIRST: 都返回做深度優先的遍歷的迭代器，DEPTH_FIRST是當前默認的 MathOrder 都是深度有先，但 DEPTH_FIRST 在已經應用一個規則之後相比不會對新轉換的節點不會重複應用剛已經匹配的規則， 因為是默認匹配次序，所以多數場景都是他。
  • TOP_DOWN: 會返回一個自頂向下遍歷的迭代器， 因為前面提到過有向圖維護是 parent 指向 input， 這裡返回迭代器是一個滿足拓撲排序的的迭代器, 來自頂向下遍歷， 在 calcite repo 中沒有場景用到， 可能別的地方有用到吧
  • BOTTOM_UP: 會返回一個自底向上的迭代器， 實現其實就是把 TOP_DOWN 做了倒序； 他在 heuristicJoinOrder 中有用來執行 JoinToMultiJoinRule, 前面 Drill 的文章中也有用。

修改 HepProgram 可以通過添加 MartchOrder 的 instruction 來在運行中對後續規則動態修改 MatchOrder.

Apply Rule

首先， Hep 使用的 rule 和我們之前討論的 Volcano 用的規則編寫上沒差別， 都是 operand -> match -> onMatch -> transformTo 的過程。

applyRule 用一個 rule 嘗試 apply 到一個 vertex 上， 首先如果 rule 是 ConverterRule ， 會檢查 convert 是否有必要應用； 如果是 CommonRelExprRule 會先檢查 vertex 是否被多個其他 vertex 做 input。

之後就是檢查 operand； 封裝一個 HepRuleCall 的特殊 RelOptRuleCall 實現， 和他的特殊之處是在 transformTo 時會保存轉換目標到 ruleCall 自己內，這樣使得 applyRule 可以通過getResults 獲得規則轉換的結果；之後檢查下 rule 的 matches 回調； fireRule 觸發 rule 的 onMatch 調用。

之後 applyTransformationResults 會將規則轉換的新 rel 從 HepRuleCall 中撈出來， 如果規則 transform 結果是多顆 rel 樹， 會根據 cost 找一個 best， 之後將新 rel addRelToGraph 加入到 graph 中，並將在 contractVertices 中修改父節點的 input 為新節點(移除老邊等，如果是根節點更新跟節點等...)， 值得注意的是 HepPlanner 不會在這時移除之前的廢棄節點因為 graph 判斷節點有沒有其他人在用的複雜性， hep 選擇了不直接銷毀節點， 而是靠後面主動或條件觸發 collectGarbage， 來清理不可達節點， 這個清理過程是一個經典的 mark-and-sweep 過程， BFS Mark 一個 rootSet，然後找出不在 root 中 vertexs(sweepSet), 然後清理這些 vertex。

Build Final Plan

最後 buildFinalPlan 從 root 向下遍歷將 vertex 剝開恢復成 rel 樹，即是這個 HepPlanner 執行的優化結果。

小結

本文我們簡單介紹了了下 HepPlanner， 在 calcite 中會和 VolcanoPlanner 配合使用並解決一些特殊的場景(join-order, materialization, interpretor, lattice, subquery 等)的優化問題。

最後來個子查詢 select * from emps e where exists (select 1 from depts d where e.deptno = d.deptno and d.name = Sales) 進行子查詢消除的日誌來體會下 HepPlanner 的實際執行，下節會看下子查詢在 calcite 的優化和執行過程~

Breadth-first from root: {
HepRelVertex#12 = rel#11:LogicalProject.NONE.[](input=HepRelVertex#10,EMPNO=$0,NAME=$1,DEPTNO=$2,GENDER=$3,CITY=$4,EMPID=$5,AGE=$6,SLACKER=$7,MANAGER=$8,JOINEDAT=$9), rowcount=25.0, cumulative cost={150.0 rows, 451.0 cpu, 0.0 io}
HepRelVertex#10 = rel#9:LogicalFilter.NONE.[](input=HepRelVertex#8,condition=EXISTS({
LogicalFilter(condition=[AND(=($cor0.DEPTNO, $0), =($1, Sales))])
CsvTableScan(table=[[SALES, DEPTS]], fields=[[0, 1]])
}),variablesSet=[$cor0]), rowcount=25.0, cumulative cost={125.0 rows, 201.0 cpu, 0.0 io}
HepRelVertex#8 = rel#0:CsvTableScan.ENUMERABLE.[](table=[SALES, EMPS],fields=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), rowcount=100.0, cumulative cost={100.0 rows, 101.0 cpu, 0.0 io}
}
2019-04-13 17:31:12,090 [main] TRACE - Applying rule set [SubQueryRemoveRule:Filter, SubQueryRemoveRule:Project, SubQueryRemoveRule:Join]
2019-04-13 17:31:12,090 [main] TRACE - collecting garbage
2019-04-13 17:31:15,403 [main] DEBUG - call#0: Apply rule [SubQueryRemoveRule:Filter] to [rel#9:LogicalFilter.NONE.[](input=HepRelVertex#8,condition=EXISTS({
LogicalFilter(condition=[AND(=($cor0.DEPTNO, $0), =($1, Sales))])
CsvTableScan(table=[[SALES, DEPTS]], fields=[[0, 1]])
}),variablesSet=[$cor0])]
2019-04-13 17:31:15,410 [main] TRACE - new LogicalProject#13
2019-04-13 17:31:15,486 [main] TRACE - new LogicalAggregate#14
2019-04-13 17:31:15,490 [main] TRACE - new LogicalCorrelate#15
2019-04-13 17:31:15,491 [main] TRACE - new LogicalProject#16
2019-04-13 17:31:59,587 [main] DEBUG - call#0: Rule SubQueryRemoveRule:Filter arguments [rel#9:LogicalFilter.NONE.[](input=HepRelVertex#8,condition=EXISTS({
LogicalFilter(condition=[AND(=($cor0.DEPTNO, $0), =($1, Sales))])
CsvTableScan(table=[[SALES, DEPTS]], fields=[[0, 1]])
}),variablesSet=[$cor0])] produced LogicalProject#16
2019-04-13 17:33:54,085 [main] TRACE - new HepRelVertex#17
2019-04-13 17:33:54,086 [main] TRACE - new LogicalFilter#18
2019-04-13 17:33:54,088 [main] TRACE - new HepRelVertex#19
2019-04-13 17:33:54,089 [main] TRACE - new LogicalProject#20
2019-04-13 17:33:54,090 [main] TRACE - new HepRelVertex#21
2019-04-13 17:33:54,091 [main] TRACE - new LogicalAggregate#22
2019-04-13 17:33:54,092 [main] TRACE - new HepRelVertex#23
2019-04-13 17:33:54,093 [main] TRACE - new LogicalCorrelate#24
2019-04-13 17:33:54,095 [main] TRACE - new HepRelVertex#25
2019-04-13 17:34:01,657 [main] TRACE - new LogicalProject#26
2019-04-13 17:34:07,638 [main] TRACE - new HepRelVertex#27
2019-04-13 17:49:54,669 [main] TRACE -
Breadth-first from root: {
HepRelVertex#12 = rel#11:LogicalProject.NONE.[](input=HepRelVertex#10,EMPNO=$0,NAME=$1,DEPTNO=$2,GENDER=$3,CITY=$4,EMPID=$5,AGE=$6,SLACKER=$7,MANAGER=$8,JOINEDAT=$9), rowcount=1.0, cumulative cost={inf}
HepRelVertex#27 = rel#26:LogicalProject.NONE.[](input=HepRelVertex#25,EMPNO=$0,NAME=$1,DEPTNO=$2,GENDER=$3,CITY=$4,EMPID=$5,AGE=$6,SLACKER=$7,MANAGER=$8,JOINEDAT=$9), rowcount=1.0, cumulative cost={inf}
HepRelVertex#25 = rel#24:LogicalCorrelate.NONE.[](left=HepRelVertex#8,right=HepRelVertex#23,correlation=$cor0,joinType=inner,requiredColumns={2}), rowcount=1.0, cumulative cost={inf}
HepRelVertex#8 = rel#0:CsvTableScan.ENUMERABLE.[](table=[SALES, EMPS],fields=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), rowcount=100.0, cumulative cost={100.0 rows, 101.0 cpu, 0.0 io}
HepRelVertex#23 = rel#22:LogicalAggregate.NONE.[](input=HepRelVertex#21,group={0}), rowcount=1.0, cumulative cost={105.5 rows, 203.25 cpu, 0.0 io}
HepRelVertex#21 = rel#20:LogicalProject.NONE.[](input=HepRelVertex#19,i=true), rowcount=2.25, cumulative cost={104.5 rows, 203.25 cpu, 0.0 io}
HepRelVertex#19 = rel#18:LogicalFilter.NONE.[](input=HepRelVertex#17,condition=AND(=($cor0.DEPTNO, $0), =($1, Sales))), rowcount=2.25, cumulative cost={102.25 rows, 201.0 cpu, 0.0 io}
HepRelVertex#17 = rel#1:CsvTableScan.ENUMERABLE.[](table=[SALES, DEPTS],fields=[0, 1]), rowcount=100.0, cumulative cost={100.0 rows, 101.0 cpu, 0.0 io}
}
2019-04-13 17:49:56,125 [main] TRACE - collecting garbage

推薦閱讀：

相关文章