物化視圖和視圖的最大區別_基于catalyst的物化視圖改寫引擎的實現

更新日志：
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/rewritenew PredicateMatcher(rewriteContext),new SPGJPredicateRewrite(rewriteContext),//groupby 條件子句的matcher/rewritenew GroupByMatcher(rewriteContext),new GroupByRewrite(rewriteContext),//聚合子句的matcher/rewrite new AggMatcher(rewriteContext),new AggRewrite(rewriteContext),//join子句的matcher/rewritenew JoinMatcher(rewriteContext),new JoinRewrite(rewriteContext),//select子句的matcher/rewritenew 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過濾方位內。

對于join語句，因為前面我們使用了優化器，會將Join On后面的條件語句進行合理下推，在LogicalPlan里會轉化成filter,所以我們只要判斷Join語法書是不是一致即可。

對于帶有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后直接發回執行即可。