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

如何优化 SQL 连接是数据库社区数十年来一直在研究的一个大问题。近日，伯克利 RiseLab 公布了一项研究表明，深度强化学习可以被成功地应用在优化 SQL 连接上。对于大型的连接，这项技术的运行速度比传统动态规划快上 10 倍，比穷举快上 10000 倍。这篇文章将介绍 SQL 连接问题以及这项强大的优化技术。

数据库社区已经针对 SQL 查询优化问题进行了近 40 年的研究，可以追溯到 System R 的动态规划方法。查询优化的核心是连接排序问题。尽管这个问题由来已久，但仍然有很多研究项目尝试更好地理解多连接查询中的连接优化器的性能，或者解决在企业级“数据湖”中无处不在的大型连接查询问题。

在我们的论文中，我们表明了如何通过深度强化学习技术来攻克这个已经存在了数十年的挑战。我们将连接排序问题表示为马尔可夫决策过程(MDP)，然后构建了一个使用深度 Q 网络(DQN)的优化器，用来有效地对连接进行排序。我们基于 Join Order Benchmark(最近提出的工作负载，专门用于压力测试连接优化)对我们的方法进行了评估。我们只使用了适量的训练数据，基于强化学习的深度优化器的执行计划成本比所有我们能想到的成本模型最优解决方案改进了 2 倍，比下一个最好的启发式改进最多可达 3 倍——所有这些都在计划的延迟范围，比动态规划快 10 倍，比穷举快 10000 倍。

背景：连接排序为什么

强化学习是解决连接排序问题的好方法?要回答这个问题，先让我们回顾一下传统的动态规划(DP)方法。

假设一个数据库包含三张表：Employees、Salaries 和 Taxes。下面这个查询用于找出“所有 Manager 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)

这样就得到了新的一行：

这个算法遍历其他二元关系集，最终找到连接所有三张表的最佳成本。这需要在二元关系和基本关系的所有可能“left-deep”组合中取最小值：

这就是动态规划方法。请注意，J 的第二个操作数(关系的右边部分)始终是基本关系，而左边可以是中间连接结果(因此叫作“left-deep”)。这个算法的空间复杂度和时间复杂度将随着关系的数量增加呈指数级增长，这就是为什么它通常只被用于 10-15 个关系的连接查询。

通过强化学习进行连接排序

我们的主要想法如下：不使用如上所示的动态规划来解决连接排序问题，而是将问题表示为马尔可夫决策过程(MDP)，并使用强化学习(RL)来解决它，这是一种用于解决 MDP 的一般性随机优化器。

首先，我们将连接排序表示为 MDP：

• 状态，G：需要连接的剩余关系。
• 动作，c：剩余关系之外的有效连接。
• 下一个状态，G’：这是旧的“剩余关系”的集合，移除了两个关系，并添加了它们的结果连接。
• 奖励，J：新连接的估算成本。

可以简单地表示成 (G, c, G’, J) 。

我们使用 Q-learning(一种流行的 RL 技术)来解决连接排序 MDP。我们定义了 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。

（编辑：晋中站长网）

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