一、背景介绍

参数化查询是指具有相同模板，且只有谓词绑定参数值不同的一类查询，它们被广泛使用在现代数据库使用程序中。它们存在重复履行动作，这为其功能优化供给了关键。

然而，当时许多商业数据库处理参数化查询的办法仅仅只优化查询中的第一条查询实例（或用户指定的实例），缓存其最佳方案并为后续的查询实例重用。该办法虽然优化时刻至最小化，但由于不同查询实例的最佳方案不同，缓存方案的履行或许是恣意次优的，这在实践使用场景中并不适用。

大多数传统优化办法需对查询优化器进行许多假定，但这些假定一般不符合实践使用场景。好在跟着机器学习的兴起，上述问题可以得以有用解决。本期将围绕发表于 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，dl.acm.org/doi/pdf/10.…

2）LYRIC DOSHI & VINCENT ZHUANG, 《Kepler: Robust Learning for Faster Parametric Query Optimization》, 2023 SIGMOD，dl.acm.org/doi/pdf/10.…