【导读】
本篇博客解说的是 2020 年由清华大学李国良传授团队发表在 ICDE 上的论文，介绍它所提出的算法与试验后果，并结合实际状况给出一些思考。
原文链接：
http://dbgroup.cs.tsinghua.edu.cn/ligl/papers/icde2020-learnedjoinorder.pdf
Part 1 – 背景
连贯程序抉择 (Join Order Selection, JOS) 是一个为 SQL 查问寻找最佳连贯程序的问题。作为数据库查问优化器的次要关注点曾经被宽泛钻研了几十年。这个问题很难，因为它的解空间很大，彻底遍历解空间来寻找最佳连贯程序的代价是十分低廉的。传统的办法通常基于基数预计和代价模型，与启发式剪枝相结合，通过一些剪枝技术来放大搜寻可能的连贯程序的解空间。
只管通过几十年的致力，传统的优化器在解决简单的 SQL 查问时依然存在低可扩展性或低准确性的问题。基于动静布局 (DP) 的算法通常会抉择最优计划，但代价十分低廉。启发式办法，如 GEQO、QuickPick-1000 和 GOO，能够更快地计算打算，但往往产生蹩脚的打算。
近年来，基于机器学习 (ML) 和深度学习 (DL) 的基于学习的优化器 (Learned Optimizer) 办法在数据库界越来越受欢迎。特地是基于深度强化学习 (Deep Reinforcement Learning, DRL) 的办法，如 ReJOIN 和 DQ，曾经显示出了令人满意的后果 —— 它们能够生成与原生查问优化器一样好的打算，但在学习后执行的速度相比原生查问优化器更快。然而，现有的基于 DRL 的学习优化器将连贯树编码为固定长度的向量，其中向量的长度由数据库中的表和列决定。这将导致两个问题：
- 这些向量不能捕捉连贯树的构造信息，可能会导致连贯程序抉择到一个蹩脚的打算 ;
- 当数据库模式发生变化，如增加列 / 表或多别名表名时，这个基于学习的优化器将会生效，这须要一个新的不同长度的输出向量，而后再从新训练神经网络。
在本文中，作者提出了一种新的基于学习的优化器 RTOS，它应用强化学习和树状构造长短期记忆 (tree-LSTM) 来进行连贯程序抉择。RTOS 对现有的基于 DRL 的办法进行了两方面的改良:
(1) 采纳图神经网络来捕捉连贯树的构造 ;
(2) 反对对数据库模式和多别名表名的批改。
在 Join Order Benchmark (JOB) 和 TPC-H 上的大量试验表明，RTOS 优于传统优化器和现有的基于 drl 的学习优化器。
Part 2 – 相干工作
DRL，深度强化学习相干概念：
对于强化学习的概念性解释在新近的博客《Constraint-aware SQL Generation Using Reinforcement Learning》中也有提到，这里不再反复赘述 Agent、Environment、State、Action、Reward 等概念，感兴趣的读者也可查找相干材料加深了解。
在 RTOS 中 Agent 对应优化器，通过与 Environment(对应 DBMS) 的试错交互从反馈中学习。对于图中所示的一条 SQL 查问语句，随着强化学习过程的推动会进入不同的 State(每个 State 对应着连贯打算)。RTOS 读取以后打算并利用 Tree-LSTM 来计算预计的长期 Reward(例如，哪个表应该连接起来以使以后状态更残缺)。而后它会抉择具备最大 Reward(对应最小 Cost) 的预期最佳 Action。当所有的表都被连贯 (即，导出一个残缺的连贯打算) 时，连贯打算将被发送到 DBMS 执行。
DQ，《Learning to Optimize Join Queries With Deep Reinforcement Learning》中提出的基于 DRL 学习优化器办法：
DQ 将连贯程序抉择问题形象为一个马尔可夫决策过程。DQ 应用了 DQN(Deep Q Network) 作为强化学习模型来领导连贯程序的抉择，因为 DQN 中的代价预计函数 Q-function 计算代价过高，因而应用一个两层的 MLP(Multilayer Perceptron) 来学习 Q-function。神经网络的输出是以后的 State，包含了 SQL 语句中的查问信息以及通过连贯左侧右侧状态示意的连贯操作信息。
REJOIN，《Deep Reinforcement Learning for Join Order Enumeration》中提出的基于 DRL 学习优化器办法：
ReJOIN 次要应用了邻近策略优化算法 (Proximal Policy Optimization) 来领导连贯程序的抉择。其中的要害组成是一个用于策略选取的神经网络。这个神经网络通过输出向量化的状态信息进行训练，这些信息蕴含：由深度信息组成的树结构向量、连贯谓词向量和选择性谓词向量。对于不同的 SQL 语句而言，存在不同的神经网络参数和 Reward，ReJOIN 会依据这条 SQL 语句之前的参数和 Reward，来估算当前的 Reward，从而达到对测试集中的 SQL 语句进行连贯程序抉择的目标。
现有基于 DRL 办法的有余：
假如一个数据库有 4 个表 T1、T2、T3、T4。DQ 应用独热编码 (1 示意表在树中，否则为 0) 来编码连贯树：图中能够发现 ((T1,T2), T3) 和 ((T1,T3),T2) 具备雷同的特征向量 [1,1,1,0]。ReJOIN 应用连贯表的深度结构特征向量：图 (b) 中能够发现，每个表的深度是 d = 2，((T1,T2),(T3 T4)) 和 ((T1, T3), (T2,T4)) 具备雷同的特征向量 [1/4,1/4,1/4,1/4]。
Part 3 – RTOS 框架
对于上述提到的基于 DRL 的学习优化器办法，因为它们无奈捕捉连贯树的结构特征，进而导致无奈总是取得代价低、执行工夫短的计划。此外这些办法无奈够适应一些扭转数据库模式的操作，如增加列 / 表或多别名表名后，须要从新对神经网络进行训练。因而本文作者提出了 RTOS，致力于捕获连贯树的结构特征，对打算进行更好的预计失去执行工夫低的打算，同时可能更快的适应一些会改变数据库有的操作。
整个 RTOS 框架由两局部组成：DRL Optimizer 和 DBMS。
- DRL Optimizer 中蕴含 State、Optimizer 和 Memory Pool。State 保护连贯过程的以后状态信息，具体内容在 Part4 局部解释；Optimizer 对应于 RL 中的 Agent，它是整个零碎的外围局部。对于给定的状态，能够将每个候选连贯条件视为一个 Action；Memory Pool 记录 RTOS 生成的打算的状态和来自 DBMS 的反馈。
- DBMS 用于为 RTOS 生成的连贯打算进行开销估算。RTOS 为给定的查问生成一个连贯打算，而后将其传递给 DBMS，例如 PostgreSQL。咱们应用 DBMS 中的两个组件，Estimator 和 Executor。Estimator 能够给出打算的 Cost，应用统计数据来估算开销，而不须要执行。而 Executor 用户取得打算理论执行的 Latency。
另外，在模型训练方面，RTOS 应用了两阶段训练的办法。具体来说，先用 Cost 作为反馈来训练失去开销较低的模型；再用实在执行的 Latency 作为反馈来调整模型参数。
Part 4 – States 示意
State 的示意由三局部组成：
- 输出 SQL 查问的示意：用于形容查问的全剧信息，通过神经网络进行示意，蕴含了查问须要连贯的表以及查问中的谓词信息等。
- 表和列的示意：通过神经网络示意查问中的表和列信息，根据谓词计算特色，对参加计算的列进行示意，而后通过池化失去表的示意。
- 连接数和连贯的示意：通过多种 Tree-LSTM 的组合示意的连贯树和连贯状态信息。
前两种信息蕴含了之前办法：DQ，ReJOIN 中提到的特征向量信息，最初一种示意保留了连贯程序以及残缺的连贯树的构造信息。通过神经网络来示意的状态信息能够实现在须要批改数据库模式，例如新减少一列或者一个表时，能够通过申请新的参数来实现，而不须要从新训练模型。
RTOS 强化学习策略：
本文应用了 DQN 的深度强化学习办法，通过设计一个 Q-network 来预计每个状态的 Q 值。在对训练的反馈进行收集时，因为 Latency 须要理论执行 SQL 查问来获取，收集的代价较高。而 Cost 作为 Latency 的近似的预计，不须要理论执行 SQL 查问，收集的代价较低，并且能够实现和 Latency 一样为领导连贯程序抉择。因在 RTOS 的强化学习的反馈和训练的过程分为两个阶段：
第一阶段，应用 SQL 语句的 Cost 作为反馈，生成大量的训练数据，使得 RTOS 的基于 DRL 的学习优化器可能达到传统办法，例如动静布局雷同的成果，抉择出 Cost 较低的连贯程序的打算。
第二阶段，应用理论执行 SQL 语句失去的 Latency 作为反馈微调 RTOS 的模型。通过理论的 Latency 微调能够改正 RTOS 中对 Cost 预计谬误的连贯程序的打算。即体现为估算的 Cost 值很高而理论执行的 Latency 较低的打算，反之亦然。
Part 5 – 试验后果
论文基于 PostgreSQL 构建了 RTOS，试验采纳的 benchmark 是 JOB(Join Order Benchmark) 和 TPC-H。JOB 是一个基于 IMDB 的实在数据集，提供实在的工作负载，它有来自 33 个模板的 113 个查问，蕴含了 3.6GB 的数据 (计算索引时为 11GB) 和 21 张表。TPC-H 是一个规范的行业数据库基准测试，有 8 张表。论文应用了 22 个模板生成了 4GB 数据和 110 个查问。除了上述提到的 baseline(例如 DQ，ReJOIN，DP) 以外，论文还比拟了 SkinnerDB(一种基于强化学习策略的办法) 和 QuickPick(一种贪婪算法)。试验后果如下：
COST 后果：
LATENCY 后果：
JOB 数据集上后果：
第一个指标：论文以 DP 作为基线，并依照之前的工作报告其余办法的 MRC(mean relative cost, 均匀绝对老本)，其中 MRC = 1 示意与 DP 性能雷同。察看 Cost 和 Latency 的后果能够发现，RTOS 在 Cost 上要优于其余四种办法，且简直与 DP 相等，在 Latency 更佳，是所有办法中提早最低的。
第二个指标：论文把数据集中的查问依照模板进行分类，计算 GMRL(Geometric Mean Relevant Latency, 几何平均相干提早)，从图 9 中能够发现，大多数状况下 RTOS 的性能都不弱于 DP，且优于其余办法。对于 T20,T26,T28,T29 等 RTOS 的性能要远远好于 DP，是因为试验数据中的测试模板少数是比拟长或者是带有多别名的查问，传统的开销模型往往会呈现估算不精确的问题，导致基于 Cost 抉择出的打算可能不是最优，而 RTOS 能够解决这一问题，通过从查问执行的 latency 中进行学习，能够修改抉择出的打算，实现更高性能。
TPC-H 数据集上后果：
图 10 显示了 TPC-H 不同模板上的，图中没有展现 DRL 办法与 DP 办法执行雷同的模板，以取得更好的视图。能够发现对于所有模板，RTOS 生成的布局并不比 DP 差 (在 GMRL= 1 处的水平线)，也比其余办法好。
Part 6 – 总结与思考
本文介绍了将机器学习利用在连贯程序抉择问题上的办法：应用 Tree-LSTM 学习连贯打算的树形构造的 RTOS。首先，RTOS 应用了深度强化学习技术解决 JOS 问题，在此基础之上，采纳了 Tree-LSTM 模型为连贯状态进行编码。基于前两个工作设计了基于 DRL 的学习优化器，利用 SQL 解析的常识、DRL 的连贯程序抉择、DNN 的打算代价估算，能够在老本和提早两个基准上生成良好的打算；并通过证实了该办法可能很好地学习连贯树的构造，获取连贯操作的信息。论文还证实，该代价能够事后训练神经网络，缩小提早调优工夫。然而，论文中有提到，在理论应用场景下还存在一些问题，例如：训练工夫过长、不能依据不同数据库状态适应性的抉择连贯程序等问题。