RLO:一个基于强化学习的连接优化方法

连接优化是数据库领域最重要的研究问题之一.传统的连接优化方法一般应用基础启发式规则,他们通常搜索代价很高,并且很难发现最优的执行计划.主要原因有两个:(1)这些基于规则的优化方法只能探索解空间的一个子集,(2)他们没有利用历史信息,不能够很好地衡量执行计划的代价,经常重复选择相同的糟糕计划.为了解决以上两个问题,我们提出RLO(reinforcement learning optimization),一个基于强化学习的连接优化方法.我们将连接优化问题建模成马尔可夫(Markov)决策过程,并且使用深度Q-学习来估计每一种可能的执行计划的执行代价.为了进一步增强RLO的有效性,我们提出了基于树形结构的嵌入方法和集束搜索策略来尽量避免错过最好的执行计划.我们在Apache Calcite和Postgres上实现了RLO.实验表明:(1)在Apache Calcite上,与一系列剪枝的启发式算法相比,RLO搜索计划的效率为它们的10~56倍,并且生成的计划能更快地执行(80%的加速);(2)与原生的Postgres相比,RLO搜索计划的效率是其14倍,并且在端到端的执行中达到12.9%的加速.