一文详解物化视图改写
簡介： 本文主要介紹什么是物化視圖，以及如何實現(xiàn)基于物化視圖的查詢改寫。
作者：阿里云數(shù)據(jù)庫OLAP產(chǎn)品部 云曦
預(yù)計算和緩存是計算機領(lǐng)域提高性能以及降低成本的最常見的手段之一。對于那些經(jīng)常重復(fù)的請求，如果可以通過緩存回答，比重新計算結(jié)果或從速度較慢的數(shù)據(jù)存儲中讀取要快得多，消耗更少的系統(tǒng)資源。在數(shù)據(jù)庫領(lǐng)域中，物化視圖是預(yù)計算和緩存的自然體現(xiàn)。
本文主要介紹什么是物化視圖，以及如何實現(xiàn)基于物化視圖的查詢改寫。
在第一部分，我們會簡單介紹物化視圖，并介紹基于物化視圖的查詢改寫的用途。在第二部分，我們將介紹查詢優(yōu)化器使用物化視圖進行查詢改寫的匹配和改寫過程。最后，我們將介紹查詢改寫的幾種實現(xiàn)方式，及其優(yōu)缺點。
背景介紹
物化視圖
物化視圖是將查詢結(jié)果預(yù)先計算并存儲的一張?zhí)厥獾谋怼?#34;物化"(Materialized) 這個詞是相對于普通視圖而言。普通視圖較普通的表提供了易用性和靈活性，但無法加快數(shù)據(jù)訪問的速度。物化視圖像是視圖的緩存，它不是在運行時構(gòu)建和計算數(shù)據(jù)集，而是在創(chuàng)建的時候預(yù)先計算、存儲和優(yōu)化數(shù)據(jù)訪問，并自動刷新來保證數(shù)據(jù)的實時性。
對于數(shù)據(jù)倉庫，物化視圖最重要的功能就是查詢加速。數(shù)據(jù)倉庫中存在大量在大型表上執(zhí)行復(fù)雜的查詢，這些查詢會消耗大量資源和時間。物化視圖可以通過預(yù)計算的結(jié)果回答查詢，消除昂貴的聯(lián)接和聚合所帶來的開銷，大幅度改善查詢處理時間，降低系統(tǒng)負載。對于可以預(yù)見并反復(fù)使用相同子查詢結(jié)果的查詢，物化視圖特別有用。
為了實現(xiàn)物化視圖的潛力，需要解決三個問題：
本文主要從查詢優(yōu)化器的角度，介紹使用物化視圖加速查詢背后的技術(shù)實現(xiàn)。
基于物化視圖的查詢改寫
直接查詢物化視圖可以大幅度改善查詢處理時間，但是需要用戶修改查詢語句。使用物化視圖加速查詢的一個重要問題是，如何采用一種系統(tǒng)化和自動化的方法，自動使用物化視圖回答查詢。通過這種透明改寫，物化視圖可以像索引一樣添加或刪除，而不會影響已有 SQL。
查詢改寫使得物化視圖具有廣泛的用途：
查詢改寫的問題定義
為了實現(xiàn)更大范圍的改寫，查詢改寫通常被集成在優(yōu)化器規(guī)則中。這有幾個方面的好處。
首先查詢改寫可以利用優(yōu)化器其他規(guī)則。依靠優(yōu)化器其他規(guī)則將查詢轉(zhuǎn)換成標準和統(tǒng)一的形式，簡化匹配流程，增加改寫范圍。其中比較重要的規(guī)則是列消除，謂詞下推，解關(guān)聯(lián)子查詢等。解關(guān)聯(lián)子查詢規(guī)則允許物化視圖對包含關(guān)聯(lián)子查詢的查詢進行改寫加速。
其次，優(yōu)化器可以遞歸每一個子樹能否被某個視圖進行改寫。每個相關(guān)視圖都會對每個子樹產(chǎn)生多次改寫，一個查詢語句不同部分可能被不同的視圖改寫。最終所有的改寫都進入基于成本的選擇器中，與原始查詢一起選出最優(yōu)的查詢計劃。
查詢改寫算法只需要考慮給定的查詢表達式和視圖，判斷這個查詢表達式能否從視圖中計算出來，然后從視圖上構(gòu)造一個等價的補償表達式，與原查詢表達式等價。查詢改寫的范圍應(yīng)該盡可能大，查詢改寫的目標是使用少量物化視圖改寫大量查詢。最終由優(yōu)化器選擇出一個最優(yōu)的查詢計劃。
查詢改寫檢查
優(yōu)化器通過多種方式來改寫查詢。最簡單的一種情況是物化視圖的查詢與查詢完全匹配，符合這種查詢重寫類型的查詢數(shù)量很少。為了進行更通用的匹配，優(yōu)化器會嘗試使用各種規(guī)則構(gòu)造一個等價表達式改寫查詢。
查詢改寫檢查包含兩個步驟，改寫匹配檢查和構(gòu)建等價表達式。一個查詢能被視圖回答需要滿足下面兩個條件：
部分條件下即使不滿足條件，視圖也可能會被用于改寫。例如視圖包含一部分查詢所需要的數(shù)據(jù)，可以使用物化視圖回答部分查詢，剩下的數(shù)據(jù)從原始數(shù)據(jù)中計算。這部分改寫檢查會放在高級改寫規(guī)則中進行介紹。
具體來說改寫檢查會依次進行 Join 檢查和 Ouput 檢查，如果查詢或視圖中含有 Grouping By 和 Aggregation，還會進行額外的檢查，如果需要，會嘗試對視圖進一步聚合。
Join 檢查
當查詢和視圖的表的 Join 關(guān)系相同時，視圖才可能包含查詢需要的所有的行和列。一種簡單的方式是只考慮沒有子查詢的 Inner Join，這時只用比較查詢表和數(shù)量是否完全一致即可。或者通過一系列規(guī)則檢查查詢和視圖的關(guān)系代數(shù)樹包含的 Join 關(guān)系是等價的。更通用的一種方法是構(gòu)建 Join Graph。Join Grpah 是一個以關(guān)系為結(jié)點，聯(lián)接為邊的圖。Inner Join 的條件表示為無向邊，Outer Join 的條件表示為有向邊。Join Graph 由查詢關(guān)系代數(shù)樹構(gòu)建而來，通過比較 Join Graph 就可以檢查物化視圖和查詢包含相同的 Join 關(guān)系。
例如對于下面的查詢
select c_custkey, c_name, l_orderkey, l_partkey, l_quantity from (select l_orderkey,l_partkey, l_quantity from lineitem where l_orderkey < 1000and l_shipdate = l_commitdate ) subquery join orders on subquery.l_orderkey = o_orderkey left join customer on o_custkey = c_custkey對于物化視圖
create materialized view mview1 enable query rewrite as select * from lineitem join customer On subquery.l_orderkey = o_orderkey left outer join orders On o_custkey = c_custkey查詢和物化視圖具有相同的 Join 關(guān)系，查詢可以被改寫
select c_custkey, c_name, l_orderkey,l_partkey, l_quantity from mview1 where l_orderkey < 1000 and l_shipdate = l_commitdateOutput 檢查
Ouput 檢查保證物化視圖有足夠的數(shù)據(jù)回答查詢，這包括 3 個步驟：
等價關(guān)系
查詢改寫能夠通過查詢中的等價關(guān)系擴展改寫的范圍。因為等值條件具有傳遞性，等價關(guān)系可以從等值條件或者代數(shù)關(guān)系推導(dǎo)而來。例如可以從 A=date_format(now(), '%Y%m%D') 和 B=date_format(now(), '%Y%m%D')，因為函數(shù)是確定性的，可以得到 A=B，如果我們還有 inner join 的條件 B=C，可以進一步得到 A=B=C。
可能會有某些其他的條件可以推導(dǎo)出等價關(guān)系，例如可以從 A=2，B=3，C=5 推導(dǎo)出 C = A + B。相比等值關(guān)系，尋找這種關(guān)系會使搜索過程更加復(fù)雜，而且我們無法實現(xiàn)所有的可能的相等關(guān)系，因此很少考慮這樣的表達式。等價關(guān)系推導(dǎo)只搜索等值條件，即使可能錯過一些改寫機會，這樣的淺層搜索可以保證速度。
表達式檢查
為了確保查詢輸出的列和補償謂詞需要的列都能從視圖中計算出來，我們需要一種方法確定來自查詢的表達式是否和視圖中的表達式相等，或者能從中計算出來。表達式檢查無法純粹從語法上實現(xiàn)，兩個表達式或者符號的文本相同，并不說明他們關(guān)系相等。例如別名的存在就會破壞基于語法的檢查。
表達式檢查需要通過等價關(guān)系和表的對應(yīng)關(guān)系推導(dǎo)而來。如果視圖和查詢中所有的表都是唯一的，那么來自同一個表的列是等價的；如果視圖和查詢中有表出現(xiàn)多次，即 self join，那么查詢到視圖的表的映射就存在多種可能，每種可能都需要進行一次改寫嘗試。有了視圖和查詢之間列的對應(yīng)關(guān)系和上一節(jié)的等價關(guān)系，通過代數(shù)系統(tǒng)確定來自查詢的表達式是否和視圖中的表達式相等，或者能否從中計算出來。
存在一些啟發(fā)式的規(guī)則，允許一個表達式從另外的表達式中計算出來。比如算數(shù)規(guī)則從 x + 1 中計算出 x，例從 SUM(x) 和 COUNT(x) 計算出 AVG(x)，還存在一些 Function Dependency 規(guī)則，例如時間函數(shù)，可以通過返回的天的結(jié)果計算年等。
謂詞檢查
視圖改寫需要物化視圖中存在查詢所有需要的行數(shù)，即視圖的謂詞的范圍大于或等于查詢的范圍。使用 Wq 表示查詢的謂詞，Wv表示視圖的謂詞，我們需要檢查 Wq => Wv，其中 => 表示 Wq 滿足 Wv 的含義。
優(yōu)化器提取所有的謂詞，并將他們轉(zhuǎn)換為 CNF 的形式，即 W=P1 ^ P2 ^ ... ^ Pn。將謂詞按照等值謂詞，范圍謂詞和剩余謂詞進一步分為 W= PE ^ PR ^ PU。PE，PR，PU 分別代表等值謂詞，范圍謂詞和剩余謂詞。謂詞檢查變成了 PEq ^ PRq ^ PUq => PEv ^ PRv ^ PUv，由于正交的性質(zhì)，最終將問題分解成 PEq => PEv，PEq ^ PRq => PRv，PEq ^ PUq => PUv 三類檢查。
查詢的等值謂詞用于推導(dǎo)等價關(guān)系。查詢中任何視圖不滿足等價關(guān)系的謂詞都構(gòu)成補償謂詞，視圖中存在查詢無法滿足的等價關(guān)系則無法改寫。
范圍謂詞在優(yōu)化器中可以存儲為范圍的形式，可以方便的計算差集。對于查詢中每一個范圍謂詞，如果視圖存在對應(yīng)的范圍精準匹配，不需要進行補償，否則視圖范圍必須大于查詢的范圍，并通過差集構(gòu)造一個補償謂詞。
查詢表達式和試圖剩余的謂詞共同構(gòu)成剩余謂詞PE，只能進行精準匹配。查詢中任何與視圖不匹配的謂詞都構(gòu)成補償謂詞。查詢與視圖不匹配則無法改寫。
所有的補償謂詞都需要通過表達式檢查，確保可以從視圖的輸出中計算出來。
例如查詢
select l_orderkey, o_custkey, l_partkey,l_quantity*l_extendedprice from lineitem, orders, part where l_orderkey = o_orderkey and l_partkey = p_partkey and l_partkey >= 150 and l_partkey <= 160 and o_custkey = 123 and o_orderdate = l_shipdate and p_name like ‘%abc%’ and l_quantity*l_extendedprice > 100物化視圖
create materialized view mview2 Enable Query Rewrite as select l_orderkey, o_custkey, l_partkey,l_shipdate, o_orderdate,l_quantity*l_extendedprice as gross_revenue from lineitem, orders, part where l_orderkey = o_orderkey and l_partkey = p_partkey and p_partkey >= 150 and o_custkey >= 50 and o_custkey <= 500 and p_name like ‘%abc%’查詢可以被改寫為
select l_orderkey, o_custkey, l_partkey, gross_revenue from mview2 where l_partkey <= 160 and o_custkey = 123 and o_orderdate = l_shipdate and gross_revenue > 100Grouping 和 Aggregation 檢查
如果視圖和查詢帶有 GroupBy 或 Aggregation 函數(shù)，需要進行額外檢查：
例如查詢
select c_nationkey, sum(l_quantity*l_extendedprice) from lineitem, orders, customer where l_orderkey = o_orderkey and o_custkey = c_custkey group by c_nationkey物化視圖
create materialized view mview3 enable Query rewrite as select o_custkey, count_big(*) as cnt, sum(l_quantity*l_extendedprice) as revenue from lineitem, orders where l_orderkey = o_orderkey group by o_custkey查詢可以被改寫為
select c_nationkey, sum(revenue) from customer join mview3 on c_custkey = o_custkey group by c_nationkey如果分組列表不同，只能改寫 Group By 在查詢最外部的情況，否則無法進行進一步聚合，無法滿足第二個改寫要求。只有特定的聚合函數(shù)支持進一步聚合，常見的聚合函數(shù)有 MIN，MAX，SUM，COUNT。
例如如下查詢
select o_custkey, count(*) as cnt, sum(l_quantity*l_extendedprice) as revenue from lineitem, orders where l_orderkey = o_orderkey group by o_custkey物化視圖
create materialized view mview4 enable Query rewrite as select o_custkey, l_partkey, count(*) as cnt, sum(l_quantity*l_extendedprice) as revenue from lineitem, orders where l_orderkey = o_orderkey group by o_custkey, l_partkey可以被改寫為
select c_nationkey, sum(cnt) as cnt, sum(revenue) as revenue from mview4 where c_custkey = o_custkey group by o_custkey如果聚合函數(shù)在視圖中不存在，可以通過一些規(guī)則進行計算，例如從 SUM(x) 和 COUNT(x) 計算出 AVG(x)，從 SUM(x) + SUM(y) 中計算出 SUM(x + y) ，這些依賴表達式改寫檢查中啟發(fā)式的規(guī)則。
高級改寫規(guī)則
如果物化視圖和查詢不滿足上一節(jié)的改寫規(guī)則，還可以通過其他規(guī)則進行轉(zhuǎn)換。
Join 補償
如果只考慮 Inner Join，視圖和查詢的 Join 關(guān)系 不一致有兩種情況：查詢比視圖包含更多的聯(lián)接，或者視圖包含更多的聯(lián)接。
如果查詢比視圖包含更多的表，我們可以簡單把缺少的 Join 添加在視圖之上，使其滿足改寫要求。Join 條件會通過謂詞改寫正確的添加進來，優(yōu)化器也可以通過后續(xù)規(guī)則調(diào)整計劃。
Join 補償使優(yōu)化器可以更早的進行匹配改寫，減少改寫的嘗試次數(shù)。
例如如下查詢
select c_custkey, c_name, l_orderkey,l_partkey, l_quantity From lineitem, customer, orders Where l_orderkey = o_orderkey And o_custkey = c_custkey Where l_orderkey between 1000 and 1500 And l_shipdate = l_commitdate物化視圖
Create materialized view mview5 Enable query rewrite as Select l_orderkey,l_partkey, l_quantity From lineitem, orders Where l_orderkey = o_orderkey And o_orderkey >= 500可以被改寫為
Select l_orderkey, l_partkey, l_quantity From mview5 join customer on o_custkey = c_custkey Where l_orderkey between 1000 and 1500 And l_shipdate = l_commitdateJoin 消除
如果一個 Join 出現(xiàn)在視圖中但是沒有出現(xiàn)在查詢中，可以嘗試使用 Join 消除規(guī)則。Join 消除是優(yōu)化器優(yōu)化中的一項常見方法，如果 Join 滿足以下5個條件，則表 T1 在與表 T2 的聯(lián)接中時不變的：
這意味著表 T1 在與 T2 的 Join 關(guān)系不會影響 T1 的結(jié)果，視圖中的 T2 可以在 Join Graph 中忽略。不變聯(lián)接的存在允許在基礎(chǔ)物化視圖上創(chuàng)建更大的并集或超集，從而允許物化視圖包含更大的預(yù)計算，也可以改寫更多的查詢。
例如查詢
Select l_orderkey, l_partkey, l_quantity From lineitem Where l_orderkey between 1000 and 1500 And l_shipdate = l_commitdate物化視圖
Create materialized view mview6 Enable query rewrite as Select c_custkey, c_name, l_orderkey,l_partkey, l_quantity From lineitem, orders, customer Where l_orderkey = o_orderkey And o_custkey = c_custkey And o_orderkey >= 500可以被改寫成
select l_orderkey, l_partkey, l_quantity from mview6 where l_orderkey between 1000 and 1500 and l_shipdate = l_commitdateJoin 派生
如果存在 Outer Join，視圖和查詢 Join 關(guān)系不一致，可以嘗試利用 Join 派生性，從物化視圖中的聯(lián)接重新計算查詢中的聯(lián)接。例如，能從物化視圖中的 left Outer Join 的結(jié)果里，計算 Inner Join，Anti Join 的結(jié)果，Inner Join 又能進一步計算 Semi Join，這樣就能使用物化視圖過濾某些行來回答不同具有不同 Join 關(guān)系的查詢。
Join 派生可以擴展改寫的范圍，允許優(yōu)化器將基于物化視圖的改寫與解關(guān)聯(lián)的規(guī)則規(guī)則結(jié)合，改寫帶有 IN，EXISTS 等的查詢，也可以避免其他優(yōu)化規(guī)則對 Join 的調(diào)整，例如 EliminateOuterJoin 和 PredicatePushDown 可能會將 outer join 優(yōu)化成 inner join。
Union 改寫
物化視圖只包含一部分查詢所需的數(shù)據(jù)，也可以用于查詢改寫。在很多場景下，物化視圖不會也無法存儲全部的數(shù)據(jù)。
一個典型的情況是，數(shù)據(jù)在不斷的寫入，但是寫入只發(fā)生在最近一段時間內(nèi)。在持續(xù)刷新的表上構(gòu)建全量物化視圖，這可能導(dǎo)致因為數(shù)據(jù)插入視圖頻繁刷新，產(chǎn)生高昂的刷新成本，甚至視圖因為持續(xù)刷新而完全不可用。更好的做法是構(gòu)建一個 T+1 條件刷新的物化視圖，存儲不變的數(shù)據(jù)，可以降低刷新成本。
另一種常見的情況是，數(shù)據(jù)倉庫存儲全量的數(shù)據(jù)，而查詢集中在最近幾個月的數(shù)據(jù)，構(gòu)建全部數(shù)據(jù)的物化視圖成本過于高昂，物化視圖只構(gòu)建最近幾個月數(shù)據(jù)，也能改寫絕大多數(shù)查詢。
?
Union 改寫會嘗試使用視圖回答部分查詢，減少查詢中實時計算的數(shù)據(jù)量。Union 改寫可以進一步應(yīng)用 Aggregation 改寫，支持使用物化視圖部分數(shù)據(jù)回答聚合查詢。
例如查詢
select l_orderkey, l_partkey, l_quantity from lineitem where l_orderkey l_orderkey > 500 and l_orderkey <= 1500 and l_shipdate = l_commitdate物化視圖
create materialized view mview8 enable query rewrite as select l_orderkey, l_partkey, l_quantity from lineitem where l_orderkey > 1000 and l_shipdate = l_commitdate改寫結(jié)果
select l_orderkey, l_partkey, l_quantity from lineitem where l_orderkey > 500 and l_orderkey <= 1000 and l_shipdate = l_commitdate union select o.shippriority from mview8 where l_orderkey > 1000 and l_orderkey <= 1500查詢改寫的實現(xiàn)
視圖改寫通常有三種查詢改寫的實現(xiàn)方式：
基于語法的改寫
文本匹配或者語法匹配是最簡單的改寫方法，將查詢的文本與物化視圖的文本或語法樹進行比較，完全匹配可以進行改寫。這種改寫只能匹配完整的查詢語句或子語句，細微的變化就會導(dǎo)致查詢無法改寫，適用的范圍很小。基于語法的改寫雖然簡單，但是效率很高，改寫的成本可以忽略不計。
基于規(guī)則的改寫
基于規(guī)則的改寫和其他優(yōu)化器規(guī)則相同，針對不同 Pattern 的查詢和視圖編寫不同的規(guī)則，尋找等價的替代關(guān)系樹。
最簡單的一條規(guī)則就是直接比較子查詢和視圖的計劃，如果相同就能改寫。高級的改寫規(guī)則不需要物化視圖等同于被替換的計劃，會嘗試計算補償謂詞，構(gòu)建等價查詢表達式。例如 Join 改寫，比較 Join 查詢的子表達式是否和視圖 Join 的某個子表達相同或者能否從中計算出來，每一個Join子表達式都存在映射關(guān)系，最后檢查補償表達式能否從視圖中計算得到。
基于規(guī)則的改寫可以實現(xiàn)大量重寫，實現(xiàn)也比較簡單，改寫匹配速度快，但是也存在局限性。這種改寫依賴轉(zhuǎn)換規(guī)則來尋找等價關(guān)系，因此需要窮舉所有可能的轉(zhuǎn)換關(guān)系來實現(xiàn)復(fù)雜視圖的重寫。一些復(fù)雜的視圖不可能窮舉所有的等價關(guān)系，例如存在很多的 Join 聯(lián)接或者復(fù)雜的 Project 關(guān)系，基于規(guī)則的改寫適用的范圍取決于規(guī)則的數(shù)量。
基于結(jié)構(gòu)的改寫
基于結(jié)構(gòu)的改寫與基于規(guī)則的改寫相反，通過提取查詢中的特征，使用一套規(guī)則進行匹配改寫。優(yōu)化器將查詢表示為 SPJG 標準形式 (Join-Select-Project-GroupBy)，提取查詢中的 Join，Projects，Filters，Grouping 和 Aggregations 五種表達式，分別與物化視圖對應(yīng)的表達式進行匹配和改寫。
這個方法是由微軟在 2001 年 SIGMOD 論文《Optimizing queries using materialized views: A practical, scalable solution》系統(tǒng)化的提出。這種方法可以改寫包含可以改寫包含 Join，Filter，Project 的任意查詢的方法，運用一系列的步驟匹配并得到補償表達式。還可以進一步改寫含有 Aggreagtion 的查詢，在需要時添加 Aggregation 節(jié)點返回進一步匯總的結(jié)果。
基于結(jié)構(gòu)的改寫很容易擴展，例如改寫 Outer Join 和子查詢等，可以完成幾乎全部的改寫。但是搜索成本較高，尤其是在查詢復(fù)雜，改寫嘗試次數(shù)很多的情況下。
?
關(guān)于我們
AnalyticDB 是阿里巴巴自主研發(fā)、唯一經(jīng)過超大規(guī)模以及核心業(yè)務(wù)驗證的 PB 級云原生數(shù)據(jù)倉庫。
AnalyticDB 在去年10月份推出了物化視圖功能，目前的版本支持定時全量刷新和查詢改寫。AnalyticDB 完整實現(xiàn)了基于文本的匹配和基于結(jié)構(gòu)的匹配，可以改寫包含 Join，Filter，Project，Group By 的任意查詢，支持 Aggregation Rollup，Union，Subquery，Outer join 等高級改寫規(guī)則。ADB 會在未來的幾個版本內(nèi)上線基于規(guī)則的匹配，提高改寫的效率。并在未來擴展更多的改寫手段，例如 Grouping sets 改寫支持，使物化視圖有傳統(tǒng)數(shù)倉中 Cube 的能力。
原文鏈接
本文為阿里云原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。
總結(jié)
以上是生活随笔為你收集整理的一文详解物化视图改写的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 收藏！这些IDE使用技巧，你都知道吗
- 下一篇： 4982亿背后的前端技术—2020天猫双