论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2011-12-21 08:42 |只看该作者 |倒序浏览

昨天晚上看了一下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<Node> startNodes, HashMap<Node, Object> nodeOutput)         throws SemanticException;     其中，startNodes表示从这些节点开始遍历，遍历包括这些节点和它们直接/间接的后继     节点；nodeOutput如果不为null，它表示节点到对象的一个映射，这个对象就是遍历中     NodeProcessor处理这个节点时的返回值。     在框架中默认实现了DefaultGraphWalker，这是一个后序遍历；PreOrderWalker，这是一个     前序遍历。     3.    NodeProcessor与NodeProcessorCtx：NodeProcessorCtx接口只是一个标记接口，用于表示     某个节点处理器的上下文信息。     NodeProcessor接口表示一个节点处理函数，它定义了一个方法：     Object process(Node nd, Stack<Node> stack, NodeProcessorCtx, procCtx,         Object... nodeOutputs) throws SemanticException;     在遍历过程中，如果某个节点满足了该Processor的规则，则会针对这个Node调用这个函数。     其中，nd表示满足规则的节点；stack表示当前的节点栈，这个栈递归地包含nd节点的前驱     节点，直到某些startNodes为止；procCtx表示这个processor的上下文，用于保存这个     处理函数特定的、跨节点的信息；nodeOutput是这个节点的所有直接后继节点被处理时     process()函数的返回值。     4.    Rule：该接口表示一个规则，它最重要的一个方法是：     int cost(Stack<Node> 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可以很好的表达。

返回列表

Chinaunix › 论坛 › IT运维 › Hadoop和大数据技术 › Hive HQL优化器

[Hive] Hive HQL优化器 [复制链接]