Presto源码分析之IterativeOptimizer

概要

查询优化是数据库系统里面特别关键的一个组件, 曾经有一个老外，我也不知道是谁说过:

Query optimizer is where the power of a database lies. （查询优化器是数据库的强大之处。）

可见查询优化的重要性，查询优化在 Presto 里面主要是由 IterativeOptimizer 完成的，今天我们来分析下 IterativeOptimizer。

PlanOptimizer

在介绍 IterativeOptimizer 之前我们先来介绍一下 PlanOptimizer。在 PlanOptimizer 里面只有一个接口，给你一个输入 PlanNode 以及一些辅助的参数，你给出一个优化后的 PlanNode:

public interface PlanOptimizer {
   PlanNode optimize(PlanNode plan,
           Session session,
           TypeProvider types,
           SymbolAllocator symbolAllocator,
           PlanNodeIdAllocator idAllocator);
}

这个接口实现一般都要实现一个 SimplePlanRewriter 这个使用了 Visitor 设计模式的类, 找到你要处理的节点进行 visit 。用起来其实蛮复杂的，关键是它把多个优化策略揉到一个类里面去做了，比如 LimitPushDown 这个实现，它是要找 LimitNode 进行优化，它里面实现了很多规则:

• 如果 LimitNode 的上游还有一个 LimitNode 那么把这两个 LimitNode 进行合并。如果合并之后要 LimitNode 的 count 是 0，那么直接把这个 LimitNode 节点换成一个空的 Values 节点。
• 如果 LimitNode 的上游有一个 TopN 节点，那么把 Limit 和 TopN 节点进行合并。
• 如果碰到 Union 节点，那么把 Limit 节点推到 Union 下面去。
• 等等。

可以看出来一个优化实现里面糅杂了很多条规则。

不管出于什么理由，把很多不那么相关的逻辑揉在一起都是不好的。

IterativeOptimizer

PlanOptimizer 的缺点正是 IterativeOptimizer 改进的地方，IterativeOptimizer 在 PlanOptimizer 上面又包装了一层，IterativeOptimizer 把每条优化规则抽象出单独的类: Rule。让我们做查询优化的时候只需要去编写 Rule 而不需要去 Optimizer， 不需要去实现 Visitor 模式，真的是太棒了。

Rule 的主要的接口是这样的:

public interface Rule<T>{
   /**
    * 你要优化的Plan的模式是怎么样的?
    */
   Pattern<T> getPattern();

   /**
    * 匹配你模式的PlanNode找到你，你去优化吧。
    */
   Result apply(T node, Captures captures, Context context);
}

首先它让你指定你要优化的 Plan 的结构是怎么样的。比如:

 找到两个相邻 LimitNode 节点的结构。

这个在 presto-matching 库的帮助下很好实现(presto-matching库我们在上一篇文章《Presto源码分析之模式匹配》专门分析过。):

   private static final Capture<LimitNode> CHILD = newCapture();
   private static final Pattern<LimitNode> PATTERN =
       limit().with(source().matching(limit().capturedAs(CHILD)));
   @Override
   public Pattern<LimitNode> getPattern() {
       return PATTERN;
   }

找到之后我们在 apply 方法里面来实现 LimitNode 合并的操作，也非常的简单。

   @Override
   public Result apply(LimitNode parent, Captures captures, Context context) {
       // 这个 child 是那个上游的 LimitNode
       LimitNode child = captures.get(CHILD);
       return Result.ofPlanNode(
               new LimitNode(
                       parent.getId(),
                       child.getSource(),
                       // 合并成一个 LimitNode 取比较小的那个 count
                       Math.min(parent.getCount(), child.getCount()),
                       parent.isPartial()));
   }

不知道大家是什么感觉，反正我在阅读 Presto Optimizer 代码之前没有想到进行查询优化的逻辑可以写得这么简单。这就是优秀框架的力量啊。

可变的执行计划: Memo

在 IterativeOptimizer 对 PlanNode 进行改写的过程中还有一个很重要的类: Memo。我们知道 Presto 源代码里面有一点做得很好，就是对象都是能不可变(immutable)就不可变，这让程序更可预期，潜在的 bug 也会少很多，同时也有一些缺点: 不可变导致要改变一个Plan结构的一部分变得很复杂，你必须重新构造整个 Plan ，因此为了执行计划优化的方便性以及性能的考虑，在对PlanNode进行优化前会把 PlanNode 转化成一个可变的对象: Memo, 下面我们来详细分析下Memo这个类。

说实话 Memo 这个类名我觉得起的特别不好，光看类名完全跟可变的PlanNode联系不上，如果让我起名字的话，我觉得还不如叫 MuttablePlanNode 来的直观。

在 Memo 里面，所有的 PlanNode 被一个新的类 GroupReference 包装一层，一个原始的计划:

原始的PlanNode结构

会被包成下面的结构:

包装过后的PlanNode结构

这里 GroupReference 仍然是不可变的，但是 Group 是可变的，PlanNode 优化的过程其实就是通过遍历 GroupReference 树，不断修改对应的 Group 里面的 PlanNode 的过程。值得注意的是，这个树的结构也可能会被修改，比如上面我们提到过的那个优化策略：

如果有两个相邻的 LimitNode 节点，那么把他们合并成一个 LimitNode 节点，取比较小的那个LimitNode的值作为最终的 LimitNode。

因此存在着一开始存在的 Group 随着优化过程对整个 PlanNode 结构的修改，最后不再被任何其它 Group 引用，因而需要删除掉的情况，因此 Memo 里面有个小小的垃圾回收的策略: 每个 Group对象上除了记录它的原始的 PlanNode 之外，还会有一个引用它的 Group 的记录:

   private Multiset<Integer> incomingReferences = HashMultiset.create();

它每次操作一个节点的时候会对相关的节点做个引用计数 + 垃圾回收的维护:

     // 增加新节点(node)的引用计数
   incrementReferenceCounts(node, group);
   // 更新节点
   getGroup(group).membership = node;
   // 减少旧节点(old)相关节点的引用计数，如果引用计数为0，则把对应的Group删掉
   decrementReferenceCounts(old, group);

感想

刚学习设计模式的时候动不动就想把设计模式用到代码里面去，这样代码会显得高大上一点。当然，在代码里面用设计模式没错，它可以有效地隔离变化，让代码更具有可维护性、可扩展性。但是就像写文章一样，堆满华丽辞藻的文章绝不是什么好文章，堆满设计模式的代码也绝不是什么好的代码。

写代码又像武侠小说里面的侠客学习武功一样，一开始你什么招式也不会，谁也打不过，后来你学了很多招式，能打过很多人了，但是仍然不是绝顶高手，所谓的绝顶高手是要在把所有招式都学过之后，再把所有的招式都忘记掉，真正要用的时候随心所至信手拈来。

设计模式就相当于武功里面的招式，真正的高手应该是学过之后忘掉它，在真正需要的的时候信手拈来用到合适的地方去，这个合适的地方就是框架，让普通开发看不到，这样普通开发同学就可以集中精力写真正的业务代码了, 我们每天要花大量时间去写的应该是业务代码。

在 Presto 查询优化的模块里面，框架代码指的是 PlanOptimizer、IterativeOptimizer, 这里面该用 Visitor 模式就用 Visitor 模式，一旦有了这个框架之后，我们真正业务是调优查询性能，这时候只需要去写 Rule 就好了，而 Rule 的实现都是平铺直叙的逻辑，没有什么复杂的模式，用户用起来会觉得很方便好用。

再引申一点，一个好的 API 一定是平铺直叙的，不需要让用户使用什么设计模式的。