SPJA场景说明

物化识别算法分类

基于替换规则的物化识别算法

举例，Query和MV如下:

识别过程如下:

算法特点:

1. Bottom-Up Manner
2. 匹配规则只关注局部算子Pattern
3. 匹配过程简单可靠，扩展能力强（SPJA以外的复杂场景）

基于语义的物化识别算法

举例:

Query:
Filter(left.col0 > 10 and left.col0 < 99)
|--Join(inner, left.col0 = right.col0)
     |--Project(col0, col1)
   |    |--ScanA
   |
   |--ScanB

Materialized View:
Join(inner, left.col0 = right.col0)
|--Filter(left.col0 > 10)   
|  |--Project(col0, col1, col2)
|     |--ScanA
|
|--ScanC
|--ScanB

Pipeline extracted from Query:
     TableA Join TableB  
===> Filter(TableA.col0 > 10 && TableA.col0 < 99)
===> Project(TableA.col0, TableA.col1, TableB.*)

Pipeline extracted from Materialized View:
     TableA Join TableB Join TableC 
===> Filter(TableA.col0 > 10)
===> Project(TableA.col0, TableA.col1, TableA.col2, TableB.*)

Matching result:
Project(TableA.col0, TableA.col1, TableB.*)
|--Filter(TableA.col0 < 99)
   |--Scan(Materialized Veiw)

算法特点：

1. 基于关系代数语义进行匹配和物化视图补偿，整个过程更加的smart；
2. 首先与语义的表达能力，算法不能处理SPJA以外的更加复杂的执行计划；

AQE物化识别算法

难点：关系代数表达的灵活性，使得有限算子可以产生出无限种组合方式，如何将无限的表达方式归结为有限的问题集合，迭代解决。

概念

下面主要介绍在物化视图匹配过程需要掌握的一些基本概念。

1. Calc : 算子，包含Project和Filter算子，可以理解为列裁剪和行过滤。
2. Replacement ：物化视图替换物, 即在物化视图匹配后，替换mv-logical的RelNode。
3. query : 用户写的查询SQL。
4. target : 物化视图计算逻辑。

下面一个小例子先简要说明物化视图。

query = SELECT a, c FROM t WHERE x = 5 AND b = 4
target = SELECT a, b, c FROM t WHERE x = 5
replacement = SELECT * FROM mv
result = SELECT a, c FROM mv WHERE b = 4

归一化

下面举个例子,说明我们为什么做归一化处理。

  归一化规则包含: Filter和Project的算子下推，Filter和Project转换或者合并成Calc, 形成SCAN-PROJECT-JOIN-AGGREGATE关系代数表达式,简化物化识别的难度。

Bottom Up Manner

1. 匹配规则基于局部Operator pattern，实现匹配算法；
2. 自底向上，逐步将匹配过程种产生的“补偿算子”不断上推；

匹配范式主要分为以下两类：
范式一：

范式二：

关键算子匹配过程说明

物化识别通过继承AbstractUnifyRule,实现目标节点pattern的匹配规则, bottom-up,在迭代中寻找物化视图等价类的迭代过程。基于替换规则的匹配方法，其思路是不断通过匹配规则将pattern向target转化，最终将pattern转化成基于target的关系代数表达，而这个关系代数即为匹配后对target的‘补偿’。
物化识别的过程主要分为两步:

1. 归一化query和target的关系代数。
   2.物化识别规则匹配和补偿谓词条件。
   我们举例说明整个过程的工作原理：

Aggregate

query:
select deptno
from emps
where deptno > 10
group by deptno

mv:
select empid, deptno
from emps
where deptno > 5
group by empid, deptno

query和mv归一化转换后的RelNode如下所示:
query RelNode:
LogicalAggregate(group=[{0}])
  LogicalCalc(expr#0..4=[{inputs}], expr#5=[10], expr#6=[>($t1, $t5)], 
              deptno=[$t1], $condition=[$t6])
    LogicalTableScan(table=[[hr, emps]])

mv RelNode:
LogicalAggregate(group=[{0, 1}])
  LogicalCalc(expr#0..4=[{inputs}], expr#5=[5], expr#6=[>($t1, $t5)], 
              proj#0..1=[{exprs}], $condition=[$t6])
    LogicalTableScan(table=[[hr, emps]])

mv 
projects : empid, deptno  
condition : deptno > 5
query 
projects : deptno
conditon :  deptno > 10

Step3

Join

JOIN 子句用于把来自两个或多个表的行关联起来,比如事实表关联维表。Join的物化识别算法涉及到JoinOnLeftCalcToJoinUnifyRule、JoinOnRightCalcToJoinUnifyRule、JoinOnCalcsToJoinUnifyRule，我们以JoinOnLeftCalcToJoinUnifyRule的例子来说明join做物化识别的整个过程。

query:
select A.empid, A.deptno, depts.deptno 
from (select empid, deptno from emps where deptno > 10) A 
join depts
on A.deptno = depts.deptno

mv:
select emps.empid, emps.deptno, emps.name, depts.deptno 
from emps 
join depts
on emps.deptno = depts.deptno

relNode:
query:
LogicalJoin(condition=[=($1, $2)], joinType=[inner])
  LogicalCalc(expr#0..4=[{inputs}], expr#5=[10], expr#6=[>($t1, $t5)], 
              proj#0..1=[{exprs}], $condition=[$t6])
    LogicalTableScan(table=[[hr, emps]])
  LogicalCalc(expr#0..3=[{inputs}], deptno=[$t0])
    LogicalTableScan(table=[[hr, depts]])
    
target:
LogicalJoin(condition=[=($1, $3)], joinType=[inner])
  LogicalCalc(expr#0..4=[{inputs}], proj#0..2=[{exprs}])
    LogicalTableScan(table=[[hr, emps]])
  LogicalCalc(expr#0..3=[{inputs}], deptno=[$t0])
    LogicalTableScan(table=[[hr, depts]])

SPJA匹配规则集

• Query ** MV Logic**
• TableScan <-----> TableScan
• Calc <-----> Calc // same input
• Calc (extra calc) <-----> Calc
• Join <-----> Join // same input
• Join(extra left calc) <-----> Join // same right
• Join(extra right calc) <-----> Join // same left
• Join(extra left & right calcs) <-----> Join
• Aggregate <-----> Aggregate // same input
• Aggregate (extra calc) <-----> Aggregate // same input
• Union <-----> Union // same input
• Union(extra calc) <-----> Union
• Intersect <-----> Intersect // same input
• Intersect(extra calc) <-----> Intersect

What's more:

1. SPJA 以外算子的匹配，e.g. Correlate, Sort, Minus ...
2. 复杂extra-node 的匹配，e.g. compensating Aggregate ...