Calcite CBO ② - VolcanoPlanner 之

一、IterativeRuleQueue

该算法不断的从 RuleQueue 中取出 Rule 并执行，该过程有两个退出条件：

1. RuleQueue 空了：没有 Rule 需要执行了
2. 超时：在规则执行时抛出 VolcanoTimeoutException 异常，当 VolcanoPlanner 的 cancelFlag 设置为 true 时会抛出这个异常，所以在使用如果觉得优化时间太长，超过一定时间可设置cancleFlag 为 true 强制优化结束

IterativeRuleQueue 主要成员变量：

• final MatchList matchList

其中 MatchList 如下

二、MatchList

class MatchList {

  /**
   * 只能放 SubstitutionRule 对应的 RuleMatch
   * 为了能区分出来以优先执行 SubstitutionRules
   */
  private final Queue<VolcanoRuleMatch> preQueue = new ArrayDeque<>();

  // 新的非替换规则对应的 RuleMatch 被追加到这个队列的末尾
  // 先进先出，不以任何方式排序。
  private final Queue<VolcanoRuleMatch> queue = new ArrayDeque<>();

  /**
   * Multi-map of RelSubset to VolcanoRuleMatches.
   */
  // multimap 容器保存的是有序的键/值对，但它可以保存重复的元素
  // multimap 中会出现具有相同键的元素序列，它们会被添加到容器
  final Multimap<RelSubset, VolcanoRuleMatch> matchMap =
      HashMultimap.create();

  // 优先把替换规则对应的 RuleMatch 拿出来
  @Nullable VolcanoRuleMatch poll() {
    VolcanoRuleMatch match = preQueue.poll();
    if (match == null) {
      match = queue.poll();
    }
    return match;
  }

  void offer(VolcanoRuleMatch match) {
    if (match.getRule() instanceof SubstitutionRule) {
      preQueue.offer(match);
    } else {
      queue.offer(match);
    }
  }

}

可以看到 matchList 如下，（如之前 setRoot 中所述）越底下的节点的 class 对应的 RuleMatch 在 matchList 中越前面

三、IterativeRuleDriver#drive() 核心流程

注①：什么情况下 rel 会被剪枝？

注②：propagateCostImprovements(rel) 是按需递归更新 parents 的 cost，比如 rel 的 bestCost 发生变化导致爸爸的 bestCost 发生变化，则会进一步更新爷爷的；如果没有导致爸爸的 bestCost 变化，则不会去更新爸爸的和爷爷的 cost

最终的到这样一个 RelSet Tree：