一、编译模块整体介绍

1 Hive执行过程回顾

client:用户通过客户端提交查询操作

Driver:提供执行接口，负责接收查询请求并建立session，创建一系列环境参数等

Compiler:Hive的编译器，负责将sql转化为平台可执行的执行计划

MetaStore:Hive的元数据服务器

Execution Engine:执行引擎，负责提交Compiler 编译好的执行计划到不同的平台上

用户通过client向Driver提交Hive Sql，Driver将Sql交给Complier，由Complier生成执行计划，Complier生成执行计划的过程需要与MetaStore做交互来获取Sql相关表，字段等属性信息，执行计划生成后，将执行计划交给Driver,Driver通过Execution Engine把执行计划提交相应平台执行，最后把执行的结果返回给用户。

这次我们主要分析的模块就是Compiler ，Hive的编译模块

 

2 Hive sql的编译总流程

词法、语法解析: Antlr定义SQL的语法规则，完成SQL词法，语法解析，将SQL转化为抽象语法树AST Tree

语义解析:遍历AST Tree，与metastore交互，检查抽象语法树中的表、列是否存在，抽象出查询的基本组成单元QueryBlock，里面保存了很多相关的元数据信息

生成逻辑执行计划: 遍历QueryBlock，翻译为执行操作树OperatorTree

优化逻辑执行计划: 逻辑层优化器进行OperatorTree变换，合并Operator，达到减少MapReduce Job，减少数据传输及shuffle数据量

生成物理执行计划: 遍历OperatorTree，翻译为MapReduce任务（其实这一步就可以交给yarn去执行了）

优化物理执行计划: hive一般还会利用物理层优化器进行进一步优化，进行MapReduce任务的变换，生成最终的执行计划

3 Hive sql的编译的代码流程

二、阶段1-词法解析与语法解析

定义SQL的词法、语法规则文件，Antlr生成词法解析程序和语法解析程序，完成SQL词法，语法解析，将SQL转化为抽象语法树AST Tree

1 词法分析和语法分析

词法分析（Lexical analysis或Scanning）

• 词法分析就是从左至右逐个字符地扫描源程序，产生一个个单词符号（Token），把源程序的字符串改造成为tokens 列表（单词序列）。
• 进行词法分析的程序或者函数叫词法分析器（Lexer）
• hive中的词法分析，就是分析sql里每个单词该怎么组成

语法分析（Syntax analysis或Parsing）

• 在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等。语法分析程序判断源程序在结构上是否正确，语法如果有错的话，抛出语法错误。
• 进行语法分析的程序或者函数叫语法分析器（Parser）
• hive中的语法分析，就是研究这些单词该以怎样的结构组成一个sql的

 

举例：select name from t1 where id=1.

• 词法分析就是识别单词或符号，比如select、from、=。
• 语法分析就是匹配语法规则，比如符合语法规则的句子是from子句在where子句前面而不是后面

2 antlr概述

• ANTLR (ANother Tool for Language Recognition ) 是一种语言识别工具，它提供了一个框架，可以通过包含 Java, C++, 或 C# 动作（action）的语法描述来构造语言识别器，编译器和解释器。
• 使用Antlr 开源软件定义语法规则，大大简化了词法和语法的编译分析过程，仅仅需要维护一份规则文件即可。
• 1989年发布第一个版本，叫做PCCTS，即antrl v1；当前市面流行的是2013年发布的antlr v4；hive所用的是antlr v3.5.2

 

antlr3官网：https://www.antlr3.org/

antlr4官网：https://www.antlr.org/

antlr3文档：

https://theantlrguy.atlassian.net/wiki/spaces/ANTLR3/pages/2687234/ANTLR+v3+documentation

antlr3语法：http://www.irisa.fr/caps/people/hardy/m1comp/doc/metalang.html

https://blog.csdn.net/timesir/category_7207797.html

https://blog.csdn.net/u013407592/article/details/50261203

 

开发流程：编写规则文件à生成解析器à调用解析器

3 antlr3

3.1 利用Antlr IDE开发规则文件

3.1.1 antlrworks介绍

antlrworks是专门用于开发Antlr的IDE，可以检查规则文件的语法，进行语法高亮，调试规则文件，生成解析器、可视化语法图、解析树、AST，直观看到语法图、规则的依赖关系图

 

下载地址：https://www.antlr3.org/download.html

帮助文档：https://www.antlr3.org/works/help/index.html

注：我们可以将jar的路径添加进环境变量中的CLASSPATH，这样就可以直接用命令打开，如：CLASSPATH = %CLASSPATH%; C:/antlrworks-1.4.jar

这样就能直接运行java org.antlr.works.IDE打开antlr的开发工具

