Spark SQL 原理和運(yùn)行機(jī)制
Catalyst 是 Spark SQL 執(zhí)行優(yōu)化器的代號，所有 Spark SQL 語句最終都能通過它來解析、優(yōu)化，最終生成可以執(zhí)行的 Java 字節(jié)碼。
Catalyst 最主要的數(shù)據(jù)結(jié)構(gòu)是樹，所有 SQL 語句都會用樹結(jié)構(gòu)來存儲，樹中的每個(gè)節(jié)點(diǎn)有一個(gè)類（class），以及 0 或多個(gè)子節(jié)點(diǎn)。Scala 中定義的新的節(jié)點(diǎn)類型都是 TreeNode 這個(gè)類的子類。
Catalyst 另外一個(gè)重要的概念是規(guī)則。基本上，所有優(yōu)化都是基于規(guī)則的。可以用規(guī)則對樹進(jìn)行操作，樹中的節(jié)點(diǎn)是只讀的，所以樹也是只讀的。規(guī)則中定義的函數(shù)可能實(shí)現(xiàn)從一棵樹轉(zhuǎn)換成一顆新樹。
整個(gè) Catalyst 的執(zhí)行過程可以分為以下 4 個(gè)階段：
分析階段，分析邏輯樹，解決引用
邏輯優(yōu)化階段
物理計(jì)劃階段，Catalyst 會生成多個(gè)計(jì)劃，并基于成本進(jìn)行對比
代碼生成階段
?catalyst整體執(zhí)行流程
說到spark sql不得不提的當(dāng)然是Catalyst了。Catalyst是spark sql的核心，是一套針對spark sql 語句執(zhí)行過程中的查詢優(yōu)化框架。因此要理解spark sql的執(zhí)行流程，理解Catalyst的工作流程是理解spark sql的關(guān)鍵。而說到Catalyst，就必須得上下面這張圖1了，這張圖描述了spark sql執(zhí)行的全流程。其中，長方形框內(nèi)為catalyst的工作流程。
圖1 spark sql 執(zhí)行流程圖
SQL語句首先通過Parser模塊被解析為語法樹，此棵樹稱為Unresolved Logical Plan；Unresolved Logical Plan通過Analyzer模塊借助于Catalog中的表信息解析為Logical Plan；此時(shí)，Optimizer再通過各種基于規(guī)則的優(yōu)化策略進(jìn)行深入優(yōu)化，得到Optimized Logical Plan；優(yōu)化后的邏輯執(zhí)行計(jì)劃依然是邏輯的，并不能被Spark系統(tǒng)理解，此時(shí)需要將此邏輯執(zhí)行計(jì)劃轉(zhuǎn)換為Physical Plan。
Catalyst工作流程
任何一個(gè)優(yōu)化器工作原理都大同小異：SQL語句首先通過Parser模塊被解析為語法樹，此棵樹稱為Unresolved Logical Plan；Unresolved Logical Plan通過Analyzer模塊借助于數(shù)據(jù)元數(shù)據(jù)解析為Logical 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；為了更好的對整個(gè)過程進(jìn)行理解，下文通過一個(gè)簡單示例進(jìn)行解釋。
Parser
Parser簡單來說是將SQL字符串切分成一個(gè)一個(gè)Token，再根據(jù)一定語義規(guī)則解析為一棵語法樹。Parser模塊目前基本都使用第三方類庫ANTLR進(jìn)行實(shí)現(xiàn)，比如Hive、 Presto、SparkSQL等。下圖是一個(gè)示例性的SQL語句（有兩張表，其中people表主要存儲用戶基本信息，score表存儲用戶的各種成績），通過Parser解析后的AST語法樹如右圖所示：
Analyzer
通過解析后的邏輯執(zhí)行計(jì)劃基本有了骨架，但是系統(tǒng)并不知道score、sum這些都是些什么鬼，此時(shí)需要基本的元數(shù)據(jù)信息來表達(dá)這些詞素，最重要的元數(shù)據(jù)信息主要包括兩部分：表的Scheme和基本函數(shù)信息，表的scheme主要包括表的基本定義（列名、數(shù)據(jù)類型）、表的數(shù)據(jù)格式（Json、Text）、表的物理位置等，基本函數(shù)信息主要指類信息。
Analyzer會再次遍歷整個(gè)語法樹，對樹上的每個(gè)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)類型綁定以及函數(shù)綁定，比如people詞素會根據(jù)元數(shù)據(jù)表信息解析為包含age、id以及name三列的表，people.age會被解析為數(shù)據(jù)類型為int的變量，sum會被解析為特定的聚合函數(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í)際上就是對語法樹進(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解析后的語法樹，語法樹中兩個(gè)表先做join，之后再使用age>10對結(jié)果進(jìn)行過濾。大家知道join算子通常是一個(gè)非常耗時(shí)的算子，耗時(shí)多少一般取決于參與join的兩個(gè)表的大小，如果能夠減少參與join兩表的大小，就可以大大降低join算子所需時(shí)間。謂詞下推就是這樣一種功能，它會將過濾操作下推到j(luò)oin之前進(jìn)行，上圖中過濾條件age>0以及id!=null兩個(gè)條件就分別下推到了join之前。這樣，系統(tǒng)在掃描數(shù)據(jù)的時(shí)候就對數(shù)據(jù)進(jìn)行了過濾，參與join的數(shù)據(jù)量將會得到顯著的減少，join耗時(shí)必然也會降低。
常量累加其實(shí)很簡單，就是上文中提到的規(guī)則 ?x+(1+2) ?-> x+3，雖然是一個(gè)很小的改動，但是意義巨大。示例如果沒有進(jìn)行優(yōu)化的話，每一條結(jié)果都需要執(zhí)行一次100+80的操作，然后再與變量math_score以及english_score相加，而優(yōu)化后就不需要再執(zhí)行100+80操作。
列值裁剪是另一個(gè)經(jīng)典的規(guī)則，示例中對于people表來說，并不需要掃描它的所有列值，而只需要列值id，所以在掃描people之后需要將其他列進(jìn)行裁剪，只留下列id。這個(gè)優(yōu)化一方面大幅度減少了網(wǎng)絡(luò)、內(nèi)存數(shù)據(jù)量消耗，另一方面對于列存數(shù)據(jù)庫（Parquet）來說大大提高了掃描效率。
除此之外，Catalyst還定義了很多其他優(yōu)化規(guī)則，有興趣深入了解的童鞋可以查看Optimizer類，下圖簡單的截取一部分規(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ù)不同場景為該算子制定了不同的算法策略，有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ì)講。
