快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。

（编辑：河北网）

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