Hive SQL編譯原理（上）

一、編譯模塊整體介紹

1 Hive執(zhí)行過程回顧

client:用戶通過客戶端提交查詢操作

Driver:提供執(zhí)行接口，負(fù)責(zé)接收查詢請(qǐng)求并建立session，創(chuàng)建一系列環(huán)境參數(shù)等

Compiler:Hive的編譯器，負(fù)責(zé)將sql轉(zhuǎn)化為平臺(tái)可執(zhí)行的執(zhí)行計(jì)劃

MetaStore:Hive的元數(shù)據(jù)服務(wù)器

Execution Engine:執(zhí)行引擎，負(fù)責(zé)提交Compiler 編譯好的執(zhí)行計(jì)劃到不同的平臺(tái)上

用戶通過client向Driver提交Hive Sql，Driver將Sql交給Complier，由Complier生成執(zhí)行計(jì)劃，Complier生成執(zhí)行計(jì)劃的過程需要與MetaStore做交互來獲取Sql相關(guān)表，字段等屬性信息，執(zhí)行計(jì)劃生成后，將執(zhí)行計(jì)劃交給Driver,Driver通過Execution Engine把執(zhí)行計(jì)劃提交相應(yīng)平臺(tái)執(zhí)行，最后把執(zhí)行的結(jié)果返回給用戶。

這次我們主要分析的模塊就是Compiler ，Hive的編譯模塊

2 Hive sql的編譯總流程

詞法、語法解析: Antlr定義SQL的語法規(guī)則，完成SQL詞法，語法解析，將SQL轉(zhuǎn)化為抽象語法樹AST Tree

語義解析:遍歷AST Tree，與metastore交互，檢查抽象語法樹中的表、列是否存在，抽象出查詢的基本組成單元QueryBlock，里面保存了很多相關(guān)的元數(shù)據(jù)信息

生成邏輯執(zhí)行計(jì)劃: 遍歷QueryBlock，翻譯為執(zhí)行操作樹OperatorTree

優(yōu)化邏輯執(zhí)行計(jì)劃: 邏輯層優(yōu)化器進(jìn)行OperatorTree變換，合并Operator，達(dá)到減少M(fèi)apReduce Job，減少數(shù)據(jù)傳輸及shuffle數(shù)據(jù)量

生成物理執(zhí)行計(jì)劃: 遍歷OperatorTree，翻譯為MapReduce任務(wù)（其實(shí)這一步就可以交給yarn去執(zhí)行了）

優(yōu)化物理執(zhí)行計(jì)劃: hive一般還會(huì)利用物理層優(yōu)化器進(jìn)行進(jìn)一步優(yōu)化，進(jìn)行MapReduce任務(wù)的變換，生成最終的執(zhí)行計(jì)劃

3 Hive sql的編譯的代碼流程

二、階段1-詞法解析與語法解析

定義SQL的詞法、語法規(guī)則文件，Antlr生成詞法解析程序和語法解析程序，完成SQL詞法，語法解析，將SQL轉(zhuǎn)化為抽象語法樹AST Tree

1 詞法分析和語法分析

詞法分析（Lexical analysis或Scanning）

詞法分析就是從左至右逐個(gè)字符地掃描源程序，產(chǎn)生一個(gè)個(gè)單詞符號(hào)（Token），把源程序的字符串改造成為tokens 列表（單詞序列）。

進(jìn)行詞法分析的程序或者函數(shù)叫詞法分析器（Lexer）

hive中的詞法分析，就是分析sql里每個(gè)單詞該怎么組成

語法分析（Syntax analysis或Parsing）

在詞法分析的基礎(chǔ)上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達(dá)式”等等。語法分析程序判斷源程序在結(jié)構(gòu)上是否正確，語法如果有錯(cuò)的話，拋出語法錯(cuò)誤。

進(jìn)行語法分析的程序或者函數(shù)叫語法分析器（Parser）

