基於catalyst的物化檢視改寫引擎的實現

語言: CN / TW / HK

更新日誌:

  1. 2020/06/16 group by 檢視的部分描述錯誤,已修正。

什麼是物化檢視

我先用我的話解釋一下什麼是物化檢視。假設我們已經有A,B兩張表,現在我建立了一張表C,

C是由A,B兩張表經過一條SQL處理得到的,這個時候我們就可以認為C是A,B的物化檢視了。那怎麼用呢?當一個使用者寫了一條使用A Join B表的SQL,系統會自動嘗試能否改寫成基於C表的查詢,如果成功,那麼可能查詢速度就非常快了,因為避免了Join的發生,只是簡單的基於C做了下過濾,但得到的結果和直接使用A,B 是一樣的。

顯然,物化檢視有個很大的問題,就是更新問題,譬如A,B發生了變化,如何保證C 也得到更新。所以這裡除了改寫以外,還涉及到了C的建立,管理和更新問題。

現在讓我們引入點術語了,前面我們提到的自動將基於A,B的查詢改寫成基於C的查詢,我們叫Query Rewrite。Query Rewrite 就是將原有的查詢不需要修改,引擎自動選擇合適的物化檢視進行查詢重寫,完全對應用透明。

物化檢視和傳統檢視的最大的區別是,物化檢視儲存不僅儲存了計算邏輯,還儲存了計算結果,並且更進一步的是,作為使用者你無需顯示使用物化檢視,系統會通過Query Rewrite自己來完成內部的改寫。不過無論技術上多先進,我們最後都可以歸納到以空間換時間裡去。

SQL Booster

