一、背景介绍
参数化查问是指具备雷同模板，且只有谓词绑定参数值不同的一类查问，它们被广泛应用在古代数据库应用程序中。它们存在重复执行动作，这为其性能优化提供了契机。
然而，以后许多商业数据库解决参数化查问的办法仅仅只优化查问中的第一条查问实例（或用户指定的实例），缓存其最佳打算并为后续的查问实例重用。该办法尽管优化工夫至最小化，但因为不同查问实例的最佳打算不同，缓存打算的执行可能是任意次优的，这在理论利用场景中并不实用。
大多数传统优化办法需对查问优化器进行许多假如，但这些假如通常不符合实际利用场景。好在随着机器学习的衰亡，上述问题能够得以无效解决。本期将围绕发表于 VLDB2022 和 SIGMOD2023 的两篇论文开展具体介绍：
论文 1：《Leveraging Query Logs and Machine Learning for Parametric Query Optimization》
论文 2：《Kepler: Robust Learning for Faster Parametric Query Optimization》
二、论文 1 精髓解说
《Leveraging Query Logs and Machine Learning for Parametric Query Optimization》此篇论文将参数化查问优化解耦为两个问题：
（1）PopulateCache：为一个查问模板缓存 K 个打算；
（2）getPlan：为每个查问实例，从缓存的打算中抉择最佳打算。
该论文的算法架构如下图所示。次要分为两个模块：PopulateCache 和 getPlan module。
PopulateCache 利用查问日志中的信息，为所有查问实例缓存 K 个打算。getPlan module 首先通过与优化器交互收集 K 个打算与查问实例之间的 cost 信息，利用该信息训练机器学习模型。将训练好的模型部署于 DBMS 中。当一个查问实例达到时，可疾速预测出该实例的最佳打算。
PopulateCache
PolulateCache 模块负责为给定的参数化查问辨认一组缓存打算，搜寻阶段利用两个优化器 API：
- Optimizer call：返回优化器为一个查问实例抉择的打算；
- Recost call：为一个查问实例和对应打算返回优化器预计的 cost；
算法流程如下：
- Plan-collection phase：调用 optimizer call，为查问日志中 n 个查问实例收集候选打算；
- Plan-recost phase：为每个查问实例，每个候选打算，调用 recost call，造成 plan-recost matrix；
- K-set identification phase：采纳贪婪算法，利用 plan-recost matrix 缓存 K 个打算，最小化次优性。
getPlan
getPlan 模块负责为给定的查问实例，从缓存的 K 个打算中抉择一个用于执行。getPlan 算法能够思考两个指标：在 K 个缓存打算中，最小化优化器预计的 cost 或最小化理论执行的 cost。
思考指标 1：利用 plan-recost matrix 训练监督 ML 模型，可思考分类和回归。
思考指标 2：利用基于多臂赌博机（Multi-Armed Bandit）的强化学习训练模型。
三、论文 2 精髓解说
《Kepler: Robust Learning for Faster Parametric Query Optimization》该论文提出一种端到端、基于学习的参数化查问优化办法，旨在缩小查问优化工夫的同时，进步查问的执行性能。
算法架构如下，Kepler 同样将问题解耦为两局部：plan generation 和 learning-based plan prediction。次要分为三个阶段：plan generation strategy、training query execution phase 和 robust neural network model。
如上图所示，将查问日志中的查问实例输出给 Kepler Trainer，Kepler Trainer 首先生成候选打算，而后收集候选打算相干的执行信息，作为训练数据训练机器学习模型，训练好后将模型部署于 DBMS 中。当查问实例到来时，利用 Kepler Client 预测最佳打算并执行。
Row Count Evolution
本文提出一种名为 Row Count Evolution (RCE) 的候选打算生成算法，通过扰动优化器基数预计生成候选打算。
该算法的想法起源：基数的谬误预计是优化器次优性的次要起因，并且候选打算生成阶段只须要蕴含一个实例的最优打算，而不是选出繁多的最优打算。
RCE 算法首先为查问实例生成最优打算，而后在指数距离范畴内扰动其子打算的 join cardinality，反复屡次并进行屡次迭代，最终将生成的所有打算作为候选打算。具体实例如下：
通过 RCE 算法，生成的候选打算可能优于优化器产生的打算。因为优化器可能存在基数预计谬误，而 RCE 通过一直扰动基数预计，可产生正确基数对应的最佳打算。
Training Data Collection
失去候选打算集后，在 workload 上为每个查问实例执行每个打算，收集实在执行工夫，用于有监督最佳打算预测模型的训练。上述过程较为繁琐，本文提出一些机制来减速训练数据的收集，如并行执行、自适应超时机制等。
Robust Best-Plan Prediction
利用失去的理论执行数据训练神经网络，为每个查问实例预测最佳打算。其中采纳的神经网络为谱归一化高斯神经过程，该模型确保网络的稳定性和训练的收敛性的同时，能够为预测提供不确定性预计。当不确定性预计大于某个阈值时，交给优化器抉择执行打算。肯定水平上防止了性能的回归。
四、总结
上述两篇论文都将参数化查问解耦为 populateCache 和 getPlan 两局部。二者的比照如下表所示。
基于机器学习模型的算法尽管在打算预测方面体现良好，但其训练数据收集过程较为低廉，且模型不易于泛化和更新。因而，现有参数化查问优化办法仍有肯定的晋升空间。
本文图示起源：
1）Kapil Vaidya & Anshuman Dutt,《Leveraging Query Logs and Machine Learning for Parametric Query Optimization》, 2022 VLDB，https://dl.acm.org/doi/pdf/10.14778/3494124.3494126
2）LYRIC DOSHI & VINCENT ZHUANG,《Kepler: Robust Learning for Faster Parametric Query Optimization》, 2023 SIGMOD，https://dl.acm.org/doi/pdf/10.1145/3588963