免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2506 | 回复: 0

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

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

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP