一个端到端的基于深度学习的查询优化引擎

孙佶 李国良

摘要：数据库查询优化迄今已经在数据库领域广泛研究数十年，一个好的查询优化器对于数据库性能来说是至关重要的，但是不论是传统的基于统计和采样的基数估计还是多表连接物理计划生成，在一些真实数据集上效果依然不尽如人意.深度学习是当前被广泛研究和使用的基于神经网络的机器学习算法，但是将深度学习应用到数据库系统中却是学术界近几年刚开始的尝试.我们结合传统主流数据库查询优化器的架构以及学术界最近的数据库查询优化进展，分析了目前查询优化所面临的痛点，并且利用深度神经网络模型和深度强化学习模型分别提升数据库查询基数估计和查询计划生成的时间性能和效果，最后，我们提出基于规则和基于置信度的两种计划验证方法以及高效异步模型更新方法.我们提出的端到端的基于机器学习的數据库查询优化引擎在标准测试集和真实数据机上的性能和效果要显著优于传统数据库Postgresql中的优化器.

关键词：数据库;查询优化;深度学习;强化学习

中图分类号：TP311.13  文献标识码：A  文章编号：1673-260X（2019）01-0001-05

1 背景介绍

查询优化器是数据库系统中的一个组件，用来为查询选择一个高效的执行策略以使得资源消耗最小.当前，多表连接查询优化是查询优化的重要任务，用户输入的包含多表的连接查询对于不同的查询执行计划有着非常不同的代价消耗.在数据库中，查询优化器会估计若干表连接的最终结果大小即“基数”，由于表连接的代价和连接“基数”有着明显的正相关关系，所以传统优化器可以通过基数来选择合适的查询顺序来执行当前的多表连接查询.

传统数据库中基于代价的多表连接查询顺序选择以动态规划方法和一些启发式算法为主，以经典数据库Postgresql为例，其连接顺序选择算法包括“LEFT-DEEP”和遗传算法两种[1]，但是这两种方法存在以下问题：（1）“LEFT-DEEP”动态规划算法在多表情况下效率很低，并且生成的“LEFT-DEEP”查询计划是次优的.（2）遗传算法能够保证效率，但由于启发式算法的特点，产生的查询计划往往比动态规划算法要差.（3）Postgresql采用的是静态查询计划生成方法，即使对于一条查询语句优化失效，系统也无法利用真实的计划执行性能获得反馈来动态调整优化策略.（4）传统优化器往往基于一个线性的代价模型作为估计的代价，但是真实环境下代价和基数之间的关系更加复杂，线性估计经常导致生成的查询计划是次优的.

经过近四十年的发展，数据库系统依然受困于糟糕的查询计划，而次优的查询计划除了次优的查询优化生成器因素之外通常还会由糟糕的基数估计导致[2].基本上所有的工业级别的数据管理系统依赖于一些定长的、针对属性的统计信息以及一些诸如均匀性，独立性，包含性，特定常量的强假设，大多数数据库系统尝试将任意一个大的数据库拟合到一个常量大小的空间里，所以这些方法对于交叉连接的查询会失效.对于真实的数据集来说，基数估计错误往往是很大的.这些错误导致了查询效率低下并且性能无法预测.另一种很有前景的替代基于直方图估计的方法是采样，因为它可以检测出任意的关联性从而生成准确的基数估计.然而，尽管已经被研究了数十年，很少有系统在生产中实际采用采样的方法估计基数.其中一个原因是过去的内存空间很小，采样技术由于随机磁盘读写的代价太高而不现实.另一个原因是无论采样多少条记录，对于估计多表查询的结果基数也是不够的，如果增加一个连接表会快速减少采样结果的数量，那么系统使用采样进行基数估计也是不可行的.最近的工作利用连接的表的索引大大增加了采样估计结果的准确度，减少了采样的代价，按时如果在缺少索引的情况下依然会退化，结果的准确性变得不可预测，甚至会导致很大的错误.在采样数据和统计信息缺少的情况下，传统算法很难对执行结果行数进行准确估计.

