作者：一帥
sql任務是odps中使用最頻繁的一類作業,大部分使用者開始使用odps時要做的第一件事情就是學習怎麼寫odps的sql。odps sql是一種非常靈活的語言,相容大部分的sql92規範,也對大規模計算場景做了一些特别的定制。有些使用者寫出的sql讓人看了之後茅塞頓開的感覺,也有一些神級使用者經常寫一些1000多行的sql,讓人看的隻想撞牆。本文會介紹一下sql是如何分析解析,并拆解成分布式飛天任務的一些實作原理。
ps.由于一些曆史包袱和工程實作的原因,odps某些内部實作細節可能與本文提到的不一緻
文法分析的作用是将一個輸入的‘字元串’變換為一個描述這個字元串的‘結構體’,讓計算機可以更容易的了解使用者輸入的字元串是什麼意義。這個階段包含三個過程,分别是詞法分析、文法分析、輸出抽象文法樹。
詞法分析器是一個确定有限自動機(dfa),可以按照我們定義好的詞法,将輸入的字元集轉換為‘單詞’。如下：
在詞法分析之後,接下來的過程就是文法分析了,詞法分析的結果會作為文法分析的輸入,文法分析在詞法分析的基礎上,來判斷使用者輸入的單詞是否符合文法邏輯,*select foo+100 from pokes*就是一個符合文法的句子,而*select foo+100 from*,是個不合法的語句,因為在from之後,一定要跟着一個表名。此時文法分析器會報錯：
<code>抽象文法樹</code>(ast)的英文全拼是：*<code>abstract syntax tree</code>*,這是使用者輸入語句的樹形結構的表現形式,樹上的每一個節點都是一個<code>單詞</code>,樹的結構展現了<code>文法</code>。抽象文法樹是随着文法分析的過程構造的,當文法分析正常結束後,文法分析器就會輸出一個抽象文法樹,使用者的輸入和抽象文法樹的結構内容是一一對應的,至此,使用者輸入的‘字元串’完完全全的變成了一個‘結構體’, select foo+100 from pokes轉換為抽象文法樹後如下所示：
ps.在odps中,真實的抽象文法樹會複雜許多,為了友善大家了解,我将輸出的抽象文法樹做了一些簡化。
編譯的過程在過去曾經是最為複雜繁瑣的,涉及到很多編譯原理的理論,但是現在,開源的編譯器工具已經足夠的多,我們可以定義好文法,讓編譯器工具來幫我們完成這個轉換。目前我們使用編譯工具:antlr來完成我們的編譯。
語義分析階段是sql解析過程中最為複雜最有難度的一環,涉及到sql标準,sql優化,和mapreduce的相關理論和概念。在這裡,接着上面環輸出的抽象文法樹,語意分析後會輸出一個<code>查詢計劃</code>,這個<code>查詢計劃</code>會指導着實體執行算子一步步的運作在我們的分布式系統之上,去讀取表的内容,根據sql的語意做運算,最後輸入使用者的内容。接下來我們會逐漸分解語義分析的過程,揭開廬山真面目
語義分析階段包含兩大塊,先<code>邏輯分析</code>後<code>實體分析</code>,邏輯分析基本上是純代數的分析過程,與底層的分布式環境無關,而實體分析則是将邏輯分析後的結果做變換,與底層的執行環境密切相關。如我們使用飛天的分布式環境,實體分析時就需要确定在mapreduce時如何将資料分區、排序、讀取資料量的大小、啟動多少個程序來執行任務,等等。
顧名思義,邏輯分析過程就是要分析一下輸入的sql語句到底是幹什麼的,都有哪些操作。一般來講,一個sql語句總有一個輸入,一個輸出,輸入資料經過sql加工後得到輸出資料,
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的人更容易與自己的思維相銜接。
根據上述的幾個sql基本操作,我們抽象出了一些<code>邏輯算子(operator)</code>,這些算子的功能是單一的不可再拆分的機關。分别是：
這些奇怪的算子是幹什麼用的呢？說白了,一個邏輯查詢計劃就是由這些算子組成的一個<code>有向無環圖(dag)</code>,每一個算子都描述了sql操作裡的不同動作,由算子組成的有向無環圖(dag)描述了資料流的方向.
對于大部分算子而言,都有一個輸入資料集,和一個輸出資料集。joinoperator和unionalloperator比較特殊,擁有兩個或者兩個以上的輸入資料集,因為這兩個算子的操作就是要将多個資料集做關聯。我們将算子的<code>輸入資料集</code>和<code>輸出資料集</code>稱之為<code>虛表(vtable)</code>
使用者是看不到虛表(vtable)的,它隻用來做内部分析,是算子和算子之間的橋梁,如下圖所示:
在sql裡,有很多子句都可以帶有表達式,比如
其中select子句中,group by子句中, where子句中都帶有表達式。表達式的解析和計算貫穿着整個sql解析的過程,是以這裡單獨講講表達式。
1.類型推導
在分析表達式時,會遇到使用者輸入的常量,我們需要通過類型推導給輸入的每一個常量做标記,識别sql中常量的類型,規則較為簡單,如：
2.隐式類型轉換
所有的程式設計語言都會遇到隐式類型轉換的問題,即當調用一個函數時,如果輸入參數類型不符合函數簽名時,就要嘗試對輸入的參數做隐式類型轉換。當然,并不一定每次隐式類型轉換都是成功的,如果發現無法無論如何轉換都無法滿足函數的簽名,就會有異常抛出,終止分析過程。
3.布爾表達式分析
布爾表達式的分析主要作用是可以讓之後的sql優化更容易的進行下去,如join時的條件下推優化,分區裁剪優化,都需要使用布爾表達式分析後的結果來進行。這步分析會用到很多布爾代數的知識,目的隻有一個,那就是将使用者輸入的冗長的布爾表達式變換為<code>最簡合取範式</code>,簡而言之,就是将使用者輸入的一大推’and’ ‘or’組成的布爾表達式變換成由’and’連接配接的最簡形式,如：
看起來這是一個很神奇的變換,實際上已經有很現成的算法來解決這個問題了。總共需要2步：
利用quine mccluskey 算法對輸入的布爾表達式生成合取範式(cnf)
利用petrick’s method 算法對第一步生成的cnf計算最簡合取範式(minimal cnf)
4.case when表達式的分析
case when表達式是一個略顯奇葩的表達式,它本身上是一個<code>值函數（scalarfunction）</code>,但又有邏輯判斷,傳回值又不固定,并且還可以嵌套使用,而且在文法上還有兩種形式(簡單case函數和case搜尋函數) – -! 想在計算機裡優雅的記錄表達這個case when真的很不容易。
condition參數是casewhen子句的條件,returnvalue1代表這then後的傳回值,returnvalue2代表else後的傳回值。
這樣,我們就可以很好的在計算機中結構化的表達,如：
有了以上的基礎,我們就可以開始生成我們的查詢計劃了。嚴格按照sql語句的執行順序來周遊編譯階段生成的ast樹,遇到什麼操作就生成什麼樣的算子,遇到表達式就調用之前的表達式分析,真是兵來将擋水來土掩。
舉個例子：
需要注意的是,在聚合函數裡的值函數、group by清單中的值函數,需要在聚合操作以前就計算完成,否則無法進行聚合操作,于是乎,出現了一個叫<code>初始投影</code>的東西,本質上這是一個selectoperator,隻是用來計算一下聚合需要用到的表達式。
題外話,在很久以前,group by 清單中和聚合函數裡都是不允許使用表達式的,隻能使用單一的值或者列,是以那時也不需要初始投影。使用者想使用類似功能時隻能通過子查詢來實作。後來sql文法擴充了,支援了group by、聚合函數中調用值函數,于是,在sql解析時要先判斷一下是否需要初始投影
還有很多結構的sql沒有講到,比如join, union all, windown function,由于篇幅原因,這裡先不提了,感興趣的同學可以來找我們私下交流。
sql文法本身就是一個遞歸的結構,支援在from之後寫一個子查詢,如:
面對這樣的語句,我們隻要先去生成子查詢的邏輯查詢計劃,将子查詢的的結果虛表作為父查詢的輸入即可,在邏輯上很友善去應對。上面這個示例的查詢計劃如下圖所示：
生成邏輯查詢計劃後,需要先對查詢計劃做一次優化,将一些顯而易見的點優化掉,避免備援的計算。主要包含三個優化：
常量表達式的計算舉個例子:
select 1+2 from pokes
“<code>1+2</code>“就是一個常量表達式,此時,我們可以将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相關的實體查詢計劃。
實體查詢計劃是通過之前産生的邏輯查詢計劃生成的,在轉換的過程中,要與飛天的mapreduce程式設計架構做适配,生成飛天系統可以識别的dag
飛天的dag是一個類似mapreduce的程式設計架構,想把剛剛一個sql跑在分布式的飛天系統上,就需要按照分布式系統程式設計架構來抽象出一些新的實體運算符。
shuffle-sort算子(在odps中,這個算子叫reducesink)在飛天系統上,我們如果想做group by或者join操作,那麼必須把相同key的資料放到同一個程序節點上來執行,而在這直線,這些相同key的資料也許是被打散在各個程序裡的,這時我們就需要一個專門的算子來做資料的重新分區、排序的操作
groupby的不同階段在飛天系統上,我們想實作一個groupby需要有4步:
準備階段(aggregationprepare), 在做一些非線性的聚合函數操作時,比如avg求平均值,需要将avg()拆解成sum(),count()兩個線性的聚合函數,最後再使用sum()/count()來算出avg()的值。在這步,隻做拆解。
本地聚合(semihashaggregation), 對于group by來說,需要将所有group by 清單的字段資料放倒一個機器上才可以進行完全聚合,但是出于優化考慮,我們可以在資料片不全的時候先做一次聚合,雖然這次聚合操作不完全,但是可以減少輸出的資料量,并且可以保證資料的正确性
流式聚合(stremaggregation), 這個聚合有個前提,一定是要求前趨的虛表group by 清單中的資料都會在這一個程序裡,并且排好序。一般而言,在本地聚合之後,資料會通過shuffle-sort運算資料重新分區和排序,再輸入到流式聚合算子中
合并(finalaggregation),這裡輸入的其實是已經聚合好的結果了,但是由于第一步提到的原因,有些非線性聚合函數被分解成了線性聚合函數,這裡要将他們合并。如:avg()=sum()/count()
在隻有線性聚合函數時,上面的1,4步可以省略。
mapjoin 算子和mergejoin算子
mergejoinmergejoin是最常見的一種join算子,一般而言,mergejoin是要求輸入資料的虛表按照join的key分區并且排序的,是以mergejoin一般出現在shuffle-sort算子之後。
mapjoin使用過的人應該都知道有一種join的優化叫mapjoin,這個名字的本意是map-side join,就是join運算在mapreduce的map階段完成。如果使用者在做join時,知道有一個資料表的資料量很小,可以選擇使用mapjoin,mapjoin算子會在每一個程序裡都把小表中的資料加載到記憶體,與打表一一做join。這樣可以減少一次shuffle-sort,提升執行效率。
邏輯查詢計劃是實體查詢計劃的輸入,我們按照拓撲序去周遊邏輯查詢計劃上的每一個邏輯算子,生成實體算子,當我們認為虛表需要重新分區排序才能滿足下一個階段的運算時,我們就在中間加入一個shuffle-sort運算符.
還是使用邏輯查詢計劃生成的那個例子來描述一下實體查詢計劃是什麼樣子：
現在,又進入了一個優化的環節。此時的優化與底層的分布式系統更相關,主要目标就是減少讀取的資料量,減少整個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算子删除,減少資料的網絡傳輸和落地。
實體查詢計劃已經生成好了,下一步就是按照飛天的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将資料寫出到磁盤。
洋洋灑灑寫了這麼多,sql解析的邏輯基本就結束了,sql解析是一個邏輯非常複雜繁瑣的過程,有很多細節和惡心的坑本文中還沒有提到,稍有不慎就可能引起sql正确性的錯誤。