快1万倍！伯克利提出用深度RL优化SQL查询

数据采集。要学习 Q 函数，我们首先需要观察过去的执行数据。DQ 可以接受来自任何底层优化器的一系列 (G,c,G’,J)。例如，我们可以运行经典的 left-deep 动态规划(如背景部分所示)，并从 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，我们使用了最近发布的 Join Order Benchmark(JOB)。这个数据库由来自 IMDB 的 21 个表组成，并提供了 33 个查询模板和 113 个查询。查询中的连接关系大小范围为 5 到 15 个。当连接关系的数量不超过 10 个时，DQ 从穷举中收集训练数据。

比较。我们与几个启发式优化器(QuickPick 和 KBZ)以及经典动态规划(left-deep、right-deep、zig-zag)进行比较。我们对每个优化器生成的计划进行评分，并与最优计划(我们通过穷举获得)进行比较。

成本模型。随着新硬件的创新(例如 NVRAM)和向无服务器 RDBMS 架构(例如 Amazon Aurora Serverless)的转变，我们期望看到大量新的查询成本模型可以捕获不同的硬件特征。为了显示基于学习的优化器可以适应不同的环境，我们设计了 3 个成本模型：

• Cost Model 1(Index Mostly)：模拟内存数据库并鼓励使用索引连接。
• Cost Model 2(Hybrid Hash)：仅考虑具有内存预算的散列连接和嵌套循环连接。
• Cost Model 3(Hash Reuse)：考虑重用已构建的散列表。

从 CM1 到 CM3，成本表现出更多的非线性，向静态策略提出了挑战。

我们进行了 4 轮交叉验证，确保仅对未出现在训练工作负载中的查询进行 DQ 评估(对于每种情况，我们在 80 个查询上训练并测试其中的 33 个)。我们计算查询的平均次优性，即“成本(算法计划)/ 成本(最佳计划)”，这个数字越低越好。例如，对 Const Model 1，DQ 平均距离最佳计划 1.32 倍。结果如图 3 所示。 

图 3：不同成本模型的平均计划次优性。

在所有成本模型中，DQ 在没有指数结构的先验知识的前提下可以与最优解决方案一比高下。对于固定的动态规划，情况并非如此：例如，left-deep 在 CM1 中产生了良好的计划(鼓励使用索引连接)，但在 CM2 和 CM3 中效果没有那么好。同样，right-deep 计划在 CM1 中没有竞争力，但如果使用 CM2 或 CM3，right-deep 计划突然变得不那么糟糕。需要注意的是，基于学习的优化器比手动设计的算法更强大，可以适应工作负载、数据或成本模型的变化。

此外，DQ 以比传统动态规划快得多的速度产生了良好的计划(图 4)。

图 4：所有 113 个 JOB 查询的优化器延迟，按查询中的关系数量进行分组。误差棒表示平均值附近的±标准偏差。共进行了 5 次试验。

在大型连接机制中，DQ 实现了极大的加速：对于最大的连接，DQ 的速度是穷举的 10000 倍，比 zig-zag 快 1000 倍，比 left-deep 和 right-deep 枚举快 10 倍。性能增益主要来自神经网络提供的丰富的批处理机会——对于单个迭代中所有的候选连接，DQ 针对整个批处理调用一次 NN。我们相信，对于这样一个学习优化器来说，这是一个意义深远的性能改进：对于更大的查询或运行在专用加速器(例如 GPU、TPU)上时，它将表现出更大的优势。

概 要我们认为深度强化学习非常适合用来解决连接排序问题。深度强化学习使用数据驱动方法来调整针对特定数据集和工作负载的查询计划，并观察连接成本，而不是使用固定的启发式。为了选择查询计划，DQ 使用了能够在训练时编对态规划表的压缩版本进行编码的神经网络。

DQ 只是冰山一角，在数据库社区存在激烈的争论，围绕着如何将更多的学习(或者说是数据适应性)纳入到现有系统中。我们希望我们的工作是实现更智能的查询优化器的第一步。

（编辑：常州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!