預計算和緩存是計算機領域提高性能以及降低成本的最常見的手段之一。對于那些經常重復的請求，如果可以通過緩存回答，比重新計算結果或從速度較慢的數據存儲中讀取要快得多，消耗更少的系統資源。在數據庫領域中，物化視圖是預計算和緩存的自然體現。

本文主要介紹什么是物化視圖，以及如何實現基于物化視圖的查詢改寫。

在第一部分，我們會簡單介紹物化視圖，并介紹基于物化視圖的查詢改寫的用途。在第二部分，我們將介紹查詢優化器使用物化視圖進行查詢改寫的匹配和改寫過程。最后，我們將介紹查詢改寫的幾種實現方式，及其優缺點。

背景介紹

物化視圖

物化視圖是將查詢結果預先計算并存儲的一張特殊的表。"物化"(Materialized)這個詞是相對于普通視圖而言。普通視圖較普通的表提供了易用性和靈活性，但無法加快數據訪問的速度。物化視圖像是視圖的緩存，它不是在運行時構建和計算數據集，而是在創建的時候預先計算、存儲和優化數據訪問，并自動刷新來保證數據的實時性。

對于數據倉庫，物化視圖最重要的功能就是查詢加速。數據倉庫中存在大量在大型表上執行復雜的查詢，這些查詢會消耗大量資源和時間。物化視圖可以通過預計算的結果回答查詢，消除昂貴的聯接和聚合所帶來的開銷，大幅度改善查詢處理時間，降低系統負載。對于可以預見并反復使用相同子查詢結果的查詢，物化視圖特別有用。

為了實現物化視圖的潛力，需要解決三個問題：

物化視圖選擇：選擇哪些查詢和表構建物化視圖；物化視圖維護：減少物化視圖更新成本和時間；物化視圖運用：如何使用物化視圖加速查詢。

本文主要從查詢優化器的角度，介紹使用物化視圖加速查詢背后的技術實現。

基于物化視圖的查詢改寫

直接查詢物化視圖可以大幅度改善查詢處理時間，但是需要用戶修改查詢語句。使用物化視圖加速查詢的一個重要問題是，如何采用一種系統化和自動化的***，自動使用物化視圖回答查詢。通過這種透明改寫，物化視圖可以像索引一樣添加或刪除，而不會影響已有SQL。

查詢改寫使得物化視圖具有廣泛的用途：

物化視圖可以透明地改寫查詢，無需改造業務就能使用物化加速查詢；方便地應用緩存公共結果集，以及預計算等跨查詢優化手段；對于數據倉庫，數據集成場景，物化視圖可以物化外表結果，屏蔽多個數據源的差異，實現本地副本或讀寫分離；查詢改寫結合自動構建物化視圖，實現數據庫自治加速。

查詢改寫的問題定義

為了實現更大范圍的改寫，查詢改寫通常被集成在優化器規則中。這有幾個方面的好處。

首先查詢改寫可以利用優化器其他規則。依靠優化器其他規則將查詢轉換成標準和統一的形式，簡化匹配流程，增加改寫范圍。其中比較重要的規則是列消除，謂詞下推，解關聯子查詢等。解關聯子查詢規則允許物化視圖對包含關聯子查詢的查詢進行改寫加速。

其次，優化器可以遞歸每一個子樹能否被某個視圖進行改寫。每個相關視圖都會對每個子樹產生多次改寫，一個查詢語句不同部分可能被不同的視圖改寫。最終所有的改寫都進入基于成本的選擇器中，與原始查詢一起選出最優的查詢計劃。

查詢改寫算法只需要考慮給定的查詢表達式和視圖，判斷這個查詢表達式能否從視圖中計算出來，然后從視圖上構造一個等價的補償表達式，與原查詢表達式等價。查詢改寫的范圍應該盡可能大，查詢改寫的目標是使用少量物化視圖改寫大量查詢。最終由優化器選擇出一個最優的查詢計劃。

查詢改寫檢查

優化器通過多種方式來改寫查詢。最簡單的一種情況是物化視圖的查詢與查詢完全匹配，符合這種查詢重寫類型的查詢數量很少。為了進行更通用的匹配，優化器會嘗試使用各種規則構造一個等價表達式改寫查詢。

查詢改寫檢查包含兩個步驟，改寫匹配檢查和構建等價表達式。一個查詢能被視圖回答需要滿足下面兩個條件：

物化視圖Join關系在查詢中存在物化視圖有足夠的數據來回答查詢

