共计 3937 个字符，预计需要花费 10 分钟才能阅读完成。
写在后面
本文次要介绍了公布于 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 的指标，即缩小查问布局工夫的同时，进步了查问执行性能。