Calcite物化视图查询改写

理论基础

论文[1]提出SPJG查询改写，是SQL Server 2000视图改写的理论基础，高效实现基于selection, project, join, group-by算子匹配的视图改写方案，是当前很多计算引擎的物化视图查询改写的理论基础，例如：Calcite、Doris、StarRocks都基于优化器的SPJG结构改写进行扩展实现。

该论文主要贡献，提出：

1. 一种高效的SPJG视图匹配算法，并给出详细的匹配步骤和需满足的条件说明；
2. 一种新颖的索引结构，用于维护待匹配的视图，快速缩小搜索范围，仅对一小部分候选视图应用视图匹配。

列等价类：一组相互之间值相等的列集合，可基于等值连接获取，实现列引用重新路由是视图改写的重要能力。

基于列等价类理论，视图与查询源表相同的情况下，SPJ需要满足四个条件：

针对具有GroupBy聚合处理的SPJG，需额外判断：

1. 分组列子集性：视图不包含聚合操作，或者聚合程度低于查询，即查询的聚合分组可通过视图输出的分组进一步聚合计算；
2. 上卷可用性：进一步聚合分组的所有列在视图中都可计算；
3. 输出列可用性：输出表达式的所有列在视图中都可计算。

Calcite实现

基于SPJG论文的理论进行实现的，核心实现逻辑 MaterializedViewRule ，基于CBO选择代价最优的改写的计划树。基于perform 实现SPJG条件判断。

查询源表与视图源表的匹配类型：

步骤一：改写前置准备

将查询和物化视图进行以下前置处理

1. 有效性校验：MaterializedViewRule#isValidPlan 判断算子的类型：
   1. SPJ：TableScan、Project、Filter、Join、若Join限制为InnerJoin
   2. SPJG：除SPJ允许允许算子外，计划子树顶点为Aggregate算子，限制GroupBy，暂不支持Grouping Set
2. CNF合取范式拆分： MaterializedViewRule#splitPredicates 拆分两部分：PE列等价谓词 + PU剩余谓词；
3. 列等价类获取：基于PE列等价谓词获取列等价类，并以 EquivalenceClasses 定义，是一组等值的列集合

步骤二：改写条件判断

1. 源表匹配模式判断：
   1. 查询源表等价视图源表：完全匹配，COMPLETE类型，
   2. 查询源表少于视图源表：查询不完全，QUERY_PARTIAL类型，根据视图额外表理论，利用外键有向图判断保持基数连接(cardinality preserving join)条件：i. 等值JOIN；ii.全列匹配；iii.外键非空; iv: 外键约束; v:唯一键约束；以源表作为顶点，外键条件为边，递归删除没有出边且仅有一条入边的顶点，实现视图额外表消除，直到视图源表与查询源表一致。
   3. .查询源表多于视图源表：视图不完全，VIEW_PARTIAL类型，针对SPJ和SPJG进行分别判断
2. 补偿谓词获取：MaterializedViewRule#computeCompensationPredicates
   1. 等值连接补偿谓词：MaterializedViewRule#generateEquivalenceClasses，判断视图等值连接是查询等值连接的子集，当视图不同列等价类分别映射到同个查询列等价类时，则补偿视图列相等谓词。
   2. 剩余补偿谓词：查询剩余谓词可应用(蕴含)在视图剩余谓词，基于SubstitutionVisitor#splitFilter 获取视图的剩余补偿谓词。
3. 补偿谓词校验：基于类等价类的引用(表/列)交换，判断补偿谓词在视图中可正确计算

步骤三：计划子树改写

1. 视图添加补偿谓词：MaterializedViewRule#pushFilterToOriginalViewPlan 添加补偿谓词并更新视图计划树；
2. 视图重写：MaterializedViewRule#rewriteView 视图重写，其中SPJ和SPJG有不同实现方式，SPJG要考虑视图上卷场景，处理更加复杂。

附录

1. Optimizing Queries Using Materialized Views: A Practical, Scalable Solution
2. 解读 Optimizing Queries Using Materialized Views: A Practical, Scalable Solution