3.1.2 规则文件示例

1、最基础版

grammar Math;

options {
  output=AST;
  ASTLabelType=CommonTree;
}

expr : NUMBER PLUS NUMBER;

NUMBER  : '1';

PLUS    : '+';

（1）grammar声明规则文件名，要求必须与文件名保持一致

（2）options里面定义了输出的类型

（3）包含两部分规则，词法的NUMBER、PLUS ，和一个语法规则expr。词法规则常常以大写字母开头，语法规则以小写字母开头。

（4）NUMBER 定义了字符'1'的token

PLUS 定义了一个简单的字符token：+

expr 定义了一个语法规则，这个语法表示希望接收一个NUMBER token，一个PLUS token，一个NUMBER token，并顺序固定。如果以不同的顺序将会触发错误消息。

（5）验证测试

1+1

1+2

============================

2、token增强

NUMBER  : '1';  -- 输入1+1 能正常解析   输入1+2 --2不匹配出现MissingTokenException

NUMBER  : '1' | '2'; -- 能匹配1+1、1+2、2+2

NUMBER  : '0'..'9';  --匹配0-9的一位数  1+3能识别，1+39不能识别

NUMBER  : ('0'..'9')+ ; --定义了包含0到9的字符的token，这些字符可以重复一次或一次以上

=============================

3、语法增强

(1)让我们接受更复杂的表达式，像1或1+2或1+2+3+4，这些表达式以一个数字开头，然后加上一个加法标志和一个数（有可能多于一次）;

*表示0或多次

expr : NUMBER (PLUS NUMBER)*

(2)如果你既想实现加法又想实现减法，你可以做一个小的调整:定义减号、添加或的逻辑

expr : NUMBER ((PLUS | MINUS) NUMBER)*

MINUS : '-';

(3)如果你希望语法分析完成加减乘除运算，则需要递归，因为乘除都是先计算的

expr         : term ( ( PLUS | MINUS ) term )*;

term         : NUMBER( ( MULT | DIV ) NUMBER)*;

MULT  : '*' ;

DIV   : '/' ;

=============================

4、忽略空格

我们的语法是不能容忍空格的：当遇到空格，标签符，回车等它会给出警告。我们要告诉词法分析器丢弃任何它所找到的空格是安全的。

首先，我们要定义空格：

    一个空格：‘ ’

    一个标签符是这样表示的：‘\t’

    新的一行是这样表示的：‘\n’

    一个回车符是这样表示的：‘r’

    一个换页符有一个十进制值12和一个十六进制值0C。Antlr用Unicode编码，所以我们将它定义为4个十六进制数字：‘\u000C’

把这些放在一块，并用一个“or”连接，允许一个或多个一块出现，那么你会得到：

WHITESPACE : ( '\t' | ' ' | '\r' | '\n' | '\u000C' )+;

那么，如果我们写3 + 4*5这个表达式，词法分析器会生成 NUMBER WHITESPACE PLUS WHITESPAC NUMBER MULT NUMBER，而且这将导致语法分析器抱怨未知WHITESPACE标记。我们需要一种方法对于语法分析器，将他们隐藏起来。

Antlr在词法分析器和语法分析器之间包含两种沟通渠道，默认渠道和隐藏渠道。语法分析器一次只听取一个渠道的内容，所以你可以用将它至于隐藏渠道的方法来隐藏一个标记。

（可以有多于两种渠道而且语法分析器可以单独听取他们中的任一个，也可以从所有合并的渠道获取信息。这在你正在写一个文字处理工具的时候非常有用，这个文字处理工具需要解析出空白和注释的输出，而且让语法分析器忽略这些元素）

对于连续不断的隐藏要求，你用设置这些token的$channel来隐藏他们。这要求你加一些大括号来在词法分析器中添加一点点代码。

5、可读性增强

（1）添加注释，比如 // 或者/*....*/

（2）将你的简单token定义（单字符，单词等）收集到文件顶部的token中

（3）

ANTLR文法中语法规则是在词法规则基础上建立的。但不一定每个词法规则都会被语法规则直接使用。这就象一个类的公有成员和私有成员，公有成员是对外公开的会被外界直接调用。而私有成员不对外公开是由公有成员间接调用的。在词法规则中那些不会被语法规则直接调用的词法规则可以用一个fragment关键字来标识，fragment标识的规则只能为其它词法规则提供基础。

DIGIT规则将不能被语法规则直接调用。

 

grammar Math;

options {
  output=AST;
  ASTLabelType=CommonTree;
}
tokens{
  PLUS     = '+' ;
  MINUS    = '-' ;
  MULT     = '*';
  DIV      = '/';
}
/*------------------------------------------------------------------

 * PARSER RULES

 *------------------------------------------------------------------*/
