Hive SQL编译原理(上)

living 发表于 2021/07/30 17:07:00 2021/07/30
【摘要】 一、编译模块整体介绍1 Hive执行过程回顾client:用户通过客户端提交查询操作Driver:提供执行接口,负责接收查询请求并建立session,创建一系列环境参数等Compiler:Hive的编译器,负责将sql转化为平台可执行的执行计划MetaStore:Hive的元数据服务器Execution Engine:执行引擎,负责提交Compiler 编译好的执行计划到不同的平台上用户通过...

一、编译模块整体介绍

1 Hive执行过程回顾

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

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

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

MetaStore:Hive的元数据服务器

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

用户通过clientDriver提交Hive SqlDriverSql交给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 analysisScanning

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

语法分析(Syntax analysisParsing

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

 

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

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

2 antlr概述

  • ANTLR (ANother Tool for Language Recognition ) 是一种语言识别工具,它提供了一个框架,可以通过包含 Java, C++, C# 动作(action)的语法描述来构造语言识别器,编译器和解释器。
  • 使用Antlr 开源软件定义语法规则,大大简化了词法和语法的编译分析过程,仅仅需要维护一份规则文件即可。
  • 1989年发布第一个版本,叫做PCCTS,即antrl v1;当前市面流行的是2013年发布的antlr v4hive所用的是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是专门用于开发AntlrIDE,可以检查规则文件的语法,进行语法高亮,调试规则文件,生成解析器、可视化语法图、解析树、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    : '+';

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

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

3)包含两部分规则,词法的NUMBERPLUS ,和一个语法规则expr。词法规则常常以大写字母开头,语法规则以小写字母开头。

4NUMBER 定义了字符'1'token

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

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

5)验证测试

1+1

1+2

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

2token增强

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

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

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

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

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

3、语法增强

(1)让我们接受更复杂的表达式,像11+21+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和一个十六进制值0CAntlrUnicode编码,所以我们将它定义为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生成解析器

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

1idea安装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>
     
<!-- antlrplugin -->
     
<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 Hiveantlr语法文件

Hive工程的pom文件设置了使用antlr插件编译HiveLexer.gHiveParser.gHintParser.g文件

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

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


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



ParseDriver

Antlr生成了HiveLexerHiveParser类之后,ParseDriver负责组织、驱动整个词法、 语法分析流程,并得到分析后的AST(调用词法、语法解析的入口类)。

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

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

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

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

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

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


4.2 源码跟踪

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

5.png

6.png

7.png

8.png

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

2.png

3.png

4.png

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;

5.png

(3)查看其词法解析

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

6.png

(4)修改源码打印出ASTNode

7.png

得到的树为:

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

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

8.png

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

9.png

(3)其中外层的from是嵌套了子查询的,对应TOK_SUBQUERY

10.png

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

1.png

2.png

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。