134      阿裏雲  技術社區[雲棲]

SQL解析過程詳解

作者：一帥

簡介

SQL任務是ODPS中使用最頻繁的一類作業,大部分用戶開始使用ODPS時要做的第一件事情就是學習怎麼寫ODPS的SQL。ODPS SQL是一種非常靈活的語言,兼容大部分的SQL92規範,也對大規模計算場景做了一些特別的定製。有些用戶寫出的SQL讓人看了之後茅塞頓開的感覺,也有一些神級用戶經常寫一些1000多行的SQL,讓人看的隻想撞牆。本文會介紹一下SQL是如何分析解析,並拆解成分布式飛天任務的一些實現原理。

ps.由於一些曆史包袱和工程實現的原因,ODPS某些內部實現細節可能與本文提到的不一致

1. 編譯

語法分析的作用是將一個輸入的‘字符串’變換為一個描述這個字符串的‘結構體’,讓計算機可以更容易的理解用戶輸入的字符串是什麼意義。這個階段包含三個過程,分別是詞法分析、語法分析、輸出抽象語法樹。

1.1詞法分析

詞法分析器是一個確定有限自動機(DFA),可以按照我們定義好的詞法,將輸入的字符集轉換為‘單詞’。如下：

1.2語法分析

在詞法分析之後,接下來的過程就是語法分析了,詞法分析的結果會作為語法分析的輸入,語法分析在詞法分析的基礎上,來判斷用戶輸入的單詞是否符合語法邏輯,*SELECT FOO+100 FROM POKES*就是一個符合語法的句子,而*SELECT FOO+100 FROM*,是個不合法的語句,因為在FROM之後,一定要跟著一個表名。此時語法分析器會報錯：

1.3抽象語法樹

抽象語法樹(AST)的英文全拚是：*abstract syntax tree*,這是用戶輸入語句的樹形結構的表現形式,樹上的每一個節點都是一個單詞,樹的結構體現了語法。抽象語法樹是隨著語法分析的過程構造的,當語法分析正常結束後,語法分析器就會輸出一個抽象語法樹,用戶的輸入和抽象語法樹的結構內容是一一對應的,至此,用戶輸入的‘字符串’完完全全的變成了一個‘結構體’, SELECT FOO+100 FROM POKES轉換為抽象語法樹後如下所示：

ps.在ODPS中,真實的抽象語法樹會複雜許多,為了方便大家理解,我將輸出的抽象語法樹做了一些簡化。

編譯的過程在過去曾經是最為複雜繁瑣的,涉及到很多編譯原理的理論,但是現在,開源的編譯器工具已經足夠的多,我們可以定義好語法,讓編譯器工具來幫我們完成這個轉換。目前我們使用編譯工具:Antlr來完成我們的編譯。

2.語義分析

語義分析階段是SQL解析過程中最為複雜最有難度的一環,涉及到SQL標準,SQL優化,和MapReduce的相關理論和概念。在這裏,接著上麵環輸出的抽象語法樹,語意分析後會輸出一個查詢計劃,這個查詢計劃會指導著物理執行算子一步步的運行在我們的分布式係統之上,去讀取表的內容,根據SQL的語意做運算,最後輸入用戶的內容。接下來我們會逐步分解語義分析的過程,揭開廬山真麵目

語義分析階段包含兩大塊,先邏輯分析後物理分析,邏輯分析基本上是純代數的分析過程,與底層的分布式環境無關,而物理分析則是將邏輯分析後的結果做變換,與底層的執行環境密切相關。如我們使用飛天的分布式環境,物理分析時就需要確定在MapReduce時如何將數據分區、排序、讀取數據量的大小、啟動多少個進程來執行任務,等等。

2.1邏輯分析

顧名思義,邏輯分析過程就是要分析一下輸入的SQL語句到底是幹什麼的,都有哪些操作。一般來講,一個SQL語句總有一個輸入,一個輸出,輸入數據經過SQL加工後得到輸出數據,

2.1.1語句的執行順序

SQL語句基本可以分解成下麵7大塊：

(5)SELECT (6)DISTINCT < select list >
(1)FROM < table source >
(2)WHERE < condition >
(3)GROUP BY < group by list >
(4)HAVING < having condition >
(7) ORDER BY < order by list >

在執行時,按照1-7的標號順序執行,有些子句是可選的,比如where子句。當沒有出現的時候就跳過這步。我們發現,寫在最前麵的select子句其實並不是最先執行的,這是因為SQL語句設計時為了讓用SQL的人更容易與自己的思維相銜接。

