Hive SQL编译原理（上）

一、编译模块整体介绍

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开发规则文件

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的开发工具

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来隐藏他们。这要求你加一些大括号来在词法分析器中添加一点点代码。

WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+  { $channel = HIDDEN; } ;

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生成解析器

点击菜单栏的Generateà

Generate Code: 生成当前语法的解析器/词法分析器代码。

Show Parser Code: 显示当前语法的解析器代码。

Show Lexer Code: 显示当前语法的词法代码。

Show Rule Code: 显示语法的当前规则的代码。

参考：

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

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

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

（2）新建grammar文件

（3）在pom.xml中添加plugin

org.antlr

antlr-runtime

3.5.2

org.antlr

antlr3-maven-plugin

antlr

./src/main/java/org/example/grammar

Math.g

（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）、结束标志（）、SQL关键字（select等）、符号（括号、点、逗号等）

（4）修改源码打印出ASTNode

得到的树为：

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

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

（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节点。

Hive SQL

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。