TopDownRuleDriver 是 cascades 論文的標(biāo)準(zhǔn)實(shí)現(xiàn)涮总，我們以下面的 case 來跟蹤代碼：

LogicalAggregate(group=[{0}], groups=[[{0}, {}]], C=[COUNT()])
  LogicalProject(DEPTNO=[$2])
    LogicalValues(tuples=[[{ 100, 'Fred', 10, null, null, 40, 25, true, false, 1996-08-03 }, { 110, 'Eric', 20, 'M', 'San Francisco', 3, 80, null, false, 2001-01-01 }, { 110, 'John', 40, 'M', 'Vancouver', 2, null, false, true, 2002-05-03 }, { 120, 'Wilma', 20, 'F', null, 1, 5, null, true, 2005-09-07 }, { 130, 'Alice', 40, 'F', 'Vancouver', 2, null, false, true, 2007-01-01 }]])

TopDownRuleDriver 主要有以下成員：

• TopDownRuleQueue ruleQueue：用來管理 TopDownRuleDriver 用到的 RuleMatchs
• Stack<Task> tasks：用來管理 Tasks

一、概述

總結(jié)來說半开，TopDownRuleDriver#drive 的執(zhí)行邏輯如下：

@Override public void drive() {
  TaskDescriptor description = new TaskDescriptor();

  // Starting from the root's OptimizeGroup task.
  tasks.push(
      new OptimizeGroup(
          requireNonNull(planner.root, "planner.root"),
          planner.infCost));

  // Iterates until the root is fully optimized.
  while (!tasks.isEmpty()) {
    Task task = tasks.pop();
    description.log(task);
    task.perform();
  }
}

整個(gè)優(yōu)化過程由上面的循環(huán)驅(qū)動(dòng)：不斷從棧頂取出 Task 執(zhí)行鉴未，Task 執(zhí)行中又會(huì)產(chǎn)生新的 Task枢冤，重復(fù)這個(gè)過程直到棧為空（或者某個(gè) Task 執(zhí)行拋異常）。

二铜秆、各類 Task 串聯(lián)

可以看到淹真，一切優(yōu)化都是從 OptimizeGroup(root) 的 task 開始的。

2.1连茧、Round1

2.2核蘸、Round2

以 VolcanoPlanner 的 RelSubset root 成員為起點(diǎn)巍糯，自下而上，不停的探索 inputs客扎，根據(jù)不同情況祟峦，執(zhí)行創(chuàng)建 Task、Task 入棧徙鱼、Task 出棧宅楞、Task執(zhí)行等操作，直到 Stack<Task> tasks 為空或過程中拋異常為止袱吆。以 Stack 模擬了遞歸的實(shí)現(xiàn)厌衙。

具體來說，基于 RelSubset root 創(chuàng)建 OptimizeGroup 類型的 Task 并入棧绞绒，從 tasks 出棧婶希，得到 Task 并執(zhí)行 perform()。每個(gè) Task 都有綁定的 RelNode蓬衡，我們下述統(tǒng)稱為 boundRel

• 如果 Task 是 OptimizeGroup 類型：對(duì)于該 Task 的 boundRel 的 set.rels

  • 先對(duì)于其中的 logical 類型的 RelNode 創(chuàng)建 OptimizeMExpr 類型 Task 并入棧
  • 再對(duì)其中的 physical 類型的 RelNode 的 inputs 創(chuàng)建 OptimizeInput1/OptimizeInputs 類型 Task 并入棧

• 如果 Task 是 OptimizeMExpr 類型

  • 創(chuàng)建對(duì)于 boundRel 的ApplyRules 類型的 Task 并入棧
  • 對(duì)于 boundRel.getInputs() 中的每個(gè) input喻杈，創(chuàng)建一個(gè) ExploreInput 類型的 Task 并入棧