hive中的語法分析，就是研究這些單詞該以怎樣的結(jié)構(gòu)組成一個(gè)sql的

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

詞法分析就是識(shí)別單詞或符號(hào)，比如select、from、=。

語法分析就是匹配語法規(guī)則，比如符合語法規(guī)則的句子是from子句在where子句前面而不是后面

2 antlr概述

ANTLR (ANother Tool for Language Recognition ) 是一種語言識(shí)別工具，它提供了一個(gè)框架，可以通過包含 Java, C++, 或 C# 動(dòng)作（action）的語法描述來構(gòu)造語言識(shí)別器，編譯器和解釋器。

使用Antlr 開源軟件定義語法規(guī)則，大大簡(jiǎn)化了詞法和語法的編譯分析過程，僅僅需要維護(hù)一份規(guī)則文件即可。

1989年發(fā)布第一個(gè)版本，叫做PCCTS，即antrl v1；當(dāng)前市面流行的是2013年發(fā)布的antlr v4；hive所用的是antlr v3.5.2

antlr3官網(wǎng)：https://www.antlr3.org/

antlr4官網(wǎng)：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

開發(fā)流程：編寫規(guī)則文件à生成解析器à調(diào)用解析器

3 antlr3

3.1 利用Antlr IDE開發(fā)規(guī)則文件

antlrworks是專門用于開發(fā)Antlr的IDE，可以檢查規(guī)則文件的語法，進(jìn)行語法高亮，調(diào)試規(guī)則文件，生成解析器、可視化語法圖、解析樹、AST，直觀看到語法圖、規(guī)則的依賴關(guān)系圖

-：https://www.antlr3.org/download.html

幫助文檔：https://www.antlr3.org/works/help/index.html

注：我們可以將jar的路徑添加進(jìn)環(huán)境變量中的CLASSPATH，這樣就可以直接用命令打開，如：CLASSPATH = %CLASSPATH%; C:/antlrworks-1.4.jar

這樣就能直接運(yùn)行java org.antlr.works.IDE打開antlr的開發(fā)工具

1、最基礎(chǔ)版

grammar Math; options { output=AST; ASTLabelType=CommonTree; } expr : NUMBER PLUS NUMBER; NUMBER : '1'; PLUS : '+';

（1）grammar聲明規(guī)則文件名，要求必須與文件名保持一致

（2）options里面定義了輸出的類型

（3）包含兩部分規(guī)則，詞法的NUMBER、PLUS ，和一個(gè)語法規(guī)則expr。詞法規(guī)則常常以大寫字母開頭，語法規(guī)則以小寫字母開頭。

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

PLUS 定義了一個(gè)簡(jiǎn)單的字符token：+

expr 定義了一個(gè)語法規(guī)則，這個(gè)語法表示希望接收一個(gè)NUMBER token，一個(gè)PLUS token，一個(gè)NUMBER token，并順序固定。如果以不同的順序?qū)?huì)觸發(fā)錯(cuò)誤消息。

（5）驗(yàn)證測(cè)試

1+1

1+2

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

2、token增強(qiáng)

NUMBER? : '1';? -- 輸入1+1 能正常解析?? 輸入1+2 --2不匹配出現(xiàn)MissingTokenException

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

NUMBER? : '0'..'9';? --匹配0-9的一位數(shù)? 1+3能識(shí)別，1+39不能識(shí)別

NUMBER? : ('0'..'9')+ ; --定義了包含0到9的字符的token，這些字符可以重復(fù)一次或一次以上

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

3、語法增強(qiáng)

(1)讓我們接受更復(fù)雜的表達(dá)式，像1或1+2或1+2+3+4，這些表達(dá)式以一個(gè)數(shù)字開頭，然后加上一個(gè)加法標(biāo)志和一個(gè)數(shù)（有可能多于一次）;

*表示0或多次

expr : NUMBER (PLUS NUMBER)*

(2)如果你既想實(shí)現(xiàn)加法又想實(shí)現(xiàn)減法，你可以做一個(gè)小的調(diào)整:定義減號(hào)、添加或的邏輯

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

