SparkSQL – 從0到1認(rèn)識(shí)Catalyst – 有態(tài)度的HBase/Spark/BigData http://hbasefly.com/2017/03/01/sparksql-catalyst/
最近想來，大數(shù)據(jù)相關(guān)技術(shù)與傳統(tǒng)型數(shù)據(jù)庫(kù)技術(shù)很多都是相互融合、互相借鑒的嗅蔬。傳統(tǒng)型數(shù)據(jù)庫(kù)強(qiáng)勢(shì)在于其久經(jīng)考驗(yàn)的SQL優(yōu)化器經(jīng)驗(yàn)济蝉，弱勢(shì)在于分布式領(lǐng)域的高可用性、容錯(cuò)性肺然、擴(kuò)展性等蔫缸，假以時(shí)日，讓其經(jīng)過一定的改造际起，比如引入Paxos拾碌、raft等，強(qiáng)化自己在分布式領(lǐng)域的能力加叁，相信一定會(huì)在大數(shù)據(jù)系統(tǒng)中占有一席之地倦沧。相反，大數(shù)據(jù)相關(guān)技術(shù)優(yōu)勢(shì)在于其天生的擴(kuò)展性它匕、可用性展融、容錯(cuò)性等，但其SQL優(yōu)化器經(jīng)驗(yàn)卻基本全部來自于傳統(tǒng)型數(shù)據(jù)庫(kù)豫柬，當(dāng)然告希，針對(duì)列式存儲(chǔ)大數(shù)據(jù)SQL優(yōu)化器會(huì)有一定的優(yōu)化策略。
本文主要介紹SparkSQL的優(yōu)化器系統(tǒng)Catalyst烧给，上文講到其設(shè)計(jì)思路基本都來自于傳統(tǒng)型數(shù)據(jù)庫(kù)燕偶，而且和大多數(shù)當(dāng)前的大數(shù)據(jù)SQL處理引擎設(shè)計(jì)基本相同（Impala、Presto础嫡、Hive（Calcite）等）指么，因此通過本文的學(xué)習(xí)也可以基本了解所有其他SQL處理引擎的工作原理酝惧。
SQL優(yōu)化器核心執(zhí)行策略主要分為兩個(gè)大的方向：基于規(guī)則優(yōu)化（RBO）以及基于代價(jià)優(yōu)化(CBO)，基于規(guī)則優(yōu)化是一種經(jīng)驗(yàn)式伯诬、啟發(fā)式地優(yōu)化思路晚唇，更多地依靠前輩總結(jié)出來的優(yōu)化規(guī)則，簡(jiǎn)單易行且能夠覆蓋到大部分優(yōu)化邏輯盗似，但是對(duì)于核心優(yōu)化算子Join卻顯得有點(diǎn)力不從心哩陕。舉個(gè)簡(jiǎn)單的例子，兩個(gè)表執(zhí)行Join到底應(yīng)該使用BroadcastHashJoin還是SortMergeJoin赫舒？當(dāng)前SparkSQL的方式是通過手工設(shè)定參數(shù)來確定悍及，如果一個(gè)表的數(shù)據(jù)量小于這個(gè)值就使用BroadcastHashJoin，但是這種方案顯得很不優(yōu)雅接癌，很不靈活心赶。基于代價(jià)優(yōu)化就是為了解決這類問題扔涧，它會(huì)針對(duì)每個(gè)Join評(píng)估當(dāng)前兩張表使用每種Join策略的代價(jià)园担，根據(jù)代價(jià)估算確定一種代價(jià)最小的方案。
本文將會(huì)重點(diǎn)介紹基于規(guī)則的優(yōu)化策略枯夜，后續(xù)文章會(huì)詳細(xì)介紹基于代價(jià)的優(yōu)化策略弯汰。下圖中紅色框框部分將是本文的介紹重點(diǎn)：
預(yù)備知識(shí)－Tree&Rule
在介紹SQL優(yōu)化器工作原理之前，有必要首先介紹兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu)：Tree和Rule湖雹。相信無論對(duì)SQL優(yōu)化器有無了解咏闪，都肯定知道SQL語(yǔ)法樹這個(gè)概念，不錯(cuò)摔吏，SQL語(yǔ)法樹就是SQL語(yǔ)句通過編譯器之后會(huì)被解析成一棵樹狀結(jié)構(gòu)鸽嫂。這棵樹會(huì)包含很多節(jié)點(diǎn)對(duì)象，每個(gè)節(jié)點(diǎn)都擁有特定的數(shù)據(jù)類型征讲，同時(shí)會(huì)有0個(gè)或多個(gè)孩子節(jié)點(diǎn)（節(jié)點(diǎn)對(duì)象在代碼中定義為TreeNode對(duì)象）据某，下圖是個(gè)簡(jiǎn)單的示例：
如上圖所示，箭頭左邊表達(dá)式有3種數(shù)據(jù)類型（Literal表示常量诗箍、Attribute表示變量癣籽、Add表示動(dòng)作），表示x+(1+2)滤祖。映射到右邊樹狀結(jié)構(gòu)后筷狼，每一種數(shù)據(jù)類型就會(huì)變成一個(gè)節(jié)點(diǎn)。另外匠童，Tree還有一個(gè)非常重要的特性埂材，可以通過一定的規(guī)則進(jìn)行等價(jià)變換，如下圖：
上圖定義了一個(gè)等價(jià)變換規(guī)則(Rule)：兩個(gè)Integer類型的常量相加可以等價(jià)轉(zhuǎn)換為一個(gè)Integer常量汤求，這個(gè)規(guī)則其實(shí)很簡(jiǎn)單俏险，對(duì)于上文中提到的表達(dá)式x+(1+2)來說就可以轉(zhuǎn)變?yōu)閤+3严拒。對(duì)于程序來講，如何找到兩個(gè)Integer常量呢竖独？其實(shí)就是簡(jiǎn)單的二叉樹遍歷算法糙俗，每遍歷到一個(gè)節(jié)點(diǎn)，就模式匹配當(dāng)前節(jié)點(diǎn)為Add预鬓、左右子節(jié)點(diǎn)是Integer常量的結(jié)構(gòu)，定位到之后將此三個(gè)節(jié)點(diǎn)替換為一個(gè)Literal類型的節(jié)點(diǎn)赊颠。
上面用一個(gè)最簡(jiǎn)單的示例來說明等價(jià)變換規(guī)則以及如何將規(guī)則應(yīng)用于語(yǔ)法樹格二。在任何一個(gè)SQL優(yōu)化器中，通常會(huì)定義大量的Rule（后面會(huì)講到）竣蹦，SQL優(yōu)化器會(huì)遍歷語(yǔ)法樹中每個(gè)節(jié)點(diǎn)顶猜，針對(duì)遍歷到的節(jié)點(diǎn)模式匹配所有給定規(guī)則（Rule），如果有匹配成功的痘括，就進(jìn)行相應(yīng)轉(zhuǎn)換长窄，如果所有規(guī)則都匹配失敗，就繼續(xù)遍歷下一個(gè)節(jié)點(diǎn)纲菌。
Catalyst工作流程
任何一個(gè)優(yōu)化器工作原理都大同小異：SQL語(yǔ)句首先通過Parser模塊被解析為語(yǔ)法樹挠日，此棵樹稱為Unresolved Logical Plan；Unresolved Logical Plan通過Analyzer模塊借助于數(shù)據(jù)元數(shù)據(jù)解析為L(zhǎng)ogical Plan翰舌；此時(shí)再通過各種基于規(guī)則的優(yōu)化策略進(jìn)行深入優(yōu)化嚣潜，得到Optimized Logical Plan；優(yōu)化后的邏輯執(zhí)行計(jì)劃依然是邏輯的椅贱，并不能被Spark系統(tǒng)理解懂算，此時(shí)需要將此邏輯執(zhí)行計(jì)劃轉(zhuǎn)換為Physical Plan；為了更好的對(duì)整個(gè)過程進(jìn)行理解庇麦，下文通過一個(gè)簡(jiǎn)單示例進(jìn)行解釋计技。
Parser
Parser簡(jiǎn)單來說是將SQL字符串切分成一個(gè)一個(gè)Token，再根據(jù)一定語(yǔ)義規(guī)則解析為一棵語(yǔ)法樹山橄。Parser模塊目前基本都使用第三方類庫(kù)ANTLR進(jìn)行實(shí)現(xiàn)垮媒，比如Hive、 Presto驾胆、SparkSQL等涣澡。下圖是一個(gè)示例性的SQL語(yǔ)句（有兩張表，其中people表主要存儲(chǔ)用戶基本信息丧诺，score表存儲(chǔ)用戶的各種成績(jī)）入桂，通過Parser解析后的AST語(yǔ)法樹如右圖所示：
Analyzer
通過解析后的邏輯執(zhí)行計(jì)劃基本有了骨架，但是系統(tǒng)并不知道score驳阎、sum這些都是些什么鬼抗愁，此時(shí)需要基本的元數(shù)據(jù)信息來表達(dá)這些詞素馁蒂，最重要的元數(shù)據(jù)信息主要包括兩部分：表的Scheme和基本函數(shù)信息，表的scheme主要包括表的基本定義（列名蜘腌、數(shù)據(jù)類型）沫屡、表的數(shù)據(jù)格式（Json、Text）撮珠、表的物理位置等沮脖，基本函數(shù)信息主要指類信息。
Analyzer會(huì)再次遍歷整個(gè)語(yǔ)法樹芯急，對(duì)樹上的每個(gè)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)類型綁定以及函數(shù)綁定勺届，比如people詞素會(huì)根據(jù)元數(shù)據(jù)表信息解析為包含age、id以及name三列的表娶耍，people.age會(huì)被解析為數(shù)據(jù)類型為int的變量免姿，sum會(huì)被解析為特定的聚合函數(shù)，如下圖所示：
SparkSQL中Analyzer定義了各種解析規(guī)則榕酒，有興趣深入了解的童鞋可以查看Analyzer類胚膊，其中定義了基本的解析規(guī)則，如下：
Optimizer
優(yōu)化器是整個(gè)Catalyst的核心想鹰，上文提到優(yōu)化器分為基于規(guī)則優(yōu)化和基于代價(jià)優(yōu)化兩種紊婉，當(dāng)前SparkSQL 2.1依然沒有很好的支持基于代價(jià)優(yōu)化（下文細(xì)講），此處只介紹基于規(guī)則的優(yōu)化策略杖挣，基于規(guī)則的優(yōu)化策略實(shí)際上就是對(duì)語(yǔ)法樹進(jìn)行一次遍歷肩榕，模式匹配能夠滿足特定規(guī)則的節(jié)點(diǎn)，再進(jìn)行相應(yīng)的等價(jià)轉(zhuǎn)換惩妇。因此株汉，基于規(guī)則優(yōu)化說到底就是一棵樹等價(jià)地轉(zhuǎn)換為另一棵樹。SQL中經(jīng)典的優(yōu)化規(guī)則有很多歌殃，下文結(jié)合示例介紹三種比較常見的規(guī)則：謂詞下推（Predicate Pushdown）乔妈、常量累加（Constant Folding）和列值裁剪（Column Pruning）。
上圖左邊是經(jīng)過Analyzer解析后的語(yǔ)法樹氓皱，語(yǔ)法樹中兩個(gè)表先做join路召，之后再使用age>10對(duì)結(jié)果進(jìn)行過濾。大家知道join算子通常是一個(gè)非常耗時(shí)的算子波材，耗時(shí)多少一般取決于參與join的兩個(gè)表的大小股淡，如果能夠減少參與join兩表的大小，就可以大大降低join算子所需時(shí)間廷区。謂詞下推就是這樣一種功能唯灵，它會(huì)將過濾操作下推到j(luò)oin之前進(jìn)行，上圖中過濾條件age>0以及id!=null兩個(gè)條件就分別下推到了join之前隙轻。這樣埠帕，系統(tǒng)在掃描數(shù)據(jù)的時(shí)候就對(duì)數(shù)據(jù)進(jìn)行了過濾垢揩，參與join的數(shù)據(jù)量將會(huì)得到顯著的減少，join耗時(shí)必然也會(huì)降低敛瓷。
常量累加其實(shí)很簡(jiǎn)單叁巨，就是上文中提到的規(guī)則 x+(1+2) -> x+3，雖然是一個(gè)很小的改動(dòng)呐籽，但是意義巨大锋勺。示例如果沒有進(jìn)行優(yōu)化的話，每一條結(jié)果都需要執(zhí)行一次100+80的操作狡蝶，然后再與變量math_score以及english_score相加宙刘，而優(yōu)化后就不需要再執(zhí)行100+80操作。
列值裁剪是另一個(gè)經(jīng)典的規(guī)則牢酵，示例中對(duì)于people表來說，并不需要掃描它的所有列值衙猪，而只需要列值id馍乙，所以在掃描people之后需要將其他列進(jìn)行裁剪，只留下列id垫释。這個(gè)優(yōu)化一方面大幅度減少了網(wǎng)絡(luò)丝格、內(nèi)存數(shù)據(jù)量消耗，另一方面對(duì)于列存數(shù)據(jù)庫(kù)（Parquet）來說大大提高了掃描效率棵譬。
除此之外显蝌，Catalyst還定義了很多其他優(yōu)化規(guī)則，有興趣深入了解的童鞋可以查看Optimizer類订咸，下圖簡(jiǎn)單的截取一部分規(guī)則：
至此曼尊，邏輯執(zhí)行計(jì)劃已經(jīng)得到了比較完善的優(yōu)化，然而脏嚷，邏輯執(zhí)行計(jì)劃依然沒辦法真正執(zhí)行骆撇，他們只是邏輯上可行，實(shí)際上Spark并不知道如何去執(zhí)行這個(gè)東西父叙。比如Join只是一個(gè)抽象概念神郊，代表兩個(gè)表根據(jù)相同的id進(jìn)行合并，然而具體怎么實(shí)現(xiàn)這個(gè)合并趾唱，邏輯執(zhí)行計(jì)劃并沒有說明涌乳。
此時(shí)就需要將邏輯執(zhí)行計(jì)劃轉(zhuǎn)換為物理執(zhí)行計(jì)劃，將邏輯上可行的執(zhí)行計(jì)劃變?yōu)镾park可以真正執(zhí)行的計(jì)劃甜癞。比如Join算子夕晓，Spark根據(jù)不同場(chǎng)景為該算子制定了不同的算法策略，有BroadcastHashJoin带欢、ShuffleHashJoin以及SortMergeJoin等（可以將Join理解為一個(gè)接口运授，BroadcastHashJoin是其中一個(gè)具體實(shí)現(xiàn)）烤惊，物理執(zhí)行計(jì)劃實(shí)際上就是在這些具體實(shí)現(xiàn)中挑選一個(gè)耗時(shí)最小的算法實(shí)現(xiàn)，這個(gè)過程涉及到基于代價(jià)優(yōu)化策略吁朦，后續(xù)文章細(xì)講柒室。
SparkSQL執(zhí)行計(jì)劃
至此，筆者通過一個(gè)簡(jiǎn)單的示例完整的介紹了Catalyst的整個(gè)工作流程逗宜，包括Parser階段雄右、Analyzer階段、Optimize階段以及Physical Planning階段纺讲。有同學(xué)可能會(huì)比較感興趣Spark環(huán)境下如何查看一條具體的SQL的整個(gè)過程擂仍，在此介紹兩種方法：
-
使用queryExecution方法查看邏輯執(zhí)行計(jì)劃，使用explain方法查看物理執(zhí)行計(jì)劃熬甚，分別如下所示：
使用Spark WebUI進(jìn)行查看逢渔，如下圖所示：
參考文章：
- Deep Dive into Spark SQL’s Catalyst Optimizer：https://databricks.com/blog/2015/04/13/deep-dive-into-spark-sqls-catalyst-optimizer.html
- A Deep Dive into Spark SQL’s Catalyst Optimiser：https://www.youtube.com/watch?v=GDeePbbCz2g&index=4&list=PL-x35fyliRwheCVvliBZNm1VFwltr5b6B
- Spark SQL: Relational Data Processing in Spark：http://people.csail.mit.edu/matei/papers/2015/sigmod_spark_sql.pdf
- 一個(gè)Spark SQL作業(yè)的一生：http://www.bitstech.net/2015/12/08/sparksql-introduction/
