Calcite物化识别原理

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

归一化

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

从SQL的语义来看,通过补偿条件, empid < 20,变能够完成物化识别过程,但是结果是fail的，我们来看query和mv生成的RelNode,当去匹配project节点时,发现mv中已经有了一个filter,而此时query并没有表达出相应的过滤条件，此时会认为，mv没有包含query中的所有数据(核心原则)，那么整个物化识别过程会fail掉。如果我们能够将query中最上层的filter条件,下推到Aggregate算子之下,那么能够完成物化视图匹配。
归一化的目的在于尽可能方便的简化query和target的关系代数表达式，力图使query和target的关系代数都形成SPJA范式, 方便后续在物化识别match过程的pattern识别。

规则	说明
FilterProjectTransposeRule	将Filter算子下推到Project算子下边
FilterMergeRule	Filter算子合并
FilterJoinRule.FILTER_ON_JOIN	join on上的谓词条件下推
FilterJoinRule.JOIN	Filter算子下推到Join下边
FilterAggregateTransposeRule	Filter算子下推到Aggregate算子下边
ProjectMergeRule	Project算子合并
ProjectRemoveRule	去除不会映射子节点的Project算子
ProjectJoinTransposeRule	Project算子下推到Join算子下边
ProjectSetOpTransposeRule	Project算子下推到SetOp算子下边
FilterToCalcRule	Filter转换成Calc算子
ProjectToCalcRule	Project转换成Calc算子
FilterCalcMergeRule	Filter与Calc算子做合并
ProjectCalcMergeRule	Project算子与Calc算子合并
CalcMergeRule	Calc算子合并

  归一化规则包含: 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]])

在物化视图匹配的过程,我们要遵循一条核心的原则:物化视图计算逻辑是否能够表达出query,也即物化视图包含了query中的所有数据。如果不满足核心原则,那么不能够完成物化视图匹配。
Step1

物化识别是一个从底向上的迭代过程，由于来自同一个table,最下层的TableScan是完全相同的，经由TrivalRule判断是完全等价的。
Step2

在Step1等价节点完成匹配后，根据pattern需要匹配Query中的Calc与MV中的Calc,在这里需要注意一点,mv Calc的projects和filter需要能够表达出Query Calc中的projects和filter。如果能够表达,则构建出新的Calc补偿条件。

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

Step3

经过上一步Calc补偿之后,物化识别的Pattern变成了Query AggregateOnCalc去匹配target中的Aggregate节点，需要能够在mv的Aggregate之上,上提Calc补偿条件以及再做一次聚合操作。根据语义可知，mv之上,能够表达出Calc补偿条件以及做一次二次聚合, 在mv加上补偿条件以及二次聚合后，最下层的节点Aggregate-Calc-Scan已经是物化视图的计算逻辑，完成了物化识别，用Replacement去替换下层mv-logical表达的计算逻辑，即可完成物化表的替换，完成整个物化识别的过程。

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]])

从关系代数的结构树来看,Query和MV的关系代数结构树大致相似,唯一不同的点在于,Query中的LeftCalc多了一个过滤条件(deptno > 10)以及MV中多了一列(emps.name)。我们下边来看具体的物化识别过程:
Step1
我们对上边的关系结构树做一层简化,由于Query和Mv的RightCalc都是相同的,我们只需要关注LeftCalc带来的差异性以及匹配。

从关系代数结构树可以看出,我们能够基于MV LeftCalc表达出Query LeftCalc 子节点的匹配根据CalcToCalc在MV LeftCalc构建出补偿条件Calc(project:[1], condition:=>($1, 10))。
Step2

经过Step1构建出了补偿条件Calc,Step2的物化识别Pattern变成了Query JoinOnLeftCalc与MV 的Join做匹配，如上图所示，基于MV的Join可以将上一步补偿上来的Calc,补偿到MV的Join之上。到这里完成了基于MV+补偿条件的物化识别。
Step3

经过物化识别后，已经能够基于mv的计算逻辑,完整表达出query的计算逻辑,将mv-logical替换成Replacement完成物化识别.JoinOnRightCalcToJoinUnifyRuleJoinOnCalcsToJoinUnifyRule物化识别的匹配过程也相似,可以结合源码理解。

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 ...