Hive HQL优化器

昨天晚上看了一下Hive HQL的优化器。这个优化器相比于GCC4、LLVM的优化器而言极其简单，但
结构也非常地清晰。

Hive优化器结构

*   总体结构
    总体上讲，Hive的优化器是一种基于Pass的优化器，Pass在Hive中称为Transform。与此同时，
为了便于每个Transform的编写，Hive还提供了一个框架，用于遍历一遍当前DAG图，并在每个节
点上执行规则指定的操作。
    Hive优化器在ql/optimizer目录中，优化器的入口是Optimizer类和PhysicalOptimizer。前者
主要是在中间语言上进行优化，后者则是在生成的MapReducer执行计划上进行优化。这两个优化
器使用的遍历框架一样，之所以区分两个不同的情况，是因为，Optimizer处理的DAG图是HQL语言
编译得到的DAG图，而PhysicalOptimizer处理的DAG图是MapReduce任务构成的执行计划。除此以
外，两者的结构类似，这里仅仅分析Optimizer。
    用于遍历DAG图的框架在ql/lib目录下，核心的接口包括Node、GraphWalker、NodeProcessor
与NodeProcessorCtx、Rule、Dispatcher几个。
    在Hive编译器内部，有一个概念十分重要：ParseContext。这个类包含了当前的IL和相关的
一些信息。每个Transform都是以一个ParseContext作为参数，返回一个ParseContext作为结果。
可以说，ParseContext就是Hive处理HQL的信息的中心。

*   Optimizer
    这是Hive优化器的驱动类。其实，更合适的叫法是PassManager或者TransformationManager，
因为它管理的transform不一定是“优化”，这些transform也可以完成规格化、阶段划分、代码
生成等其它任务。
    Optimizer主要维护两个信息：
    1.    当前的ParseContext：pctx；
    2.    一个序列的Transform：transformations；
    Optimizer在初始化时，向transformations序列中依次加入各个Transform，在执行时(
optimize()方法中)按照顺序依次调用每个Transform，每个Transform的输入都是当前Optimizer的
pctx，输出都重新赋值给该pctx。第一个Transform的pctx是被语法分析器显式设置的
(setPctx()方法)。
    Optimizer可能根据配置信息/选项跳过（不执行）某些Transform。

*   Transform
    这是一个接口，用于表示一个变换遍。它的定义非常简单，仅仅包含一个方法：
    ParseContext transform(ParseContext pctx) throws SemanticException;
    它的用法从Optimizer中可以看出。

*   遍历框架
    其实，有了Optimizer和Transform的定义，已经可以写变换遍了。由于很多变换遍的逻辑都是
很相似的：
    1.    按照某种顺序(如前序、后序等)遍历整个IL；
    2.    在遍历过程中，每到一个节点，对其进行处理：
    对一个节点的处理可能分为不同的情况，针对不同的情况进行不同的处理。一个简单的
    例子就是，针对不同的节点（load、map join、filter）做不同的处理。所以，在这里
    我们有一个（规则 --> 处理函数）的映射集合，根据节点满足的规则选择处理函数。
    有了这些观察，Hive的遍历框架就很容易理解了：
    1.    Node：该接口表示IL中的每个节点，被框架使用；
    2.    GraphWalker：该接口表示一个遍历器，它只有一个接口：
    void startWalking(Collection startNodes, HashMap nodeOutput)
        throws SemanticException;
    其中，startNodes表示从这些节点开始遍历，遍历包括这些节点和它们直接/间接的后继
    节点；nodeOutput如果不为null，它表示节点到对象的一个映射，这个对象就是遍历中
    NodeProcessor处理这个节点时的返回值。
    在框架中默认实现了DefaultGraphWalker，这是一个后序遍历；PreOrderWalker，这是一个
    前序遍历。
    3.    NodeProcessor与NodeProcessorCtx：NodeProcessorCtx接口只是一个标记接口，用于表示
    某个节点处理器的上下文信息。
    NodeProcessor接口表示一个节点处理函数，它定义了一个方法：
    Object process(Node nd, Stack stack, NodeProcessorCtx, procCtx,
        Object... nodeOutputs) throws SemanticException;
    在遍历过程中，如果某个节点满足了该Processor的规则，则会针对这个Node调用这个函数。
    其中，nd表示满足规则的节点；stack表示当前的节点栈，这个栈递归地包含nd节点的前驱
    节点，直到某些startNodes为止；procCtx表示这个processor的上下文，用于保存这个
    处理函数特定的、跨节点的信息；nodeOutput是这个节点的所有直接后继节点被处理时
    process()函数的返回值。
    4.    Rule：该接口表示一个规则，它最重要的一个方法是：
    int cost(Stack stack) throws SemanticException;
    其中，stack是当前的节点栈，stack顶部的节点就是正在遍历的节点。每个规则对应一个
    处理函数。在当前所有可用规则中，cost()返回值最小的规则是“匹配规则”。
    5.    Dispatcher：该接口表示一个分发器。如前文所述，每个Transform都有一组
    (规则 --> 处理函数）的集合，这组集合注册给一个Dispatcher，Dispatcher注册给
    GraphWalker。当调用GraphWalker的startWalking后，GraphWalker会按定义的顺序遍历
    每个节点，每遍历到一个节点，就会针对它调用Dispatcher的dispatch()函数，在这个函
    数内部，Dispatcher会依次尝试匹配每个Rule，最终针对当前节点调用匹配到的Rule对应
    的NodeProcessor。
    dispatch()方法和NodeProcessor的process()方法参数类似，只是没有NodeProcessorCtx
    参数。
    有了这个遍历框架，实现一个Transform时就会避免很多重复的代码。

*   一个改进点
    将Transform组织成树的形式，即，一个Transform可以包含若干个子Transform。当执行这种
Transform时，该Transform本身不做什么操作，而是按序执行各个子Transform。同时，存在一个
TransformCtx，在几个子Transform中共享。这是因为，一个顶层的Transform应该代表一个逻辑
上语义等价的变换，这样就可以方便地启用/禁用某个Transform；而一个变换不一定通过一个遍历
就可以完成，它可能包含若干个（可能被复用的）遍历。这种情况用子Transform可以很好的表达。