MINUS : '-';

(3)如果你希望語法分析完成加減乘除運(yùn)算，則需要遞歸，因?yàn)槌顺际窍扔?jì)算的

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

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

MULT? : '*' ;

DIV?? : '/' ;

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

4、忽略空格

我們的語法是不能容忍空格的：當(dāng)遇到空格，標(biāo)簽符，回車等它會(huì)給出警告。我們要告訴詞法分析器丟棄任何它所找到的空格是安全的。

首先，我們要定義空格：

一個(gè)空格：‘ ’

一個(gè)標(biāo)簽符是這樣表示的：‘\t’

新的一行是這樣表示的：‘\n’

一個(gè)回車符是這樣表示的：‘r’

一個(gè)換頁符有一個(gè)十進(jìn)制值12和一個(gè)十六進(jìn)制值0C。Antlr用Unicode編碼，所以我們將它定義為4個(gè)十六進(jìn)制數(shù)字：‘\u000C’

把這些放在一塊，并用一個(gè)“or”連接，允許一個(gè)或多個(gè)一塊出現(xiàn)，那么你會(huì)得到：

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

那么，如果我們寫3 + 4*5這個(gè)表達(dá)式，詞法分析器會(huì)生成 NUMBER WHITESPACE PLUS WHITESPAC NUMBER MULT NUMBER，而且這將導(dǎo)致語法分析器抱怨未知WHITESPACE標(biāo)記。我們需要一種方法對(duì)于語法分析器，將他們隱藏起來。

Antlr在詞法分析器和語法分析器之間包含兩種溝通渠道，默認(rèn)渠道和隱藏渠道。語法分析器一次只聽取一個(gè)渠道的內(nèi)容，所以你可以用將它至于隱藏渠道的方法來隱藏一個(gè)標(biāo)記。

（可以有多于兩種渠道而且語法分析器可以單獨(dú)聽取他們中的任一個(gè)，也可以從所有合并的渠道獲取信息。這在你正在寫一個(gè)文字處理工具的時(shí)候非常有用，這個(gè)文字處理工具需要解析出空白和注釋的輸出，而且讓語法分析器忽略這些元素）

對(duì)于連續(xù)不斷的隱藏要求，你用設(shè)置這些token的$channel來隱藏他們。這要求你加一些大括號(hào)來在詞法分析器中添加一點(diǎn)點(diǎn)代碼。

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

5、可讀性增強(qiáng)

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

（2）將你的簡(jiǎn)單token定義（單字符，單詞等）收集到文件頂部的token中

（3）

ANTLR文法中語法規(guī)則是在詞法規(guī)則基礎(chǔ)上建立的。但不一定每個(gè)詞法規(guī)則都會(huì)被語法規(guī)則直接使用。這就象一個(gè)類的公有成員和私有成員，公有成員是對(duì)外公開的會(huì)被外界直接調(diào)用。而私有成員不對(duì)外公開是由公有成員間接調(diào)用的。在詞法規(guī)則中那些不會(huì)被語法規(guī)則直接調(diào)用的詞法規(guī)則可以用一個(gè)fragment關(guān)鍵字來標(biāo)識(shí)，fragment標(biāo)識(shí)的規(guī)則只能為其它詞法規(guī)則提供基礎(chǔ)。

DIGIT規(guī)則將不能被語法規(guī)則直接調(diào)用。

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

點(diǎn)擊菜單欄的Generateà

Generate Code: 生成當(dāng)前語法的解析器/詞法分析器代碼。

Show Parser Code: 顯示當(dāng)前語法的解析器代碼。

Show Lexer Code: 顯示當(dāng)前語法的詞法代碼。

Show Rule Code: 顯示語法的當(dāng)前規(guī)則的代碼。

參考：

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

參數(shù)列表：

