Chinaunix首页 | 论坛 | 博客
  • 博客访问: 958057
  • 博文数量: 104
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1868
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(104)

文章存档

2013年(1)

2012年(9)

2011年(41)

2010年(3)

2009年(3)

2008年(47)

分类: 云计算

2011-06-29 09:09:50

昨天晚上看了一下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可以很好的表达。

阅读(3409) | 评论(0) | 转发(0) |
0

上一篇:Why not C++

下一篇:HindleyMilner类型推导器

给主人留下些什么吧!~~