部分條件下即使不滿足條件，視圖也可能會被用于改寫。例如視圖包含一部分查詢所需要的數據，可以使用物化視圖回答部分查詢，剩下的數據從原始數據中計算。這部分改寫檢查會放在高級改寫規則中進行介紹。

具體來說改寫檢查會依次進行Join檢查和Ouput檢查，如果查詢或視圖中含有GroupingBy和Aggregation，還會進行額外的檢查，如果需要，會嘗試對視圖進一步聚合。

Join檢查

當查詢和視圖的表的Join關系相同時，視圖才可能包含查詢需要的所有的行和列。一種簡單的方式是只考慮沒有子查詢的InnerJoin，這時只用比較查詢表和數量是否完全一致即可。或者通過一系列規則檢查查詢和視圖的關系代數樹包含的Join關系是等價的。更通用的一種***是構建JoinGraph。JoinGrpah是一個以關系為結點，聯接為邊的圖。InnerJoin的條件表示為無向邊，OuterJoin的條件表示為有向邊。JoinGraph由查詢關系代數樹構建而來，通過比較JoinGraph就可以檢查物化視圖和查詢包含相同的Join關系。

例如對于下面的查詢

selectc_custkey,c_name,l_orderkey,l_partkey,l_quantityfrom(selectl_orderkey,l_partkey,l_quantityfromlineitemwherel_orderkey<1000andl_shipdate=l_commitdate)subqueryjoinordersonsubquery.l_orderkey=o_orderkeyleftjoincustomerono_custkey=c_custkey

對于物化視圖

creatematerializedviewmview1enablequeryrewriteasselect*fromlineitemjoincustomerOnsubquery.l_orderkey=o_orderkeyleftouterjoinordersOno_custkey=c_custkey

查詢和物化視圖具有相同的Join關系，查詢可以被改寫

selectc_custkey,c_name,l_orderkey,l_partkey,l_quantityfrommview1wherel_orderkey<1000andl_shipdate=l_commitdate

Output檢查

Ouput檢查保證物化視圖有足夠的數據回答查詢，這包括3個步驟：

驗證查詢所有輸出需要的列能夠從視圖中計算出來優化器需要檢查視圖包含查詢所有需要的行數，也就是視圖的謂詞的范圍大于查詢的范圍補償謂詞能否從視圖中計算得來

等價關系

查詢改寫能夠通過查詢中的等價關系擴展改寫的范圍。因為等值條件具有傳遞性，等價關系可以從等值條件或者代數關系推導而來。例如可以從A=date_format(now(),'%Y%m%D')和B=date_format(now(),'%Y%m%D')，因為函數是確定性的，可以得到A=B，如果我們還有innerjoin的條件B=C，可以進一步得到A=B=C。

可能會有某些其他的條件可以推導出等價關系，例如可以從A=2，B=3，C=5推導出C=A+B。相比等值關系，尋找這種關系會使搜索過程更加復雜，而且我們無法實現所有的可能的相等關系，因此很少考慮這樣的表達式。等價關系推導只搜索等值條件，即使可能錯過一些改寫機會，這樣的淺層搜索可以保證速度。

表達式檢查

為了確保查詢輸出的列和補償謂詞需要的列都能從視圖中計算出來，我們需要一種***確定來自查詢的表達式是否和視圖中的表達式相等，或者能從中計算出來。表達式檢查無法純粹從語法上實現，兩個表達式或者符號的文本相同，并不說明他們關系相等。例如別名的存在就會破壞基于語法的檢查。

表達式檢查需要通過等價關系和表的對應關系推導而來。如果視圖和查詢中所有的表都是唯一的，那么來自同一個表的列是等價的；如果視圖和查詢中有表出現多次，即selfjoin，那么查詢到視圖的表的映射就存在多種可能，每種可能都需要進行一次改寫嘗試。有了視圖和查詢之間列的對應關系和上一節的等價關系，通過代數系統確定來自查詢的表達式是否和視圖中的表達式相等，或者能否從中計算出來。

存在一些啟發式的規則，允許一個表達式從另外的表達式中計算出來。比如算數規則從x+1中計算出x，例如SUM(x)和COUNT(x)計算出AVG(x)，還存在一些FunctionDependency規則，例如時間函數，可以通過返回的天的結果計算年等。

謂詞檢查

視圖改寫需要物化視圖中存在查詢所有需要的行數，即視圖的謂詞的范圍大于或等于查詢的范圍。使用Wq表示查詢的謂詞，Wv表示視圖的謂詞，我們需要檢查Wq=>Wv，其中=>表示Wq滿足Wv的含義。

