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
(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)、结束标志(
(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小时内删除侵权内容。