Hive SQL编译原理(上)

网友投稿 1080 2022-05-30

一、编译模块整体介绍

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' ;

Hive SQL编译原理(上)

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小时内删除侵权内容。

上一篇:园区第三方认证类API概述及向导
下一篇:从浏览器渲染到性能优化
相关文章