Hive是基于Hadoop的一個(gè)數(shù)據(jù)倉(cāng)庫(kù)系統(tǒng)，在各大公司都有廣泛的應(yīng)用姐仅。美團(tuán)數(shù)據(jù)倉(cāng)庫(kù)也是基于Hive搭建属铁，每天執(zhí)行近萬(wàn)次的Hive ETL計(jì)算流程，負(fù)責(zé)每天數(shù)百GB的數(shù)據(jù)存儲(chǔ)和分析莽鸿。Hive的穩(wěn)定性和性能對(duì)我們的數(shù)據(jù)分析非常關(guān)鍵。
在幾次升級(jí)Hive的過(guò)程中拾给，我們遇到了一些大大小小的問(wèn)題祥得。通過(guò)向社區(qū)的 咨詢和自己的努力，在解決這些問(wèn)題的同時(shí)我們對(duì)Hive將SQL編譯為MapReduce的過(guò)程有了比較深入的理解蒋得。對(duì)這一過(guò)程的理解不僅幫助我們解決了 一些Hive的bug级及，也有利于我們優(yōu)化Hive SQL，提升我們對(duì)Hive的掌控力额衙，同時(shí)有能力去定制一些需要的功能饮焦。
MapReduce實(shí)現(xiàn)基本SQL操作的原理
詳細(xì)講解SQL編譯為MapReduce之前，我們先來(lái)看看MapReduce框架實(shí)現(xiàn)SQL基本操作的原理
Join的實(shí)現(xiàn)原理
select u.name, o.orderid from order o join user u on o.uid = u.uid;
在map的輸出value中為不同表的數(shù)據(jù)打上tag標(biāo)記窍侧，在reduce階段根據(jù)tag判斷數(shù)據(jù)來(lái)源追驴。MapReduce的過(guò)程如下（這里只是說(shuō)明最基本的Join的實(shí)現(xiàn)，還有其他的實(shí)現(xiàn)方式）
Group By的實(shí)現(xiàn)原理
select rank, isonline, count(*) from city group by rank, isonline;
將GroupBy的字段組合為map的輸出key值疏之，利用MapReduce的排序殿雪，在reduce階段保存LastKey區(qū)分不同的key。MapReduce的過(guò)程如下（當(dāng)然這里只是說(shuō)明Reduce端的非Hash聚合過(guò)程）
Distinct的實(shí)現(xiàn)原理
select dealid, count(distinct uid) num from order group by dealid;
當(dāng)只有一個(gè)distinct字段時(shí)锋爪，如果不考慮Map階段的Hash GroupBy丙曙，只需要將GroupBy字段和Distinct字段組合為map輸出key爸业，利用mapreduce的排序，同時(shí)將GroupBy字段作 為reduce的key亏镰，在reduce階段保存LastKey即可完成去重
如果有多個(gè)distinct字段呢扯旷，如下面的SQL
select dealid, count(distinct uid), count(distinct date) from order group by dealid;
實(shí)現(xiàn)方式有兩種：
（1）如果仍然按照上面一個(gè)distinct字段的方法，即下圖這種實(shí)現(xiàn)方式索抓，無(wú)法跟據(jù)uid和date分別排序钧忽，也就無(wú)法通過(guò)LastKey去重，仍然需要在reduce階段在內(nèi)存中通過(guò)Hash去重
（2）第二種實(shí)現(xiàn)方式逼肯，可以對(duì)所有的distinct字段編號(hào)耸黑，每行數(shù)據(jù)生成n行數(shù)據(jù)，那么相同字段就會(huì)分別排序篮幢，這時(shí)只需要在reduce階段記錄LastKey即可去重大刊。
這種實(shí)現(xiàn)方式很好的利用了MapReduce的排序，節(jié)省了reduce階段去重的內(nèi)存消耗三椿，但是缺點(diǎn)是增加了shuffle的數(shù)據(jù)量缺菌。
需要注意的是，在生成reduce value時(shí)搜锰，除第一個(gè)distinct字段所在行需要保留value值伴郁，其余distinct數(shù)據(jù)行value字段均可為空
SQL轉(zhuǎn)化為MapReduce的過(guò)程
了解了MapReduce實(shí)現(xiàn)SQL基本操作之后，我們來(lái)看看Hive是如何將SQL轉(zhuǎn)化為MapReduce任務(wù)的蛋叼，整個(gè)編譯過(guò)程分為六個(gè)階段：
- Antlr定義SQL的語(yǔ)法規(guī)則焊傅，完成SQL詞法，語(yǔ)法解析鸦列，將SQL轉(zhuǎn)化為抽象語(yǔ)法樹AST Tree
- 遍歷AST Tree，抽象出查詢的基本組成單元QueryBlock
- 遍歷QueryBlock鹏倘，翻譯為執(zhí)行操作樹OperatorTree
- 邏輯層優(yōu)化器進(jìn)行OperatorTree變換薯嗤，合并不必要的ReduceSinkOperator，減少shuffle數(shù)據(jù)量
- 遍歷OperatorTree纤泵，翻譯為MapReduce任務(wù)
- 物理層優(yōu)化器進(jìn)行MapReduce任務(wù)的變換骆姐，生成最終的執(zhí)行計(jì)劃
下面分別對(duì)這六個(gè)階段進(jìn)行介紹
Phase1 SQL詞法，語(yǔ)法解析
Antlr
Hive使用Antlr實(shí)現(xiàn)SQL的詞法和語(yǔ)法解析捏题。Antlr是一種語(yǔ)言識(shí)別的工具玻褪，可以用來(lái)構(gòu)造領(lǐng)域語(yǔ)言。
這里不詳細(xì)介紹Antlr公荧，只需要了解使用Antlr構(gòu)造特定的語(yǔ)言只需要編寫一個(gè)語(yǔ)法文件带射，定義詞法和語(yǔ)法替換規(guī)則即可，Antlr完成了詞法分析循狰、語(yǔ)法分析窟社、語(yǔ)義分析券勺、中間代碼生成的過(guò)程。
Hive中語(yǔ)法規(guī)則的定義文件在0.10版本以前是Hive.g一個(gè)文件灿里，隨著語(yǔ)法規(guī)則越來(lái)越復(fù)雜关炼，由語(yǔ)法規(guī)則生成的Java解析類可能超過(guò)Java類文 件的最大上限，0.11版本將Hive.g拆成了5個(gè)文件匣吊，詞法規(guī)則HiveLexer.g和語(yǔ)法規(guī)則的4個(gè)文件 SelectClauseParser.g儒拂，F(xiàn)romClauseParser.g，IdentifiersParser.g色鸳，HiveParser.g社痛。
抽象語(yǔ)法樹AST Tree
經(jīng)過(guò)詞法和語(yǔ)法解析后，如果需要對(duì)表達(dá)式做進(jìn)一步的處理缕碎，使用 Antlr 的抽象語(yǔ)法樹語(yǔ)法Abstract Syntax Tree褥影，在語(yǔ)法分析的同時(shí)將輸入語(yǔ)句轉(zhuǎn)換成抽象語(yǔ)法樹，后續(xù)在遍歷語(yǔ)法樹時(shí)完成進(jìn)一步的處理咏雌。
下面的一段語(yǔ)法是Hive SQL中SelectStatement的語(yǔ)法規(guī)則凡怎，從中可以看出，SelectStatement包含select, from, where, groupby, having, orderby等子句赊抖。
（在下面的語(yǔ)法規(guī)則中统倒，箭頭表示對(duì)于原語(yǔ)句的改寫，改寫后會(huì)加入一些特殊詞標(biāo)示特定語(yǔ)法氛雪，比如TOK_QUERY標(biāo)示一個(gè)查詢塊）
electStatement
:
selectClause
fromClause
whereClause?
groupByClause?
havingClause?
orderByClause?
clusterByClause?
distributeByClause?
sortByClause?
limitClause? -> ^(TOK_QUERY fromClause ^(TOK_INSERT ^(TOK_DESTINATION ^(TOK_DIR TOK_TMP_FILE))
selectClause whereClause? groupByClause? havingClause? orderByClause? clusterByClause?
distributeByClause? sortByClause? limitClause?))
;
樣例SQL
為了詳細(xì)說(shuō)明SQL翻譯為MapReduce的過(guò)程房匆，這里以一條簡(jiǎn)單的SQL為例，SQL中包含一個(gè)子查詢报亩，最終將數(shù)據(jù)寫入到一張表中
FROM
(
SELECT
p.datekey datekey,
p.userid userid,
c.clienttype
FROM
detail.usersequence_client c
JOIN fact.orderpayment p ON p.orderid = c.orderid
JOIN default.user du ON du.userid = p.userid
WHERE p.datekey = 20131118
) base
INSERT OVERWRITE TABLE `test`.`customer_kpi`
SELECT
base.datekey,
base.clienttype,
count(distinct base.userid) buyer_count
GROUP BY base.datekey, base.clienttype
SQL生成AST Tree
Antlr對(duì)Hive SQL解析的代碼如下浴鸿，HiveLexerX，HiveParser分別是Antlr對(duì)語(yǔ)法文件Hive.g編譯后自動(dòng)生成的詞法解析和語(yǔ)法解析類弦追，在這兩個(gè)類中進(jìn)行復(fù)雜的解析岳链。
HiveLexerX lexer = new HiveLexerX(new ANTLRNoCaseStringStream(command)); //詞法解析，忽略關(guān)鍵詞的大小寫
TokenRewriteStream tokens = new TokenRewriteStream(lexer);
if (ctx != null) {
ctx.setTokenRewriteStream(tokens);
}
HiveParser parser = new HiveParser(tokens); //語(yǔ)法解析
parser.setTreeAdaptor(adaptor);
HiveParser.statement_return r = null;
try {
r = parser.statement(); //轉(zhuǎn)化為AST Tree
} catch (RecognitionException e) {
e.printStackTrace();
throw new ParseException(parser.errors);
}
最終生成的AST Tree如下圖右側(cè)（使用Antlr Works生成劲件，Antlr Works是Antlr提供的編寫語(yǔ)法文件的編輯器）掸哑，圖中只是展開了骨架的幾個(gè)節(jié)點(diǎn)，沒有完全展開零远。
子查詢1/2苗分，分別對(duì)應(yīng)右側(cè)第1/2兩個(gè)部分。
這里注意一下內(nèi)層子查詢也會(huì)生成一個(gè)TOK_DESTINATION節(jié)點(diǎn)牵辣。請(qǐng)看上面SelectStatement的語(yǔ)法規(guī)則摔癣，這個(gè)節(jié)點(diǎn)是在語(yǔ)法改寫中特 意增加了的一個(gè)節(jié)點(diǎn)。原因是Hive中所有查詢的數(shù)據(jù)均會(huì)保存在HDFS臨時(shí)的文件中，無(wú)論是中間的子查詢還是查詢最終的結(jié)果供填，Insert語(yǔ)句最終會(huì)將 數(shù)據(jù)寫入表所在的HDFS目錄下拐云。
詳細(xì)來(lái)看，將內(nèi)存子查詢的from子句展開后近她，得到如下AST Tree叉瘩，每個(gè)表生成一個(gè)TOK_TABREF節(jié)點(diǎn)粘捎，Join條件生成一個(gè)“=”節(jié)點(diǎn)。其他SQL部分類似泳桦，不一一詳述娩缰。
Phase2 SQL基本組成單元QueryBlock
AST Tree仍然非常復(fù)雜浮毯，不夠結(jié)構(gòu)化债蓝，不方便直接翻譯為MapReduce程序饰迹，AST Tree轉(zhuǎn)化為QueryBlock就是將SQL進(jìn)一部抽象和結(jié)構(gòu)化余舶。
QueryBlock
QueryBlock是一條SQL最基本的組成單元匿值，包括三個(gè)部分：輸入源，計(jì)算過(guò)程憎妙，輸出。簡(jiǎn)單來(lái)講一個(gè)QueryBlock就是一個(gè)子查詢龙誊。
下圖為Hive中QueryBlock相關(guān)對(duì)象的類圖趟大，解釋圖中幾個(gè)重要的屬性
- QB#aliasToSubq（表示QB類的aliasToSubq屬性）保存子查詢的QB對(duì)象逊朽，aliasToSubq key值是子查詢的別名
- QB#qbp 即QBParseInfo保存一個(gè)基本SQL單元中的給個(gè)操作部分的AST Tree結(jié)構(gòu)叽讳，QBParseInfo#nameToDest這個(gè)HashMap保存查詢單元的輸出岛蚤，key的形式是inclause-i（由于Hive 支持Multi Insert語(yǔ)句涤妒，所以可能有多個(gè)輸出）她紫，value是對(duì)應(yīng)的ASTNode節(jié)點(diǎn)犁苏，即TOK_DESTINATION節(jié)點(diǎn)围详。類QBParseInfo其余 HashMap屬性分別保存輸出和各個(gè)操作的ASTNode節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系助赞。
- QBParseInfo#JoinExpr保存TOK_JOIN節(jié)點(diǎn)。QB#QBJoinTree是對(duì)Join語(yǔ)法樹的結(jié)構(gòu)化畜普。
- QB#qbm保存每個(gè)輸入表的元信息吃挑，比如表在HDFS上的路徑舶衬，保存表數(shù)據(jù)的文件格式等逛犹。
- QBExpr這個(gè)對(duì)象是為了表示Union操作虽画。
AST Tree生成QueryBlock
AST Tree生成QueryBlock的過(guò)程是一個(gè)遞歸的過(guò)程渗柿，先序遍歷AST Tree脖岛，遇到不同的Token節(jié)點(diǎn)鸡岗，保存到相應(yīng)的屬性中轩性，主要包含以下幾個(gè)過(guò)程
- TOK_QUERY => 創(chuàng)建QB對(duì)象揣苏，循環(huán)遞歸子節(jié)點(diǎn)
- TOK_FROM => 將表名語(yǔ)法部分保存到QB對(duì)象的TOK_INSERT => 循環(huán)遞歸子節(jié)點(diǎn)
- TOK_DESTINATION => 將輸出目標(biāo)的語(yǔ)法部分保存在QBParseInfo對(duì)象的nameToDest屬性中
- TOK_SELECT => 分別將查詢表達(dá)式的語(yǔ)法部分保存在destToAggregationExprs卸察、TOK_WHERE => 將Where部分的語(yǔ)法保存在QBParseInfo對(duì)象的destToWhereExpr屬性中
最終樣例SQL生成兩個(gè)QB對(duì)象坑质，QB對(duì)象的關(guān)系如下涡扼，QB1是外層查詢吃沪，QB2是子查詢
QB1 \ QB2
