更新日志：
- 2020/06/16 group by 視圖的部分描述錯誤鸭丛，已修正竞穷。
什么是物化視圖
我先用我的話解釋一下什么是物化視圖。假設(shè)我們已經(jīng)有A鳞溉，B兩張表瘾带，現(xiàn)在我創(chuàng)建了一張表C,
C是由A,B兩張表經(jīng)過一條SQL處理得到的，這個時候我們就可以認(rèn)為C是A穿挨，B的物化視圖了月弛。那怎么用呢？當(dāng)一個用戶寫了一條使用A Join B表的SQL科盛，系統(tǒng)會自動嘗試能否改寫成基于C表的查詢帽衙，如果成功，那么可能查詢速度就非痴昝啵快了厉萝，因為避免了Join的發(fā)生，只是簡單的基于C做了下過濾榨崩，但得到的結(jié)果和直接使用A,B 是一樣的谴垫。
顯然，物化視圖有個很大的問題母蛛，就是更新問題翩剪，譬如A，B發(fā)生了變化彩郊，如何保證C 也得到更新前弯。所以這里除了改寫以外蚪缀，還涉及到了C的創(chuàng)建，管理和更新問題恕出。
現(xiàn)在讓我們引入點術(shù)語了询枚，前面我們提到的自動將基于A，B的查詢改寫成基于C的查詢浙巫，我們叫Query Rewrite金蜀。Query Rewrite 就是將原有的查詢不需要修改，引擎自動選擇合適的物化視圖進行查詢重寫的畴，完全對應(yīng)用透明。
物化視圖和傳統(tǒng)視圖的最大的區(qū)別是苗傅，物化視圖存儲不僅存儲了計算邏輯抒线，還存儲了計算結(jié)果渣慕，并且更進一步的是，作為用戶你無需顯示使用物化視圖逊桦，系統(tǒng)會通過Query Rewrite自己來完成內(nèi)部的改寫眨猎。不過無論技術(shù)上多先進强经，我們最后都可以歸納到以空間換時間里去睡陪。
SQL Booster
今天我們探討的重點是如何實現(xiàn)Query Rewrite。我去年寫了一個Query Rewrite 引擎[s
ql-booster](https://github.com/aistack/sql-booster),其實是受到阿里李呈祥團隊的relational cache啟發(fā)匿情。當(dāng)時看了他們的分享覺得太棒了兰迫，很想立馬就用，但是想著等他們推到開源項目里就太漫長了炬称，加之目前大數(shù)據(jù)里的物化視圖的實現(xiàn)汁果，已經(jīng)開源的貌似只有hive了，是基于Calcite實現(xiàn)的,而Spark 的話是自己開發(fā)的catlyst引擎玲躯，而我自己又重度使用Spark据德，所以干脆自己動手基于catalyst實現(xiàn)一個。后面在開發(fā)過程中也遇到了不少公司也在做類似的實現(xiàn)跷车，也有問我的棘利，可惜一直沒有寫文章，這次趁著周末朽缴，寫了善玫，既可以做為交流用，也可以作為備忘錄密强。因為時間久了蝌焚，代碼和思路就很容易遺忘裹唆，文章可以很容易喚醒記憶誓斥，一箭雙雕只洒。
知識準(zhǔn)備篇
一個物化視圖由兩部分構(gòu)成：
1. 生成該物化視圖的SQL
2. 表數(shù)據(jù)
表數(shù)據(jù)很簡單，就是為了查詢的劳坑。記錄生成該物化視圖的SQL的原因是毕谴，我們需要知道這個物化視圖的數(shù)據(jù)是來源哪些表的，每個字段的是來源哪些表距芬，不然沒辦法做改寫涝开。
Query Rewrite的基本步驟如下
1. 注冊各個視圖，這些視圖都會以AST(Catalyst里的LogicalPlan)存在
2. 待改寫的用戶SQL框仔，這些SQL不會顯示使用物化視圖舀武。
3. 將SQL解析成方便遍歷處理的AST，也是Catalyst里的LogicalPlan,并且經(jīng)過Analyzed的离斩，因為我們需要明確知道每個字段屬于哪個表银舱。
4. 處理待改寫的LogicalPlan,然后去和每個已經(jīng)存在的視圖LogicalPlan匹配，對于匹配上的跛梗，則實行改寫
5. 最后將該寫過的LogicalPlan重新生成SQL或者直接執(zhí)行得到結(jié)果寻馏。
所以實際上，上面涉及到如下幾個概念核偿，大家需要有個基本感知：
1. 所有視圖的LogicalPlan
2. 待改寫的查詢LogicalPlan
Query Rewrite 的分而治之
在思考Query Rewrite實現(xiàn)的的時候诚欠，我想到的第一個問題就是，一條待改寫的SQL是不是可能會使用到多個視圖漾岳？
答案是肯定的轰绵。理由有三：
1. 如果一條SQL只匹配一個視圖尼荆，如果該視圖能覆蓋到這條SQL的大部分表，那么該視圖的通用性必然不好翔悠。如果只能覆蓋SQL里的一小部分，那么如果只匹配到一個視圖蓄愁，那么可能最后查詢速度的提升不會太好狞悲。
2. 匹配度太低，還會導(dǎo)致大量存儲的使用摇锋，否則就相當(dāng)于不起作用了站超。
3. 對于一條復(fù)雜的SQL死相，里面會包含各種子查詢，所以作為一個整體的SQL去匹配一個視圖算撮，實現(xiàn)上也是有難度的县昂。
實際上，一條SQL倒彰，其復(fù)雜度主要來源于子查詢和join。 join是我們需要盡量通過物化視圖消解掉的芒澜，而子查詢，本質(zhì)上就是SQL內(nèi)置的虛擬視圖耙箍，我們希望盡可能通過物化視圖來替換掉這些虛擬視圖（虛擬視圖意味著大量的計算，因為虛擬視圖里一般也會有復(fù)雜的Join查詢）阅酪。這樣汁针，事情就變得簡單了，我們只要把一條SQL里的所有子查詢都拎出來辉词，最后每個句子都會符合SPJG形式。
所謂SPJG形式的語句是指僅包含如下語法塊的語句：
1. project
2. agg
3. filter
4. join
其他如limit瑞躺，Order by之類的并不影響視圖替換兴想，我們無需考慮。
如果把子查詢都拉出來捞镰，最后會形成一個子查詢樹狀結(jié)構(gòu)，理論上我們只要對葉子節(jié)點做處理即可（只包含基礎(chǔ)表的SPJG語句）岸售，每個葉子節(jié)點一定是符合SPEG格式要求的。當(dāng)然了凸丸，如果我們的物化視圖還帶有層級結(jié)構(gòu)，也就是基于物化視圖上再生成新的物化視圖解孙，那么還可以進一步按現(xiàn)在的邏輯匹配抛人。不過我們先不搞他妖枚。我們先只處理非視圖表替換成視圖表的情況苍在。
有了上面的思路绝页，事情就簡單了续誉，因為我們是對很簡單的SQL語句做視圖替換匹配初肉，而且因為一個復(fù)雜的SQL會包含很多只包含了基礎(chǔ)表的SPJG語句，我們一一嘗試用物化視圖替換他們就好牙咏。
具體做法是，我們把SQL先用Catalyst解析成 Analyzed LogicalPlan摔握，另外我們還要做一些適當(dāng)?shù)膬?yōu)化丁寄，我目前是做了EliminateOuterJoin，PushPredicateThroughJoin盛正，這樣可以將多種原先形式不同的 LogicalPlan 轉(zhuǎn)化成相同的形式奢浑，可以提高命中率。得到了這個語法樹后我們通過AST提供的transformDown/transformUp拿到所有符合SPEG形態(tài)的語句壤蚜。接著拿著這些SPEG語句一一去匹配是不是有符合的物化視圖。
接下來我們在具體看SEPG具體匹配和修改邏輯的之前聪富，我們還需要解決一個問題，我們可能有幾十個甚至上千個物化視圖墩蔓，一一去匹配效率肯定是不行的萧豆，如果快速縮小范圍呢？
一個簡單的視圖倒排索引
我們在創(chuàng)建物化視圖的時候阵面，系統(tǒng)會自動拿到視圖里的主表洪鸭，也就是join最左側(cè)的表。如果該主表被多個視圖包含览爵，最終會形成下面的結(jié)構(gòu)：
主表 -> 視圖1, 視圖2,視圖3...
注意，這里的主表和視圖箕母，都是Catalyst里的LogicalPlan梅肤。
當(dāng)我們在處理SPEG 語句的時候，我們也按相同的方式拿到主表姨蝴，然后以它為key去拿到對應(yīng)的視圖，這個過程是非呈谂粒快的浮梢。得到視圖后，我們會遍歷這些視圖芥映，去看這些視圖里的表是不是和SPEG里出現(xiàn)的表是一樣的，如果是一樣奈偏，就算匹配上了。完全匹配上了的視圖丽涩，可能也會有多個裁蚁，然后我們會進一步做測試他們的等價性径筏，如果只有一個匹配上短纵，那萬事大吉，做改寫就好吸祟，如果還有多個匹配上炒刁，那么可能就需有個打分模型了，不過我們也可以簡單的取第一個匹配上的就完事倒脓。
當(dāng)然了含思，如果你不怕空間浪費，也可以將每個視圖涉及到的表都拿出來做形成前面的結(jié)構(gòu)饲做，性能上應(yīng)該會更好遏弱，但是內(nèi)存可能消耗會大一點，這個就要考實現(xiàn)者自己權(quán)衡了漱逸。
如何將SPEG使用物化視圖進行改寫
改寫其實是要經(jīng)歷兩個階段的，第一個是匹配階段肮砾，第二個才是改寫階段袋坑。
因為SPEG組成已經(jīng)比較簡單了，因為只包含了project/agg/filter/group/join 等幾個部分婆誓。所以我們匹配和改寫主要就是針對這么幾個部分。這意味著我們至少需要五個匹配器模叙，五個改寫器鞋屈。然后執(zhí)行邏輯是，五個匹配器都去匹配渠啊，只有都符合了权旷，才會觸發(fā)五個改寫器進行改寫
下面是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)
))
每個匹配器都需要實現(xiàn)一定的規(guī)則躲查。比如where條件子句要求視圖的過濾子句必須包含查詢SQL的译柏。什么意思呢？比如假設(shè)我們有基礎(chǔ)表A典唇，用戶的原生查詢?nèi)缦拢?/p>
select A.a from A where A.a<10;
物化視圖C的定義是：
select a from A where a<11;
顯然介衔，在filter(where)里，C的數(shù)據(jù)集是包含用戶原生查詢的炎咖，所以對于where條件我們除了替換成C的a屬性以外侣签，其他的都不用動。
select a from C where a<10;
實際上蹦肴，對于這一個簡單的語句，我們至少需要檢查如下兩點：
1. 用戶的project屬性是不是都在 C的project屬性（select語句里的屬性）里
2. 用戶的filter的過濾范圍是不是都在C的filter過濾方位內(nèi)阴幌。
對于帶有agg/group 的則比較復(fù)雜。
比如視圖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))。具體的一些改寫規(guī)則我在文章中就不一一羅列并炮，大家感興趣可以去看看我上面羅列的五個改寫器。
注意： 名詞filter/predicate 是等價的羡棵，一般是指過濾條件;project 是指select語句部分；
如何從LogicalPlan轉(zhuǎn)化會SQL
我其實我希望sql-booster是一個標(biāo)準(zhǔn)的Query Rewrite服務(wù)店展。只要把表和視圖的定義注冊進來，給定一條SQL赂蕴，就能返回一條改寫后的SQL概说。所以如何把LogicalPlan轉(zhuǎn)換回SQL也是一個比較重要的工作。正如我們前面討論的萍丐，無論SQL多復(fù)雜，最后都是由SPEG的樹狀結(jié)構(gòu)構(gòu)成逝变，所以我們還原的語句其實會比較簡單，核心就是遞歸處理子查詢拱层，把每個子查詢都轉(zhuǎn)化成一個標(biāo)準(zhǔn)的SPEG語句宴咧。
比較繁瑣的是表達式需要還原回字符串，這個需要大量的枚舉烙肺。具體參看org.apache.spark.sql.catalyst.sqlgenerator.LogicalPlanSQL柿冲，該代碼主要修改自Moonbox項目，對此表示感謝怎栽。
當(dāng)然了宿饱，很多情況我們可能也不需要這個步驟谬以，僅僅需要直接執(zhí)行改寫后的LogicalPlan或者序列化LogicalPlan后直接發(fā)回執(zhí)行即可。
最后的結(jié)束語
物化視圖的Query Rewrite是個需要積累的活为黎，目前sql-booster僅僅是實現(xiàn)了部分匹配/改寫規(guī)則，畢竟當(dāng)時自己好像只開發(fā)一到兩個禮拜剪廉。不過后續(xù)我有時間會繼續(xù)完善炕檩，也希望能夠在公司應(yīng)用起來。