usage: java org.antlr.Tool [args] file.g [file2.g file3.g ...] -o outputDir 指定生成所有輸出的輸出目錄 -fo outputDir 與-o相同，但是即使具有相對(duì)路徑的文件也強(qiáng)制使用dir -lib dir 指定token文件的位置 -depend 生成文件依賴項(xiàng) -report 打印有關(guān)處理的語法的報(bào)告 -print 無需任何操作即可打印出語法 -debug 生成一個(gè)發(fā)出調(diào)試事件的解析器 -profile 生成解析器，該解析器計(jì)算性能分析信息 -nfa 為每個(gè)規(guī)則生成一個(gè)NFA -dfa 為每個(gè)決策點(diǎn)生成DFA -message-format name 名稱指定消息的輸出樣式 -verbose 生成ANTLR版本和其他信息 -X 顯示擴(kuò)展參數(shù)列表

注：我們可以將jar的路徑添加進(jìn)環(huán)境變量中的CLASSPATH，這樣就不需要指定jar包，如：

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

這樣就能直接運(yùn)行java org.antlr.Tool XXX.g

（1）idea安裝antlr3的插件（不兼容，沒人維護(hù)了）

（1）新建項(xiàng)目，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 調(diào)用解析器

（1）將生成的解析器代碼拷貝到我們的項(xiàng)目中

（2）編寫測(cè)試樣例調(diào)用，將輸入的字符串解析成AST樹（抽象語法樹）

public static void run(String expr) throws RecognitionException { // 對(duì)每一個(gè)輸入的字符串，構(gòu)造一個(gè) ANTLRStringStream 流 in CharStream in = new ANTLRStringStream(expr); // 用 in 構(gòu)造詞法分析器 lexer，詞法分析的作用是產(chǎn)生記號(hào)token MathLexer lexer = new MathLexer(in); // 用詞法分析器 lexer 構(gòu)造一個(gè)記號(hào)流 tokens --完成詞法解析 CommonTokenStream tokens = new CommonTokenStream(lexer); // 再使用 tokens 構(gòu)造語法分析器 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文件設(shè)置了使用antlr插件編譯HiveLexer.g、HiveParser.g、HintParser.g文件

HiveLexer.g是Hive的詞法文件，其中定義了Hive所有的關(guān)鍵字、保留字以及可以被Hive識(shí)別的合法字符，不在其中定義的字符，將被Hive認(rèn)為是非法字符輸入。

HiveParser.g是語法分析的總?cè)肟冢锩鎖mport了四個(gè)規(guī)則文件

編譯后得到antlr根據(jù).g文件生成的詞法、語法解析器

ParseDriver

在Antlr生成了HiveLexer和HiveParser類之后，ParseDriver負(fù)責(zé)組織、驅(qū)動(dòng)整個(gè)詞法、 語法分析流程，并得到分析后的AST（調(diào)用詞法、語法解析的入口類）。

在ParseDriver中定義了幾個(gè)輔助類，簡(jiǎn)要說明如下。

ANTLRNoCaseStringStream繼承自ANTLRStringStream類，是Lexer使用的 輸入流之一（基于字符串的輸入流）。這里定義的輔助類的作用就是，在Lexer使用其LA()(look ahead)從流中查看字符的時(shí)候，將字符轉(zhuǎn)換成大寫字符，從而實(shí)現(xiàn)大小寫不敏感的lexer。在Hive.g 定義的語法中，只要識(shí)別大寫字母就可以了。然而，真正存放在$token.text中的值仍然是原始String 中的值（這種值是lexer通過ANTLRStringStream的consume()方法獲得的，這個(gè)方法沒有在輔 助類中override）。

HiveLexerX是實(shí)際使用的詞法分析類，它繼承自antlr生成的HiveLexer。提供這個(gè)類主要是顯示、記錄分析過程中的錯(cuò)誤信息。

