VLDB19 ｜ Neo： A Learned Query Optimizer

Neo 全称 Neural Optimizer，是一个基于深度神经网络设计的优化方案。NEO 使用 Postgres 的优化器作为 bootstrap，在此基础上利用强化学习+DNN模型做迭代改进，能获得比肩商业数据库的性能。

下图是 Neo 的系统结构，它替换了 DBMS 中的优化器部分。主要流程如下：

1. 使用一个“弱”的优化器（比如 PG 的优化器）生成一个初始执行计划，称为 bootstrap
2. Experience 表示一个（执行计划 -> latency）的集合，这是训练样本
3. Featurizer 抽取两种类型的特征：Query-level 特征、(Partial) Plan-level 特征
4. 用抽取到的特征训练模型 Value Model，建立 plan -> latency 的预测模型
5. 在这个模型上做 Plan Search，这里用的是简单的贪心搜索，选出一个执行计划

Query-level 编码（也就是特征抽取）文中给出了两个方法，核心目的是把 Query 中的各种 predicate 都表示出来。文中先说了一种简单的编码，又给出了一种复杂的编码，后者中借鉴 word2vec 模型来捕捉数据表 rows 之间的相关性，显然会效果更好点（当然训练也要多了一步）。

(Partial) Plan-Level 编码要简单些，文中阐述了对 SPJ query 的编码。注意 Plan 编码的输出是一个 tree of vector！（因为 plan 就是 tree 结构的）这个结构比较少见，所以后边会用对应 tree 结构的 DNN 来处理它。Partial Plan（Plan Tree 的某些子树）也会参与训练，不过它的目标 latency 是所有包含这个 subplan 的 plan 的延迟的最小值。

Value Model，也就是如何预测一个 Plan 的 latency。这也就相当于 CBO 优化器中的 Cost，只不过 Cost 是人为设计的，而 latency 是系统根据实际运行情况观察得到的。

总之，之前的 (Partial) Query 和 Plan 的编码会被 feed into 下面这个 DNN 网络里。最后预测出一个 latency。评测中发现这个网络收敛速度还不错，100次迭代的效果就很好了。

最后是 Plan Search，它会维护一个最小堆结构，priority=Value Model 预测的 latency。每次把堆顶的 plan 取出来，找到它所有可能的 Children —— 也就是所有包含这个 subplan 的 subplan，选出 children 中的最小值再放进堆中。如此往复，直到选出一个完整的 plan。

Evaluation 环节，对于三个数据集 JOB，TPC-H 和一个合作企业提供的 2TB 数据，作者用 PG 优化器做 bootstrap，然后对每个查询迭代 100 次，得到了相当 promising 的结果，“基本和商业数据库一样好，有时甚至超过”。

局限性总结：注意测试中使用的 value model 需要不断迭代，显然对于 ad-hoc 查询这个方法就就没有帮助了。另外训练 word2vec 不知道代价有多高（类似于 analyze） 。不过总的来说，结果还是很令人激动的。