如何优化SQLjoin是数据库社区研究了几十年的大问题。最近，BerkeleyRiseLab发表了一项研究，表明深度强化学习可以成功应用于优化SQL连接。对于大型连接，此技术的运行速度比传统动态规划快10倍，比穷举快10,000倍。本文将介绍SQL连接问题和这种强大的优化技术。近40年来，数据库社区一直致力于解决SQL查询优化问题，这可以追溯到SystemR的动态规划方法。查询优化的核心是连接排序问题。尽管这个问题由来已久，但仍有许多研究项目试图更好地理解连接优化器在多连接查询中的性能，或者解决企业“数据湖”中普遍存在的大型连接查询问题。在我们的论文中，我们展示了如何通过深度强化学习技术克服这一存在了几十年的挑战。我们将连接排序问题表述为马尔可夫决策过程(MDP)，然后使用深度Q网络(DQN)构建优化器以有效地对连接进行排序。我们根据JoinOrderBenchmark评估我们的方法，这是最近提出的一种专门用于压力测试连接优化的工作负载。我们只使用了少量的训练数据，我们基于强化学习的深度优化器的执行计划成本比我们能想到的所有成本模型解决方案好2倍，比下一个最佳启发式改进高2倍3倍-全部在计划延迟内，比动态规划快10倍，比穷举快10000倍。背景：连接排序为什么强化学习是解决连接排序问题的好方法？要回答这个问题，我们先来回顾一下传统的动态规划（DP）方法。假设一个数据库包含三个表：Employees、Salaries和Taxes。以下查询用于查找“所有经理1员工的总税额”：此查询包含三个关系连接。在下面的示例中，我们使用J(R)表示访问基本关系R的成本，使用J(T1,T2)表示连接T1和T2的成本。为简单起见，我们假设一种访问方法、一种连接方法和对称连接成本（即J(T1,T2)=J(T2,T1)）。经典的“left-deep”DP方法首先计算访问三个基本关系的最小成本，我们将结果放在一个表中：然后，它根据这些信息枚举所有二元关系。例如，在计算{E,S}连接的最佳成本时，它会查找之前的相关计算：Best({E,S})=Best({E})+Best({S})+J({E},S)这会产生一个新行：该算法迭代其他二元关系集，并最终找到连接所有三个表的最佳成本。这需要对二元关系和基本关系的所有可能的“左深”组合进行最小化：这就是动态规划方法。请注意，J的第二个操作数（关系的右侧部分）始终是基本关系，而左侧可以是中间连接结果（因此称为“left-deep”）。该算法的空间和时间复杂度会随着关系的数量呈指数增长，这就是为什么它通常只用于具有10-15个关系的连接查询。ConnectionSortingviaReinforcementLearning我们的主要思想如下：我们不使用如上所示的动态规划来解决连接排序问题，而是将问题表示为马尔可夫决策过程(MDP)并使用强化学习(RL)来解决它，这是用于解决MDP的通用随机优化器。首先，我们将连接顺序表示为MDP：状态，G：需要连接的剩余关系。action,c:剩余关系之外的有效连接。下一个状态G'：这是旧的“剩余关系”的集合，删除了两个关系并添加了它们的结果连接。奖励，J：新连接的估计成本。可以简单表示为(G,c,G',J)。我们使用Q-learning，一种流行的RL技术，来解决join-rankedMDPs。我们定义了Q函数Q(G,c)，它直观地描述了每个连接的长期成本：在当前连接决策之后我们对所有后续连接的操作的累积成本。Q(G,c)=J(c)+\min_{c'}Q(G',c')请注意，如果我们可以访问真正的Q函数，贪心连接排序是可能的：算法1从查询图开始;找到Q(G,c)***的连接；更新查询图并重复。根据贝尔曼的最终性原则，我们的算法可证明是唯一的。该算法的迷人之处在于它的计算复杂度为O(n^3)，虽然仍然很高，但远低于动态规划的指数级运行时复杂度。图1：使用神经网络逼近Q函数。输出的意思是“如果我们在当前查询图G上做一个连接c，最小化长期连接计划的成本是多少？”当然，在实践中我们无法获得真正的Q函数，需要对其进行近似。为此，我们使用神经网络(NN)来学习Q函数并将其称为深度Q网络(DQN)。这种技术与用于学习Atari游戏专家玩家能力的技术相同。总而言之，我们的目标是训练一个以(G,c)作为输入并输出估计的Q(G,c)的神经网络，见图1。深度强化学习优化器DQ现在介绍我们的深度强化学习优化器DQ。数据采集??。要学习Q函数，我们首先需要观察过去的执行数据。DQ可以接受来自任何底层优化器的(G,c,G',J)序列。例如，我们可以运行经典的左深度动态规划（如背景部分所示）并从DP表计算一系列“连接轨迹”。完整轨迹中的元组看起来像(G,c,G',J)=({E,S,T},join(S,T),{E,ST},110)，表示初始查询图（状态）开始并将S和T连接在一起（动作）。我们使用J作为连接的估计成本，但如果数据是从真实的数据库执行中收集的，我们也可以使用实际的运行时间。状态和动作的表征。由于我们使用神经网络来表示Q(G,c)，因此我们需要将状态G和动作c作为固定长度的特征向量输入网络。DQ的特征化方案很简单：我们使用1-hot向量来编码(1)查询图中存在的所有属性的集合，包括模式中的所有属性，(2)连接左侧的参与属性，(3)连接右边的属性。如图2所示。图2：查询及其相应的特征化。假设一个数据库包含三个表Employees、Positions和Salaries。该图显示了部分连接和完全连接。(G,c)的最终特征向量是A_G（查询图的属性）、A_L（左边的属性）和A_R（右边的属性）的串联。虽然这个方案非常简单，但我们发现它的表现力足够了。请注意，我们的方案（和学习网络）假设有一个固定的数据库，因为它需要知道确切的属性集和表格。神经网络训练和规划。默认情况下，DQ使用简单的两层全连接网络，使用标准随机梯度下降进行训练。经过训练后，DQ可以接受一个纯文本的SQL查询，将其解析成一个抽象语法树，对树进行表征，并在每次对候选连接进行评分时调用神经网络（即在算法1的步骤2中调用神经网络在）。***，可以使用实际执行的反馈定期重新调整DQ。评估为了评估DQ，我们使用最近发布的JoinOrderBenchmark(JOB)。该数据库由来自IMDB的21个表组成，提供33个查询模板和113个查询。query中的joinrelationshipsize范围为5~15，当connectionrelations的个数不超过10个时，DQ从exhausted中收集训练数据。比较。我们与几种启发式优化器（QuickPick和KBZ）以及经典动态规划（左深、右深、锯齿形）进行了比较。我们对每个优化器生成的计划进行评分，并将它们与最佳计划（我们通过耗尽获得）进行比较。成本模型。随着新硬件（例如NVRAM）的创新和向无服务器RDBMS架构（例如AmazonAuroraServerless）的转变，我们预计会看到大量捕获不同硬件特征的新查询成本模型。为了表明基于学习的优化器可以适应不同的环境，我们设计了3个成本模型：成本模型1（主要是索引）：模拟内存数据库并鼓励使用索引连接。成本模型2（混合哈希）：仅考虑具有内存预算的哈希连接和嵌套循环连接。成本模型3（哈希重用）：考虑重用已经构建的哈希表。从CM1到CM3，成本表现出更多的非线性，对静态策略提出了挑战。我们执行了4轮交叉验证，以确保仅针对训练工作负载中不存在的查询对DQ进行评估（对于每种情况，我们训练了80个查询并测试了其中的33个）。我们将查询的平均次优性计算为“Cost(algorithmplan)/Cost(***plan)”，数字越小越好。例如，对于Const模型1，平均DQ与最佳计划相差1.32倍。结果如图3所示。图3：不同成本模型的平均计划次优性。在所有成本模型中，DQ可以在没有指数结构先验知识的情况下与最佳解决方案竞争。固定动态规划的情况并非如此：例如，left-deep在CM1中产生了良好的计划（鼓励使用索引连接），但在CM2和CM3中却不太好。同样，右深计划在CM1中没有竞争力，但如果您使用CM2或CM3，右深计划突然变得不那么糟糕了。需要注意的是，基于学习的优化器比手动设计的算法更健壮，并且可以适应工作负载、数据或成本模型的变化。此外，DQ生成好的计划的速度比传统的动态规划快得多（图4）。图4：所有113个JOB查询的优化器延迟，按查询中的关系数分组。误差条表示围绕平均值的±标准偏差。总共进行了5次试验。在largejoin机制中，DQ实现了极大的提速：对于最大join，DQ比穷举枚举快10000倍，比zig-zag快1000倍，比left-deep和right-deep枚举快10倍。性能提升主要来自神经网络提供的丰富的批处理机会——对于单次迭代中的所有候选连接，DQ为整个批处理调用一次神经网络。我们相信，对于学习型优化器来说，这是一个意义深远的性能改进，它将胜过更大的查询或在专用加速器（例如GPU、TPU）上运行。总结我们认为深度强化学习非常适合解决连接排名问题。深度强化学习使用数据驱动的方法来调整特定数据集和工作负载的查询计划，并观察连接成本，而不是使用固定的启发式方法。为了选择查询计划，DQ使用能够在训练时对状态计划表的压缩版本进行编码的神经网络。DQ只是冰山一角，数据库社区围绕如何将更多的学习（或数据适配）纳入现有系统展开了激烈的争论。我们希望我们的工作是迈向更智能的查询优化器的第一步。
