RLO:一个基于强化学习的连接优化方法
发布时间：2021-06-27 09:27
连接优化是数据库领域最重要的研究问题之一.传统的连接优化方法一般应用基础启发式规则,他们通常搜索代价很高,并且很难发现最优的执行计划.主要原因有两个:（1）这些基于规则的优化方法只能探索解空间的一个子集,（2）他们没有利用历史信息,不能够很好地衡量执行计划的代价,经常重复选择相同的糟糕计划.为了解决以上两个问题,我们提出RLO （reinforcement learning optimization）,一个基于强化学习的连接优化方法.我们将连接优化问题建模成马尔可夫（Markov）决策过程,并且使用深度Q-学习来估计每一种可能的执行计划的执行代价.为了进一步增强RLO的有效性,我们提出了基于树形结构的嵌入方法和集束搜索策略来尽量避免错过最好的执行计划.我们在Apache Calcite和Postgres上实现了RLO.实验表明:（1）在Apache Calcite上,与一系列剪枝的启发式算法相比, RLO搜索计划的效率为它们的1056倍,并且生成的计划能更快地执行（80%的加速）;（2）与原生的Postgres相比, RLO搜索计划的效率是其14倍,并且在端到端的...
【文章来源】：中国科学:信息科学. 2020,50(05)北大核心CSCD
【文章页数】：12 页
【部分图文】：
(网络版彩图)RLO优化器框架
(5)最后优化器按传统方法[3]添加Agg,Group等计划节点,便得到最终的物理计划,交由执行器执行,并返回查询结果.在这个过程中,我们可以收集实际的执行数据,对神经网络进行微调(fine-tuning)[15],实现从反馈中学习.接下来,我们按照以上的执行步骤依次介绍:状态与动作的表征(3.3小节),Q值的计算(3.4小节),搜索新动作(3.5小节)以及网络微调(3.6小节).
其次,RLO算法的搜索效率在关系数目较多的时候占有较大的优势.例如对于较多的关系数,RLO和DQ算法实现了极大的提速:RLO最多可以比EX快104倍,比ZZ快100倍,比LD,RD快10倍以上.平均来说,当关系数大于6时,RLO算法比EX快2867倍,比ZZ快56倍,比LD,RD快5.6倍.原因与我们之前的分析相同,RLO具有贪心算法的时间复杂度,远快于动态规划.另外,GD,QP一直保持着最小的优化时间,这是因为它们剪枝的策略太严格,忽略了大部分的解空间,这会导致较差的执行效率(参见4.2.2小节).最后,RLO的搜索效率略差于DQ算法.例如RLO的平均搜索时间为DQ的1.1倍.这是因为RLO采用了集束搜索策略,即RLO在每步决策时保存多个动作.但是带来的好处是RLO的执行效率更高(参见4.2.2小节).
本文编号：3252587
【文章来源】：中国科学:信息科学. 2020,50(05)北大核心CSCD
【文章页数】：12 页
【部分图文】：
(网络版彩图)RLO优化器框架
(5)最后优化器按传统方法[3]添加Agg,Group等计划节点,便得到最终的物理计划,交由执行器执行,并返回查询结果.在这个过程中,我们可以收集实际的执行数据,对神经网络进行微调(fine-tuning)[15],实现从反馈中学习.接下来,我们按照以上的执行步骤依次介绍:状态与动作的表征(3.3小节),Q值的计算(3.4小节),搜索新动作(3.5小节)以及网络微调(3.6小节).
其次,RLO算法的搜索效率在关系数目较多的时候占有较大的优势.例如对于较多的关系数,RLO和DQ算法实现了极大的提速:RLO最多可以比EX快104倍,比ZZ快100倍,比LD,RD快10倍以上.平均来说,当关系数大于6时,RLO算法比EX快2867倍,比ZZ快56倍,比LD,RD快5.6倍.原因与我们之前的分析相同,RLO具有贪心算法的时间复杂度,远快于动态规划.另外,GD,QP一直保持着最小的优化时间,这是因为它们剪枝的策略太严格,忽略了大部分的解空间,这会导致较差的执行效率(参见4.2.2小节).最后,RLO的搜索效率略差于DQ算法.例如RLO的平均搜索时间为DQ的1.1倍.这是因为RLO采用了集束搜索策略,即RLO在每步决策时保存多个动作.但是带来的好处是RLO的执行效率更高(参见4.2.2小节).
本文编号：3252587
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3252587.html