優化器提取所有的謂詞，并將他們轉換為CNF的形式，即W=P1^P2^...^Pn。將謂詞按照等值謂詞，范圍謂詞和剩余謂詞進一步分為W=PE^PR^PU。PE，PR，PU分別代表等值謂詞，范圍謂詞和剩余謂詞。謂詞檢查變成了PEq^PRq^PUq=>PEv^PRv^PUv，由于正交的性質，最終將問題分解成PEq=>PEv，PEq^PRq=>PRv，PEq^PUq=>PUv三類檢查。

查詢的等值謂詞用于推導等價關系。查詢中任何視圖不滿足等價關系的謂詞都構成補償謂詞，視圖中存在查詢無法滿足的等價關系則無法改寫。

范圍謂詞在優化器中可以存儲為范圍的形式，可以方便的計算差集。對于查詢中每一個范圍謂詞，如果視圖存在對應的范圍精準匹配，不需要進行補償，否則視圖范圍必須大于查詢的范圍，并通過差集構造一個補償謂詞。

查詢表達式和試圖剩余的謂詞共同構成剩余謂詞PE，只能進行精準匹配。查詢中任何與視圖不匹配的謂詞都構成補償謂詞。查詢與視圖不匹配則無法改寫。

所有的補償謂詞都需要通過表達式檢查，確保可以從視圖的輸出中計算出來。

例如查詢

selectl_orderkey,o_custkey,l_partkey,l_quantity*l_extendedpricefromlineitem,orders,partwherel_orderkey=o_orderkeyandl_partkey=p_partkeyandl_partkey>=150andl_partkey<=160ando_custkey=123ando_orderdate=l_shipdateandp_namelike‘%abc%’andl_quantity*l_extendedprice>100

物化視圖

creatematerializedviewmview2EnableQueryRewriteasselectl_orderkey,o_custkey,l_partkey,l_shipdate,o_orderdate,l_quantity*l_extendedpriceasgross_revenuefromlineitem,orders,partwherel_orderkey=o_orderkeyandl_partkey=p_partkeyandp_partkey>=150ando_custkey>=50ando_custkey<=500andp_namelike‘%abc%’

查詢可以被改寫為

selectl_orderkey,o_custkey,l_partkey,gross_revenuefrommview2wherel_partkey<=160ando_custkey=123ando_orderdate=l_shipdateandgross_revenue>100

Grouping和Aggregation檢查

如果視圖和查詢帶有GroupBy或Aggregation函數，需要進行額外檢查：

檢查查詢請求的數據分組是否與物化視圖中存儲的數據分組相同，如果不同，優化器會嘗試對物化視圖進行匯總。如果需要進一步匯總計算，所有需要的列的都可以從視圖輸出中計算出來。

例如查詢

selectc_nationkey,sum(l_quantity*l_extendedprice)fromlineitem,orders,customerwherel_orderkey=o_orderkeyando_custkey=c_custkeygroupbyc_nationkey

物化視圖

creatematerializedviewmview3enableQueryrewriteasselecto_custkey,count_big(*)ascnt,sum(l_quantity*l_extendedprice)asrevenuefromlineitem,orderswherel_orderkey=o_orderkeygroupbyo_custkey

查詢可以被改寫為

selectc_nationkey,sum(revenue)fromcustomerjoinmview3onc_custkey=o_custkeygroupbyc_nationkey

如果分組列表不同，只能改寫GroupBy在查詢最外部的情況，否則無法進行進一步聚合，無法滿足第二個改寫要求。只有特定的聚合函數支持進一步聚合，常見的聚合函數有MIN，MAX，SUM，COUNT。

例如如下查詢

selecto_custkey,count(*)ascnt,sum(l_quantity*l_extendedprice)asrevenuefromlineitem,orderswherel_orderkey=o_orderkeygroupbyo_custkey

物化視圖

creatematerializedviewmview4enableQueryrewriteasselecto_custkey,l_partkey,count(*)ascnt,sum(l_quantity*l_extendedprice)asrevenuefromlineitem,orderswherel_orderkey=o_orderkeygroupbyo_custkey,l_partkey

可以被改寫為

selectc_nationkey,sum(cnt)ascnt,sum(revenue)asrevenuefrommview4wherec_custkey=o_custkeygroupbyo_custkey