expr    : term ( ( PLUS | MINUS )  term )* ;
term    : NUMBER ( ( MULT | DIV ) NUMBER )* ;
/*------------------------------------------------------------------

 * LEXER RULES

 *------------------------------------------------------------------*/
NUMBER  : (DIGIT)+ ;
WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+  { $channel = HIDDEN; } ;
fragment DIGIT  : '0'..'9' ;

 

3.2 利用antlr生成解析器

3.2.1 antlr IDE

点击菜单栏的Generateà

• Generate Code: 生成当前语法的解析器/词法分析器代码。
• Show Parser Code: 显示当前语法的解析器代码。
• Show Lexer Code: 显示当前语法的词法代码。
• Show Rule Code: 显示语法的当前规则的代码。

3.2.2 antlr command

参考：

https://theantlrguy.atlassian.net/wiki/spaces/ANTLR3/pages/2687158/Command+line+options

（1）下载antlr-3.5.2-complete.jar包

http://www.antlr3.org/download/antlr-3.5.2-complete.jar

（2）命令行使用antlr生成解析器

java -jar antlr-3.5.2-complete.jar Math.g

或者

java -cp antlr-3.5.2-complete.jar org.antlr.Tool Math.g

参数列表：

usage: java org.antlr.Tool [args] file.g [file2.g file3.g ...]

  -o outputDir          指定生成所有输出的输出目录

  -fo outputDir         与-o相同，但是即使具有相对路径的文件也强制使用dir

  -lib dir              指定token文件的位置

  -depend             生成文件依赖项

  -report            打印有关处理的语法的报告

  -print                无需任何操作即可打印出语法

  -debug               生成一个发出调试事件的解析器

  -profile              生成解析器，该解析器计算性能分析信息

  -nfa                 为每个规则生成一个NFA

  -dfa                  为每个决策点生成DFA

  -message-format name  名称指定消息的输出样式

  -verbose              生成ANTLR版本和其他信息

  -X                   显示扩展参数列表

 

注：我们可以将jar的路径添加进环境变量中的CLASSPATH，这样就不需要指定jar包，如：

CLASSPATH = %CLASSPATH%; C:/antlr-3.2.jar

这样就能直接运行java org.antlr.Tool XXX.g

 

3.2.3 antlr maven plugin

（1）idea安装antlr3的插件（不兼容，没人维护了）

（1）新建项目，pom.xml添加依赖、antlr编译插件

（2）新建grammar文件

（3）在pom.xml中添加plugin

<dependencies>   <dependency>     <groupId>org.antlr</groupId>     <artifactId>antlr-runtime</artifactId>     <version>3.5.2</version>   </dependency> </dependencies> <build>   <pluginManagement>     <plugins>       <!-- antlr的plugin -->       <plugin>         <groupId>org.antlr</groupId>         <artifactId>antlr3-maven-plugin</artifactId>         <executions>           <execution>             <goals>               <goal>antlr</goal>             </goals>           </execution>         </executions>         <configuration>           <sourceDirectory>./src/main/java/org/example/grammar</sourceDirectory>           <includes>             <include>Math.g</include>           </includes>         </configuration>       </plugin>     </plugins>   </pluginManagement> </build>

（4）命令：mvn org.antlr:antlr3-maven-plugin:antlr

参考：

https://theantlrguy.atlassian.net/wiki/spaces/ANTLR3/pages/2687051/Building+ANTLR+Projects+with+Maven

https://theantlrguy.atlassian.net/wiki/spaces/ANTLR3/pages/2687071/Building+ANTLR+with+Maven

4.3 调用解析器

（1）将生成的解析器代码拷贝到我们的项目中

（2）编写测试样例调用，将输入的字符串解析成AST树（抽象语法树）

public static void run(String expr) throws RecognitionException {
    // 对每一个输入的字符串，构造一个 ANTLRStringStream 流 in
    CharStream in = new ANTLRStringStream(expr);
    // 用 in 构造词法分析器 lexer，词法分析的作用是产生记号token
    MathLexer lexer = new MathLexer(in);
    // 用词法分析器 lexer 构造一个记号流 tokens  --完成词法解析
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    // 再使用 tokens 构造语法分析器 parser --完成语法解析
    MathParser parser = new MathParser(tokens);
    // 获取解析树
    CommonTree tree = parser.expr().getTree();
}

参考：

https://theantlrguy.atlassian.net/wiki/spaces/ANTLR3/pages/2687232/How+do+I+use+ANTLR+v3+generated+Lexer+and+Parser+from+Java

4 Hive中解析过程