• 如果 Task 是 OptimizeInput1 類型：為只有一個(gè)輸入的 physical node 優(yōu)化其 input 的 Task

  • 創(chuàng)建 CheckInput 類型 Task 并入棧，主體是 physical node
  • 創(chuàng)建 OptimizeGroup 類型 Task 并入棧撤蟆，主體是 physical node 的 input0

• 如果 Task 是 OptimizeInputs類型：用于優(yōu)化 physical node 的 inputs奕塑。此 Task 計(jì)算的適當(dāng)上限（RelOptCost upperBound）并調(diào)用 OptimizeGroup Task堂污。 當(dāng) input 的 upperBound 小于 input 的下限時(shí)家肯，Group 剪枝主要發(fā)生在這里

• 如果 Task 是 CheckInput 類型：

  • 如果 input 發(fā)生變更（可能由其他規(guī)則的action導(dǎo)致），對(duì)于 input 創(chuàng)建 OptimizeGroup Task 重新 explore
  • 如果 input 的 inputs 都已經(jīng) explore 過盟猖，函數(shù)返回
  • 如果是 OptimizeInputs Task 創(chuàng)建的 CheckInput讨衣，會(huì)計(jì)算當(dāng)前的 lower cost 并向上更新 OptimizeInputs 對(duì)應(yīng)的 lowerBoundSum ，即 OptimizeInputs 對(duì)應(yīng)的多個(gè) inputs 的 cost 之和

• 如果 Task 是 ApplyRules 類型：從 TopDownRuleDriver 的 TopDownRuleQueue ruleQueue 成員 pop 出適用于 boundRel 的 ruleMatchs 并為每一個(gè) ruleMatch 創(chuàng)建一個(gè) ApplyRule （主體是 boundRel 對(duì)應(yīng)的 RelSubset 及 ruleMatch）類型的 Task 并入棧

• 如果 Task 是 ExploreInput 類型：對(duì)于 boundRel.set.rels 中每個(gè) logical node式镐，創(chuàng)建一個(gè) OptimizeMExpr 類型的 Task 用于進(jìn)一步 explore inputs

• 如果 Task 是 ApplyRule 類型：說白了就是將一個(gè) ruleMatch apply 到 boundRel反镇，生成新的 plan，新的 plan 又會(huì)進(jìn)入到某個(gè) RelSubset 中娘汞，進(jìn)而又會(huì)進(jìn)一步觸發(fā)后續(xù)的優(yōu)化任務(wù)（這部分位于 onProduce）

  • 如果產(chǎn)生的是 logical plan 則生成 OptimizeMExpr
  • 如果產(chǎn)生的是 physical plan 則生成 OptimizeInputs

• 如果 Task 是 ExploreInput 類型：和 OptimizeGroup 對(duì)等的作用歹茶，也是優(yōu)化 group，差別是這里只處理 group.set.rels 中的邏輯算子你弦。還有一個(gè)很容易被忽略的細(xì)節(jié)惊豺，這里 explore 的值：

  • 如果是通過 OptimizeGroup 生成的 OptimizeMExpr，explore=false
  • 而通過ExploreInput生成的 OptimizeMExpr禽作，explore=true

  explore 會(huì)影響 applyRules 的時(shí)候的 rule 的篩選尸昧，為 true，只會(huì) apply TransformationRule

上述這些 task 共同構(gòu)成了 top-down 優(yōu)化的遞歸過程旷偿。上圖是各個(gè) task 之間的調(diào)用關(guān)系烹俗，藍(lán)色回邊意味著遞歸進(jìn)入下一層節(jié)點(diǎn)

三爆侣、關(guān)鍵要點(diǎn)

3.1、停止條件

• tasks 為空
• Task 執(zhí)行拋異常

3.2幢妄、復(fù)用

以 OptimizeInputs兔仰、OptimizeGroup 的 perform 方法為例：

    @Override public void perform() {
      RelOptCost winner = group.getWinnerCost();
      if (winner != null) {
        return;
      }

當(dāng) RelSubset 已經(jīng)被 fully optimized 后（也就是 RelSubset 中的每個(gè) RelNode 都被優(yōu)化過或剪枝了），Task 直接返回?zé)o需再執(zhí)行