2.1.2邏輯算子

根據上述的幾個SQL基本操作,我們抽象出了一些邏輯算子(Operator),這些算子的功能是單一的不可再拆分的單位。分別是：

這些奇怪的算子是幹什麼用的呢？說白了,一個邏輯查詢計劃就是由這些算子組成的一個有向無環圖(DAG),每一個算子都描述了SQL操作裏的不同動作,由算子組成的有向無環圖(DAG)描述了數據流的方向.

對於大部分算子而言,都有一個輸入數據集,和一個輸出數據集。JoinOperator和UnionAllOperator比較特殊,擁有兩個或者兩個以上的輸入數據集,因為這兩個算子的操作就是要將多個數據集做關聯。我們將算子的輸入數據集和輸出數據集稱之為虛表(vtable)

用戶是看不到虛表(vtable)的,它隻用來做內部分析,是算子和算子之間的橋梁,如下圖所示:

2.1.3表達式分析

在SQL裏,有很多子句都可以帶有表達式,比如

其中SELECT子句中,GROUP BY子句中, WHERE子句中都帶有表達式。表達式的解析和計算貫穿著整個SQL解析的過程,所以這裏單獨講講表達式。

1.類型推導

在分析表達式時,會遇到用戶輸入的常量,我們需要通過類型推導給輸入的每一個常量做標記,識別SQL中常量的類型,規則較為簡單,如：

2.隱式類型轉換

所有的編程語言都會遇到隱式類型轉換的問題,即當調用一個函數時,如果輸入參數類型不符合函數簽名時,就要嚐試對輸入的參數做隱式類型轉換。當然,並不一定每次隱式類型轉換都是成功的,如果發現無法無論如何轉換都無法滿足函數的簽名,就會有異常拋出,終止分析過程。

3.布爾表達式分析

布爾表達式的分析主要作用是可以讓之後的SQL優化更容易的進行下去,如Join時的條件下推優化,分區裁剪優化,都需要使用布爾表達式分析後的結果來進行。這步分析會用到很多布爾代數的知識,目的隻有一個,那就是將用戶輸入的冗長的布爾表達式變換為最簡合取範式,簡而言之,就是將用戶輸入的一大推’and’ ‘or’組成的布爾表達式變換成由’and’連接的最簡形式,如：

看起來這是一個很神奇的變換,實際上已經有很現成的算法來解決這個問題了。總共需要2步：

1. 利用Quine McCluskey 算法對輸入的布爾表達式生成合取範式(CNF)
2. 利用Petrick’s method 算法對第一步生成的CNF計算最簡合取範式(Minimal CNF)

4.CASE WHEN表達式的分析

CASE WHEN表達式是一個略顯奇葩的表達式,它本身上是一個值函數（ScalarFunction）,但又有邏輯判斷,返回值又不固定,並且還可以嵌套使用,而且在語法上還有兩種形式(簡單CASE函數和CASE搜索函數) – -! 想在計算機裏優雅的記錄表達這個CASE WHEN真的很不容易。

condition參數是casewhen子句的條件,returnvalue1代表這THEN後的返回值,returnvalue2代表ELSE後的返回值。
這樣,我們就可以很好的在計算機中結構化的表達,如：

2.1.4邏輯查詢計劃生成

有了以上的基礎,我們就可以開始生成我們的查詢計劃了。嚴格按照SQL語句的執行順序來遍曆編譯階段生成的AST樹,遇到什麼操作就生成什麼樣的算子,遇到表達式就調用之前的表達式分析,真是兵來將擋水來土掩。
舉個例子：

需要注意的是,在聚合函數裏的值函數、Group by列表中的值函數,需要在聚合操作以前就計算完成,否則無法進行聚合操作,於是乎,出現了一個叫初始投影的東西,本質上這是一個SelectOperator,隻是用來計算一下聚合需要用到的表達式。

題外話,在很久以前,group by 列表中和聚合函數裏都是不允許使用表達式的,隻能使用單一的值或者列,所以那時也不需要初始投影。用戶想使用類似功能時隻能通過子查詢來實現。後來SQL語法擴展了,支持了group by、聚合函數中調用值函數,於是,在SQL解析時要先判斷一下是否需要初始投影

還有很多結構的SQL沒有講到,比如JOIN, UNION ALL, WINDOWN FUNCTION,由於篇幅原因,這裏先不提了,感興趣的同學可以來找我們私下交流。

2.1.5子查詢

