- 分享人：朱道冰
- Keywords: Query Optimization, Materialized View
- 分享PPT: 2023-05-06-通过物化视图进行查询优化
随着数据规模的日益增大，批量SQL查询效率有待进一步提高，经实验表明，批量SQL查询中存在重复的子查询，可以通过选择合适的子查询建立物化视图来减少重复计算从而提升查询效率。如下图所示，在创建物化视图后，Query的部分数据直接从物化视图中获取，减少了join和group by的计算开销，有可能加速查询。
如下图所示的是通过物化视图进行查询优化的生命中期，主要有：视图设计、视图维护、视图利用三个模块。其中视图设计又涵盖三个小问题：从查询负载中识别候选子查询，从候选子查询中进一步选择子查询用于物化，最后是随着查询负载的变化，随着新的子查询要物化，物化视图占用的空间越来越大，需要将一部分不能给系统带来收益的物化视图淘汰删除。视图维护时指在基表发生变化的情况夏，使用何种策略更新对应的物化视图。视图利用是通过物化视图进行查询优化的关键，只有将查询负载的一部分用物化视图重写替代，才能真正的发挥物化视图的作用。
从查询负载中识别出不同查询语句之间的等价子查询作为建立物化视图的候选集。
将查询负载转换为执行计划，不同执行计划构成一个图，用图的方法判断等价性。
判断 SQL 语句的符号是否满足等价性。
两个子查询被称为等价子查询：当且仅当他们对应的关系代数表达式是等价的，这表明两个等价子查询可以互相利用彼此的查询结果。
方法：
**基于符号表示的等价判断：**判断 SQL 语句的符号是否满足等价性。
一种粗糙的办法：
1.将 alias 还原为 relation。
2.排序，如对不同谓词，不同relation等。
3.采用hash等方式进行等价性判断。
**基于逻辑语义的等价判断：**将查询解析成符号关系上的约束，从而去验证等价性。
Cosette[02,03]可以用于对两两查询语句的逻辑语义进行等价判断。如下图所示的是Cosette的步骤：
1.通过Rosette（SMT solver，可满足理论）找反例，返回不等价(Inequiv)；没找到在算法允许的开销限制内increate relation size重新找。
2.拆分为多个UniNomial表达式(subgoal)，使用Coq进行形式化证明，如果有不能证明的，则调用Rosette对subgoal找返例，最终根据所有subgoal的反例和形式化证明情况返回等价(Equiv)，不等价(Inequiv)和未知(TimeOut)。
选择子查询建立物化视图：在约束条件内尽可能选择出能够系统和查询负载带来最大收益的候选子查询进行物化。
挑战：
•在有限的存储空间下选择最优的视图进行物化
方法：
•基于DAG图的启发式方法
•基于ILP的方法
•基于策略的动态选择方法
DAG（Directed Acyclic Graph）
1.基于AND/OR图的贪心算法
2.基于MVPP（Multi-View Processing Plan）图的遗传算法
3.基于数据立方体格图的算法
选择子查询的另一个办法是整数线性规划问题，这属于最优化问题，选择一组参数（变量），在满足一系列有关的限制条件（约束）下，使设计指标（目标）达到最优值。当目标函数和约束函数结为线性时被称为线性最优化问题。当解只能是整数时属于整数线性最优化问题，选择子查询进行物化这个问题的解只有0和1两种情况，被称为01整数线性规划问题。
•**最优化问题：**选择一组参数（变量），在满足一系列有关的限制条件（约束）下，使设计指标（目标）达到最优值。
•**线性规划问题（LP问题）：**指目标函数和约束条件皆为线性的最优化问题。
•**整数线性规划问题（Integer Linear Programming）：**上面最优解可能是分数或小数，但是对于某些具体问题要求解答是整数。我们称这样的线性规划问题为整数线性规划问题。
•0/1 ILP**：**所有的整数变量只能是0或者1
左侧是有限投资下收益问题的01ILP问题的定义，cj 是收益，bj是投资开销，xj是投资与否。
右侧是物化视图选择问题的ILP问题的定义，uij是视图对查询语句的收益，zj是是否物化，可以看出两个问题宏观上较为相似。
Zj表示是否选择物化视图，还不够，当存在多个物化视图可以被用于同一个查询的重写时，当这几个物化视图存在包含关系时，只有一个物化视图能被同时使用，所以要把他们之间的互斥关系体现出来，于是使用yij和xjk来增加限制：
yij :是否选择j这个物化视图 用于qi的重写
Xjk :jk两个物化视图是否有包含关系
如第二个依赖所示，当使用k物化视图重写qi的时候，任何与k有包含关系的j不能被选择用于物化视图重写。至此将在有限的存储空间限制下选择子查询用于物化和重写被转换为一个01ILP问题，当mn比较大时该问题会难以在多项式时间内得到解，属于NP-hard问题。
微软在解决这个问题时，通过将该问题转换为二分图涂色问题，将一个巨大的整数规划问题转换为了多个小的ILP问题，使得该问题可以在多项式时间内得到较好得近视解。左边顶点为查询 qi，右边顶点为子表达 sj，左右两边的顶点相连表示 sj 是查询 qi 的一个子表达，S1 s2右边的01代表着是否选择该物化视图进行物化。实线代表左边的q可以使用右边的subexpression进行重写从而带来收益。
针对映射后的问题，微软BIGSUB的使用了一种基于迭代的方法进行求解，
(i) 为子表达式顶点分配标签 <- 基于启发式策略的选择物化视图
(ii) 给出第一步确定的子表达顶点，为边分配标签。 <- 更小的ILP问题
这个两步过程不断重复，直到顶点和边的标签没有变化，或者直到达到预定的迭代次数。
每个subexpression是否翻转的概率与两个因素有关系一个是当前距离整体预算的距离，距离越大，翻转的可能性越大，以尝试更多的机会。另一个是该节点带来的收益，收益越大，它被取消选择的可能性就越低，被选择的可能性越高。
随着人工智能的发展，后续工作将进一步选择子查询建立物化视图转换为马尔可夫决策过程，用强化学习进行问题求解。在某个状态下，选择不同子查询创建物化视图是行动，对此数据库系统会有一个Reward，从而不断迭代训练。
动作价值函数（state-action value function），也叫 Q 函数，即在某一状态 s 采取某一动作 a，假设一直使用同一个策略 π，得到的累计激励的期望值。这个公式是Q函数的增量更新方式，其中关键的是Rs,a这个奖励函数。
根据奖励函数分类可以分为三种：
-
空闲时间异步收集奖励数据用于训练DQM[06]
先看异步收集训练数据的做法，只看一个物化视图的创建与否，它的奖励函数是：物化视图对查询语句带来的Improvement提升，减去它的开销。
进一步展开看提升函数是指：使用物化视图的query的开销 减去 不使用物化视图query的开销。在这篇工作中，系统的训练数据是异步获取的，系统记录下历史查询语句，并在IDLE时间去在有无物化视图的情况下去运行查询语句，从而记录下数据以便用于后续训练。
-
训练学习型代价估计模型计算奖励
-
2020 RLView Wide-Deep Model[07]
RLView使用wide-deep model,其中 deep学习query 和view的执行计划特征，wide网络学习关联的metadata。
-
2021 AutoView Encoder-Reducer Model[08]
2021年的AutoView的Encoder-Reducer是RNN的模型
-
2022 GnnMV Gnn-Based Model[09]
2022年的GnnMv使用Gnn图神经网络对代价进行估计。
-
直观来说，提前选择的物化视图可能在以后的查询中被复用的频率逐渐降低，这就会导致物化视图的效用随着时间的推移逐渐降低。随着负载的积累，系统可以创建的物化视图越来越多，存储空间占用会越来越大，所以需要删除一部分不那么有用的物化视图。
如下图所示是静态物化视图和动态物化视图给系统带来的总收益的差别。
除了static外淘汰策略有以下4种：
-
DynaMat[10]: 依据频率、执行时间、大小等对物化视图进行打分
-
HAWC[11]：Cost Model + ILP(执行代价最小)
HAWC 提出了 基础Cost Model + ILP(执行代价最小)的淘汰策略。HAWC会维护一个历史查询语句池，并将物化视图选择问题转换为了一定存储空间限制下的整数规划问题，其中的收益函数使用传统代价估计模型的方法进行，删除策略是，不在整数规划求解答案中的物化视图需要被淘汰。
**删除策略：**删除不在ILP结果中的物化视图
-
DQM[06]：Learned Cost Model + 指标打分
如之前所示DQM采用异步真实运行+指标打分的机制进行淘汰。
-
GnnMV[09]：Learned Cost Model + ILP(收益最大)
GnnMV则是使用Gnn的学习型代价估计模型以及ILP问题进行淘汰，同样是不在ILP求解答案中的物化视图需要被淘汰。
**视图维护：**在基表更新时有效地更新物化视图。
视图维护主要是数据新鲜度(一致性)和数据操作开销(延迟)之间的权衡。
更新方式：
- 增量更新**(FAST):** 添加上次刷新到当前时间段内，base表变化过的数据。
- 全量更新**(COMPLETE):** 相当于重新执行一次创建视图的查询语句。
- 智能**(FORCE):** 能增量的时候增量，不能的时候全量更新，如有的数据库不支持update的更新。
更新时机：
-
立即更新**(ON COMMIT):** 物化视图和基表同步更新，保持较高的数据新鲜度。
-
手动更新**(ON DEMAND):** 提供接口让用户按需主动触发更新。
-
定时更新**(START** WITH&NEXT**):** 按照一定的时间间隔更新，避免物化视图的频繁更新。
| 数据库 | 物化视图 | 刷新方式 | 刷新时机 | 查询重写 |
|---|---|---|---|---|
| Oracle | 支持 | 全量/增量 默认****FORCE | 1.立即更新 2.手动更新 3.定时更新 | 支持 |
| PostgreSQL | 支持 | 全量 | 1.手动更新 2.定时更新 | 不支持 |
| MaxCompute | 支持 | 全量 | 定时 | 支持 |
| D****oris | 支持 | 增量 | 立即更新 | 支持 |
| MySql/TiDB | 不支持 | / | / | / |
注：加粗为默认方式，TiDB可以通过 TiCDC + Flink 的方式实现强一致的物化视图。
**视图利用：**有效地利用物化视图来加速查询处理。
**关键技术：**基于物化视图的查询匹配与重写。
步骤：
- 将创建好的物化视图注册到优化器中。
- 优化器将物化视图作为普通表参与查询优化过程。
方法：
-
Calcite[12]
-
基于图的物化匹配
另一种思路是基于图算法完成物化匹配
原则上是在图上判断 查询语句与物化视图存在包含关系、重叠关系，对物化视图不存在的部分进行补偿。
[01] – 综述- 李国良, 周煊赫, 孙佶, 等. 基于机器学习的数据库技术综述[J]. 计算机学报, 2020, 43(11): 2019-2049.
[02] - Cosette - Cosette 官网：http://cosette.cs.washington.edu/, demo： https://demo.cosette.cs.washington.edu/ Paper：Cosette: An Automated Prover for SQL
[03] - Count Bug - 嵌套查询优化中的 COUNT bug：https://developer.aliyun.com/article/69133，Ganski, Paper: R. A., & Wong, H. K. (1987). Optimization of nested SQL queries revisited. ACM SIGMOD Record, 16(3), 23-33.
[04] - MVPP - Horng J T, Chang Y J, Liu B J. Applying evolutionary algorithms to materialized view selection in a data warehouse[J]. Soft Computing, 2003, 7(8): 574-581.
[05] - BigSubs - Jindal A, Karanasos K, Rao S, et al. Selecting subexpressions to materialize at datacenter scale[J]. Proceedings of the VLDB Endowment, 2018, 11(7): 800-812.
[06] - DQM - Liang X, Elmore A J, Krishnan S. Opportunistic view materialization with deep reinforcement learning[J]. arXiv preprint arXiv:1903.01363, 2019.
[07] - RLView - Yuan, H., Li, G., Feng, L., Sun, J., & Han, Y. (2020, April). Automatic view generation with deep learning and reinforcement learning. In 2020 IEEE 36th International Conference on Data Engineering (ICDE) (pp. 1501-1512). IEEE.
[08] - AutoView - Han, Y., Li, G., Yuan, H., & Sun, J. (2021, April). An autonomous materialized view management system with deep reinforcement learning. In 2021 IEEE 37th International Conference on Data Engineering (ICDE) (pp. 2159-2164). IEEE.
[09] - GnnMV - Han, Y., Chai, C., Liu, J., Li, G., Wei, C., & Zhan, C. Dynamic Materialized View Management using Graph Neural Network.
[10] - DynaMat - Kotidis, Y., & Roussopoulos, N. (1999). Dynamat: A dynamic view management system for data warehouses. ACM Sigmod record, 28(2), 371-382.
[11] - HAWC - Perez, L. L., & Jermaine, C. M. (2014, March). History-aware query optimization with materialized intermediate views. In 2014 IEEE 30th International Conference on Data Engineering (pp. 520-531). IEEE.
[12] - View Matching used by Calcite - dstein J, Larson P.-Å. Optimizing queries using materialized views: a practical, scalable solution[J]. ACM SIGMOD Record, 2001, 30(2): 331-342.