如果聚合函數在視圖中不存在，可以通過一些規則進行計算，例如從SUM(x)和COUNT(x)計算出AVG(x)，從SUM(x)+SUM(y)中計算出SUM(x+y)，這些依賴表達式改寫檢查中啟發式的規則。

高級改寫規則

如果物化視圖和查詢不滿足上一節的改寫規則，還可以通過其他規則進行轉換。

Join補償

如果只考慮InnerJoin，視圖和查詢的Join關系不一致有兩種情況：查詢比視圖包含更多的聯接，或者視圖包含更多的聯接。

如果查詢比視圖包含更多的表，我們可以簡單把缺少的Join添加在視圖之上，使其滿足改寫要求。Join條件會通過謂詞改寫正確的添加進來，優化器也可以通過后續規則調整計劃。

Join補償使優化器可以更早的進行匹配改寫，減少改寫的嘗試次數。

例如如下查詢

selectc_custkey,c_name,l_orderkey,l_partkey,l_quantityFromlineitem,customer,ordersWherel_orderkey=o_orderkeyAndo_custkey=c_custkeyWherel_orderkeybetween1000and1500Andl_shipdate=l_commitdate

物化視圖

Creatematerializedviewmview5EnablequeryrewriteasSelectl_orderkey,l_partkey,l_quantityFromlineitem,ordersWherel_orderkey=o_orderkeyAndo_orderkey>=500

可以被改寫為

Selectl_orderkey,l_partkey,l_quantityFrommview5joincustomerono_custkey=c_custkeyWherel_orderkeybetween1000and1500Andl_shipdate=l_commitdate

Join消除

如果一個Join出現在視圖中但是沒有出現在查詢中，可以嘗試使用Join消除規則。Join消除是優化器優化中的一項常見***，如果Join滿足以下5個條件，則表T1在與表T2的聯接中時不變的：

聯接條件是一個簡單的等值條件T1.fk是T2.pk的外鍵T1.fk滿足非null約束T2沒有任何的謂詞T2在與T1以外的表的聯接是不變的

這意味著表T1在與T2的Join關系不會影響T1的結果，視圖中的T2可以在JoinGraph中忽略。不變聯接的存在允許在基礎物化視圖上創建更大的并集或超集，從而允許物化視圖包含更大的預計算，也可以改寫更多的查詢。

例如查詢

Selectl_orderkey,l_partkey,l_quantityFromlineitemWherel_orderkeybetween1000and1500Andl_shipdate=l_commitdate

物化視圖

Creatematerializedviewmview6EnablequeryrewriteasSelectc_custkey,c_name,l_orderkey,l_partkey,l_quantityFromlineitem,orders,customerWherel_orderkey=o_orderkeyAndo_custkey=c_custkeyAndo_orderkey>=500

可以被改寫成

selectl_orderkey,l_partkey,l_quantityfrommview6wherel_orderkeybetween1000and1500andl_shipdate=l_commitdate

Join派生

如果存在OuterJoin，視圖和查詢Join關系不一致，可以嘗試利用Join派生性，從物化視圖中的聯接重新計算查詢中的聯接。例如，能從物化視圖中的leftOuterJoin的結果里，計算InnerJoin，AntiJoin的結果，InnerJoin又能進一步計算SemiJoin，這樣就能使用物化視圖過濾某些行來回答不同具有不同Join關系的查詢。

Join派生可以擴展改寫的范圍，允許優化器將基于物化視圖的改寫與解關聯的規則規則結合，改寫帶有IN，EXISTS等的查詢，也可以避免其他優化規則對Join的調整，例如EliminateOuterJoin和PredicatePushDown可能會將outerjoin優化成innerjoin。

Union改寫

物化視圖只包含一部分查詢所需的數據，也可以用于查詢改寫。在很多場景下，物化視圖不會也無法存儲全部的數據。

一個典型的情況是，數據在不斷的寫入，但是寫入只發生在最近一段時間內。在持續刷新的表上構建全量物化視圖，這可能導致因為數據插入視圖頻繁刷新，產生高昂的刷新成本，甚至視圖因為持續刷新而完全不可用。更好的做法是構建一個T+1條件刷新的物化視圖，存儲不變的數據，可以降低刷新成本。

另一種常見的情況是，數據倉庫存儲全量的數據，而查詢集中在最近幾個月的數據，構建全部數據的物化視圖成本過于高昂，物化視圖只構建最近幾個月數據，也能改寫絕大多數查詢。