今天我們探討的重點是如何實現Query Rewrite。我去年寫了一個Query Rewrite 引擎[s

ql-booster]( https://github.com/aistack/sql-booster ),其實是受到阿里李呈祥團隊的relational cache啟發。當時看了他們的分享覺得太棒了,很想立馬就用,但是想著等他們推到開源專案裡就太漫長了,加之目前大資料裡的物化檢視的實現,已經開源的貌似只有hive了,是基於Calcite實現的,而Spark 的話是自己開發的catlyst引擎,而我自己又重度使用Spark,所以乾脆自己動手基於catalyst實現一個。後面在開發過程中也遇到了不少公司也在做類似的實現,也有問我的,可惜一直沒有寫文章,這次趁著週末,寫了,既可以做為交流用,也可以作為備忘錄。因為時間久了,程式碼和思路就很容易遺忘,文章可以很容易喚醒記憶,一箭雙鵰。

知識準備篇

一個物化檢視由兩部分構成:

1. 生成該物化檢視的SQL

2. 表資料

表資料很簡單,就是為了查詢的。記錄生成該物化檢視的SQL的原因是,我們需要知道這個物化檢視的資料是來源哪些表的,每個欄位的是來源哪些表,不然沒辦法做改寫。

Query Rewrite的基本步驟如下

1. 註冊各個檢視,這些檢視都會以AST(Catalyst裡的LogicalPlan)存在

2. 待改寫的使用者SQL,這些SQL不會顯示使用物化檢視。

3. 將SQL解析成方便遍歷處理的AST,也是Catalyst裡的LogicalPlan,並且經過Analyzed的,因為我們需要明確知道每個欄位屬於哪個表。

4. 處理待改寫的LogicalPlan,然後去和每個已經存在的檢視LogicalPlan匹配,對於匹配上的,則實行改寫

5. 最後將該寫過的LogicalPlan重新生成SQL或者直接執行得到結果。

所以實際上,上面涉及到如下幾個概念,大家需要有個基本感知:

1. 所有檢視的LogicalPlan

2. 待改寫的查詢LogicalPlan

Query Rewrite 的分而治之

在思考Query Rewrite實現的的時候,我想到的第一個問題就是,一條待改寫的SQL是不是可能會使用到多個檢視?

答案是肯定的。理由有三:

1. 如果一條SQL只匹配一個檢視,如果該檢視能覆蓋到這條SQL的大部分表,那麼該檢視的通用性必然不好。如果只能覆蓋SQL裡的一小部分,那麼如果只匹配到一個檢視,那麼可能最後查詢速度的提升不會太好。

2. 匹配度太低,還會導致大量儲存的使用,否則就相當於不起作用了。

3. 對於一條複雜的SQL,裡面會包含各種子查詢,所以作為一個整體的SQL去匹配一個檢視,實現上也是有難度的。

實際上,一條SQL,其複雜度主要來源於子查詢和join。 join是我們需要儘量通過物化檢視消解掉的,而子查詢,本質上就是SQL內建的虛擬檢視,我們希望儘可能通過物化檢視來替換掉這些虛擬檢視(虛擬檢視意味著大量的計算,因為虛擬視圖裡一般也會有複雜的Join查詢)。這樣,事情就變得簡單了,我們只要把一條SQL裡的所有子查詢都拎出來,最後每個句子都會符合SPJG形式。

所謂SPJG形式的語句是指僅包含如下語法塊的語句:

1. project

2. agg

3. filter

4. join

其他如limit,Order by之類的並不影響檢視替換,我們無需考慮。

如果把子查詢都拉出來,最後會形成一個子查詢樹狀結構,理論上我們只要對葉子節點做處理即可(只包含基礎表的SPJG語句),每個葉子節點一定是符合SPEG格式要求的。當然了,如果我們的物化檢視還帶有層級結構,也就是基於物化檢視上再生成新的物化檢視,那麼還可以進一步按現在的邏輯匹配。不過我們先不搞他。我們先只處理非視圖表替換成視圖表的情況。

有了上面的思路,事情就簡單了,因為我們是對很簡單的SQL語句做檢視替換匹配,而且因為一個複雜的SQL會包含很多隻包含了基礎表的SPJG語句,我們一一嘗試用物化檢視替換他們就好。

具體做法是,我們把SQL先用Catalyst解析成 Analyzed LogicalPlan,另外我們還要做一些適當的優化,我目前是做了EliminateOuterJoin,PushPredicateThroughJoin,這樣可以將多種原先形式不同的 LogicalPlan 轉化成相同的形式,可以提高命中率。得到了這個語法樹後我們通過AST提供的transformDown/transformUp拿到所有符合SPEG形態的語句。接著拿著這些SPEG語句一一去匹配是不是有符合的物化檢視。

接下來我們在具體看SEPG具體匹配和修改邏輯的之前,我們還需要解決一個問題,我們可能有幾十個甚至上千個物化檢視,一一去匹配效率肯定是不行的,如果快速縮小範圍呢?

一個簡單的檢視倒排索引

我們在建立物化檢視的時候,系統會自動拿到視圖裡的主表,也就是join最左側的表。如果該主表被多個檢視包含,最終會形成下面的結構:

主表 -> 檢視1, 檢視2,檢視3...

注意,這裡的主表和檢視,都是Catalyst裡的LogicalPlan。

當我們在處理SPEG 語句的時候,我們也按相同的方式拿到主表,然後以它為key去拿到對應的檢視,這個過程是非常快的。得到檢視後,我們會遍歷這些檢視,去看這些視圖裡的表是不是和SPEG裡出現的表是一樣的,如果是一樣,就算匹配上了。完全匹配上了的檢視,可能也會有多個,然後我們會進一步做測試他們的等價性,如果只有一個匹配上,那萬事大吉,做改寫就好,如果還有多個匹配上,那麼可能就需有個打分模型了,不過我們也可以簡單的取第一個匹配上的就完事。

當然了,如果你不怕空間浪費,也可以將每個檢視涉及到的表都拿出來做形成前面的結構,效能上應該會更好,但是記憶體可能消耗會大一點,這個就要考實現者自己權衡了。

如何將SPEG使用物化檢視進行改寫

改寫其實是要經歷兩個階段的,第一個是匹配階段,第二個才是改寫階段。

因為SPEG組成已經比較簡單了,因為只包含了project/agg/filter/group/join 等幾個部分。所以我們匹配和改寫主要就是針對這麼幾個部分。這意味著我們至少需要五個匹配器,五個改寫器。然後執行邏輯是,五個匹配器都去匹配,只有都符合了,才會觸發五個改寫器進行改寫

下面是sql-booster的匹配器和改寫器。

val pipeline = buildPipeline(rewriteContext: RewriteContext, Seq(

//filter條件子句的matcher/rewrite

new PredicateMatcher(rewriteContext),

new SPGJPredicateRewrite(rewriteContext),

//groupby 條件子句的matcher/rewrite

new GroupByMatcher(rewriteContext),

new GroupByRewrite(rewriteContext),

//聚合子句的matcher/rewrite

new AggMatcher(rewriteContext),

new AggRewrite(rewriteContext),

//join子句的matcher/rewrite

new JoinMatcher(rewriteContext),

new JoinRewrite(rewriteContext),

//select子句的matcher/rewrite

new ProjectMatcher(rewriteContext),

new ProjectRewrite(rewriteContext)

))

每個匹配器都需要實現一定的規則。比如where條件子句要求檢視的過濾子句必須包含查詢SQL的。什麼意思呢?比如假設我們有基礎表A,使用者的原生查詢如下:

select A.a from A where A.a<10;

物化檢視C的定義是:

select a from A where a<11;

顯然,在filter(where)裡,C的資料集是包含使用者原生查詢的,所以對於where條件我們除了替換成C的a屬性以外,其他的都不用動。

select a from C where a<10;

實際上,對於這一個簡單的語句,我們至少需要檢查如下兩點:

1. 使用者的project屬性是不是都在 C的project屬性(select語句裡的屬性)裡

2. 使用者的filter的過濾範圍是不是都在C的filter過濾方位內。

對於帶有agg/group 的則比較複雜。

比如檢視C由如下SQL得到:

select m,c,count(*) as a from A group by m,c

使用者查詢語句如下:

select c,count(*) as a from A group by c

這個時候匹配比較容易,我們需group by語句的條件檢視是使用者查詢語句的超集,並且順序必須是後面的。比如視圖裡是group by m,c 那使用者的查詢只能是m,c 或者c,同時依然要符合檢視的project屬性要包含使用者的所有的project屬性,但是改寫上會麻煩一些,需要改寫成如下形式才會是等價的:

select sum(a) from C group by c

另外一個例子是avg,他最後要改寫成sum(k)/a(a等於視圖裡的avg(k))。具體的一些改寫規則我在文章中就不一一羅列,大家感興趣可以去看看我上面羅列的五個改寫器。

注意: 名詞filter/predicate 是等價的,一般是指過濾條件;project 是指select語句部分;

如何從LogicalPlan轉化會SQL

我其實我希望sql-booster是一個標準的Query Rewrite服務。只要把表和檢視的定義註冊進來,給定一條SQL,就能返回一條改寫後的SQL。所以如何把LogicalPlan轉換回SQL也是一個比較重要的工作。正如我們前面討論的,無論SQL多複雜,最後都是由SPEG的樹狀結構構成,所以我們還原的語句其實會比較簡單,核心就是遞迴處理子查詢,把每個子查詢都轉化成一個標準的SPEG語句。

比較繁瑣的是表示式需要還原回字符串,這個需要大量的列舉。具體參看 org.apache.spark.sql.catalyst.sqlgenerator.LogicalPlanSQL ,該程式碼主要修改自Moonbox專案,對此表示感謝。

當然了,很多情況我們可能也不需要這個步驟,僅僅需要直接執行改寫後的LogicalPlan或者序列化LogicalPlan後直接發回執行即可。

最後的結束語

物化檢視的Query Rewrite是個需要積累的活,目前sql-booster僅僅是實現了部分匹配/改寫規則,畢竟當時自己好像只開發一到兩個禮拜。不過後續我有時間會繼續完善,也希望能夠在公司應用起來。