Learning to Optimize Join Queries With Deep Reinforcement Learning

Background

传统的多表 join 算法采用的是动态规划：

1. 从初始 query graph 开始
2. 找到 cost 最少的 join
3. 更新 query graph 直到只剩下一个节点。但这种贪心策略并不会保证一定会选到合适的 join order，因为它只直观表示了每个 join 的短期cost。例如：

动态规划的结果 cost 为 140，而最优解的 cost 为 110。

Learning to Optimize Join Queries With Deep Reinforcement Learning 论文中将 join 问题表示为马尔可夫决策过程（MDP），然后构建了一个使用深度 Q 网络（DQN）的优化器，用来有效地优化 join 顺序。

Method

将连接排序表示为 MDP：

• 状态G：a query graph
• 动作c：a join
• 下一个状态G’：join后的query graph
• 奖励J(c)：join的估算成本

用 Q-Learning 算法来解决 join 顺序 MDP。在 Q-Learning 中最关键的是得到 Q 函数 Q(G,c)，它可以知道当前 query graph 中进行每个 join 的长期cost。如果我们可以访问真正的 Q(G,c)，就可以对传统的动态规划进行改进：

1. 从初始 query graph 开始
2. 找到 Q(G,c) 值最小的 join
3. 更新 query graph 直到只剩下一个节点，从而得到最优的 join order。实际上我们无法访问真正的 Q 函数，因此，我们需要训练一个神经网络，它接收 (G,c) 作为输入，并输出估算的 Q(G,c)。在论文中算法如下，给定query：

状态 G 和动作 c 的特征化

1. query graph 中的每个关系的所有属性放入集合 A-G 中；join 左侧的所有属性放入集合 A-L 中；join 右侧的所有属性放入集合 A-R 中。并使用 1-hot 向量来编码。对于该例子，论文中表示如下：

2. 对于查询中的每个选择，我们可以获得 selectivity ∈ [0,1]（用来估计选择后存在的元组占选择前总元组的比例），我们需要根据 selectivity 的值去更新向量。例如：

3. 还可以根据在物理计划中选择的具体 join 算法去产生新的 1-hot 向量（例如，IndexJoin 为 [1 0], HashJoin 为 [0 1]）,与原向量进行串联，如下：

根据在论文 2.5 节的假设：

在这里我们就可以知道 query graph 特征 fG 为 fG = AG，join 决策特征 fc 为 fc = A-L ⊕ A-R，对于一个特定的元组（G,c）特征化为 fG ⊕ fc。

模型训练

DQ 使用多层感知机（MLP）神经网络来表示 Q 函数。它以（G,c）的最终特征化 fG ⊕ fc 作为输入。在实验中发现，两层的 MLP 可以提供最佳表现。模型使用随机梯度下降算法进行训练。

执行

训练后，在原有基础上再对多表 join 算法进行改进：

1. 从初始 query graph 开始
2. 使每个 join 特征化
3. 找到模型估计的 Q 值最小的 join（即神经网络的输出）
4. 更新 query graph 直到只剩下一个节点，从而得到最优的 join order。在执行过程中，还可以对 DQ 进行进一步微调。

Experiment Result

论文中使用了 Join Order Benchmark（JOB） 来评估 DQ。这个数据库由来自 IMDB 的 21 个表组成，并提供了 33 个查询模板和 113 个查询。查询中的连接关系大小范围为 5 到 15 个。当连接关系的数量不超过 10 个时，DQ 从穷举中收集训练数据。

将 DQ 与几个启发式优化器（QuickPick 和 KBZ）以及经典动态规划（left-deep、right-deep、zig-zag）进行比较。对每个优化器生成的计划进行评分，并与最优计划（通过穷举获得）进行比较。
此外，论文中设计了 3 个成本模型：

1. Cost Model 1（Index Mostly）：模拟内存数据库并鼓励使用索引连接
2. Cost Model 2（Hybrid Hash）：仅考虑具有内存预算的散列连接和嵌套循环连接
3. Cost Model 3（Hash Reuse）：考虑重用已构建的散列表

进行了 4 轮交叉验证后，确保仅对未出现在训练工作负载中的查询进行 DQ 评估（对于每种情况，论文中在 80 个查询上训练并测试其中的 33 个）。计算查询的平均次优性，即“成本（算法计划）/ 成本（最佳计划）”，这个数字越低越好。例如，对 Const Model 1，DQ 平均距离最佳计划 1.32 倍。结果如下：

在所有成本模型中，DQ 在没有指数结构的先验知识的前提下可以与最优解决方案一比高下。对于固定的动态规划，情况并非如此：例如，left-deep 在 CM1 中产生了良好的计划，但在 CM2 和 CM3 中效果没有那么好。同样，right-deep在 CM1 中没有竞争力，但如果使用 CM2 或 CM3，right-deep 不是最差的。需要注意的是，基于学习的优化器比手动设计的算法更强大，可以适应工作负载、数据或成本模型的变化。

此外，DQ 以比传统动态规划快得多的速度产生了良好的计划：

对于最大的连接（15），DQ 的速度是穷举的 10000 倍，比 zig-zag 快 1000 倍，比 left-deep 和 right-deep 快 10 倍。

Future work

本文研究中存在的不足：

1. 奖励值（即J(c)）依赖于数据库系统的代价模型，当代价估计错误时，算法的 join 计划无法达到最优
2. 需要大量的 query 进行训练，估计的 Q 函数的值才能趋向稳定

可以拓展的思路：
同样使用强化学习，参考于 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning，一条 join query 的执行框架如下：

查询时，Pre-Processor 首先通过一元谓词过滤基表，接着由 Join Processor 生成查询的连接顺序与执行结果，最后调用 Post-Processor 对结果进行分组、聚合与排序等操作。

Join Processor 包括 4 部分，Join Processor 将每个连接操作分为多个时间片，每个时间片首先由 Learning Optimizer 选择连接顺序，选中的连接顺序由特定的 Join Executor 执行，每次执行固定时长，并将执行结果加入结果集中。Progress Tracker 跟踪被处理的数据，最后由 Reward Calcultor 计算连接顺序的得分。当所有数据被连接后，完成连接操作。学习优化器使用强化学习领域的上限置信区间算法（UCT），在每个时间片中根据连接顺序的枚举空间生成搜索树，并选择一条路径。UCT 算法的特点即不依赖任何具体示例的参数设置，能够适用于较大的搜索空间。

该算法不需要任何查询上下文及 Cardinality 估计模型。