hive ast

http://blog.csdn.net/zhifeidie/article/details/6919014

 

 

hive就是一个将sql语句转化为MR工具

hive的工作原理：

1、使用antlr定义sql语法，（详细见hive.g），由antlr工具将hive.g编译为两个java文件：HiveLexer.java    HiveParser.java，可以将输入的sql解析为ast树

2、org.apache.hadoop.hive.ql.Driver对ast树进行初步的解析（combile），调用相应的语法分析器进行分析处理（包括DDl，Explain，Load等，其中最重要的是：SemanticAnalyzer）

3、SemanticAnalyzer的主要分析过程：调用analyzeInternal函数

• 1）doPhase1过程：主要是将sql语句中涉及到的各种信息存储起来，存到QB中去，供后续调用
• 2）getMetaData：这个过程主要是获取元数据信息，主要是sql中涉及到的表到元数据的关联
• 3）genPlan：这是最重要的过程之一，主要是生成算子树（operator tree）
• 4）optimize：优化，对算子树进行一些优化操作，例如列剪枝等
• 5）genMapRedTasks：这个步骤是最关键的步骤，将算子树通过一定的规则生成若干相互以来的MR任务

4、Driver编译完成以后，开始进入执行阶段（execute），执行过程按照任务树从roottask开始依次执行，直至结束。

 

 

genplan是语法分析最重要的一个阶段，在genplan过程中生成一个算子树。

 

1、一条sql语句的结构：

一条sql主要包括，insert子句，select子句，from子句，groupby子句，以及其他的条件子句，如limit，orderby等，还有join和union等操作符。其中的from子句，一般可以直接跟一个表，多个表（笛卡尔积等同于join），或者一个子查询，或者由join或union连接的两个表，或者两个子查询。包含子查询则意味着sql语句自身会包含这一些递归的操作。

 

2、hive对一条sql执行的过程：

一条sql语句（以查询sql为例）的目的最终是将一个表或者若干个表中的所有行数据，一条一条的进行处理，最终生成一组目标记录。为了实现这样的目的，首先将处理过程分解为若干个算子，将初始的表数据记录依次通过这些算子来计算，最终得出结果。

例如：select a from tbl where b>1 order by c，对于这条sql，首先需要一个ts（table scan）算子，从表中读出数据，然后读出的数据经过一个fil（filter）算子，过滤那些不满足条件b>1的数据，最后经过一个fetch算子，将正确的数据返回。对于任意复杂的sql语句都可以生成这样的算子树进行处理。

 

 

3、genplan的过程：有了以上信息以后可以根据ast树生成算子树

 

1）任何一个查询子句首先检查这个子句有没有子查询语句，如果有首先递归的对子查询语句进行处理得出子查询的算子树，这个算子树的唯一输出算子，作为本查询的输入算子。

2）一个查询子句的输入来源，要么是子查询语句，要么就是来自表 ，那么一个查询在处理完子查询以后，要对输入表进行处理，生成一个tablescan算子

3）生成genLateralViewPlans算子？？

4）对于from子句包含join的查询语句来说，这里必须对join进行处理，生成join算子

5）以上的处理都集中于输入数据的算子处理上，完成这些以后进入genbodyplan，主要处理select子句，groupby等子句

6）对于每个输入源，分析过滤条件，生成一个FilterOperator作为一个子op

7）生成groupby operator

8）生成hiveing operator

9）生成select operator

10）生成filesink operator

 

以上就是operator tree，实际上这个数据结构不一定有唯一的根节点，也并不一定有唯一的归宿节点，最终按照这个树即可实现sql的语义。

 

AST:抽象语法树

抽象语法树（AST）

最近在做一个类JAVA语言的编译器，整个开发过程，用抽象语法树（Abstract SyntaxTree,AST）作为程序的一种中间表示，所以首先就要学会建立相对应源代码的AST和访问AST。Eclipse AST是Eclipse JDT的一个重要组成部分，定义在包org.eclipse.jdt.core.dom中，用来表示JAVA语言中的所有语法结构。

Eclipse AST的总体结构

1、org.eclipse.jdt.core.dom.AST（AST节点类）

Eclipse AST的工厂类，用于创建表示各种语法结构的节点。

 

2、org.eclipse.jdt.core.dom.ASTNode及其派生类（AST类）

用于表示JAVA语言中的所有语法结构，在实际使用中常作为AST上的节点出现。

 

3、org.eclipse.jdt.core.dom.ASTVisitor（ASTVisitor类）

Eclipse AST的访问者类，定义了统一的访问AST中各个节点的方法。

详细介绍：

一、AST节点类