4.1 Hive的antlr语法文件

Hive工程的pom文件设置了使用antlr插件编译HiveLexer.g、HiveParser.g、HintParser.g文件

HiveLexer.g是Hive的词法文件，其中定义了Hive所有的关键字、保留字以及可以被Hive识别的合法字符，不在其中定义的字符，将被Hive认为是非法字符输入。

HiveParser.g是语法分析的总入口，里面import了四个规则文件

编译后得到antlr根据.g文件生成的词法、语法解析器

ParseDriver

在Antlr生成了HiveLexer和HiveParser类之后，ParseDriver负责组织、驱动整个词法、 语法分析流程，并得到分析后的AST（调用词法、语法解析的入口类）。

在ParseDriver中定义了几个辅助类，简要说明如下。

ANTLRNoCaseStringStream继承自ANTLRStringStream类，是Lexer使用的 输入流之一（基于字符串的输入流）。这里定义的辅助类的作用就是，在Lexer使用其LA()(look ahead)从流中查看字符的时候，将字符转换成大写字符，从而实现大小写不敏感的lexer。在Hive.g 定义的语法中，只要识别大写字母就可以了。然而，真正存放在$token.text中的值仍然是原始String 中的值（这种值是lexer通过ANTLRStringStream的consume()方法获得的，这个方法没有在辅 助类中override）。

HiveLexerX是实际使用的词法分析类，它继承自antlr生成的HiveLexer。提供这个类主要是显示、记录分析过程中的错误信息。

TreeAdapter对象，实际上是CommonTreeAdapter对象。在使用生成的Parser的时候， 会给它设置该适配器对象。Parser每当需要使用某个token创建一个AST节点的时候，会调用该对象 的create(token)进行创建。这里，适配器对象会创建一个ASTNode并返回。ASTNode是Hive自己定义的一个树节点对象，它继承自Antlr的CommonTree类（antlr生成的AST是CommonTree，参考之前的例子），并实现了Node和Serializable接 口。我们在前面grammar options中看到，这个Parser返回的是CommonTree类型的对象，由于 ASTNode是CommonTree的子类，所以并不违反协议。

Hive之所以要这样做，主要是： （1）实现Node接口，以便可以使用Hive自己的遍历框架（后文描述）对AST进行遍历；（2）实现Serializable接口，以便可以将AST序列化。

HiveParse类维护了一个静态成员xlateMap，它将关键字的名字（以 KW_开头的名字，与Hive.g中定义的相同）映射到关键字本身。xlateMap也包含内置操作符名字到 操作符字符串的映射。

4.2 源码跟踪

Driver.run()--》runInternal()--》compileInternal()--》compile()--》ParseUtils.parse()

ParseUtils.parse()--》pd.parse(command, ctx, viewFullyQualifiedName)

4.3 案例说明

（1）创建表

CREATE TABLE score (
id INT,
math_score INT,
english_score INT
);
CREATE TABLE people (
id INT,
age INT,
name INT
);
--关闭mapjoin
set hive.auto.convert.join = false;

（2）开启debug，执行下面语句

SELECT sum(v)
FROM (
SELECT score.id,
100 + 80 + score.math_score + score.english_score AS v
FROM people
JOIN score
ON people.id = score.id
AND people.age > 10
) tmp;

（3）查看其词法解析

解析出了74个token，其中包含空格、换行符（\n）、结束标志（<EOF>）、SQL关键字（select等）、符号（括号、点、逗号等）

（4）修改源码打印出ASTNode

得到的树为：

（1）这是Hive查询语句的语法树主体结构，所有的查询语句都会转换成这样结构的语法树，不同的是from、select等子树的不同，子树的生成同样也是根据语法文件中定义的语法规则，对各个子句进行重写，生成对应的语法树子树，拼接到语法树的主体结构上，最终生成HiveQL对应的完整抽象语法树。

根节点是nil，下面跟着SQL语法树主体和结束标志符<EOF>

（2）语法树由TOK_FROM和 TOK_INSERT 两部分组成。TOK_FROM代表了 from子句的语法树；TOK_INSERT 子树是查询的主体部分，包含了查询结果目的数据源TOK_DESTINATION子树（Hive的查询的数据会存在hdfs的临时文件中）、select子句语法树、body子句(where, group,having等)语法树。

（3）其中外层的from是嵌套了子查询的，对应TOK_SUBQUERY

（4）每个表生成一个TOK_TABREF节点，对from关键字生成一个TOK_FROM节点，对查询的每个字段生成一个TOK_SELEXPR节点，每个使用到的属性列生成一个TOK_TABLE_OR_COL节点，where关键字对应生成TOK_WHERE节点。