SQL語法本身就是一個遞歸的結構,支持在FROM之後寫一個子查詢,如:

麵對這樣的語句,我們隻要先去生成子查詢的邏輯查詢計劃,將子查詢的的結果虛表作為父查詢的輸入即可,在邏輯上很方便去應對。上麵這個示例的查詢計劃如下圖所示：

2.1.6邏輯優化

生成邏輯查詢計劃後,需要先對查詢計劃做一次優化,將一些顯而易見的點優化掉,避免冗餘的計算。主要包含三個優化：

• 常量表達式的計算舉個例子:

  SELECT 1+2 FROM POKES
  “1+2“就是一個常量表達式,此時,我們可以將1+2的結果先計算出來,然後將結果放入查詢計劃,避免在執行時,對每一行數據都去計算這個固定結果的表達式。

• 列裁剪在生成查詢計劃時,默認會把全表中沒一列的數據都讀取出來,但現實的情況是用戶可能隻需要其中的某幾列做計算,其他的列就變成了冗餘數據,讀取出來耗時耗力,但沒有被用到。此時,我們就使用列裁剪這個優化去把不必要的列裁剪掉。
• Predict Push Down在遇有JOIN運算時,用戶很有可能還要在JOIN之後做WHERE運算,此時就要從代數邏輯上分析,WHERE中計算的條件是否可以被提前到JOIN之前運算,以此來減少JOIN運算的數據量,提升效率,千言萬語不勝一張圖,(又稱no pic you say a bird):

  SELECT * FROM A JOIN B ON A.ID=B.ID WHERE A.AGE>10 AND B.AGE>5

  

  左麵的是未優化前的查詢計劃,在FIL_4中計算了A.AGE>10 AND B.AGE>5這個表達式,右麵的是優化後的查詢計劃,將A.AGE>10放入了FIL_7計算並且提前,將B.AGE>5放入了FIL_8中計算並且提前,最後將原有的FIL_4刪除,以此來達到減少JOIN輸入數據量的目的。

至此,邏輯查詢與邏輯優化就結束了,邏輯查詢計劃和邏輯優化在所有的SQL係統中都是差不多的,下麵來講講與我們分布式係統MapReduce相關的物理查詢計劃。

2.2物理分析

物理查詢計劃是通過之前產生的邏輯查詢計劃生成的,在轉換的過程中,要與飛天的MapReduce編程框架做適配,生成飛天係統可以識別的DAG

2.2.1物理算子

飛天的DAG是一個類似MapReduce的編程框架,想把剛剛一個SQL跑在分布式的飛天係統上,就需要按照分布式係統編程框架來抽象出一些新的物理運算符。

• Shuffle-Sort算子(在ODPS中,這個算子叫ReduceSink)在飛天係統上,我們如果想做Group by或者Join操作,那麼必須把相同key的數據放到同一個進程節點上來執行,而在這直線,這些相同key的數據也許是被打散在各個進程裏的,這時我們就需要一個專門的算子來做數據的重新分區、排序的操作
• GroupBy的不同階段在飛天係統上,我們想實現一個GroupBy需要有4步:
  1. 準備階段(AggregationPrepare), 在做一些非線性的聚合函數操作時,比如AVG求平均值,需要將AVG()拆解成SUM(),COUNT()兩個線性的聚合函數,最後再使用SUM()/COUNT()來算出AVG()的值。在這步,隻做拆解。
  2. 本地聚合(SemiHashAggregation), 對於Group by來說,需要將所有Group by 列表的字段數據放倒一個機器上才可以進行完全聚合,但是出於優化考慮,我們可以在數據片不全的時候先做一次聚合,雖然這次聚合操作不完全,但是可以減少輸出的數據量,並且可以保證數據的正確性
  3. 流式聚合(StremAggregation), 這個聚合有個前提,一定是要求前趨的虛表Group by 列表中的數據都會在這一個進程裏,並且排好序。一般而言,在本地聚合之後,數據會通過Shuffle-Sort運算數據重新分區和排序,再輸入到流式聚合算子中
  4. 合並(FinalAggregation),這裏輸入的其實是已經聚合好的結果了,但是由於第一步提到的原因,有些非線性聚合函數被分解成了線性聚合函數,這裏要將他們合並。如:AVG()=SUM()/COUNT()

  在隻有線性聚合函數時,上麵的1,4步可以省略。

• MapJoin 算子和MergeJoin算子