整体结构包括CompilationUnit类(编译单元）、TypeDeclaration类（类型声明）、MethodDeclaration类（方法声明）；

语句包括Block类（语句块）、ExpressionStatement类（表达式）、IfStatement(if语句）、WhileStatement类（while语句）、EmptyStatement类（空语句）、BreakStatement类和ContinueStatement类；

表达式包括MethodInvocation类（方法调用）、Assignment类（赋值表达式）（“=”、“+=”、“-=”、“*=”、“/=”）、InfixExpression类（中缀表达式）（“+”、“-”、“*”、“/”、“%”、“==”、“！=”、“<"、“<=”、“>=”、“&&”、“||”。）、 PrefixExpression类（前缀表达式）（“+”PLUS  “-”MINUS  “！”NOT）、ParenthesizedExpression类（带括号的表达式）、NumberLiteral类（整数）、Name类（simple）、MethodInvocation类（方法调用）。

二、AST类

关键是创建编译单元节点，创建类AST的实例。

AST ast = AST.newAST(JLS3);

三、ASTVisitor类

它提供与节点类有关的visit()方法和endVisit()法，与节点类无关的preVisit()方法和postVisit()方法。

boolean  visit( T node):这类方法如果返回true，则接着访问子节点。如果返回false，则不再访问子节点。

void endVisit(T node):这类方法在节点node的子节点已经被访问或者是在visit(node)返回false后调用。

void preVisit():这类方法在visit(node)之前被调用。

void postVisit():这类方法在endVisit(node)之后被调用。

在做简单解释器过程中，分析句子时我主要用到了上面的visit()和endVisit()方法，其中visit()方法是比较好理解的，主要是endVisit()方法在没有特定语法分析树的情况下分析是比较抽象的，所以下面我举几个例子分析。

endVisit（）在node的子节点已被访问后调用型：

a、赋值语句分析为例：

 

i1 = 1;

i4 = i1;

它们对应语法树结构： 

Expressionstatement

 

Assignment

 

 

 

 

simplename

numberLiteral

 

 

 

 

Expressionstatement

Assignment

 

 

 

 

 

simplename

simplename

 

 

 

实现程序：

int rightis_num = 1;

visit(Assignment n){

return true;

}

public void endVisit(Assignment n)//访问完所有的节点后，rightis_num已经能够确定

    {

        Expression string = n.getLeftHandSide();//返回表达式左部

        String simplename =((SimpleName) string).getIdentifier();//将变量串赋给simplename

        try

        {  

           if(rightis_num == 1)

           {

               Expression data1 = n.getRightHandSide();//返回表达式右部

               System.out.println(simplename);

               hm.put(simplename,new Integer(((NumberLiteral) data1).getToken()));//将变量及值加入hashmap

               System.out.println(hm.get(simplename));

        }

           else//右部为标识符

           {  

               Expression data2 = n.getRightHandSide();//返回表达式右部

               String rightname = ((SimpleName) data2).getIdentifier();

               hm.put(simplename,hm.get(rightname));

               System.out.println(hm.get(simplename));             

           }

        }

        catch(Exception e)

        {}

    }

 

 

 

对应源程序AST的建立

            

class Program{

static void main(){

    i = 10;

    }

}

 

/************实现方法************/

 

AST ast = AST.newAST(JLS3);

 

CompilationUnit cu = ast.newCompilationUnit();//CompilationUnit实例中包含一个TypeDeclaration

 

TypeDeclaration type = ast.newTypeDeclaration();//TypeDeclaration实例表示程序中的类

type.setName(ast.newSimpleName("Program"));

 

MethodDeclaration method = ast.newMethodDeclaration();//TypeDeclaration实例中添加类Program中的方法main();

method.setName(ast.newSimpleName("main"));

type.bodyDeclarations().add(method);

method.modifiers().add(

    ast.newModifier(Modifier.ModifierKeyword.STATIC_KEYWORD));//设置方法main()的modifier修饰语为static

method.setReturnType2(ast.newPrimitiveType(PrimitiveType.VOID));//设置方法main()的返回类型为void

 

Block mainBody = ast.newBlock();

method.setBody(mainBody);//构造main函数的函数体mainBody

 

//向方法main函数体mainBody中添加语句

Assignment.assign = ast.newAssignment();//构建赋值表达式

assign.setLeftHandSide(ast.newSimpleName("i"));//设置赋值表达式的左值为i

assign.setOperator(Assignment.Operator.ASSIGN);//设置赋值表达式的赋值算符为=

assign.setRightHandSide(ast.newNumberLiteral("10"));//设置赋值表达式的右值为数字10

 

ExpressionStatement statement = ast.newExpressionStatement(assign);

mainBody.statements().add(statement);//由赋值表达式构建语句，并把这个语句加入方法Main()的函数体。

 

              

 

访问方法

在Eclipse AST中，结合AST节点的accept()方法和ASTVisitor实例，假设待访问的AST树的根节点为root，则调用root.accept()就可以启动对这棵AST树的遍历。

 

总结：做这个简单解释器的主要目的是熟悉程序源代码对应AST的映射，创建对应的AST方法都比较的固定，问题不大。难主是难在遍历树上，分析不同的语句结构，需要重写Visit()方法，同时要适当利用endVisit()方法增加一些控制变量，以决定应该解释句子的哪一分支。到现在对preVisit()和postVisit()方法仍然不怎么了解，在接下来的编译器开发中仍需慢慢摸索。熟悉了AST相关知识，后续工作可以展开了。