Efficient Join Order Selection Learning with Graph-based Representation

连接顺序选择在DBMS查询优化中起着重要的作用。该问题旨在寻找代价最小的最优连接顺序，由于搜索空间呈指数级增长，通常成为NP-hard问题。最近的高级研究试图使用深度强化学习(DRL)来生成比传统查询优化器提供的连接计划更好的连接计划。然而，基于深度强化学习的方法需要耗时的训练，不适用于需要频繁周期性再训练的在线应用。本文提出了一种新的学习框架JOGGER (efficient Join Order selection learninG with Graph-basEd Representation)。首先根据主-外键关系构建模式图，从模式图中学习表的表示，以捕获表之间的相关性;第二个组件是状态表示，其中使用图卷积网络对查询图进行编码，并设计了基于定制树的注意力模块对连接计划进行编码。为了加快深度强化学习训练过程的收敛速度，采用课程学习的思想，根据查询难度的高低，将查询增量地添加到训练集中。在JOB和TPC-H数据集上进行了大量实验，验证了所提方法的有效性和高效性。

 

 为了解决基于深度强化学习方法效率低下的问题，本文提出了一种基于图表示的高效连接顺序选择学习(JOGGER)框架。解决低效问题的一个直观想法是在不损害状态表示的表达能力的情况下减少深度神经网络的参数，这是深度强化学习的一个关键组成部分。为此，该框架包含两个基于图的组件，以学习参数较少的信息表示。第一个组成部分是表表示学习，可以很好地捕获表之间的相关性。基于原生数据库的主-外键关系构建模式图，利用DeepWalk[22]算法学习表的表示。与以往研究中简单的列嵌入连接相比，这些学习到的表表示捕获了表之间的相关性，包含了更多连接的语义信息。状态表示的第二个组件利用图卷积网络对查询进行编码，并包含一个基于树的注意力模块来表示连接计划。这两个组件都具有相对较小的网络规模和较少的参数，其训练效率很高。