- 论坛徽章:
- 0
|
昨天晚上看了一下Hive HQL的优化器。这个优化器相比于GCC4、LLVM的优化器而言极其简单,但<br>结构也非常地清晰。<br><br>Hive优化器结构<br><br>* 总体结构<br> 总体上讲,Hive的优化器是一种基于Pass的优化器,Pass在Hive中称为Transform。与此同时,<br>为了便于每个Transform的编写,Hive还提供了一个框架,用于遍历一遍当前DAG图,并在每个节<br>点上执行规则指定的操作。<br> Hive优化器在ql/optimizer目录中,优化器的入口是Optimizer类和PhysicalOptimizer。前者<br>主要是在中间语言上进行优化,后者则是在生成的MapReducer执行计划上进行优化。这两个优化<br>器使用的遍历框架一样,之所以区分两个不同的情况,是因为,Optimizer处理的DAG图是HQL语言<br>编译得到的DAG图,而PhysicalOptimizer处理的DAG图是MapReduce任务构成的执行计划。除此以<br>外,两者的结构类似,这里仅仅分析Optimizer。<br> 用于遍历DAG图的框架在ql/lib目录下,核心的接口包括Node、GraphWalker、NodeProcessor<br>与NodeProcessorCtx、Rule、Dispatcher几个。<br> 在Hive编译器内部,有一个概念十分重要:ParseContext。这个类包含了当前的IL和相关的<br>一些信息。每个Transform都是以一个ParseContext作为参数,返回一个ParseContext作为结果。<br>可以说,ParseContext就是Hive处理HQL的信息的中心。<br><br>* Optimizer<br> 这是Hive优化器的驱动类。其实,更合适的叫法是PassManager或者TransformationManager,<br>因为它管理的transform不一定是“优化”,这些transform也可以完成规格化、阶段划分、代码<br>生成等其它任务。<br> Optimizer主要维护两个信息:<br> 1. 当前的ParseContext:pctx;<br> 2. 一个序列的Transform:transformations;<br> Optimizer在初始化时,向transformations序列中依次加入各个Transform,在执行时(<br>optimize()方法中)按照顺序依次调用每个Transform,每个Transform的输入都是当前Optimizer的<br>pctx,输出都重新赋值给该pctx。第一个Transform的pctx是被语法分析器显式设置的<br>(setPctx()方法)。<br> Optimizer可能根据配置信息/选项跳过(不执行)某些Transform。<br><br>* Transform<br> 这是一个接口,用于表示一个变换遍。它的定义非常简单,仅仅包含一个方法:<br> ParseContext transform(ParseContext pctx) throws SemanticException;<br> 它的用法从Optimizer中可以看出。<br><br>* 遍历框架<br> 其实,有了Optimizer和Transform的定义,已经可以写变换遍了。由于很多变换遍的逻辑都是<br>很相似的:<br> 1. 按照某种顺序(如前序、后序等)遍历整个IL;<br> 2. 在遍历过程中,每到一个节点,对其进行处理:<br> 对一个节点的处理可能分为不同的情况,针对不同的情况进行不同的处理。一个简单的<br> 例子就是,针对不同的节点(load、map join、filter)做不同的处理。所以,在这里<br> 我们有一个(规则 --> 处理函数)的映射集合,根据节点满足的规则选择处理函数。<br> 有了这些观察,Hive的遍历框架就很容易理解了:<br> 1. Node:该接口表示IL中的每个节点,被框架使用;<br> 2. GraphWalker:该接口表示一个遍历器,它只有一个接口:<br> void startWalking(Collection<Node> startNodes, HashMap<Node, Object> nodeOutput)<br> throws SemanticException;<br> 其中,startNodes表示从这些节点开始遍历,遍历包括这些节点和它们直接/间接的后继<br> 节点;nodeOutput如果不为null,它表示节点到对象的一个映射,这个对象就是遍历中<br> NodeProcessor处理这个节点时的返回值。<br> 在框架中默认实现了DefaultGraphWalker,这是一个后序遍历;PreOrderWalker,这是一个<br> 前序遍历。<br> 3. NodeProcessor与NodeProcessorCtx:NodeProcessorCtx接口只是一个标记接口,用于表示<br> 某个节点处理器的上下文信息。<br> NodeProcessor接口表示一个节点处理函数,它定义了一个方法:<br> Object process(Node nd, Stack<Node> stack, NodeProcessorCtx, procCtx, <br> Object... nodeOutputs) throws SemanticException;<br> 在遍历过程中,如果某个节点满足了该Processor的规则,则会针对这个Node调用这个函数。<br> 其中,nd表示满足规则的节点;stack表示当前的节点栈,这个栈递归地包含nd节点的前驱<br> 节点,直到某些startNodes为止;procCtx表示这个processor的上下文,用于保存这个<br> 处理函数特定的、跨节点的信息;nodeOutput是这个节点的所有直接后继节点被处理时<br> process()函数的返回值。<br> 4. Rule:该接口表示一个规则,它最重要的一个方法是:<br> int cost(Stack<Node> stack) throws SemanticException;<br> 其中,stack是当前的节点栈,stack顶部的节点就是正在遍历的节点。每个规则对应一个<br> 处理函数。在当前所有可用规则中,cost()返回值最小的规则是“匹配规则”。<br> 5. Dispatcher:该接口表示一个分发器。如前文所述,每个Transform都有一组<br> (规则 --> 处理函数)的集合,这组集合注册给一个Dispatcher,Dispatcher注册给<br> GraphWalker。当调用GraphWalker的startWalking后,GraphWalker会按定义的顺序遍历<br> 每个节点,每遍历到一个节点,就会针对它调用Dispatcher的dispatch()函数,在这个函<br> 数内部,Dispatcher会依次尝试匹配每个Rule,最终针对当前节点调用匹配到的Rule对应<br> 的NodeProcessor。<br> dispatch()方法和NodeProcessor的process()方法参数类似,只是没有NodeProcessorCtx<br> 参数。<br> 有了这个遍历框架,实现一个Transform时就会避免很多重复的代码。<br><br>* 一个改进点<br> 将Transform组织成树的形式,即,一个Transform可以包含若干个子Transform。当执行这种<br>Transform时,该Transform本身不做什么操作,而是按序执行各个子Transform。同时,存在一个<br>TransformCtx,在几个子Transform中共享。这是因为,一个顶层的Transform应该代表一个逻辑<br>上语义等价的变换,这样就可以方便地启用/禁用某个Transform;而一个变换不一定通过一个遍历<br>就可以完成,它可能包含若干个(可能被复用的)遍历。这种情况用子Transform可以很好的表达。<br><br> |
|