TreeAdapter對(duì)象，實(shí)際上是CommonTreeAdapter對(duì)象。在使用生成的Parser的時(shí)候， 會(huì)給它設(shè)置該適配器對(duì)象。Parser每當(dāng)需要使用某個(gè)token創(chuàng)建一個(gè)AST節(jié)點(diǎn)的時(shí)候，會(huì)調(diào)用該對(duì)象 的create(token)進(jìn)行創(chuàng)建。這里，適配器對(duì)象會(huì)創(chuàng)建一個(gè)ASTNode并返回。ASTNode是Hive自己定義的一個(gè)樹節(jié)點(diǎn)對(duì)象，它繼承自Antlr的CommonTree類（antlr生成的AST是CommonTree，參考之前的例子），并實(shí)現(xiàn)了Node和Serializable接 口。我們?cè)谇懊鎔rammar options中看到，這個(gè)Parser返回的是CommonTree類型的對(duì)象，由于 ASTNode是CommonTree的子類，所以并不違反協(xié)議。

Hive之所以要這樣做，主要是： （1）實(shí)現(xiàn)Node接口，以便可以使用Hive自己的遍歷框架（后文描述）對(duì)AST進(jìn)行遍歷；（2）實(shí)現(xiàn)Serializable接口，以便可以將AST序列化。

HiveParse類維護(hù)了一個(gè)靜態(tài)成員xlateMap，它將關(guān)鍵字的名字（以 KW_開頭的名字，與Hive.g中定義的相同）映射到關(guān)鍵字本身。xlateMap也包含內(nèi)置操作符名字到 操作符字符串的映射。

4.2 源碼跟蹤

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

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

4.3 案例說明

（1）創(chuàng)建表

CREATE TABLE score ( id INT, math_score INT, english_score INT ); CREATE TABLE people ( id INT, age INT, name INT ); --關(guān)閉mapjoin set hive.auto.convert.join = false;

（2）開啟debug，執(zhí)行下面語句

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個(gè)token，其中包含空格、換行符（\n）、結(jié)束標(biāo)志（）、SQL關(guān)鍵字（select等）、符號(hào)（括號(hào)、點(diǎn)、逗號(hào)等）

（4）修改源碼打印出ASTNode

得到的樹為：

（1）這是Hive查詢語句的語法樹主體結(jié)構(gòu)，所有的查詢語句都會(huì)轉(zhuǎn)換成這樣結(jié)構(gòu)的語法樹，不同的是from、select等子樹的不同，子樹的生成同樣也是根據(jù)語法文件中定義的語法規(guī)則，對(duì)各個(gè)子句進(jìn)行重寫，生成對(duì)應(yīng)的語法樹子樹，拼接到語法樹的主體結(jié)構(gòu)上，最終生成HiveQL對(duì)應(yīng)的完整抽象語法樹。

根節(jié)點(diǎn)是nil，下面跟著SQL語法樹主體和結(jié)束標(biāo)志符

（2）語法樹由TOK_FROM和 TOK_INSERT 兩部分組成。TOK_FROM代表了 from子句的語法樹；TOK_INSERT 子樹是查詢的主體部分，包含了查詢結(jié)果目的數(shù)據(jù)源TOK_DESTINATION子樹（Hive的查詢的數(shù)據(jù)會(huì)存在hdfs的臨時(shí)文件中）、select子句語法樹、body子句(where, group,having等)語法樹。

（3）其中外層的from是嵌套了子查詢的，對(duì)應(yīng)TOK_SUBQUERY

（4）每個(gè)表生成一個(gè)TOK_TABREF節(jié)點(diǎn)，對(duì)from關(guān)鍵字生成一個(gè)TOK_FROM節(jié)點(diǎn)，對(duì)查詢的每個(gè)字段生成一個(gè)TOK_SELEXPR節(jié)點(diǎn)，每個(gè)使用到的屬性列生成一個(gè)TOK_TABLE_OR_COL節(jié)點(diǎn)，where關(guān)鍵字對(duì)應(yīng)生成TOK_WHERE節(jié)點(diǎn)。

Hive SQL

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。