写在前面
本文首要介绍了发布于 2023 年 SIGMOD 的论文《Kepler: Robust Learning for Faster Parametric Query Optimization》，该文章针对参数化查询，将参数化查询优化与查询优化结合，旨在削减查询规划时刻的一起进步查询功能。
为此，作者提出了一种端到端的、根据深度学习的参数化查询优化办法，名为 Kepler (K-plan Evolution for Parametric Query Optimization: Learned, Empirical, Robust)。
它经过一种新颖的候选方案生成算法以及鲁棒的深度学习模型来实现查询功能上的显着进步。参数化查询是指具有相同 SQL 结构，只在绑定的参数值上不同的一类查询。举个比如，考虑以下查询结构：
该查询结构可以看作一个参数化查询的模板，”?”处代表着不同的参数值。用户履行的 SQL 语句都具有该查询结构，只是实践的参数值或许不同，这就是一个参数化查询。这样的参数化查询在现代数据库中的运用非常频繁。由于其不断重复履行同一查询模板，为进步它的查询功能带来了机会。
参数化查询优化 (PQO) 用于优化上述参数化查询的功能，方针是尽或许地削减查询规划时刻，一起防止功能的回归。现有的办法过度依赖于体系内置的查询优化器，使其遭到优化器固有的次优性的约束。作者认为，参数化查询的抱负体系不应该只经过 PQO 削减查询规划时刻，也应该经过查询优化 (QO) 进步体系的查询履行功能。
查询优化 (QO) 用于协助一条查询找到其最优的履行方案。现有的改善查询优化的办法大多应用了机器学习，如根据机器学习的基数/成本估量器。但现在根据学习的查询优化办法存在一些缺陷： （1）推理时刻过长； （2）泛化能力差； （3）对功能的进步不明确； （4）不具有鲁棒性，功能或许会回归。
上述缺陷为根据学习的办法带来了应战，由于它们不能确保猜测结果对履行时刻的进步。为解决上述问题，作者提出了 Kepler：一种端到端的根据学习的参数化查询优化办法。
作者将参数化查询优化解耦为两个问题：候选方案生成和根据学习的猜测结构。首要分为三个进程：新颖的候选方案生成、练习数据搜集以及鲁棒神经网络模型规划。三者结合，削减了查询规划时刻的一起进步了查询履行功能，一起满足了 PQO 和 QO 的方针。接下来，咱们首要介绍 Kepler 的整体架构，然后详细解说每个模块的详细内容。
整体架构
Kepler 的整体架构如上图所示。首要，从数据库体系日志中获取参数化查询模板以及对应的的查询实例（即带有实践参数值的查询），组成一个作业负载。Kepler Trainer 用于为该作业负载练习神经网络猜测模型。它首要在整个作业负载上生成候选方案，并在暂时的数据库体系中进行履行，获得实践的查询履行时刻。
利用该查询时刻练习神经网络模型。练习完成后将其部署于生产环境下的数据库体系中，称为 Kepler Client。当用户输入一个查询实例时，Kepler Client 可以为其猜测最佳的履行方案，用 plan hint 的形式交给优化器，从而生成并履行最佳方案。
候选方案生成：Row Count Evolution
候选方案生成的方针在于构建一组方案，使其为作业负载中的每个查询实例都包含近最优的履行方案。此外，应该尽或许的小，以免后续练习数据搜集进程开销过大。二者相互约束，怎么平衡这两个方针是候选方案生成的一个首要应战。
等式 1 公式化了详细的方案生成方针。其间，为作业负载 W 上的一个查询实例，为优化器挑选的履行方案，为抱负情况下，在方案会集的最优方案，ExecTime 为对应方案在实例上的履行时刻。因而，等式1的内在为，在整个作业负载上，候选方案集比较优化器生成的方案集，在履行时刻上带来的加快。算法旨在最大化该加快作用。
为此，本文提出了 Row Count Evolution (RCE)，一种经过随机扰动优化器基数估量来生成新方案的算法。它为每个查询实例生成一系列方案，兼并成为整个作业负载的候选方案集。该算法的思路来源在于：基数的错误估量是优化器次优性的首要原因。一起，候选方案生成阶段并不需求为每个查询实例找到详细的单一 (近) 最优方案，而是只需包含了该 (近) 最优方案即可。
RCE 算法是经过迭代不断发生新的方案的。首要，初始迭代方案为优化器发生的方案。为了构建后续迭代，首要需求从上一代方案中均匀随机采样。关于每一个采样出来的方案，扰动 (改变) 其 join 子方案的 cardinality。
扰动办法是，在其当时预估 cardinality 的指数距离规模内随机采样。将扰动后的 cardinality 交给优化器，生成对应的最佳方案。对每个方案重复 N 次，发生许多履行方案，其间没出现过的履行方案保存作为下一代方案，并重复上述进程。
咱们给出一个详细的实例来形象化的阐明上述算法，如下图所示。首要，Base Plan 为优化器挑选的最佳方案，他有两个 join 子方案，分别为 A join B 和 C join D，它们预估的基数分别为 40 和 17。
接下来，从指数距离规模 10-1~101 为两个 join 子方案生成扰动集，分别为 [4,40,400] 和 [1,17,170]。从扰动会集随机采样，并将其交给优化器进行方案的挑选。Plan 1 即为优化器在 cardinality 分别为 400 和 17 时挑选出来的新方案。重复 N 次，终究生成了 C1 个方案作为下一代。接下来，从中采样 S 个方案，并为每个方案重复上述流程，形成第 2 代方案。
作者选用指数距离规模作为扰动集的原因是为了符合优化器基数估量差错的分布。经过上述算法可知，只需扰动的次数足够多，会发生许多的 cardinality 以及其对应的 plan。这样，当一个查询实例到来时，咱们的方案会集应该存在和真实 cardinality 相近的 plan，可以视为该实例的 (近) 最优方案。
练习数据搜集
发生候选方案集后，在作业负载上履行每个方案，已生成履行时刻数据，以便进行有监督的最佳方案猜测。选用实践履行数据而不是优化器估量的 cost，可以防止优化器次优性带来的约束。履行进程是可并行的。但是，履行一切方案是一笔很大的开销。因而，作者提出了两种战略来削减不必要的次优方案履行带来的资源浪费。
Adaptive timeouts and plan execution reordering，自适应的超时机制和方案履行重排序。作者选用一种超时机制来约束次优方案的履行。关于每个查询实例，在履行每个方案时，可以记载现在最短履行时刻。
一旦某个方案的履行时刻超越该最短履行时刻的必定规模，便可以不再履行，由于他必定不是最优的履行方案。一起，最短履行时刻是不断更新的。此外，根据其他查询实例上每个方案的履行情况，按照履行时刻升序履行查询方案，可以作为一种启发式的方案来加快超时机制。
Online plan covering pruning，在线方案集剪枝。在为前 N 个查询实例履行一切方案后，利用 Set Cover 问题将其剪枝为 K 个方案。后续的数据搜集和模型练习都运用这 K 个方案。Set Cover 问题的定义如下图所示。
在本文的上下文环境中，代表一切查询实例，可以表示为不同的方案，每个方案是某些查询实例的近最优方案。因而，该问题可以表述为，竭尽或许最小的方案集，为一切查询实例供给近最优性。该问题是 NP 的，因而作者选用贪心算法来解决。
鲁棒的最佳方案猜测
搜集好候选方案集的实践履行时刻的练习数据后，选用有监督的机器学习来为任意一个查询实例猜测最佳方案。练习的方针在逻辑上可以用以下等式来表示。其间代表模型为查询实例挑选的最佳方案。该等式的内在为模型挑选的方案比较与优化器挑选的方案带来的加快。它的上限是等式 1。换句话说，模型要尽或许捕获到 RCE 生成的候选方案所带来的加快。
模型的结构选用前向神经网络，并应用了机器学习不确定性的最新进展，即 Spectral-normalized Neural Gaussian Processes (SNGPs)，谱归一化高斯处理进程。将其结合到神经网络中，进步模型收敛性的一起，使得神经网络可以输出猜测的不确定性。当不确定性高于个阈值时，将方案猜测的作业返还给优化器，由优化器决议最佳方案。
模型的特征选用的是每个参数的实践值。为了将参数的实践值可以输入到神经网络中，需求进行一些预处理，尤其是字符串类型的数据。关于字符串类型的数据，作者经过一个固定巨细的词汇表以及不在词汇表中的桶来将其表示为 one-hot 向量，并参加一层嵌入层来学习该 one-hot 向量的嵌入，进而可以处理字符串类型的数据。
试验作用
本文作者将 Kepler 集成于 PostgreSQL，并组织了一系列试验。试验的总结如上图所示，Kepler 总共带来的加快作用为 2.41 倍。其间，RCE 生成的候选方案集可以带来 2.92 倍的加快，被 SNGP 猜测模型捕获到了 80.8%，并且仅有 0.4% 的回归。此外，模型的推理时刻均匀只要 0.15ms。
总结
本文提出了 Kepler，一种根据学习的办法，可以稳健地加快参数化查询。其经过 Row Count Evolution (RCE) 算法生成候选方案集，并在 workload 上履行以获取实践履行时刻，利用该实践履行时刻练习猜测模型。
猜测模型选用机器学习不确定性估量的最新进展 Spectral-normalized Neural Gaussian Processes (SNGPs)，进步收敛性的一起输出猜测的不确定性，根据该不确定性挑选由该模型仍是优化器完成方案猜测的任务。试验证明 RCE 可以带来很高的加快作用，并且 SNGP 在防止回归的一起尽或许捕获到 RCE 带来的加快作用。因而，一起完成了 PQO 和 QO 的方针，即削减查询规划时刻的一起，进步了查询履行功能。