Union改寫會嘗試使用視圖回答部分查詢，減少查詢中實時計算的數據量。Union改寫可以進一步應用Aggregation改寫，支持使用物化視圖部分數據回答聚合查詢。

例如查詢

selectl_orderkey,l_partkey,l_quantityfromlineitemwherel_orderkeyl_orderkey>500andl_orderkey<=1500andl_shipdate=l_commitdate

物化視圖

creatematerializedviewmview8enablequeryrewriteasselectl_orderkey,l_partkey,l_quantityfromlineitemwherel_orderkey>1000andl_shipdate=l_commitdate

改寫結果

selectl_orderkey,l_partkey,l_quantityfromlineitemwherel_orderkey>500andl_orderkey<=1000andl_shipdate=l_commitdateunionselecto.shippriorityfrommview8wherel_orderkey>1000andl_orderkey<=1500查詢改寫的實現

視圖改寫通常有三種查詢改寫的實現方式：

基于語法的改寫基于規則的改寫基于結構的改寫

基于語法的改寫

文本匹配或者語法匹配是最簡單的改寫***，將查詢的文本與物化視圖的文本或語法樹進行比較，完全匹配可以進行改寫。這種改寫只能匹配完整的查詢語句或子語句，細微的變化就會導致查詢無法改寫，適用的范圍很小。基于語法的改寫雖然簡單，但是效率很高，改寫的成本可以忽略不計。

基于規則的改寫

基于規則的改寫和其他優化器規則相同，針對不同Pattern的查詢和視圖編寫不同的規則，尋找等價的替代關系樹。

最簡單的一條規則就是直接比較子查詢和視圖的計劃，如果相同就能改寫。高級的改寫規則不需要物化視圖等同于被替換的計劃，會嘗試計算補償謂詞，構建等價查詢表達式。例如Join改寫，比較Join查詢的子表達式是否和視圖Join的某個子表達相同或者能否從中計算出來，每一個Join子表達式都存在映射關系，最后檢查補償表達式能否從視圖中計算得到。

基于規則的改寫可以實現大量重寫，實現也比較簡單，改寫匹配速度快，但是也存在局限性。這種改寫依賴轉換規則來尋找等價關系，因此需要窮舉所有可能的轉換關系來實現復雜視圖的重寫。一些復雜的視圖不可能窮舉所有的等價關系，例如存在很多的Join聯接或者復雜的Project關系，基于規則的改寫適用的范圍取決于規則的數量。

基于結構的改寫

基于結構的改寫與基于規則的改寫相反，通過提取查詢中的特征，使用一套規則進行匹配改寫。優化器將查詢表示為SPJG標準形式(Join-Select-Project-GroupBy)，提取查詢中的Join，Projects，Filters，Grouping和Aggregations五種表達式，分別與物化視圖對應的表達式進行匹配和改寫。

這個***是由微軟在2001年SIGMOD論文《Optimizingqueriesusingmaterializedviews:Apractical,scalablesolution》系統化的提出。這種***可以改寫包含可以改寫包含Join，Filter，Project的任意查詢的***，運用一系列的步驟匹配并得到補償表達式。還可以進一步改寫含有Aggreagtion的查詢，在需要時添加Aggregation節點返回進一步匯總的結果。

基于結構的改寫很容易擴展，例如改寫OuterJoin和子查詢等，可以完成幾乎全部的改寫。但是搜索成本較高，尤其是在查詢復雜，改寫嘗試次數很多的情況下。

參考資料

GoldsteinJ,LarsonP?.Optimizingqueriesusingmaterializedviews:apractical,scalablesolution[J].ACMSIGMODRecord,2001,30(2):331-342.BelloRG,DiasK,DowningA,etal.MaterializedviewsinOracle[C]//VLDB.1998,98:24-27.ZhouJ,LarsonPA,GoldsteinJ,etal.Dynamicmaterializedviews[C]//2007IEEE23rdInternationalConferenceonDataEngineering.IEEE,2007:526-535.JindalA,QiaoS,PatelH,etal.Computationreusein***yticsjobserviceatmicrosoft[C]//Proceedingsofthe2018InternationalConferenceonManagementofData.2018:191-203.Calcite:MaterializedView.Oracle:DatabaseDataWarehousingGuide:AdvancedQueryRewriteforMaterializedViews.Redshift:Automaticqueryrewritingtousematerializedviews.Snowflake:CreatingandWorkingWithMaterializedViews.

作者：阿里云數據庫OLAP產品部云曦

本文為阿里云原創內容，未經允許不得轉載。