连接顺序选择在查询性能中起着重要作用。但是，现代查询优化器通常采用静态连接顺序枚举算法，该算法不包含有关结果计划质量的反馈。 因此，优化器经常重复选择相同的错误计划，因为它们没有“从错误中吸取教训”的机制。 在这里，我们认为可以应用深度强化学习技术来应对这一挑战。这些技术由人工神经网络提供支持，可以通过合并反馈来自动改善优化程序的决策制定。 为了实现这一目标，我们提出了概念验证连接枚举器ReJOIN，以及初步结果，表明ReJOIN在计划质量和连接枚举效率方面可以匹配或优于PostgreSQL优化器。
为关系查询确定良好的连接顺序是数据库系统中研究最深入的问题之一，因为选择的连接顺序对查询性能有极大的影响[11]。 选择连接顺序的主要挑战是枚举一组候选顺序并确定最具成本效益的顺序。 搜索更大的候选空间会增加找到低成本订单的几率，但要花更多时间在查询优化上。 因此，连接顺序枚举器同时寻求将枚举的计划的数量和所选计划的最终成本最小化。
传统的DBMS使用多种连接枚举策略。 例如，系统R [18]使用动态编程来查找成本最低的左深连接树，而PostgreSQL [1]则贪婪地选择低成本的关系对，直到建立一棵树为止。 许多商业产品都允许DBA通过结构约束（例如，仅用于左侧深度的计划）或在经过一段时间后切断枚举来控制候选计划空间的大小。
不幸的是，这些启发式方法经常会错过良好的执行计划。 更重要的是，传统的查询优化器依靠静态策略，因此不会从过去的经验中学到东西。 传统系统计划一个查询，执行查询计划，然后忘记他们曾经优化过该查询。 由于缺乏反馈，查询优化器可能会反复选择相同的错误计划，而永远不会从其先前的好选择或坏选择中学习。
在本文中，我们分享了我们基于学习的优化器的愿景，该优化器利用了以往的经验，旨在学习如何更有效地（即更好的查询计划）和有效地（即更少的优化时间）优化未来的查询。 我们介绍一种基于深度强化学习（DRL）[5]的查询优化新方法，该过程是机器借助神经网络借助连续反馈来学习任务的过程。 我们认为可以利用现有的深度强化学习技术以更少的优化时间来提供更好的查询计划。
第一步，我们介绍ReJOIN，这是一个概念证明的连接顺序枚举器，完全由深度强化学习驱动。 在第2节中，我们描述ReJOIN。 在第3节中，我们提供了令人鼓舞的初步结果，这些结果表明ReJOIN在有效性和效率方面可以胜过PostgreSQL的join枚举过程。 据我们所知，这项工作是第一个使用深度强化学习做出查询优化决策的工作。 同时工作[14]正在研究深度学习方法，以学习查询优化过程中每个步骤的表示形式。 先前的自适应方法[4、7、19]已使用查询执行反馈来修复错误的统计估计。
接下来，我们介绍概念验证的深度强化学习联接顺序枚举器，称为ReJOIN。
联接枚举ReJOIN假设许多现代DBMS使用传统的基于成本的查询优化方法（例如[1，10]）。具体来说，给定一个SQL查询作为输入，连接顺序枚举器将搜索所有可能的连接顺序的子空间，并选择“最便宜”的顺序（根据成本模型）执行。此枚举不执行索引选择，联接运算符选择等。这些任务留给DBMS优化器的其他组件。联接顺序由二叉树捕获，其中每个叶节点代表一个基本关系。图1显示了关系A，B，C和D的三种可能的连接顺序。
图 1
强化学习假设[5] 智能体与环境交互。环境告诉智能体程序其当前状态st和一组可能的动作At = {a0，a1，。 。 。 }，智能体可以执行。智能体选择一个动作a∈At，基于该动作环境向智能体奖励rt。该环境还为智能体提供了新状态st + 1和新操作集At + 1。 重复此过程，直到智能体达到终端状态为止，在该状态下不再有可用的操作。 这标志着一个查询轮次的结束，然后一个新查询轮次开始。 智能体的目标是通过从经验（先前的动作，状态和奖励）中学习来最大化其对整个查询轮次的回报。 这是通过在探索新策略与利用当前知识之间取得平衡来实现的。
我们将连接顺序枚举过程抽象化为强化学习问题。 发送给优化器的每个查询都代表一个情节，并且在发送查询时ReJOIN不断学习。 除了有关查询连接和选择谓词的信息之外，每个状态还将表示二进制联接树的子树。 每个动作代表将两个子树组合成一个树。 子树可以表示输入关系或子树之间的联接。 当所有输入关系都加入时（终端状态），这一查询轮次结束。 此时，ReJOIN根据优化程序的成本模型为最终的连接顺序分配奖励。 最终的连接顺序将发送到优化器，并且生成的物理计划由DBMS执行。
ReJOIN的框架如图2所示。形式上，给定查询q，访问关系r1，r2，...。 。 。 ，rn，我们将查询的初始状态定义为s1 = {r1，r2，...。 。 。 ，rn}。该状态表示为状态向量。该状态向量通过神经网络[16]馈送，该神经网络在潜在动作上产生概率分布。任何状态的动作集Ai是从1到| si |的每个唯一有序整数对，包括：Ai = [1，| si |]×[1，| si |]。动作（x，y）∈Ai表示将si的xth和yth元素连接在一起。神经网络的输出用于选择一个动作（即新的联接），该动作被发送回环境，并转换为新的状态。选择动作（x，y）后的状态si + 1为si + 1 =（si-{si [x]，si [y]}）∪{si [x]▷◁si [y]}。新状态被馈入神经网络。每个非终端状态（部分排序）的奖励为零，而到达终端状态sf的操作的奖励（完全排序）是连接树t的成本的倒数M（t），用sf表示，即1/M（t）。智能体会定期利用其经验来调整神经网络的权重，以期获得更大的回报。
图 2
图3显示了涉及四个关系：A，B，C和D的查询的潜在轮次。初始状态为s1 = {A，B，C，D}。操作集A1包含每个有序关系对的一个元素 ，例如 （1，4）∈A1代表将A与D连接起来，（2，3）∈A1代表将B与C连接起来. 智能体选择动作（1，3），代表选择将A和C连接起来。 下一个状态是s2 = {A▷◁C，B，D}。 智能体接下来选择动作（2，3），代表选择加入B和D。下一个状态是s3 = {A▷◁C，B▷◁D}。 此时，智能体只有两个可能的选择，A3 = {（1，2），（2，1）}。 假设智能体选择了动作（1，2），则下一个状态s4 = {（A▷◁C）▷◁（B▷◁D）}表示最终状态。此时，智能体将基于成本模型对最终联接顺序的评估。
ReJOIN需要每个状态的向量表示，该向量表示有关联接树结构和联接/选择谓词的信息。接下来，我们概述了一个简单的矢量化策略，该策略可以捕获此信息，并说明即使输入数据有限，强化学习策略也可以有效。
为了捕获树结构数据，我们将每个二进制子树（即到目前为止确定的连接顺序）x∈sj编码为大小为n的行向量v，其中n是数据库中关系的总数。如果第ith个关系不在x中，则vi的值为零，否则等于1/h（i，x），其中h（i，x）是子树x中ri的关系,即为ri的高度（与根的距离） ）。在图3的示例中，倒数第二个状态的树矢量的第一行{A▷◁C，B▷◁D}对应于（A▷◁C）。第一行的第三列的值为1/2，对应于子树中高度为2的C。由于关系B未包含在子树中，因此第一行的第二列的值为零。
图 3
为了捕获有关连接谓词的关键信息，我们为每个查询轮次创建一个n×n二进制对称矩阵m。 如果存在连接ith和jth关系的连接谓词，则值mi，j为1，否则为0。 这个简单的表示捕获了可行的等联接运算。 图3示出了这种矩阵m的示例。 由于谓词A.id = B.id，因此值m2,1 = m1,2 = 1。 值m2,3 = m3,2 = 0，因为没有连接B和C的连接谓词。
选择谓词向量是k维向量，其中k是数据库中属性的总数（所有关系中属性的总数）。 当ith属性在给定查询中具有选择谓词时，ith值为1，否则为0。 这表明哪些属性不用于过滤元组。 例如，在图3中，由于谓词B.a2> 100，因此对应于B.a2的值为1。
ReJOIN依赖于策略梯度方法[22]，这是强化学习的一个特定子集。 策略梯度强化学习代理基于参数化策略πθ选择动作，其中θ是代表策略参数的向量。给定状态st和动作集At，策略πθ为At（在我们的上下文中）的每个动作输出分数 ，这是结合两个联接子树的分数）。 然后使用不同方法选择动作[5]。
强化学习旨在优化查询轮次中的策略πθ，即识别优化预期奖励Jπ（θ）的策略参数θ。 但是，奖励Jπ（θ）通常无法精确计算，因此策略梯度方法通过构造奖励梯度的估计量E来搜索最佳策略参数：E（θ）≈∇θJπ（θ） 。
给定估计值E时，当梯度∇θiJπ（θ）为正时，梯度上升方法通过将θi中的每个参数增加一个较小的值来调整初始参数θ（正梯度表示θi的值越大将增加奖励） ，当梯度为负时，将θi中的参数减小一个较小的值。
策略梯度深度学习方法（例如，[17]）将策略πθ表示为神经网络，其中θ是网络权重，因此可以有效区分πθ[16]。 图2显示了我们在ReJOIN中使用的策略网络。 当前状态的矢量化表示被馈送到状态层，在此状态层将转换每个值并将其发送到第一隐藏层。 第一个隐藏层将其数据转换并传递给第二个隐藏层，第二个隐藏层将数据传递给最终的动作层。动作层中的每个神经元都代表一个潜在的动作，并将其输出标准化以形成概率分布。 策略πθ（si，Ai）通过从该概率分布中采样来选择行动，从而平衡了搜索和开发的难度[22]。
使用前几集（查询）的样本来估计策略梯度∇θJπ（θ）。 每次轮次完成时（选择给定查询的连接顺序），ReJOIN代理都会记录新的观察值（θ，r）。 在此，θ表示该事件所用的策略参数以及收到的最终成本（奖励）r。 给定一组关于多个情节的经验，X = {（θ0，r 0），（θ1，r 1），。 。 。 ，（θ2，r 2}}，可以使用各种高级技术来估计预期奖励的梯度E（θ）[17，21]。
图 4
图 5
在这里，我们提供的初步实验表明ReJOIN可以生成成本和延迟都一样好的连接顺序（而且通常更好）作为从PostgreSQL [1]优化器生成的代码。
我们的实验利用了连接顺序基准（JOB），即先前在查询优化器评估中使用的一组查询[11]。 该基准测试包括在图4上的33个查询模板的113个查询实例：重新加入IMDB数据集。 我们已经创建了一个预加载了数据集[2]的虚拟机。 每个查询在4和17个关系之间联接。两个最大的关系包含36M和15M行。 ReJOIN经过103条查询的训练，并经过10条查询的测试。 我们的测试查询集包括一个随机选择的查询模板（模板＃1）的所有实例，以及其他六个随机选择的查询。
在具有2个核心，4GB RAM和最大1GB共享缓冲池的虚拟机上使用PostgreSQL [1]，数据库的总大小为11GB（所有主键和外键均已建立索引）。我们将PostgreSQL配置为执行生成的连接顺序，这个连接顺序是由ReJOIN代替使用自己的联接枚举器。
为了评估ReJOIN的学习收敛性，我们重复运行ReJOIN算法，并在每个轮次开始时从训练集中选择一个随机查询。结果如图4所示。x轴显示ReJOIN智能体到目前为止已学习的查询（片段）数，y轴显示所生成计划相对于PostgreSQL优化器所生成计划的成本。 例如值200％表示一个计划，其成本是PostgreSQL优化程序选择的计划的两倍。 ReJOIN从没有信息开始，因此最初的表现很差。随着观察到的情节（查询）数量的增加，算法的性能也会提高。在大约8,000个观察到的查询中，ReJOIN开始查找预测成本低于PostgreSQL优化器的计划。经过10,000次查询后，ReJOIN生成的计划的平均成本是PostgreSQL生成的计划的80％。这表明，通过足够的培训，ReJOIN可以学习生成有效的连接顺序。
为了评估ReJOIN产生的连接顺序的有效性，我们首先从103个训练查询中随机选择了10,000个以上的查询来训练我们的系统（该过程耗时约3个小时）。 然后，我们使用生成的模型为10个测试查询生成连接顺序。 对于每个测试查询，我们使用了聚合模型来生成连接顺序，但是我们没有更新模型（即，该模型没有将有关测试查询的任何信息添加到其体验集中）。 我们记录了由这些测试连接顺序产生的计划的成本（根据PostgreSQL成本模型）及其执行时间。 我们将ReJOIN与PostgreSQL和Quickpick [20]的效果进行比较，后者启发式地采样了100个半随机连接顺序，并选择了连接顺序，将其提供给DBMS成本模型后，会得出成本最低的计划。
我们首先根据成本模型评估ReJOIN枚举器产生的连接顺序。图5a显示了PostgreSQL的默认枚举过程Quickpick和ReJOIN在10个测试查询上生成的计划的成本。 x轴上的“查询XY”是指模板X的实例Y。平均而言，ReJOIN生成的连接顺序使查询计划的成本比PostgreSQL优化器低20％。 在最坏的情况下，ReJOIN的成本仅比PostgreSQL优化器（15a）高2％。 这表明ReJOIN能够学习到一种通用化的策略，该策略的性能优于或匹配PostgreSQL优化器产生的连接顺序的成本。Quickpick相对较差的性能表明ReJOIN的良好性能并不是随机带来的。
图5b显示了Quickpick和ReJOIN创建的查询计划被执行的延迟相对于由PostgreSQL创建的计划的延迟（十次执行，冷缓存）。显示了最小，最大和中位数的延迟改进。 ReJOIN的连接顺序产生的计划胜过或匹配PostgreSQL产生的计划。 因此，ReJOIN可以产生执行时间更短的计划（不仅降低了优化器成本）。Quickpick相对较差的性能表明ReJOIN并非简单地猜测随机连接顺序。
关于神经网络（通常是机器学习）的一个普遍看法是，它们需要的操作过于昂贵，无法包含在数据库内部。 在这里，我们证明了ReJOIN之类的方法实际上可以减少查询计划时间。 图5c显示了所有113个查询的平均总查询优化时间，按要连接的关系数分组。 我们含有存在策略更新或者不存在的ReJOIN计划时间。
对于PostgreSQL，正如预期的那样，查询中更多的关系会导致更长的优化时间，因为需要考虑更多的连接顺序并通过成本模型运行，但是ReJOIN可以在时间上线性地将其模型应用于关系数量：在每个关系上 一轮，将两个子树连接起来，直到产生完整的连接顺序。 结果，尽管PostgreSQL的查询优化时间增长比线性的差，但ReJOIN的查询优化时间却（相对）平稳。
策略更新的每个轮次使用PPO的额外开销相对较小，例如， <12ms。 但是，一旦ReJOIN模型充分收敛，就可以跳过策略更新，将查询计划时间再减少10％到30％，从而实现更短的查询计划时间。
我们用于连接枚举的典型强化学习方法表明，在应用深度强化学习算法来查询优化问题的空间上还有进步的空间。 总体而言，我们相信ReJOIN开辟了令人振奋的新研究途径，接下来我们将重点介绍其中的一些。
成本模型取决于基数估计，基数估计通常容易出错。 期望将执行计划的实际延迟（而不是成本模型的估计）用作奖励信号。 ReJOIN使用成本模型作为查询性能的智能体，因为它使我们能够快速训练大量查询轮次的算法-执行查询计划，尤其是早期情节中生成的不良计划会非常耗时。 我们目前正在研究通过以下方法“引导”学习过程的技术[9]：先观察标准系统（例如Postgres查询优化器），然后模仿它，然后改进模仿策略。
ReJOIN仅处理连接顺序选择，并且需要优化器选择运算符，选择索引，合并谓词等。可以通过修改操作空间以包括运算符级别的决策来开始扩展ReJOIN以处理这些问题。