基于上述背景，本文提出一个新颖的基于端到端深度神经网络的数据库查询优化引擎.针对基数估计不准的问题，我们利用一个深度多集合卷积神经网络（MSCN）[7]与卷积神经网络（CNN）[10]构成的联合训练网络模型实现对任意查询的基数准确估计，MSCN模型层数少效率高，具有很强的查询特征表达能力，能够实现对实际负载查询基数的精确估计;而CNN可以利用卷积核实现对于数据表的特征抽取.针对传统数据库多表连接查询优化算法效率低，效果次优的问题，本文使用一个深度强化Q-学习模型来构建新型的多表连接查询计划优化引擎[6，8]，该查询优化具有高效率，强鲁棒性，动态灵活的特点，而且能够增量在线调节模型使得查询计划生成器能够随着负载变化而进化.本文提出的引擎没有对代价模型做更多的考虑，这是由于（1）基于强化学习的优化器在启动训练中能够从实际执行中获得反馈进行自我调整从而对代价模型有着很强的鲁棒性，（2）基数估计的精度要比代价模型更加重要.我们在真实测试集“JOB”上将我们的引擎与Postgresql从基数估计，多表连接顺序选择，执行计划生成效率三个方面进行了对比，实验显示我们的优化引擎无论在效率还是效果都有显著提高.

本文有如下贡献：

（1）提出一个端到端的基于深度学习的查询优化框架.

（2）设计一个数据表表示和基数估计联合卷积神经网络及其训练方式，能够提高模型的泛化并且支持数据更新之后的迁移学习.

（3）基于多集合卷积神经网络设计出一个新的基于Q网络的强化学习方法.

（4）设计一个查询计划生成器的校验模块，并且在校验失败之后能够高效异步更新网络模型.

2 系统概述

训练：整个系统分为如下图所示的几个部分，作为一个端到端的查询优化引擎，系统支持冷启动，每部分的网络都有其特定的功能而可以分阶段训练，面对复杂的场景具有高效灵活易部署的特点.部署在一个数据库上时，首先使用配套的训练集生成器生成训练查询语句，通过实际执行获得每条语句的真实执行代价和真实结果基数，然后训练多集合卷积网络直到验证数据集上的Q错误达到最小的值后停止训练.在执行计划生成部分，对每一条语句建立一个连接边池，每一步从池子中选择一条边作为动作，生成的当前计划作为查询语句输入之前训练好的基数估计网络计算当前子查询估计的基数，之后再使用选择的代价模型计算代价作为回报，使用回报和当前Q网络计算下一个状态对应的Q值，将这个值与直接使用历史Q网络计算出的下个状态的Q值的差值作为损失函数来训练网络.注意到每条语句结束之后对应的完整的计划都有个真实的代价，直接根据这个真实的代价可以对Q网络进行细调节使得模型对于不同代价模型的鲁棒性更好.

应用：对于任意一条SQL语句，首先抽取其所有的连接边放入一个池子，任意选取一个表作为初始状态，使用深度强化学习模型中获得状态对应的一个动作（下一个需要连接的表），生成的两表连接作为下一个状态，输入模型获得进一步的连接，循环上述步骤直到所有连接都已经使用，输出一个优化之后的执行计划.这个执行计划可以交给传统数据库管理系统来选择合适的物理操作，然后执行操作，返回结果.

验证计划：和基数估计相比，执行计划生成是个更加复杂的问题，所以会不可避免地出现对于某些查询语句生成次优的执行计划甚至于查询优化失效的情况.但是幸运的是，深度强化学习可以针对每一条查询语句进行快速的增量训练.对于每一条查询语句，利用用户指定的规则或者当前执行计划的置信度判断是否失效，如果可能失效，比较当前生成计划和传统查询优化器生成的计划总代价，如果比传统优化器生成的计划代价要高则利用当前的查询进行训练来更新Q-网络.模型验证和更新基本不会影响整体优化效率，因为（1）训练单条语句的效率很高，只有几十毫秒的量级.（2）模型不需要同步更新，旧的模型可以继续优化新来的查询，当模型更新完成之后，将新的参数更新到活动空间中即可.

3 系统组件

3.1 基数估计模块

Andreas Kipf[7]等提出的多集合卷积神经网络（MSCN）是一种较为有效的深度学习模型来估计查询代价，该网络能够利用查询语句的表示和集合语义学习查询的特征和真实的结果基数.MSCN解决了基于采样方法在缺少有效采样情况下无法工作的问题，并且能够有效获得连接的多表的相关性.但是MSCN模型也具有泛化能力不足，依赖记忆等缺点.

基于集合的查询表示：一条表连接查询语句包括三个部分，数据源，连接条件（相等连接），查询条件.首先收集整个数据库中所有的数据属性构造一个属性全集，根据这个全集对查询属性进行独热编码.数据源根据数据表全集进行独热编码，查询条件的比较操作则根据操作全集进行独热编码，查询条件右值如果是数值型则利用表中的统计信息归一化成0和1之间的浮点型数值，如果是字符串则使用训练出来的单词编码.对于一张数据表，除了独热编码表之外还需要额外的信息来帮助模型理解查询条件，比如当前查询中每个数据表有多少行被查询条件选中或者是采样中选中位置设为1的一个位图向量，但是无论是选择率还是位图都不能反映表的重要内容信息，如果希望神经网络能够学习到数据的高阶内容和规律而达到泛化和快速收斂的目的，必须要包含更多的信息，否则模型只是一个“记忆”的过程而且容易发生采样向量全零的问题，这部分内容由下一个小节（数据表示与基数估计联合训练）来介绍.