1. MergeJoinMergeJoin是最常見的一種Join算子,一般而言,MergeJoin是要求輸入數據的虛表按照Join的Key分區並且排序的,所以MergeJoin一般出現在Shuffle-Sort算子之後。
2. MapJoin使用過的人應該都知道有一種Join的優化叫MapJoin,這個名字的本意是Map-side JOIN,就是JOIN運算在MapReduce的Map階段完成。如果用戶在做Join時,知道有一個數據表的數據量很小,可以選擇使用MapJoin,MapJoin算子會在每一個進程裏都把小表中的數據加載到內存,與打表一一做Join。這樣可以減少一次Shuffle-Sort,提升執行效率。

2.2.2生成物理查詢計劃

邏輯查詢計劃是物理查詢計劃的輸入,我們按照拓撲序去遍曆邏輯查詢計劃上的每一個邏輯算子,生成物理算子,當我們認為虛表需要重新分區排序才能滿足下一個階段的運算時,我們就在中間加入一個Shuffle-Sort運算符.
還是使用邏輯查詢計劃生成的那個例子來描述一下物理查詢計劃是什麼樣子：

2.2.3物理優化

現在,又進入了一個優化的環節。此時的優化與底層的分布式係統更相關,主要目標就是減少讀取的數據量,減少整個SQL執行的過程中,數據分區排序落地的過程。以此來提高執行效率。

• 分區裁剪大家知道,我們的業務表一般都是有分區的,而且一般都是按照時間來分區。大部分情況下不需要全表掃描,隻需讀出幾個分區的數據就可以完成我們的業務邏輯。於是,分區裁剪優化誕了。
  我們會分析用戶寫在WHERE子句中的分區字段,將分區字段的條件拿出來,再去metastore中讀取所有的分區信息,用WHERE子句中的條件做過濾,最後,我們就知道哪些分區是需要讀取的了,我們把要讀取的分區信息放入對應的TableScanOperator,在執行是時,就不用讀取不必要的數據了。

  需要注意的是,並不是所有的WHERE條件中的分區條件都可以做裁剪,當用戶寫了LEFT JOIN,RIGHT JOIN, FULL OUTER JOIN時,如果在JOIN條件中涉及到了分區字段,那麼很有可能就無法完成分區裁剪的優化,因為裁剪後SQL的結果就不對了。

• 減少不必要的Shuffle-Sort有時我們會寫出這樣的語句：

  在上麵這個例子中,Join 後做Group by ,應該在Join和Group by之間加入一個Shuffle-Sort算子,以保證Group by 算子的輸入虛表按照固定的A.ID來排序,但是我們發現,JOIN之後A.ID這個字段本來就是有序的,所以,我們可以將中間這個Shuffle-Sort算子刪除,減少數據的網絡傳輸和落地。

2.2.4生成飛天的DAG

物理查詢計劃已經生成好了,下一步就是按照飛天的DAG編程模型把物理查詢計劃的算子適配進去。飛天DAG的單位是Stage,由多個Stage組成了DAG,Stage和Stage之間可以進行對數據的分區和排序,有點想Map和Reduce的關係。

生成飛天DAG的規則也很簡單：

• 按照拓撲序遍曆物理查詢計劃上的每一個算子,每一個算子都在一個獨立的集和裏。如果兩個算子相連接,則將這兩個集和合並。當遇到Shuffle-Sort算子時終止,並開始新一輪的合並集和過程。

對於上麵這個語句,按照規則生成DAG後的樣子如下:

其中每一個灰色的方塊代表Fuxi的一個Stage。TS_1在STAGE1中讀取表A,RS_3進按A.ID進行分區排序,TS_2在STAGE2中讀取表B,RS_4按照B.ID進行分區排序。JOIN_5在STAGTE3中,按照A.ID=B.ID做MergeJoin, SEMIHASH_7為Group by A.AGE做半聚合,通過RS_8將數據按照A.AGE重新分區排序。 STAGE3的第一算子是STREAMEDAGG_9,接收按照A.AGE排序後的數據做流式聚合,最後SEL_10將數據做投影,FS_11將數據寫出到磁盤。

3.結語

洋洋灑灑寫了這麼多,SQL解析的邏輯基本就結束了,SQL解析是一個邏輯非常複雜繁瑣的過程,有很多細節和惡心的坑本文中還沒有提到,稍有不慎就可能引起SQL正確性的錯誤。

最後更新：2017-04-03 08:26:24

  上一篇： Windows 服務卸載之後 重新安裝提示 “指定的服務已標記為刪除”

  下一篇： 隨手記UIKit Dynamics