calcite物化視圖詳解
- 2022 年 3 月 20 日
- 筆記
- java/scala, 大數據計算
概述
物化視圖和視圖類似，反映的是某個查詢的結果，但是和視圖僅保存SQL定義不同，物化視圖本身會存儲數據，因此是物化了的視圖。
當用戶查詢的時候，原先創建的物化視圖會註冊到優化器中，用戶的查詢命中物化視圖後，會直接去物化視圖拿數據（緩存），提高運行速度，是典型的空間換時間。
本篇文章會先介紹《Optimizing Queries Using Materialized Views: A Practical, Scalable Solution》如果改寫物化視圖，接下來會說明 calcite 的物化視圖改寫邏輯。
物化視圖有三個需要解決的問題：
- View design: determining what views to materialize, including how to store and index them.
第一個問題，是要選擇哪些數據需要進行物化，這個通常是由用戶自己決定的，我們能做的就是收集用戶的統計信息，展示高頻的表信息，查詢謂詞或者子查詢，輔助用戶判斷哪些數據需要物化。
另外 calcite 也有一個 Lattices 的功能，可以自動收集統計星型模型和雪花模型的表，自動構建部分 cube 的物化視圖。
- View maintenance: efficiently updating materialized views when base tables are updated.
第二個問題，當原始表更新後，如果更新物化視圖表。
當原始表增加數據或更新數據後，是直接增量更新到物化視圖，還是全量更新到物化視圖，實時觸發還是延遲觸發抑或是定時觸發，這些都是需要考慮的點。
- View exploitation: making efficient use of materialized views to speed up query processing.
如果利用物化視圖進行加速，主要是對用戶查詢進行改寫，使查詢命中物化視圖然後進行改寫。
主要有三種改寫方法，基於語法的改寫，基於規則的改寫 ，基於結構的改寫。
這裡只介紹論文中的基於結構的改寫算法，對其他幾種有興趣的同學可以看看阿里的這篇：一文詳解物化視圖改寫 。
物化視圖重寫算法
《Optimizing Queries Using Materialized Views: A Practical, Scalable Solution》 一文介紹了一種物化視圖重寫算法，Calcite 有一種 SPJG 重寫算法，正式基於這篇 paper 實現的。
這篇論文，主要介紹了一種 SPJG視圖（即 Join-Select-Project-GroupBy 視圖） rewrite 的方法，即前面提到的基於結構的改寫算法。
基於結構的改寫算法，會提取查詢和物化視圖的各項結構信息，包括，表，列信息，謂詞信息，表達式等等，然後用一個算法這些結構信息進行驗證，物化視圖補償等等操作，最終完成改寫。
join-select-project (SPJ) views and queries 改寫
物化視圖能夠被用戶查詢改寫的先決條件：
- equivalence classes （等價類，即 SQL 相等的列，是後續做進一步判斷的基礎）
- The view contains all rows needed by the query expression.（ 物化視圖 view 包含的行，需要覆蓋用戶 query 查詢所需要的行。）
- All required rows can be selected from the view.（ 用戶 query 需要的數據，都能夠在 view 中查詢得到。）
- Can output expressions be computed （query sql 中的表達式都能過被 view 計算出來）
- Do rows occur with correct duplication factor（有相同的重複語義，比如 distinct）
接下來，將說明前面的幾種先決條件判斷方法。
等價類（equivalence classes）
等價類（equivalence classes），即一組等價的列的集合 ，是基於等價謂詞求出來的。如果在一條 SQL 中，兩個列包含在一個等價類中，那麼就說明這兩個列在這一條 SQL 中是完全等價的。
另外等價類可以基於傳遞性，判斷兩個列等價，例如 A=date_format(now(), ‘%Y%m%D’) 和 B=date_format(now(), ‘%Y%m%D’)，因為函數是確定性的，可以得到 A=B，如果我們還有 inner join 的條件 B=C，可以進一步得到 A=B=C。
根據 calcite 的代碼，equivalence classes 的計算方式，是通過計算所有的等價謂詞信息 ，將所有相等的 columns 按照 HashMap<column ,Set
根據等價類的特性，物化視圖 view 中一些缺失的列可以通過等價類獲得等價的列作為替代。
條件1 ： The view contains all rows needed by the query expression
為什麼
為什麼需要判斷物化視圖 view 包含的行，覆蓋用戶 query 查詢所需要的行，這裡舉個簡單的例子：
//物化視圖
CREATE MATERIALIZED VIEW mv1 AS
SELECT column1,column2,column3,column4
FROM test1
WHERE column1=column2
AND column3=column4;
//用戶查詢
SELECT column1,column2,column3,column4
FROM test1
WHERE column1=column2;
這裡物化視圖的條件為 column1=column2 & column3=column4，而用戶 query 的條件為 column1=column2。物化視圖多了一個謂詞條件column3=column4，那麼物化視圖的 SQL 查詢結果數據大概率是比用戶 query 的數據少的，所以用戶查詢無法將自身改寫成這個物化視圖。
如果驗證條件
令Wq表示查詢表達式的謂詞，而Wv表示視圖表達式的謂詞。我們只要確定， (select * from T1,T2,…,Tm where Wq) 和(select * from T1,T2, …,Tm where Wv) 的情況下，Wq是 Wv的子集。即我們需要確定Wq⇒Wv是否成立。
然後我們對 Wq 和 Wv 進行拆解，將謂詞重寫為Wq = Pq1 ∧ Pq2 ∧…∧Pqm ，和Wv = Pv1∧Pv2 ∧…∧ Pvn。
paper 設計一種算法來對 sql 進行匹配，將所有的謂詞分為三種，等價謂詞 PE，範圍謂詞 PN，剩餘謂詞PU。
公式 (A⇒C) ⇒ (AB⇒C) 對任意謂詞 A、B、C 成立。換句話說，如果我們能推導出 A 本身包含 C 那麼肯定 A 和 B 一起就包含 C 。為了確定查詢所需的所有行是否存在於視圖中，我們可以應用以下三個測試：
(PEq ⇒ PEv ) (Equijoin subsumption test)
(PEq∧ PRq ⇒ PRv) (Range subsumption test)
(PEq ∧PUq ⇒ PUv ) (Residual subsumption test)
Equijoin subsumption test（等價包含測試）
Equijoin subsumption test 要求視圖中所有相等的列在查詢中也必須相等（反之則不然，因為用戶 query 可以補償到物化視圖中）。通過為用戶查詢 query 和物化視圖計算列等價類來實現此測試，假設視圖包含（A=B 和 B=C），查詢包含（A=C 和 C=B）。
- 用戶 query 的等價類為：<A , B , C>
- 物化視圖等價類為：<A , C , B>
即使實際的謂詞不匹配，它們在邏輯上也是等價的，因為它們都暗示 A=B=C。這一點將等價類摘出來就可以很清楚得觀測到。 即通過使用等價類可以正確捕獲傳遞性的影響。
另外如果用戶 query 包含更多的條件，比如多一個 C=D ，這個條件在最後的改寫過程中，也可以加到物化視圖中，這個謂詞就稱為補償謂詞（即物化視圖沒有，補償給物化視圖）。
Range subsumption test（範圍謂詞包含測試）
範圍包含測試有一個簡單的算法。 將查詢中的每個等價類與一個範圍相關聯，該範圍指定了等價類中列的下限和上限， 兩個邊界最初都未初始化。
然後我們一一考慮範圍謂詞，找到包含引用列的等價類，並根據需要設置或調整其範圍。 如果謂詞是 (Ti.Cp <= c) 類型，我們將上限設置為其當前值和 c 的最小值。 如果是 (Ti.Cp >= c) 類型，我們將上限設置為其當前值和 c 的最大值。 (Ti.Cp < c) 形式的謂詞被視為 (Ti.Cp <= c-Δ)，其中 c-Δ 表示列 Ti.Cp 的域中 c 之前的最小值。 (Ti.Cp > c) 形式的謂詞被視為 (Ti.Cp <= c+Δ)。 最後，形如 (Ti.Cp = c) 的謂詞被視為 (Ti.Cp >= c)∧ (Ti.Cp <= c)。 對視圖重複相同的過程。
舉個簡單的例子：
//物化視圖
CREATE MATERIALIZED VIEW mv1 AS
SELECT column1,column2,column3,column4,column5
FROM test1
WHERE column3 > 10;
//查詢
SELECT column1,column2,column3,column4,column5
FROM test1
WHERE column3 > 50;
- 物化視圖範圍謂詞：{column3 } ∈ (10, +∞)
- 用戶查詢謂詞：{column3 } ∈ (50, +∞)
query 中的範圍謂詞在物化視圖的範圍之內，在最終改寫中，需要將 column3 > 50 這個條件作為補償謂詞加到物化視圖中。
Residual subsumption test（剩餘謂詞包含測試）
剩餘謂詞就是出去上面兩種謂詞後，剩下的謂詞（比如 a like “str”），只能通過精確匹配，判斷用戶 query 和物化視圖是否屬於同一種類型的謂詞 & 有相同的值，確定它們是否包含。
條件2 ： All required rows can be selected from the view
經過調解1 的驗證，就可以確定用戶查詢的謂詞，包含物化視圖的謂詞，接下來要確保補償謂詞能夠在物化視圖執行。
三種補償謂詞為：
- 比較物化視圖和用戶 query 等價類時獲得的列等價謂詞。 比如謂詞：(o_orderdate = l_shipdate)。
- 根據物化視圖範圍謂詞，檢查用戶 query 範圍謂詞時獲得的範圍謂詞。 比如謂詞： ({p_partkey, l_partkey} <= 160) 。
- 查詢中不匹配的剩餘謂詞。 比如謂詞：(l_quantity*l_extendedprice > 100)。
要使條件2 驗證通過：
- 將視圖等價類與查詢等價類進行比較時構造補償列等價謂詞。 嘗試將每個列引用映射到物化視圖輸出列（通過視圖等價類），若映射失敗，則改寫失敗。
- 通過比較列範圍來構造補償範圍謂詞。 嘗試將每個列引用映射到物化視圖的輸出列（使用查詢等價類）。 若映射失敗，則改寫失敗。
- 查找物化視圖中缺少的 query 的剩餘謂詞。 嘗試將每個列引用映射到物化視圖輸出列（使用查詢等價類）。 若映射失敗，則改寫失敗。
條件3 ： Can output expressions be computed
檢查是否可以從視圖中計算查詢的所有輸出表達式，即檢查附加謂詞是否可以正確計算。
如果輸出表達式是常量，則只需將常量複製到輸出中即可。 如果輸出表達式是簡單的列引用，需要檢查是否可以將其映射（使用查詢等效類）到視圖的輸出列。
對於其他表達式，我們首先檢查視圖輸出是否包含完全相同的表達式（考慮到列的等效性）。如果是這樣，則僅將輸出表達式替換為對匹配視圖輸出列的引用。 如果不是，我們將檢查表達式的源列是否可以全部映射到視圖輸出列，即是否可以從（簡單）輸出列中計算出完整的表達式。
條件 4 ：Do rows occur with correct duplication factor?
這個點比較直觀，不細說。
rewrite
如果完成了前面提到的物化視圖 rewrite 判斷，以及謂詞補償，那進行重寫其實就比較簡單了，直接生成新的 logical plan 節點然後替換就可以了。
這部分通常是做到 CBO 優化器中，一條 sql 可以被多個物化視圖改寫，甚至可以被一個物化視圖改寫多次，在 CBO 優化器中可以利用其特性，根據 COST 模型找出最佳 plan。
故重點是如果判斷物化視圖 view 的邏輯計劃能否進行 rewrite ，是否進行補償。
舉例
例1
創建視圖：
Create view V2 with schemabinding as
Select l_orderkey, o_custkey, l_partkey,
l_shipdate, o_orderdate,
l_quantity*l_extendedprice as gross_revenue
From dbo.lineitem, dbo.orders, dbo.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%』
用戶 Query：
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
Step 1: 計算等價類
- View equivalence classes: {l_orderkey, o_orderkey}, {l_partkey, p_partkey}, {o_orderdate}, {l_shipdate}
- Query equivalence classes: {l_orderkey, o_orderkey}, {l_partkey, p_partkey}, {o_orderdate, l_shipdate}
Step 2: 檢查 View 等價類
這裡 view 相比 query ，少了 {o_orderdate, l_shipdate}，所以後續需要加上這個等價謂詞。
Step 3 : 計算範圍謂詞
- View ranges: {l_partkey, p_partkey} ∈ (150, +∞), {o_custkey} ∈ (50, 500)
- Query ranges: {l_partkey, p_partkey} ∈ (150, 160), {o_custkey} ∈ (123, 123)
Step 4 : 計算 Query 範圍謂詞
Query 中 {l_partkey, p_partkey} 的範圍 (150, 160) 在相應的 View 相關謂詞的範圍內，但上限不匹配，因此我們必須在 View 中添加補償謂詞 ({l_partkey, p_partkey} <= 160)。 {o_custkey} 上的範圍 (123, 123) 在 View 也在相應的視圖謂詞的範圍內，但邊界不匹配，因此我們必須添加補償謂詞 (o_custkey >= 123) 和 (o_custkey <= 123)，可以簡化為 (o_custkey = 123)。
Step 5 : 計算 View 剩餘謂詞
- View residual predicate: p_name like 『%abc%』
- Query residual predicate: p_name like 『%abc%』, l_quantity*l_extendedprice > 100
該 View只有一個剩餘謂詞 p_name like 『%abc%』，它也存在於 Query 中。 必須添加補償額外的剩餘謂詞 l_quantity*l_extendedprice > 100。
該視圖通過了所有測試，因此我們得出結論，它包含所有必需的行。 必須添加的補償謂詞是 (o_orderdate = l_shipdate)、({p_partkey, l_partkey} <= 160)、(o_custkey = 123) 和 (l_quantity*l_extendedprice > 100.00)。
Calcite 物化視圖實現
前面提到物化視圖的三個問題：
- 哪些數據需要被物化
- 如何保持原始表與物化表的同步關係
- 如何進行改寫
這裡主要是看 calcite 如果進行改寫。那麼衍生出兩個問題：
- 物化視圖如何被定義 & 註冊
- 物化視圖改寫流程
兩種改寫算法
Calcite 有兩種物化視圖 rewrite 的實現，一種是 SubstitutionVisitor 及其擴展 MaterializedViewSubstitutionVisitor（使用的 rule 是 unifyrule系列規則），另一種則是MaterializedViewRule。
- SubstitutionVisitor: based on pattern, and bottom-up visit.
- MaterializedViewRule: analyze semantics with relnode, such as SPJA
SubstitutionVisitor 的優勢和缺陷：
- 輕鬆擴展：可以方便新建一個自定義模式來匹配並使用 mv 重寫查詢的計劃。
- 支持out join
- 不止 ‘SPJA’ ：SubstitutionVisitor支持更多模式，如：Sort。
缺陷：
- 不支持 JOIN 補償，這在
MaterializedViewRule中實現 - 受join順序影響，eg：query(a join b), mv(b join a)
第二種MaterializedViewRule，實現並拓展自 [GL01] 所述算法，其實現方式提取 query 的relnode結構（謂詞信息，列信息等），然後進行驗證，構建補償謂詞並完成重寫，這是一種更加先進的方式，但目前其適用範圍比 SubstitutionVisitor更窄，比如join 類型必須為 inner-join。
第一種SubstitutionVisitor 重寫，在 calcite 基本快要被廢棄了，這裡主要介紹 MaterializedViewRule的主要實現方式，即前面介紹的算法。
calcite 物化視圖原理
MV 是怎麼註冊的
在 model json 文件中，可以配置 Materize View SQL，然後 Calcite 會將 MV 的 SQL 解析成 RelNode 而後存儲到 VolcanoPlanner#materializations 字段中。
每次執行的時候，並不會直接循環所有緩存中的物化視圖，而是會通過VolcanoPlanner#registerMaterializations() 找出被命中的物化視圖，然後進一步判斷是否該寫。
protected void registerMaterializations() {
// Avoid using materializations while populating materializations!
final CalciteConnectionConfig config =
context.unwrap(CalciteConnectionConfig.class);
if (config == null || !config.materializationsEnabled()) {
return;
}
// Register rels using materialized views.
//通過 `SubstitutionVisitor` ，獲取可能進行重寫的物化視圖
final List<Pair<RelNode, List<RelOptMaterialization>>> materializationUses =
RelOptMaterializations.useMaterializedViews(originalRoot, materializations);
for (Pair<RelNode, List<RelOptMaterialization>> use : materializationUses) {
RelNode rel = use.left;
Hook.SUB.run(rel);
registerImpl(rel, root.set);
}
//通過 table 引用構建的圖算法，計算剩餘可能被重寫的物化視圖
// Register table rels of materialized views that cannot find a substitution
// in root rel transformation but can potentially be useful.
final Set<RelOptMaterialization> applicableMaterializations =
new HashSet<>(
RelOptMaterializations.getApplicableMaterializations(
originalRoot, materializations));
for (Pair<RelNode, List<RelOptMaterialization>> use : materializationUses) {
applicableMaterializations.removeAll(use.right);
}
for (RelOptMaterialization materialization : applicableMaterializations) {
RelSubset subset = registerImpl(materialization.queryRel, null);
RelNode tableRel2 =
RelOptUtil.createCastRel(
materialization.tableRel,
materialization.queryRel.getRowType(),
true);
registerImpl(tableRel2, subset.set);
}
// Register rels using lattices.
//通過 lattices 計算物化視圖
final List<Pair<RelNode, RelOptLattice>> latticeUses =
RelOptMaterializations.useLattices(
originalRoot, ImmutableList.copyOf(latticeByName.values()));
if (!latticeUses.isEmpty()) {
RelNode rel = latticeUses.get(0).left;
Hook.SUB.run(rel);
registerImpl(rel, root.set);
}
}
計算物化視圖和用戶 query 表引用計算
這裡的條件基本就一個：物化視圖至少包含一個 Query 的表引用。
表引用情況有三種：
- 全匹配
- 物化視圖的表引用是用戶 query 表引用的子集
- 用戶 query 表引用是物化視圖的表引用的子集
這三種情況都有可能進行改寫，但物化視圖至少包含一個用戶 query 的表引用。
通過 lattices 註冊
第三個是使用 lattices 進行註冊，lattices 是 Calcite 針對星型模型和雪花模型推出的一種物化視圖框架，主要可以物化星型模型中部分 cube ，能夠智能收集信息並智能決定物化哪些維度等。有點類似 kylin 的思路。
CBO 註冊邏輯（registerImpl）
上面註冊邏輯中可以看到，計算出 List<Pair<RelNode, ListregisterImpl註冊。這裡涉及到 calcite 中 rule 註冊的邏輯，Calcite 用 VolcanoPlanner 模型來進行 CBO 優化，這裡不詳細說明流程，具體情況可以看這裡：Apache Calcite 優化器詳解（二）
簡單說就是每個新的 Relnode 都會生成一個 Relset 和 RelSubset。每次新建一個 RelSubset ，都會遍歷所有可以 match 該 RelSubset 的 Rule（物化視圖改寫也是一種 rule），創建一個 VolcanoRuleMatch 對象（會記錄 RelNode、RelOptRuleOperand 等信息，RelOptRuleOperand 中又會記錄 Rule 的信息）。記錄 importance 信息並將這個 VolcanoRuleMatch 添加到對應的 RuleQueue 中。
實際進行優化的findBestExp()方法中，主要就是遍歷 RuleQueue ，實現 DP 優化算法。
第二個問題，MV 改寫是怎樣的
VolcanoPlanner CBO 優化的最後一個階段，就是通過 findBestExp() 方法找到最佳的 plan，這裡會先通過 registerMaterializations() 註冊 物化視圖相關 rule，這也就是上面說到的內容。
而實際註冊的 rule ，基本都是 AbstractMaterializedViewRule 的子類 ，這個 Rule 有多個衍生的 rule，MaterializedViewProjectFilterRule，MaterializedViewProjectJoinRule 等適配不同的 query。在上一步中，會尋找 equel 的 relnode 和 match，然後調用這些 rule 迭代 rel 信息，替換 MV 後生成新的 RelNode，完成物化視圖的 sql rewrite 過程。
觸發入口，是在每個 rule 的 onMatch() 方法中，但實際執行，是在 AbstractMaterializedViewRule#perform() 中。
/**
* Rewriting logic is based on "Optimizing Queries Using Materialized Views:
* A Practical, Scalable Solution" by Goldstein and Larson.
*
* <p>On the query side, rules matches a Project-node chain or node, where node
* is either an Aggregate or a Join. Subplan rooted at the node operator must
* be composed of one or more of the following operators: TableScan, Project,
* Filter, and Join.
*
* <p>For each join MV, we need to check the following:
* <ol>
* <li> The plan rooted at the Join operator in the view produces all rows
* needed by the plan rooted at the Join operator in the query.</li>
* <li> All columns required by compensating predicates, i.e., predicates that
* need to be enforced over the view, are available at the view output.</li>
* <li> All output expressions can be computed from the output of the view.</li>
* <li> All output rows occur with the correct duplication factor. We might
* rely on existing Unique-Key - Foreign-Key relationships to extract that
* information.</li>
* </ol>
*
* <p>In turn, for each aggregate MV, we need to check the following:
* <ol>
* <li> The plan rooted at the Aggregate operator in the view produces all rows
* needed by the plan rooted at the Aggregate operator in the query.</li>
* <li> All columns required by compensating predicates, i.e., predicates that
* need to be enforced over the view, are available at the view output.</li>
* <li> The grouping columns in the query are a subset of the grouping columns
* in the view.</li>
* <li> All columns required to perform further grouping are available in the
* view output.</li>
* <li> All columns required to compute output expressions are available in the
* view output.</li>
* </ol>
*
* <p>The rule contains multiple extensions compared to the original paper. One of
* them is the possibility of creating rewritings using Union operators, e.g., if
* the result of a query is partially contained in the materialized view.
*/
protected void perform(RelOptRuleCall call, Project topProject, RelNode node) {
final RexBuilder rexBuilder = node.getCluster().getRexBuilder();
final RelMetadataQuery mq = call.getMetadataQuery();
final RelOptPlanner planner = call.getPlanner();
final RexExecutor executor =
Util.first(planner.getExecutor(), RexUtil.EXECUTOR);
final RelOptPredicateList predicates = RelOptPredicateList.EMPTY;
final RexSimplify simplify =
new RexSimplify(rexBuilder, predicates, executor);
final List<RelOptMaterialization> materializations =
planner.getMaterializations();
//調用 `isValidPlan(topProject, node, mq)`，驗證 RelNode 是否滿足 rewrite 先覺條件，這個每個 rule 都有不同的實現，比如 join 需要通過 `RelMetadataQuery` 獲取 RelNode 的 NodeType。
if (!materializations.isEmpty()) {
// 1. Explore query plan to recognize whether preconditions to
// try to generate a rewriting are met
if (!isValidPlan(topProject, node, mq)) {
return;
}
// 2. Initialize all query related auxiliary data structures
// that will be used throughout query rewriting process
// Generate query table references
//獲取所有 table 引用，以便後續各種操作，這一步基本都是通過RelMetadataQuery獲取各種信息
final Set<RelTableRef> queryTableRefs = mq.getTableReferences(node);
if (queryTableRefs == null) {
// Bail out
return;
}
// Extract query predicates
//提取 查詢的所有謂詞，等價謂詞和剩餘謂詞
final RelOptPredicateList queryPredicateList =
mq.getAllPredicates(node);
if (queryPredicateList == null) {
// Bail out
return;
final RexNode pred =
simplify.simplifyUnknownAsFalse(
RexUtil.composeConjunction(rexBuilder,
queryPredicateList.pulledUpPredicates));
//將查詢兩種謂詞包裝成 RexNode，等價謂詞（左）和剩餘謂詞（右）
final Pair<RexNode, RexNode> queryPreds = splitPredicates(rexBuilder, pred);
// Extract query equivalence classes. An equivalence class is a set
// of columns in the query output that are known to be equal.
//提取 query 的等價類（equivalence class），equivalence class 即 query output 中，已知等價的 columns 的集合
final EquivalenceClasses qEC = new EquivalenceClasses();
//遍歷等價謂詞，並將等價謂詞的列都存起來
for (RexNode conj : RelOptUtil.conjunctions(queryPreds.left)) {
assert conj.isA(SqlKind.EQUALS);
RexCall equiCond = (RexCall) conj;
qEC.addEquivalenceClass(
(RexTableInputRef) equiCond.getOperands().get(0),
(RexTableInputRef) equiCond.getOperands().get(1));
}
// 3. We iterate through all applicable materializations trying to
// rewrite the given query
//遍歷所有給定物化視圖，並嘗試重寫，一個 relnode 可以對應多個 materialization view
for (RelOptMaterialization materialization : materializations) {
//獲取 view 的 RelNode，並提取各種基礎信息，比如所有的 RelTableRef
RelNode view = materialization.tableRel;
Project topViewProject;
RelNode viewNode;
//materialization.queryRel 表示註冊的 MV sql
//materialization.tableRel 表示註冊的 MV 的 table name relnode
//這裡找到 topViewProject
if (materialization.queryRel instanceof Project) {
topViewProject = (Project) materialization.queryRel;
viewNode = topViewProject.getInput();
} else {
topViewProject = null;
viewNode = materialization.queryRel;
}
// Extract view table references
final Set<RelTableRef> viewTableRefs = mq.getTableReferences(viewNode);
if (viewTableRefs == null) {
// Skip it
continue;
}
// Filter relevant materializations. Currently, we only check whether
// the materialization contains any table that is used by the query
//第一個過濾條件，這裡只檢查 MV 是否包含用戶 query 所要的表
// TODO: Filtering of relevant materializations can be improved to be more fine-grained.
boolean applicable = false;
for (RelTableRef tableRef : viewTableRefs) {
if (queryTableRefs.contains(tableRef)) {
applicable = true;
break;
}
}
if (!applicable) {
// Skip it
continue;
}
//跟步驟 1 一樣，不過這裡對 MV query 進行校驗（Valid）
// 3.1. View checks before proceeding
if (!isValidPlan(topViewProject, viewNode, mq)) {
// Skip it
continue;
}
// 3.2. Initialize all query related auxiliary data structures
// that will be used throughout query rewriting process
// Extract view predicates
//跟步驟 2 類似，不過這裡獲取的是 MV 的各種謂詞信息，表達式
final RelOptPredicateList viewPredicateList =
mq.getAllPredicates(viewNode);
if (viewPredicateList == null) {
// Skip it
continue;
}
final RexNode viewPred = simplify.simplifyUnknownAsFalse(
RexUtil.composeConjunction(rexBuilder,
viewPredicateList.pulledUpPredicates));
//獲取 MV 的兩種謂詞，等價謂詞（左）和剩餘謂詞（右）
final Pair<RexNode, RexNode> viewPreds = splitPredicates(rexBuilder, viewPred);
// Extract view tables
//用 view 和 query 的所有表進行匹配，有三種匹配結果
//MatchModality.COMPLETE：所有 MV view 的 tables 和 query 的 tables 都一致
//MatchModality.QUERY_PARTIAL：用戶查詢是 MV 視圖的子集 的情況，檢查 MV 和 query 是否保持相同的基數，主要是獲取所有等價謂詞，tableref 等信息，然後 compensatePartial 進行判斷
//MatchModality.VIEW_PARTIAL：MV 視圖是用戶 query 的子集，直接調用compensateViewPartial（不同 rule 有不同實現）進行重寫添加缺失的 view，重寫成功則更新 view 相關信息，後面再對 view 進行補償
MatchModality matchModality;
Multimap<RexTableInputRef, RexTableInputRef> compensationEquiColumns =
ArrayListMultimap.create();
if (!queryTableRefs.equals(viewTableRefs)) {
//進行補償
// We try to compensate, e.g., for join queries it might be
// possible to join missing tables with view to compute result.
// Two supported cases: query tables are subset of view tables (we need to
// check whether they are cardinality-preserving joins), or view tables are
// subset of query tables (add additional tables through joins if possible)
if (viewTableRefs.containsAll(queryTableRefs)) {
//通過這個來控制補償機制
matchModality = MatchModality.QUERY_PARTIAL;
//對於用戶查詢是 MV 視圖的子集 的情況，主要是獲取所有等價謂詞，tableref 等信息，然後 compensatePartial 進行判斷
final EquivalenceClasses vEC = new EquivalenceClasses();
for (RexNode conj : RelOptUtil.conjunctions(viewPreds.left)) {
assert conj.isA(SqlKind.EQUALS);
RexCall equiCond = (RexCall) conj;
vEC.addEquivalenceClass(
(RexTableInputRef) equiCond.getOperands().get(0),
(RexTableInputRef) equiCond.getOperands().get(1));
}
//確認 query 是否能夠使用 MV view 進行 rewrite
if (!compensatePartial(viewTableRefs, vEC, queryTableRefs,
compensationEquiColumns)) {
// Cannot rewrite, skip it
continue;
}
} else if (queryTableRefs.containsAll(viewTableRefs)) {
//若MV 視圖是用戶 query 的子集，直接調用compensateViewPartial（不同 rule 有不同實現）進行重寫
// 重寫目標是將 QUery 有但 view 沒有的表添加到 view 中，重寫成功則更新 view 相關信息，後續會再使用
matchModality = MatchModality.VIEW_PARTIAL;
ViewPartialRewriting partialRewritingResult = compensateViewPartial(
call.builder(), rexBuilder, mq, view,
topProject, node, queryTableRefs, qEC,
topViewProject, viewNode, viewTableRefs);
if (partialRewritingResult == null) {
// Cannot rewrite, skip it
continue;
}
// Rewrite succeeded
view = partialRewritingResult.newView;
topViewProject = partialRewritingResult.newTopViewProject;
viewNode = partialRewritingResult.newViewNode;
} else {
// Skip it
continue;
}
} else {
matchModality = MatchModality.COMPLETE;
}
// 4. We map every table in the query to a table with the same qualified
// name (all query tables are contained in the view, thus this is equivalent
// to mapping every table in the query to a view table).
//獲取 query 中所有具有相等 qualified name 的 RelTableRef，並存儲起來
final Multimap<RelTableRef, RelTableRef> multiMapTables = ArrayListMultimap.create();
for (RelTableRef queryTableRef1 : queryTableRefs) {
for (RelTableRef queryTableRef2 : queryTableRefs) {
if (queryTableRef1.getQualifiedName().equals(
queryTableRef2.getQualifiedName())) {
multiMapTables.put(queryTableRef1, queryTableRef2);
}
}
}
// If a table is used multiple times, we will create multiple mappings,
// and we will try to rewrite the query using each of the mappings.
// Then, we will try to map every source table (query) to a target
// table (view), and if we are successful, we will try to create
// compensation predicates to filter the view results further
// (if needed).
//
//如果一張表被使用多次，將對該表創建多重映射，並將重寫用戶 query 使用這些映射。
//然後嘗試將 QUERY 的 table 映射到 MV view 的 table。
//如果可以進行映射，那麼下一步將填充剩餘謂詞
final List<BiMap<RelTableRef, RelTableRef>> flatListMappings =
generateTableMappings(multiMapTables);
//遍歷 query table -> view table 的映射集合
for (BiMap<RelTableRef, RelTableRef> queryToViewTableMapping : flatListMappings) {
// TableMapping : mapping query tables -> view tables
// 4.0. If compensation equivalence classes exist, we need to add
// the mapping to the query mapping
//如果存在compensation equivalence（補償等價類），我們需要將這些加到 query mapping 中
final EquivalenceClasses currQEC = EquivalenceClasses.copy(qEC);
if (matchModality == MatchModality.QUERY_PARTIAL) {
for (Entry<RexTableInputRef, RexTableInputRef> e
: compensationEquiColumns.entries()) {
// Copy origin
RelTableRef queryTableRef = queryToViewTableMapping.inverse().get(
e.getKey().getTableRef());
RexTableInputRef queryColumnRef = RexTableInputRef.of(queryTableRef,
e.getKey().getIndex(), e.getKey().getType());
// Add to query equivalence classes and table mapping
currQEC.addEquivalenceClass(queryColumnRef, e.getValue());
queryToViewTableMapping.put(e.getValue().getTableRef(),
e.getValue().getTableRef()); // identity
}
}
// 4.1. Compute compensation predicates, i.e., predicates that need to be
// enforced over the view to retain query semantics. The resulting predicates
// are expressed using {@link RexTableInputRef} over the query.
// First, to establish relationship, we swap column references of the view
// predicates to point to query tables and compute equivalence classes.
//計算補償謂詞，生成的謂詞在查詢中使用 {@link RexTableInputRef} 表示。
final RexNode viewColumnsEquiPred = RexUtil.swapTableReferences(
rexBuilder, viewPreds.left, queryToViewTableMapping.inverse());
final EquivalenceClasses queryBasedVEC = new EquivalenceClasses();
for (RexNode conj : RelOptUtil.conjunctions(viewColumnsEquiPred)) {
assert conj.isA(SqlKind.EQUALS);
RexCall equiCond = (RexCall) conj;
queryBasedVEC.addEquivalenceClass(
(RexTableInputRef) equiCond.getOperands().get(0),
(RexTableInputRef) equiCond.getOperands().get(1));
}
//計算得到補償的等價謂詞和剩餘謂詞
// TODO : computeCompensationPredicates 是如果提取補償謂詞的
Pair<RexNode, RexNode> compensationPreds =
computeCompensationPredicates(rexBuilder, simplify,
currQEC, queryPreds, queryBasedVEC, viewPreds,
queryToViewTableMapping);
//若補償謂詞為空，並且允許 union rewrite，那麼進行 union 的改寫
if (compensationPreds == null && generateUnionRewriting) {
// Attempt partial rewriting using union operator. This rewriting
// will read some data from the view and the rest of the data from
// the query computation. The resulting predicates are expressed
// using {@link RexTableInputRef} over the view.
//嘗試加上 union operator 進行 sql rewrite
compensationPreds = computeCompensationPredicates(rexBuilder, simplify,
queryBasedVEC, viewPreds, currQEC, queryPreds,
queryToViewTableMapping.inverse());
if (compensationPreds == null) {
// This was our last chance to use the view, skip it
continue;
}
RexNode compensationColumnsEquiPred = compensationPreds.left;
RexNode otherCompensationPred = compensationPreds.right;
assert !compensationColumnsEquiPred.isAlwaysTrue()
|| !otherCompensationPred.isAlwaysTrue();
// b. Generate union branch (query).
//進行改寫，生成 union branch
final RelNode unionInputQuery = rewriteQuery(call.builder(), rexBuilder,
simplify, mq, compensationColumnsEquiPred, otherCompensationPred,
topProject, node, queryToViewTableMapping, queryBasedVEC, currQEC);
if (unionInputQuery == null) {
// Skip it
continue;
}
// c. Generate union branch (view).
// We trigger the unifying method. This method will either create a Project
// or an Aggregate operator on top of the view. It will also compute the
// output expressions for the query.
final RelNode unionInputView = rewriteView(call.builder(), rexBuilder, simplify, mq,
matchModality, true, view, topProject, node, topViewProject, viewNode,
queryToViewTableMapping, currQEC);
if (unionInputView == null) {
// Skip it
continue;
}
// d. Generate final rewriting (union).
//分別對 query 和 view 進行 rewrite，最後再處理
final RelNode result = createUnion(call.builder(), rexBuilder,
topProject, unionInputQuery, unionInputView);
if (result == null) {
// Skip it
continue;
}
call.transformTo(result);
} else if (compensationPreds != null) {
RexNode compensationColumnsEquiPred = compensationPreds.left;
RexNode otherCompensationPred = compensationPreds.right;
// a. Compute final compensation predicate.
//判斷等價補償謂詞和剩餘補償謂詞，是否都返回 true
if (!compensationColumnsEquiPred.isAlwaysTrue()
|| !otherCompensationPred.isAlwaysTrue()) {
// All columns required by compensating predicates must be contained
// in the view output (condition 2).
// 條件 2 判斷，補償謂詞所需的列都在 view 中
// 使用映射的方式，將表引用及對應列引用映射到 View 中，若返回 null 則失敗，即改寫失敗
List<RexNode> viewExprs = topViewProject == null
? extractReferences(rexBuilder, view)
: topViewProject.getChildExps();
// For compensationColumnsEquiPred, we use the view equivalence classes,
// since we want to enforce the rest
//如果等價謂詞不總為 TRUE，使用視圖等價類，因為要強制執行剩餘部分
if (!compensationColumnsEquiPred.isAlwaysTrue()) {
//這裡 rewrite 的作用，基本上就是把之前 column 的映射再轉回來
compensationColumnsEquiPred = rewriteExpression(rexBuilder, mq,
view, viewNode, viewExprs, queryToViewTableMapping.inverse(), queryBasedVEC,
false, compensationColumnsEquiPred);
if (compensationColumnsEquiPred == null) {
// Skip it
continue;
}
}
// For the rest, we use the query equivalence classes
//對於剩餘謂詞，使用 query 等價類
if (!otherCompensationPred.isAlwaysTrue()) {
otherCompensationPred = rewriteExpression(rexBuilder, mq,
view, viewNode, viewExprs, queryToViewTableMapping.inverse(), currQEC,
true, otherCompensationPred);
if (otherCompensationPred == null) {
// Skip it
continue;
}
}
}
// 合併補償的等價謂詞和剩餘謂詞，獲得最終需要在 view 上面執行的剩餘謂詞
final RexNode viewCompensationPred =
RexUtil.composeConjunction(rexBuilder,
ImmutableList.of(compensationColumnsEquiPred,
otherCompensationPred));
// b. Generate final rewriting if possible.
// First, we add the compensation predicate (if any) on top of the view.
// Then, we trigger the unifying method. This method will either create a
// Project or an Aggregate operator on top of the view. It will also compute
// the output expressions for the query.
//生成最終重寫，
//1. 添加補償謂詞到 view
//2. 調用統一方法，生成一個 project 或一個 Aggregate operator on top of view。
RelBuilder builder = call.builder().transform(c -> c.withPruneInputOfAggregate(false));
RelNode viewWithFilter;
// 如果最終的補償謂詞並非總是 true，生成 viewWithFilter 的時候需要加上 FIlter
if (!viewCompensationPred.isAlwaysTrue()) {
RexNode newPred =
simplify.simplifyUnknownAsFalse(viewCompensationPred);
viewWithFilter = builder.push(view).filter(newPred).build();
// No need to do anything if it's a leaf node.
if (viewWithFilter.getInputs().isEmpty()) {
call.transformTo(viewWithFilter);
return;
}
// We add (and push) the filter to the view plan before triggering the rewriting.
// This is useful in case some of the columns can be folded to same value after
// filter is added.
// 觸發重寫前，添加 filter 並 PUSH 到 view plan。
Pair<RelNode, RelNode> pushedNodes =
pushFilterToOriginalViewPlan(builder, topViewProject, viewNode, newPred);
topViewProject = (Project) pushedNodes.left;
viewNode = pushedNodes.right;
} else {
//如果 filter 總是 TRUE ，那麼只需要生成 view
viewWithFilter = builder.push(view).build();
}
//進行重寫，生成最終的 view
//這裡 Agg 和 Join rule 都有自己的實現，主要看 join
final RelNode result = rewriteView(builder, rexBuilder, simplify, mq, matchModality,
false, viewWithFilter, topProject, node, topViewProject, viewNode,
queryToViewTableMapping, currQEC);
if (result == null) {
// Skip it
continue;
}
call.transformTo(result);
} // end else
}
}
}
}
這種方式有以下限制：
- Aggregate 或 Join 類型的 sql ，其子查詢節點的 root ，必須為以下幾種：TableScan, Project, Filter, and Join，且僅支持 inner join 類型的 sql。
Join 類型進行改寫，條件如下：
- MV 的 logical plan 中 join operator ，需包含所有 query 中，join operator 需要的所有數據。
- 擁有補償謂詞所需的列
- 所有的輸出表達式都可以從視圖的輸出中計算出來。
- 所有輸出行都以正確的重複因子出現。
而對於 aggregate MV，需要滿足以下：
- MV 的 logical plan 中 Aggregate operator ，需包含所有 query Aggregate operator 需要的所有數據。
- 擁有補償謂詞所需的列
- 查詢中的分組列是視圖中分組列的子集。
- 視圖輸出中提供了進一步分組所需的所有列。
- 視圖輸出中提供了計算輸出表達式所需的所有列。
基本都是最上面提到的條件。
說明：
等價類：EquivalenceClasses：a set of equivalent columns
具體流程如下：
首先，對用戶 query 進行預處理，包括校驗，提取信息，構建等價類等。
- 調用
isValidPlan(topProject, node, mq)，驗證 RelNode 是否滿足 rewrite 先決定條件，這個join 和 Aggregate rule 都有不同的實現，比如 join 僅支持 relnode 節點類型：TableScan – Project – Filter – Inner Join。 - 通過 RelMetadataQuery，生成 sql rewrite 過程中，所需要的一些輔助數據（所有 table 表引用等）。提取用戶 query 的謂詞條件，分為兩部分：等價謂詞，剩餘謂詞。表引用，表達式（常量表達式，函數等）等等。
- 構建等價類
EquivalenceClasses，等價類是從等價謂詞中提取的 columns 集合
然後，遍歷 relnode 的所有物化視圖，嘗試重寫並註冊新 relnode。
-
首先，和 query 一樣，獲取物化視圖的基本信息，校驗，構建等價類。
-
嘗試計算補償謂詞，若不能則跳過視圖，根據 query 和 MV 物化視圖的 table 表引用數量，分三種情況。
- MatchModality.COMPLETE：所有 MV view 的 tables 和 query 的 tables 都一致，什麼都不做。
- MatchModality.QUERY_PARTIAL：用戶查詢 表引用是 MV 視圖的子集 的情況，檢查 MV 和 query 是否保持相同的基數（join 的情況），主要是獲取所有等價謂詞，tableref 等信息，然後 compensatePartial 進行判斷是否物化視圖能進行 review。即最上面介紹的特殊 case，需要根據唯一健，外健等約束進行判斷。
- MatchModality.VIEW_PARTIAL：MV 視圖表引用是用戶 query 的子集，會調用compensateViewPartial（不同 rule 有不同實現）檢測業務 query 能否使用 view 進行重寫，可以的話會將 Query 中多出來的表（若存在謂詞那便添加這些補償謂詞）添加到 view 中並新生成一個物化視圖（初步改寫）。
-
經過上述步驟，可以認定 Query 和 View 具有相同的表引用關係（或 view 有多的表引用但不影響）。
-
開始計算補償謂詞，需要在視圖 view 上執行補償謂詞以保證 query 語義。
- 創建 query 表引用 -> view 表引用的映射集合
List<BiMap<RelTableRef, RelTableRef>>。 - 物化視圖的等價謂詞，交換 view column 指向的 TABLE 為 QUERY 的 table ，然後再計算等價類。調用
computeCompensationPredicates計算補償謂詞，包括等價補償謂詞和剩餘補償謂詞。交換 view 的表引用，是為了方便判斷：視圖 view 的查詢條件都為 query 條件的子集。如果 view 條件不為 query 的子集，補償謂詞為空。 - 若計算得到的補償謂詞為空並且允許 union 重寫，則進行 union 重寫（最開始 union 類型是不支持改寫的，這裡是 calcite 的擴展。這部分先忽略。）
- 先進行優化，如果補償謂詞條件用 AND 相連後，結果總為 true ，類似 where 1=1，那麼省略部分操作，生成新的 view。
- 否則進行判斷，All columns required by compensating predicates must be contained in the view output（條件二） 。具體做法是將補償謂詞的列進行映射。
- 生成 view ，並將補償謂詞信息加到這個 view 中，調用統一方法，生成一個 project 或一個 Aggregate operator on top of view。最後再調用
rewriteView（不同 join 有不同實現）生成最終重寫後的 relnode，再將新的 relnode 註冊。等待後續 CBO 進一步優化。
- 創建 query 表引用 -> view 表引用的映射集合
小結
本篇文章主要介紹了物化視圖的功能，作用，以及實現過程中需要解決的三個問題。主要介紹物化視圖如何進行改寫，需要實現哪些條件等等。
然後主要說明 Calcite 如何註冊物化視圖和實現 SPJG 改寫算法。
以上～
Optimizing Queries Using Materialized Views: A Practical, Scalable Solution