MSCN模型介绍：多集合卷积模型是基于在排列不变的集合S上的任何函数f（S）都可以分解成 ？籽[∑x∈s？覬（x）]，可以使用多层神经网络（MLPs）来描述参数？籽和？覬并且依赖它们的函数拟合能力学习映射f（S）.对于查询的表示包括了多个集合，对于每一个集合，都可以学习一个神经网络MLPs（vs）.集合中的每一个元素都会经过一个MLP的变换：

之所以选择的是平均而不是求和是因为这样结果不会因为集合元素个数变化而变化.最终，模型拼接来自数据表，连接键，谓词网络的向量输入给最后的输出层MLP.除了输出层，所有的MLP模块都是两层全连接神经网络，激活函数是ReLU（x）=max（0，x）.对于输出层MLP，模型最后一层使用sigmoid=1/（1+exp（-x））作为激活函数并且只输出一个[0，1]之间的值.对于目标基数使用如下方法进行正则化：首先取log成为分布更加均匀的值，然后使用min-max方法正则化成为[0，1]之间的值，这种正则化方式是可逆的，之后可以从网络输出将基数恢复出来.训练使得平均Q错误最小.

3.2 数据表示与基数估计联合训练

数据表特征编码：一维深度卷积神经网络要求输入向量为定长定高，假设定长N为表的行数，表的属性个数作为通道数设定为M（M是数据库中所有数据表最大的行向量的长度）.对于行数大于N的数据表，采样N条记录，反之，对于行数不足N的数据表，使用0值扩充至N长度向量.类似地，对于一行向量长度不足M的数据表使用0值扩充.每个数据表中，数值型的值可以采用最大最小正则化表示，类别型数据使用独热编码表示.对于字符串类型值，则需要借助其他属性以及数据库中主键外键连接关系训练一个嵌入式特征编码，原理和自然语言处理中的分布式词向量构造类似，使在数据库全表上有潜在连接关系的两个值编码的余弦距离接近.数据表中所有的元素添加表名作为前缀加入词库，直接关联的主键和外键当作是同一个词（选择主键的表名作为前缀），扫描全数据库，生成训练元组，每个元组看作是自然语言中的一句话，使用神经网络语言模型（NNLM）[9]进行训练.

训练集生成：和传统MSCN一样，本模型也可以在获得实际负载之前训练模型.方法是根据模式信息生成随机的查询并且从实际的数据库中逐个选取值.一个训练实例包括表标号，连接谓词，基表谓词，和查询真实的基数.训练集分为两部分，一部分只包含涉及小于等于两个表的查询用于联合训练数据表表示，另一部分各种规模查询均匀分布用于MSCN模型的训练.具体地，训练集查询生成器首先均匀选取连接数量|Jq|并且均匀选取一个具有至少一个连接的数据表.如果|Jq|>0，均匀选择一个可以和之前选择表连接的新表，添加对应的连接边，重复这个过程|Jq|次.对于查询中的每个基表，均匀选择|Ptq|个查询条件（0<=|Ptq|<=非键列的数量）.对于每个谓词，均匀从三种操作（=，<或者>）中选择一个，并且从对应的列中选择一个真实值.最后对这些随机查询进行去重，并且实际执行获得真实的基数.

数据表编码模型结构：编码结构由两个一维卷积层构成，第一个卷积层，输入每个值都已经编码的数据表，表的行数作为向量长度，表的列数作为表的高度（卷积通道数），第一层使用10个卷积核心增加向量的通道数，输出之后经过一层非线性激活层，再使用池化层减少向量长度.这个过程再做一次，最后将一个“高而短”的向量扁平化成一维且经过一层线性全连接网络输出.

訓练过程：由于训练数据表特征表示的输入很大，每一个批次的训练要消耗很多计算资源，所以训练这部分网络的时候不适合使用很大的查询，所以第一阶段联合训练过程只选择涉及两个表以下的查询，这种短查询足够覆盖每个查询条件对于单表选择的影响以及每两表之间的连接关系.第一阶段结束之后，表的表示将被记录在内存中并且不再变化.之后使用所有生成的训练集，将3.1中的表集合表示成表序号独热编码和数据表特征表示拼接的形式送入多集合卷积网络进行训练，对上层网络参数进行微调直到测试Q-错误达到最小.

