前言

這篇文章是轉載一位大神的文章，為什么要轉載的，實在是因為寫的太經典了，所以忍不住希望能有更多的人可以看到。后續還會轉載兩篇好的文章，如有冒犯請聯系。

正文

最近想來，大數據相關技術與傳統型數據庫技術很多都是相互融合、互相借鑒的。傳統型數據庫強勢在于其久經考驗的SQL優化器經驗，弱勢在于分布式領域的高可用性、容錯性、擴展性等，假以時日，讓其經過一定的改造，比如引入Paxos、raft等，強化自己在分布式領域的能力，相信一定會在大數據系統中占有一席之地。相反，大數據相關技術優勢在于其天生的擴展性、可用性、容錯性等，但其SQL優化器經驗卻基本全部來自于傳統型數據庫，當然，針對列式存儲大數據SQL優化器會有一定的優化策略。
本文主要介紹SparkSQL的優化器系統Catalyst，上文講到其設計思路基本都來自于傳統型數據庫，而且和大多數當前的大數據SQL處理引擎設計基本相同（Impala、Presto、Hive（Calcite）等），因此通過本文的學習也可以基本了解所有其他SQL處理引擎的工作原理。
SQL優化器核心執行策略主要分為兩個大的方向：基于規則優化（RBO）以及基于代價優化(CBO)，基于規則優化是一種經驗式、啟發式地優化思路，更多地依靠前輩總結出來的優化規則，簡單易行且能夠覆蓋到大部分優化邏輯，但是對于核心優化算子Join卻顯得有點力不從心。舉個簡單的例子，兩個表執行Join到底應該使用BroadcastHashJoin還是SortMergeJoin？當前SparkSQL的方式是通過手工設定參數來確定，如果一個表的數據量小于這個值就使用BroadcastHashJoin，但是這種方案顯得很不優雅，很不靈活。基于代價優化就是為了解決這類問題，它會針對每個Join評估當前兩張表使用每種Join策略的代價，根據代價估算確定一種代價最小的方案。

本文將會重點介紹基于規則的優化策略，后續文章會詳細介紹基于代價的優化策略。下圖中紅色框框部分將是本文的介紹重點：
在這里插入圖片描述

預備知識－Tree&Rule

在介紹SQL優化器工作原理之前，有必要首先介紹兩個重要的數據結構：Tree和Rule。相信無論對SQL優化器有無了解，都肯定知道SQL語法樹這個概念，不錯，SQL語法樹就是SQL語句通過編譯器之后會被解析成一棵樹狀結構。這棵樹會包含很多節點對象，每個節點都擁有特定的數據類型，同時會有0個或多個孩子節點（節點對象在代碼中定義為TreeNode對象），下圖是個簡單的示例：
在這里插入圖片描述
如上圖所示，箭頭左邊表達式有3種數據類型（Literal表示常量、Attribute表示變量、Add表示動作），表示x+(1+2)。映射到右邊樹狀結構后，每一種數據類型就會變成一個節點。另外，Tree還有一個非常重要的特性，可以通過一定的規則進行等價變換，如下圖：
在這里插入圖片描述
上圖定義了一個等價變換規則(Rule)：兩個Integer類型的常量相加可以等價轉換為一個Integer常量，這個規則其實很簡單，對于上文中提到的表達式x+(1+2)來說就可以轉變為x+3。對于程序來講，如何找到兩個Integer常量呢？其實就是簡單的二叉樹遍歷算法，每遍歷到一個節點，就模式匹配當前節點為Add、左右子節點是Integer常量的結構，定位到之后將此三個節點替換為一個Literal類型的節點。
上面用一個最簡單的示例來說明等價變換規則以及如何將規則應用于語法樹。在任何一個SQL優化器中，通常會定義大量的Rule（后面會講到），SQL優化器會遍歷語法樹中每個節點，針對遍歷到的節點模式匹配所有給定規則（Rule），如果有匹配成功的，就進行相應轉換，如果所有規則都匹配失敗，就繼續遍歷下一個節點。

Catalyst工作流程

任何一個優化器工作原理都大同小異：SQL語句首先通過Parser模塊被解析為語法樹，此棵樹稱為Unresolved Logical Plan；Unresolved Logical Plan通過Analyzer模塊借助于數據元數據解析為Logical Plan；此時再通過各種基于規則的優化策略進行深入優化，得到Optimized Logical Plan；優化后的邏輯執行計劃依然是邏輯的，并不能被Spark系統理解，此時需要將此邏輯執行計劃轉換為Physical Plan；為了更好的對整個過程進行理解，下文通過一個簡單示例進行解釋。

Parser