四蕉鸳、剪枝

4.1斋陪、通過 lower bound 與 upper bound 剪枝

在 TopDown 優(yōu)化中，對(duì)于一個(gè) RelSubset置吓，會(huì)有一個(gè) RelNode 會(huì)率先計(jì)算出 cost无虚，此時(shí)會(huì)暫時(shí)將該 cost 設(shè)置為 RelSubset.bestCost，同時(shí)賦值給 RelSubset.upperBound衍锚，當(dāng)要對(duì)同 RelSubset 的其他 RelNode 及其 inputs 進(jìn)行向下搜索時(shí)友题。

有沒有可能在搜索之前，就可以判斷其代價(jià)已經(jīng)過大戴质，無法產(chǎn)生比當(dāng)前 bestCost 更好的 cost度宦，從而實(shí)現(xiàn) purning 呢？

比如告匠，此時(shí) best（RelNode）如下戈抄，bestCost/upperBound 為 {84.80000000000001 rows, 1702.8593150429992 cpu, 0.0 io}

EnumerableMergeJoin(subset=[rel#11141:RelSubset#6.ENUMERABLE.[2]], condition=[=($0, $2)], joinType=[inner])
  EnumerableProject(subset=[rel#11087:RelSubset#3.ENUMERABLE.[0]], DEPTNO=[$0])
    EnumerableTableScan(subset=[rel#11091:RelSubset#2.ENUMERABLE.[0]], table=[[scott, DEPT]])
  EnumerableProject(subset=[rel#11110:RelSubset#1.ENUMERABLE.[1]], EMPNO=[$0], DEPTNO=[$7])
    EnumerableSort(subset=[rel#11113:RelSubset#0.ENUMERABLE.[7]], sort0=[$7], dir0=[ASC])
      EnumerableTableScan(subset=[rel#11100:RelSubset#0.ENUMERABLE.[0]], table=[[scott, EMP]])

接下來，要去 check 同一個(gè) RelSubset 下的另一個(gè) RelNode（記為 anotherRel）及其包含的各級(jí) children 來看是否會(huì)有更加 cheap 的 cost后专。

EnumerableHashJoin(condition=[=($1, $2)], joinType=[inner])
  EnumerableProject(subset=[rel#11110:RelSubset#1.ENUMERABLE.[1]], EMPNO=[$0], DEPTNO=[$7])
    EnumerableSort(subset=[rel#11113:RelSubset#0.ENUMERABLE.[7]], sort0=[$7], dir0=[ASC])
      EnumerableTableScan(subset=[rel#11100:RelSubset#0.ENUMERABLE.[0]], table=[[scott, EMP]])
  EnumerableProject(subset=[rel#11145:RelSubset#3.ENUMERABLE.[]], DEPTNO=[$0])
    EnumerableTableScan(subset=[rel#11091:RelSubset#2.ENUMERABLE.[0]], table=[[scott, DEPT]])

這里會(huì)計(jì)算兩個(gè)值：

• RelOptCost upperForInput

  • upperForInput = planner.upperBoundForInputs(anotherRel, upperBound)
  • 得到 {35.453197385386396 rows, 1702.8593150429992 cpu, 0.0 io}

• RelOptCost lowerBoundSum：

  • 即 anotherRel 的所有 planner.getLowerBound(input) 的 cost 之和
  • 得到 {42.0 rows, 1668.6593150429992 cpu, 0.0 io}

當(dāng) upperForInput < lowerBoundSum 時(shí)划鸽，無需再向下搜索 anotherRel 的各級(jí) children 了，達(dá)到了一個(gè)剪枝的目的戚哎。目前在 Calcite 中裸诽，cost 的比較主要看 rowCount债朵，不怎么看 cpu 和 io掂之。