3.3 查询计划优化模块

Sanjay Krishnan等[8]证明使用强化学习优化查询连接顺序的方法是可行的，但是这篇文章没有提供具体的Q网络设计细节，查询语句编码也过于简单无法获得连接条件，查询条件以及数据表的高层内容信息.为了提高模型精度和鲁棒性，本文设计了一个基于多集合卷积神经网络的高效的Q网络并且说明训练方法.

状态编码：强化学习过程中影响下一步连接决策的因素有当前已经连接数据表生成的中间结果，下一步可选的连接边集合，下一步每一步连接的代价以及未来可能的代价期望.使用基数估计模块提供的编码方式完全可以满足强化学习的状态表示，即采用表集合，连接键集合和查询条件谓词集合来表示.

Q网络设计：对于同一个连接图，基于基数估计模块训练出来的数据表表示以及底层的三个多集合卷积网络可以复用，而且由于同一个数据库中数据分布和数据表之间的连接关系也是不变的，所以底层网络的网络参数也可以复用.这里我们在原有的上层MSCN网络下部增加了一个新的MSCN网络，将最后一个激活函数修改为输出函数Softmax输出多个概率分布用来选择动作.上层网络如下图所示：

公式中？兹是上层Q网络的网络参数，？琢是衰减系数，G是状态，a是选择的连接动作，Q是Q-学习的值.对于产生的每一个新状态，我们利用之前训练出来的基数估计和代价估计器生成的代价作为代价，这个代价要比Postgres估计器生成的代价更加准确，而在线生成训练集比使用离线的动态规划代价表中的子计划收敛更快.而在验证阶段使用失效查询语句在线训练更新Q网络的时候，需要的仅仅是查询语句本身以及最终执行完的实际代价，中间的代价从代价估计器中获得或者直接设置为0效率更高.

3.4 查询计划验证模块

这部分的目的是在运行中验证模型对于当前来的查询是否有效，如果失效，则需要更新模型参数.这部分需要使用生成计划效果估计，最终基数估计，总代价估计，离线重训练这四个部分.

基于规则验证：用户可以对每个数据库设置一些计划验证启动规则，比如某种查询的执行时间期望上界，当这些规则被违反之后，系统会另开一个异步进程去进行验证，如果发现优化器对于当前查询语句失效，那么就会启动模型细致调节，调节的时候确保Q网络的底下两层参数不动，只调整最后输出层的参数，这样可以在确保有效调节的基础上大大提高训练效率，使得调整之后的模型能够尽快应用.模型训练完成之后，冻结数据库更新内存中对应位置的参数，冻结时间非常短（亚毫秒级别）.

基于置信度验证：基于深度强化学习本身可以做到利用置信度自动检测模型对于当前查询是否适用.方法是每一个连接决策的时候在Q网络输出层的分布进行采样，获得最小Q值区域的累积概率，将这个概率当作是下一个选择的连接的置信度，把一条完整语句生成计划的过程中最小的一个置信度作为当前语句的置信度，如果这个置信度小于一个阈值，那么就可以判定模型参数需要更新.

参考文献：

〔1〕Gregory Smith. PostgreSQL 9.0 High Performance[M]. Packt Publishing，2010.

〔2〕Viktor Leis， et al. How Good Are Query Optimizers， Really？[C]. Proceedings of the VLDB Endowment，2015，9-3：204-215.

〔3〕Viktor Leis， et al. Cardinality Estimation Done Right： Index-Based Join Sampling[C]. 7th Biennial Conference on Innovative Data Systems Research （CIDR ‘17）， 2017.

〔4〕W. Wu， et al. Predicting query execution time： Are optimizer cost models really unusable？ Data Engineering （ICDE）， 2013， 1081–1092.

〔5〕R. Bellman. Dynamic programming[M]. Princeton University Press， 1957.

〔6〕V. Mnih， et al. Human-level control through deep reinforcement learning. In Nature. Nature Research， 2015.

〔7〕Andreas Kipf， etal. Learned Cardinalities： Estimating Correlated Joins with Deep Learning[C]. 9th Biennial Conference on Innovative Data Systems Research （CIDR ‘19）， 2019.

〔8〕Sanjay Krishnan， et al. Learning to Optimize Join Queries With Deep Reinforcement Learning[DB]. CoRR， 2018， abs/1808.03196.

〔9〕Yoshua Bengio， et al. A Neural Probabilistic Language Model[C]. Journal of Machine Learning Research， 2003， 1137–1155.

〔10〕Alex Krizhevsky， et al. ImageNet Classification with Deep Convolutional Neural Networks[C]. NIPS， 2012， 1106-1114.