Parser簡單來說是將SQL字符串切分成一個一個Token，再根據一定語義規則解析為一棵語法樹。Parser模塊目前基本都使用第三方類庫ANTLR進行實現，比如Hive、 Presto、SparkSQL等。下圖是一個示例性的SQL語句（有兩張表，其中people表主要存儲用戶基本信息，score表存儲用戶的各種成績），通過Parser解析后的AST語法樹如右圖所示：（注意對應的aggregate,project,filter,join,scan等節點對應于sql中的那一部分）
在這里插入圖片描述

Analyzer

（理解為對解析后語法樹進行一個精細化的操作（將每個節點進行詳細的描述））
通過解析后的邏輯執行計劃基本有了骨架，但是系統并不知道score、sum這些都是些什么鬼，此時需要基本的元數據信息來表達這些詞素，最重要的元數據信息主要包括兩部分：表的Scheme和基本函數信息，表的scheme主要包括表的基本定義（列名、數據類型）、表的數據格式（Json、Text）、表的物理位置等，基本函數信息主要指類信息。
Analyzer會再次遍歷整個語法樹，對樹上的每個節點進行數據類型綁定以及函數綁定，比如people詞素會根據元數據表信息解析為包含age、id以及name三列的表，people.age會被解析為數據類型為int的變量，sum會被解析為特定的聚合函數，如下圖所示：（#8L等可以看作是對應變量id的別名）
在這里插入圖片描述
SparkSQL中Analyzer定義了各種解析規則，有興趣深入了解的童鞋可以查看Analyzer類，其中定義了基本的解析規則，如下：

Optimizer

優化器是整個Catalyst的核心，上文提到優化器分為基于規則優化和基于代價優化兩種，當前SparkSQL 2.1依然沒有很好的支持基于代價優化（下文細講），此處只介紹基于規則的優化策略，基于規則的優化策略實際上就是對語法樹進行一次遍歷，模式匹配能夠滿足特定規則的節點，再進行相應的等價轉換。因此，基于規則優化說到底就是一棵樹等價地轉換為另一棵樹。SQL中經典的優化規則有很多，下文結合示例介紹三種比較常見的規則：謂詞下推（Predicate Pushdown）、常量累加（Constant Folding）和列值裁剪（Column Pruning）。
在這里插入圖片描述
上圖左邊是經過Analyzer解析后的語法樹，語法樹中兩個表先做join，之后再使用age>10對結果進行過濾。大家知道join算子通常是一個非常耗時的算子，耗時多少一般取決于參與join的兩個表的大小，如果能夠減少參與join兩表的大小，就可以大大降低join算子所需時間。謂詞下推就是這樣一種功能，它會將過濾操作下推到join之前進行，上圖中過濾條件age>0以及id!=null兩個條件就分別下推到了join之前。這樣，系統在掃描數據的時候就對數據進行了過濾，參與join的數據量將會得到顯著的減少，join耗時必然也會降低。 在這里插入圖片描述

常量累加其實很簡單，就是上文中提到的規則 x+(1+2) -> x+3，雖然是一個很小的改動，但是意義巨大。示例如果沒有進行優化的話，每一條結果都需要執行一次100+80的操作，然后再與變量math_score以及english_score相加，而優化后就不需要再執行100+80操作。
在這里插入圖片描述
列值裁剪是另一個經典的規則，示例中對于people表來說，并不需要掃描它的所有列值，而只需要列值id，所以在掃描people之后需要將其他列進行裁剪，只留下列id。這個優化一方面大幅度減少了網絡、內存數據量消耗，另一方面對于列存數據庫（Parquet）來說大大提高了掃描效率。
除此之外，Catalyst還定義了很多其他優化規則，有興趣深入了解的童鞋可以查看Optimizer類，下圖簡單的截取一部分規則：
在這里插入圖片描述
至此，邏輯執行計劃已經得到了比較完善的優化，然而，邏輯執行計劃依然沒辦法真正執行，他們只是邏輯上可行，實際上Spark并不知道如何去執行這個東西。比如Join只是一個抽象概念，代表兩個表根據相同的id進行合并，然而具體怎么實現這個合并，邏輯執行計劃并沒有說明。
在這里插入圖片描述
此時就需要將邏輯執行計劃轉換為物理執行計劃，將邏輯上可行的執行計劃變為Spark可以真正執行的計劃。比如Join算子，Spark根據不同場景為該算子制定了不同的算法策略，有BroadcastHashJoin、ShuffleHashJoin以及SortMergeJoin等（可以將Join理解為一個接口，BroadcastHashJoin是其中一個具體實現），物理執行計劃實際上就是在這些具體實現中挑選一個耗時最小的算法實現，這個過程涉及到基于代價優化策略，后續文章細講。