NEO: A Learned Query Optimizer 论文

摘要：查询优化是数据库系统中最具挑战性的问题之一。尽管在过去几十年中取得了进展，查询优化器仍然是非常复杂的组件，需要针对特定的工作负载和数据集进行大量的手动调优。由于这一缺点，并受到将机器学习应用于数据管理挑战的最新进展的启发，我们引入了 Neo (Neural Optimizer)，这是一种基于学习的新型查询优化器，它依赖于深度神经网络来生成查询执行计划。Neo 从现有的优化器中引导其查询优化模型，并继续从传入的查询中学习，以其成功为基础，从失败中学习。此外，Neo 自然地适应底层数据模式，并且对估计误差具有鲁棒性。实验结果表明，即使从 PostgreSQL 这样的简单优化器启动，Neo 也可以学习一个模型，提供与最先进的商业优化器相似的性能，在某些情况下甚至超过它们。

介绍

面对大量机器学习的成功案例，每个数据库研究人员可能都想知道是否有可能学习一个查询优化器。查询优化器是在数据库系统中实现良好性能的关键，可以将查询执行速度提高几个数量级。然而，今天构建一个好的优化器需要成千上万的人-工程-小时，并且是一门只有少数专家完全掌握的艺术。更糟糕的是，查询优化器需要进行冗长的维护，特别是当系统的执行和存储引擎不断发展时。因此，没有一个免费的开源查询优化器能达到 IBM、Oracle 或 Microsoft 提供的商业优化器的性能。

由于查询优化的启发式性质，已经有许多尝试将学习应用于查询优化器。例如，大约在 20 年前，人们提出了 DB2 的学习优化器 Leo[53]。随着时间的推移，Leo 通过调整基数估计从错误中吸取教训。然而，Leo 仍然需要人工设计的成本模型、精心挑选的搜索策略和大量开发人员调整的启发式方法。重要的是，Leo 只改进了它的基数估计模型，而不能基于数据进一步优化它的搜索策略(例如，为连接顺序选择考虑基数估计中的不确定性)。

最近，数据库社区已经开始探索如何使用神经网络来改进查询优化器[36,60]。这项工作的大部分都集中在用学习模型替换优化器的组件上。例如，DQ[25]和 ReJOIN[35]使用强化学习结合传统的人工工程成本模型来自动学习搜索策略并探索可能的连接排序空间。这些论文表明，在给定的成本模型上，学习搜索策略可以优于传统的启发式策略。此外，除了成本模型之外，这些系统还依赖于启发式方法来进行基数估计、物理算子选择和索引选择。

其他方法展示了如何使用机器学习来获得更好的基数估计[22,28,43,44]。然而，没有人证明他们改进的基数估计实际上会带来更好的查询计划。改善基数估计的平均误差相对容易，但对于实际改善查询计划的情况，比改进估计要困难得多[27]。此外，与连接顺序选择不同，选择连接算子(例如，散列连接、合并连接)和选择索引不能完全简化为基数估计。SkinnerDB[56]的研究表明，自适应查询处理策略可以从强化学习中受益，但它需要一个专门的(自适应)查询执行引擎，不能从算子流水线中受益。

在本文中，我们介绍了 Neo(神经优化器)，这是一种学习查询优化器，与最先进的商业优化器(Oracle 和 Microsoft)相比，它在自己的查询执行引擎上实现了类似或改进的性能。给定一组查询重写规则以确保语义正确性，Neo 学会了对连接顺序、算子和索引选择做出决策。Neo 使用强化学习优化这些决策，根据用户的数据库实例进行调整，并根据实际查询延迟做出决策。

Neo 的设计模糊了传统查询优化器的主要组件之间的界限：基数估计、成本模型和计划搜索算法。Neo 没有明确地估计基数或依赖于手工制作的成本模型。Neo 在一个价值网络中结合了这两个功能，这是一个神经网络，它采用部分查询计划并预测完成该部分计划可能产生的最佳预期运行时间。在价值网络的指导下，Neo 在查询计划空间中执行简单的搜索以做出决策。当 Neo 发现更好的查询计划时，Neo 的价值网络会得到改进，将搜索重点放在更好的计划上。这随后导致对价值网络的进一步改进，从而产生更好的计划，等等。这个值迭代[7]的强化学习过程一直持续到 Neo 的决策策略收敛为止。

Neo 需要克服几个关键的挑战。首先，为了自动捕获树结构查询计划中的直观模式，我们设计了一个价值网络，一个深度神经网络模型，使用树卷积[40]。其次，为了确保值网络理解给定数据库的语义，我们开发了行向量，这是一种通过使用底层数据库中的数据自动表示查询谓词语义的特性。第三，我们通过使用一种称为“从演示中学习”的技术克服了强化学习臭名昭著的样本低效问题[18,36]。最后，我们将这些方法集成到一个能够构建查询执行计划的端到端强化学习系统中。

虽然我们相信 Neo 是向前迈出的重要一步，但 Neo 仍然有许多重要的局限性。首先，Neo 需要关于查询重写规则的先验知识(以保证正确性)。其次，我们将 Neo 限制为 select-project-equijoin-aggregate 查询。第三，我们的优化器还不能从一个数据库泛化到另一个数据库，因为我们的特性是特定于模式的——然而，Neo 可以泛化到不可见的查询(包含任意数量的已知表)。第四，Neo 需要一个传统的查询优化器来引导它的学习过程(尽管这个优化器可以很简单)。

有趣的是，Neo 会自动适应输入精度的变化。此外，Neo 可以根据客户偏好进行调整(例如，在最坏情况下的性能与平均性能之间进行权衡)，这些调整对于更传统的查询优化器来说并不是微不足道的。

我们认为 Neo 代表了构建完全可学习的优化器的一个进步。据我们所知，Neo 是第一个以端到端方式(即从查询延迟开始)构建查询执行计划的完全学习系统(对查询重写规则取模)。Neo 已经可以用来提高成千上万依赖于 PostgreSQL 和其他开源数据库系统(如 SQLite)的应用程序的性能。我们希望 Neo 能够激励许多其他数据库研究人员以新的方式将查询优化器和学习系统结合起来进行实验。

综上所述，我们做出了以下贡献：

1. Neo，一个端到端的查询优化学习方法，包括连接顺序、索引和物理算子选择。

2. 我们表明，在使用样本查询工作负载进行训练后，Neo 甚至能够泛化到以前没有遇到过的查询。

3. 我们评估了查询编码技术，并提出了一种新的查询编码技术，它隐式地表示数据库内的相关性。

4. 我们表明，经过短时间的训练，Neo 能够在各自的执行引擎上实现与 Oracle 和 Microsoft 的查询优化器相当的性能。

接下来，在第 2 节中，我们将概述 Neo 的学习框架。第 3 节描述了 Neo 如何表示查询和查询计划。第 4 节解释 Neo 的核心学习组成部分——价值网络。第 5 节描述了行向量，这是底层数据库的一种可选的学习表示，可以帮助 Neo 理解用户数据中的相关性。我们在第 6 节对 Neo 进行了实验评估，在第 7 节讨论了相关工作，并在第 8 节给出了结束语。

学习框架概述

接下来我们讨论 Neo 的系统模型，如图 1 所示，以及整体强化学习策略。Neo 分为两个阶段：初始阶段，从专家优化器收集专业知识；运行时阶段，处理查询。

• Expertise Collection

在第一个阶段，称为 Expertise, Neo 从传统的查询优化器生成经验，如[36]中提出的。Neo 假设存在一个由代表用户总工作负载和底层引擎功能的查询组成的示例工作负载(即，执行一组具有代表性的算子)。此外，我们假设 Neo 可以访问一个简单的，传统的基于规则或成本的专家优化器(例如，Selinger [51]， PostgreSQL[3])。Neo 使用此优化器仅为示例工作负载中的每个查询创建查询执行计划(QEPs)。这些选定的计划 QEPs，连同它们的延迟，被添加到 Neo 的经验集(一组计划/延迟对)中，用作模型训练阶段的起点。请注意，专家优化器可能与底层执行引擎无关。

• Model Building

根据收集到的经验，Neo 建立了一个初始的价值模型。价值模型是一种深度神经网络，用于预测给定的部分或完整计划的最终执行时间。我们以监督的方式使用收集到的经验来训练价值网络。这个过程包括将每个收集到的查询转换为特征(Featurizer)。这些特性包含查询级信息(例如，连接图)和计划级信息(例如，连接顺序)。Neo 可以使用许多不同的特征，从简单的 one hot 编码到更复杂的 embeddings(第 5 节)。Neo 的价值网络使用树卷积[40]来处理树状结构的 QEPs(第 4.1 节)。

• Plan Search

一旦对查询级信息进行了编码，Neo 就会使用值模型在 QEPs 的空间中搜索(即，选择连接顺序、连接算子和索引)，并发现具有最小预测执行时间(即，值)的计划。由于特定查询的所有执行计划的空间太大，无法进行穷尽搜索，因此 Neo 使用学习值模型来指导空间的最佳优先搜索(第 4.2 节)。由 Neo 创建的完整计划，包括连接排序、连接算子(如哈希、合并、循环)和访问路径(如索引扫描、表扫描)被发送到底层执行引擎，后者负责应用语义有效的查询重写规则(如插入必要的排序操作)并执行最终计划。这样可以确保生成的执行计划的正确性。

• Model Retraining

随着 Neo 优化了更多的查询，值模型被迭代地改进，并根据用户的数据库进行定制。这是通过合并新收集的关于每个已执行的 QEP 的经验来实现的。具体来说，一旦为特定查询选择了 QEP，它就被发送到底层执行引擎，后者处理查询并将结果返回给用户。此外，Neo 记录 QEP 的最终执行延迟，并将计划/延迟对添加到其体验集中。然后，Neo 根据这个经验重新训练价值模型，迭代地改进它的估计。

• Discussion

这个过程——搜索和模型再训练——对于用户发送的每个查询都是重复的。Neo 的架构旨在创建一个纠正反馈循环：当 Neo 的学习成本模型将 Neo 引导到一个查询计划时，Neo 预测该查询计划将执行得很好，但结果延迟很高，Neo 的成本模型将学习预测执行不佳计划的更高成本。因此，Neo 在未来不太可能选择与表现不佳的计划具有相似属性的计划。因此，Neo 的成本模型变得更加准确，有效地从错误中吸取了教训。

Neo 将查询优化表示为马尔可夫决策过程(MDP，在第 3.1 节中形式化)，其中每个状态对应于部分查询计划，每个动作对应于以自下而上的方式构建查询计划的一个步骤，并且仅在基于计划延迟的最终(终止)状态给出奖励。Neo 引导这个 MDP 的方法被称为值迭代[7]。如图 2 所示，训练一个函数来根据以前的经验近似特定状态的效益(值)。这个函数，我们称之为价值网络，然后用于创建策略。传统上，创建的策略很简单，就像基于价值网络贪婪地选择操作一样。

Neo 以两种方式构建传统的价值迭代模型。首先，Neo 不会贪婪地遵循价值网络的建议：最近有研究表明[33,52]，使用训练好的价值网络作为启发式来指导搜索可以改善结果。其次，Neo 不是“从零开始”，而是从传统查询优化器(由人类专家设计)构建的查询执行计划数据集中进行引导。这避免了强化学习臭名昭著的样本低效率[18,48]：在初始策略引导下，强化学习算法可能需要数百万次迭代[38]才能与人类专家手动构建的系统竞争。直观地说，从专家那里进行引导(从示范中学习)反映了幼儿如何通过模仿成人(专家)来获得语言或学习走路，并且已被证明可以大大减少学习良好策略所需的时间[18,49]。这对于数据库管理系统来说尤其重要：每次迭代都需要执行一次查询，在实现与当前优化器相当的性能之前，用户可能不愿意执行数百万次查询。更糟糕的是，执行一个糟糕的查询计划比执行一个好的查询计划需要更长的时间，因此初始迭代将花费不可行的时间来完成[36]。

任何强化学习系统的一个重要方面是平衡探索和利用。Neo 通过计划搜索程序利用知识，严重依赖价值网络来指导最佳优先搜索。与值迭代[38]一样，Neo 确保通过模型再训练来探索新的策略：每次重新训练值网络时，其权重被重置为随机值，并根据收集到的经验对整个网络进行训练。这确保了值网络对不可见查询计划的预测具有高度的随机性(因为不可见查询计划是“off manifold”[10,33])。我们还注意到，Neo 的架构与 AlphaGo 非常相似[52]，AlphaGo 是一种为玩围棋而创建的强化学习系统。由于篇幅限制，Neo 和 AlphaGo 的详细对比见在线附录第 2 节[34]。

查询特征化

在本节中，我们将从一些必要的符号开始，描述如何将查询计划表示为向量。

3.1 Notation

对于查询 q，我们定义 q 中使用的基本关系集为 R(q)。查询 q 的部分执行计划 P(记作 Q(P) = q)是一个树的森林，表示仍在构建的执行计划。每个内部(非叶)树节点都是一个连接算子。

${\bowtie }_i\in J$，其中$J$是可能的连接算子的集合(例如，hash ${\bowtie }_H$, merge ${\bowtie }_M$，loop ${\bowtie }_L$)，每个叶节点要么是表扫描，要么是索引扫描，要么是对关系$r\in R(q)$的未指定扫描，分别表示为$T(r)$，$I(r)$和$U(r)$。未指定扫描是指尚未分配为表扫描或索引扫描的扫描。例如，部分查询执行计划可以表示为：

在这里，未指定 B 的扫描类型，并且没有选择连接谓词来将 B 与计划的其余部分链接起来。该计划确实为表 D 和表 A 的表扫描指定了谓词，这些表扫描提供给合并连接，然后使用与 C 的循环连接连接其结果。

一个完整的执行计划是一个只有根并且没有未指定扫描的计划；关于如何执行计划的所有决定都已作出。我们说一个执行计划$P_i$是另一个执行计划$P_j$的子计划，写为$P_i\subset P_j$，如果$P_j$可以由$P_i$构造通过 (1)用索引或表扫描替换未指定的扫描，或者 (2)用连接算子组合$P_i$中的子树。

建立一个完整的执行计划可以看作是一个马尔可夫决策过程(MDP)。MDP 的初始状态是部分计划，其中每次扫描都未指定，并且没有连接。每个操作涉及 (1)使用连接算子将两个根融合在一起，或 (2)将未指定的扫描转换为表或索引扫描。更正式地说，每个动作都将当前计划

转变为任意计划

，使得

⊂

。每个动作的奖励都是零，除了最终动作，它的奖励等于生成的执行计划的延迟。与先前的工作[25,35]一样，该公式具有“无循环”的优点：在有限数量的动作之后，总能得到完整的查询执行计划。

3.2 Encodings

Neo 使用两种编码：一种是查询编码，它编码有关查询的信息，但独立于查询计划；另一种是计划编码，它表示部分执行计划。

• Query Encoding

与查询相关但与计划无关的信息的表示与之前的工作相似[25,35,43]，由两个部分组成。第一个组件将查询的连接图编码为邻接矩阵，例如在图 3 中，第一行第三列中的 1 对应连接 A 和 C 的连接谓词。对应于关系 E 的行和列都是空的，因为示例查询中没有涉及到 E。为简单起见，我们假设每个关系之间最多存在一个外键。然而，这种表示可以很容易地扩展为包含多个外键(例如，通过使用相关键的索引而不是“1”)。此外，由于这个矩阵是对称的，我们只编码上三角形部分(红色)。

查询编码的第二个组件是列谓词向量。在 Neo 中，我们目前支持三种越来越强大的变体，具有不同级别的预计算需求：

1. 1-Hot(谓词的存在性)：一个简单的“one-hot”编码，其属性涉及任何查询谓词。one-hot 编码向量的长度是所有数据库表上的属性数。例如，图 3 显示了“one-hot”编码向量，属性 A.2 和 B.1 的位置设置为 1，因为这两个属性都用作谓词的一部分。这里不考虑连接谓词。学习的 agent 只知道某个属性是否存在于谓词中。虽然简单，但 1-Hot 表示可以在不访问底层数据库的情况下构建。

2. Hist(谓词的选择性)：1-hot 编码的扩展，用谓词的预测选择性替换“0”或“1”(例如，如果我们预测选择性为 20%，A.2 可以是 0.2)。为了预测选择性，我们使用带有均匀性假设的现成直方图方法。

3. R-Vector(谓词的语义)：最先进的编码，使用行向量。基于自然语言处理模型 word2vec[37]，将列谓词向量中的每个条目替换为包含与该谓词相关的语义信息的向量。这种编码需要在数据库中的数据上构建一个模型，这是最昂贵的选择。我们将在第 5 节讨论行向量。

更强大的编码为模型学习复杂关系提供了更多的自由度。然而，这并不意味着更简单的编码就排除了模型学习复杂关系的可能性。例如，即使 Hist 不编码表之间的相关性，模型仍然可以学习它们并相应地在内部纠正基数估计，例如通过重复观察查询延迟。但是 R-Vector 编码通过提供查询谓词的语义增强表示使 Neo 的工作更容易。

• Plan Encoding

除了查询编码，我们还需要部分或完整查询执行计划的表示。虽然先前的研究[25,35]已经将每个部分执行计划的树状结构扁平化，但我们的编码保留了执行计划固有的树状结构。我们将部分执行计划的每个节点转换为一个向量，创建一个向量树，如图 4 所示。虽然向量的数量(即树节点的数量)可以增加，并且树本身的结构可能会改变(例如，左深或密集)，但每个向量具有相同数量的列。

这种表示是通过将每个节点转换成一个大小为|J| + 2|R|的向量来创建的，其中|J|是连接类型的数量，|R|是关系的数量。每个向量的第一个|J|项编码连接类型(例如，在图 4 中，根节点使用循环连接)，接下来的 2 个|R|项编码使用的关系，以及相关的扫描类型(表、索引或未指定)。对于叶节点，这个子向量是 one-hot 编码，除非叶节点表示未指定的扫描，在这种情况下，它被视为索引扫描和表扫描(在“表”和“索引”列中都放置了 1)。对于内部节点，这些条目是对应子节点的并集。例如，图 4 中最底部的循环连接在对应于 A 和 D 上的表扫描和 C 上的索引扫描的位置上有 1。

请注意，这种表示可以包含两个尚未连接的部分查询计划(即几个根)，例如，为了表示公式 1 中的部分计划，在编码时，U(B)根节点将被编码为：[0000110000]。这些编码的目的仅仅是为 Neo 的价值网络提供执行计划的表示，下面将介绍。

价值网络

接下来，我们提出 Neo 的价值网络，这是一个神经网络，它被训练来预测部分执行计划

的最佳查询延迟：换句话说，完整执行计划

可以实现的最佳查询延迟，使得

⊂

。由于不可能提前知道查询的最佳执行计划，因此我们使用系统迄今为止看到的最佳查询延迟来近似最佳查询延迟。

假设 Neo 的经验集 E 是一组完整的查询执行计划

∈E，已知延迟 L(

)。我们训练一个模型 M 来近似，对于所有

是任意

∈E 的子平面：

其中 C(

)是一个完整计划的成本。用户可以通过改变成本函数来改变 Neo 的行为。例如，如果用户只关心最小化整个工作负载的总查询延迟，则可以将成本定义为延迟，即 C(

) = L(

)。但是，如果用户希望确保工作负载中的每个查询 q 都比特定基线执行得更好，则可以将成本函数定义为

其中 Base(

)是计划

与该基线的延迟。无论成本函数是如何定义的，Neo 都会尝试随着时间的推移将其最小化。通过最小化损失函数来训练模型[50]。我们使用一个简单的 L2 损失函数：

根据外部状态(缓存、并发事务)的不同，相同的查询计划可能表现出不同的延迟。默认情况下，Neo 的值模型将尝试预测查询计划的最终平均延迟(这将最小化 L2 损失)。但是，根据用户的需求，可以修改损失函数，以鼓励值网络预测最终最差的观察延迟(例如，选择对缓存状态具有鲁棒性的查询计划)，或者预测最佳的观察延迟(例如，选择假设当前缓存了正确数据的查询计划)。如果需要，甚至可以使用分段损失函数来支持用户工作负载中不同查询的最差、平均或最佳情况。

• Network Architecture

Neo 价值网络的架构如图 5 所示。该架构旨在创建适合查询优化的归纳偏差[33]：神经网络本身的结构旨在反映对导致查询计划快或慢的原因的直观理解。研究查询计划的人们学习通过模式匹配来识别次优或良好的计划：在带有共享连接键的散列连接之上的合并连接可能会导致冗余排序或散列；在两个散列连接之上的循环连接可能对基数估计错误高度敏感；使用 fact 表作为“构建”关系的哈希连接可能会导致溢出；一系列不需要重新排序的合并连接可能会执行得很好，等等。我们的见解是，可以通过分析查询执行计划的子树来识别所有这些模式。Neo 的模型架构本质上是一个大型的模式库，这些模式是通过利用一种称为树卷积的技术从数据本身自动学习的[40]。

如图 5 所示，当模型评估部分查询计划时，查询级编码将通过许多完全连接的层提供，每个层的大小都在减小。第三个完全连接层输出的向量与计划级编码连接，即每个树节点(将相同的向量添加到所有树节点)。这是一种标准技术，称为“空间复制”[52,62]，用于组合固定大小的数据(查询级编码)和动态大小的数据(计划级编码)。一旦每个树节点向量被增强，树的森林就会被发送到几个树卷积层[40]，这是一个将树映射到树的操作。然后，应用动态池化操作[40]，将树结构扁平化为单个向量。使用几个额外的全连接层将该向量映射到单个值，用作模型对输入计划的预测。[34]给出了价值网络模型的形式化描述。

4.1 Tree Convolution

CNNs[29]等神经网络模型采用固定结构的输入张量，如矢量或图像。对于 Neo，嵌入在每个执行计划中的特征被结构化为树中的节点(如图 4)。因此，我们使用树卷积[40]，这是传统图像卷积对树结构数据的一种改进。

树卷积很适合 Neo。与图像的卷积变换类似，树卷积在计划树的每个部分上滑动一组共享过滤器。直观地说，这些过滤器可以捕获各种各样的本地父子关系。例如，过滤器可以在合并连接之上查找散列连接，或者在存在特定谓词时查找两个关系的连接。这些滤波器的输出提供由价值网络的最终层利用的信号；过滤器输出可能表示相关因素，例如何时对连接算子的子算子进行排序(建议合并连接)，或者过滤器可能会估计连接的右侧关系是否具有低基数(建议索引可能有用)。本节稍后将提供两个具体的示例。

由于查询树的每个节点恰好有两个子节点，因此每个过滤器由三个权重向量

、

、

组成。每个过滤器应用于每个局部“三角形”，该“三角形”由节点的向量

和它的两个左右子节点

和

(如果节点是叶子节点，则为

)组成，以产生一个新的树节点

：

这里，σ(·)是一个非线性变换(例如，ReLU[16])，⊙是一个点积，

是过滤器的输出。因此，每个过滤器结合来自树节点的本地邻域的信息。在执行计划中的每个树上“滑动”相同的过滤器，从而允许将过滤器应用于任意大小的计划。可以将一组过滤器应用于树，以生成具有相同结构的另一棵树，但每个节点的向量大小可能不同。在实践中，应用了数百个过滤器。

由于树卷积的输出是另一棵树，因此多层树卷积过滤器可以“堆叠”。树卷积过滤器的第一层将访问增强的执行计划树(即，每个过滤器将滑动到增强树的每个父/左子/右子三角形)。特定过滤器看到的信息量被称为过滤器的接受域[31]。第二层过滤器将应用于第一层的输出，因此第二层中的每个过滤器将看到从原始增强树中的节点 n, n 的子节点和 n 的孙子节点中派生的信息：因此每个树卷积层具有比上一层更大的接受域。因此，第一个树卷积层学习简单的特征(例如，识别合并连接之上的合并连接)，而最后一个树卷积层学习复杂的特征(例如，识别左深的合并连接链)。

我们给出了两个具体的示例，展示了树卷积的第一层如何检测查询执行计划中有趣的模式。在图 6a 的示例 1 中，我们展示了两个执行计划，它们仅在最上面的连接算子(合并连接和散列连接)上不同。如图 6b 顶部所示，连接类型(散列或合并)编码在每个节点特征向量的前两个条目中。树形卷积过滤器(图 6c 顶部)由三个权重向量组成，前两个位置为{1，−1}，其余位置为零，将作为具有两个顺序合并连接的查询计划的“检测器”。这可以在图 6d(顶部)中看到：具有两个顺序合并连接的计划的根节点从该过滤器接收到输出 2，而在合并连接之上具有散列连接的计划的根节点接收到输出 0。后续的树卷积层可以使用这些信息来形成更复杂的检测器，比如检测一行中的三个合并连接(流水线查询执行计划)，或者合并连接和散列连接的混合(这可能导致重新散列或重新排序)。

在示例 2(图 6)中，假设表 A 和表 B 按照相同的键排序，因此理想情况下使用合并连接将它们连接在一起，但是 C 没有排序。图 6(c，底部)中所示的过滤器用于检测使用合并连接连接 A 和 B 的查询计划，这种行为可能是理想的。最高权值(

)识别合并连接，而右子权值(

)识别所有其他表之上的表 B。这个卷积的结果(图 6d，底部)显示了 A 和 B 的合并连接(第一个计划)的最高输出，而 A 和 C 的合并连接(第二个计划)的负输出。

在实践中，过滤器权重是随着时间的推移而学习的，而不是手工配置的。执行梯度下降来更新过滤器权重将使与延迟相关的过滤器(有用的特征)得到奖励(保持稳定)，而与延迟没有明确关系的过滤器将受到惩罚(被推向更有用的值)。这创造了一个校正反馈回路，从而产生了提取有用特征的滤波器组[29]。

4.2 DNN-Guided Plan Search

价值网络预测执行计划的质量，但不直接给出执行计划。在最近的工作[4,52]中，我们将价值网络与搜索技术结合起来生成计划，从而产生了价值迭代技术[7]。

给定一个训练好的值网络和一个传入的查询 q, Neo 对给定的查询执行计划空间的搜索。在某些方面，这种搜索反映了传统数据库优化器使用的搜索过程，训练值网络承担了数据库成本模型的角色。然而，与这些传统系统不同的是，价值网络并不预测子计划的成本，而是预测包含给定子计划的执行计划可能实现的最佳延迟。这种差异使我们能够执行最佳优先搜索[12]，以寻找具有低预期成本的执行计划。从本质上讲，这相当于重复探索具有最佳预测成本的候选，直到出现停止条件。

查询 q 的搜索过程首先初始化一个空的最小堆来存储部分执行计划。这个最小堆是根据价值网络对每个部分计划成本的估计排序的。最初，将对 R(q)中的每个关系进行未指定扫描的部分执行计划添加到堆中。例如，如果 R(q) = {A, B, C, D}，那么堆将以

初始化：

每次搜索迭代从移除最小堆顶部的子计划

开始。我们枚举

的子节点，Children(

)，使用值网络对每个子节点进行评分，并将它们添加到最小堆中。直观地说，

的子节点是通过在

中指定扫描或通过使用连接算子连接两棵

树来创建的所有计划。形式上，如果

是一个完整的计划，我们将 Children(

)定义为空集，否则将其定义为 MDP 在此状态下的可用动作集(参见 3.1 节)。一旦每个子节点都被评分并添加到最小堆中，就会开始另一次搜索迭代，探索下一个最有希望的计划。每一步的搜索操作耗时 O(log n)，其中 n 为最小堆的大小。

虽然这个过程可以在找到一个叶子(一个完整的计划)时终止，但这个搜索过程可以很容易地转化为随时搜索算法[63]：一种持续寻找更好结果的算法，直到固定的时间截止。在这个变体中，Neo 继续从堆中探索最有希望的节点，直到达到一个时间阈值，此时返回最有希望的完整执行计划。这使用户可以控制计划时间和执行时间之间的权衡。用户可以根据自己的需要为不同的查询选择不同的时间截止。当到达时间阈值后还没有找到完整的执行计划时，Neo 的搜索过程进入“hurry up”模式[55]，贪婪地搜索最后一个计划中最有希望的子计划，直到找到一个叶子节点。截止时间应该根据每个应用程序进行调整。我们发现 250ms 对于各种各样的工作负载已经足够了(第 6.6 节)。

行向量嵌入

Neo 可以用多种方式表示查询谓词，包括简单的 one-hot 编码(1-Hot)或基于直方图的表示(Hist)，如第 3.2 节所述。在这里，我们激发并描述行向量，这是 Neo 表示查询谓词(R-Vector)的最高级选项。

虽然基数估计对传统查询优化器的成功至关重要[26,30]，但数据库系统经常做出简化的假设，例如一致性、独立性、and/or 包含原则，这些假设往往会破坏这一目标[27]。Neo 采用了一种不同的方法：我们没有对数据分布做出简化的假设，也没有试图直接估计谓词基数，而是构建了一个语义丰富的、向量化的查询谓词表示，它可以作为 Neo 的值模型的输入，使网络能够学习对数据相关性的泛化见解。根据最近在语义查询[9]、实体匹配[41]、数据发现[14]和错误检测[17]方面的工作，我们基于数据库本身的数据构建了每个查询谓词的矢量化表示。

我们的行向量方法基于流行且研究得很好的 word2vec 算法[37]，这是一种将自然语言单词(例如英语单词)转换为向量的方法。虽然这些向量本身没有意义，但它们之间的距离具有语义意义：例如，“spaghetti”和“pasta”之间的距离将很小，而“banana”和“doorknob”之间的距离将很大。直观地说，word2vec 通过利用单词的上下文来工作：经常出现在文本附近的单词被分配相似的向量表示，很少出现的单词被分配不同的向量(例如，“在意大利餐馆，我点了……”)。在 Neo 中，我们将数据库中每个表的每一行视为一个句子，将表行的每一列值视为一个单词。因此，经常在行中同时出现的值被映射到类似的向量。我们称这些向量为行向量。Neo 的价值网络可以将这些行向量作为输入，并使用它们来识别数据和谓词之间的相关性，这些相关性具有语法上不同但语义上相似的值(例如，“动作”和“冒险”经常与“超级英雄”同时出现)。

本节的其余部分首先概述如何构建 Neo 的行向量，然后探讨为什么行向量在捕获实际数据中的相关性方面是有效的。详见在线附录[34]。

5.1 R-Vector Featurization

在高层次上，我们的目标是构建一个语义丰富的查询谓词表示，Neo 可以将其用作输入。例如，如果对 IMDB 电影数据集/ JOB 数据集[26]进行查询，查找标记为“marvel-comics”的电影中的所有演员，查询将返回许多扮演超级英雄的演员。类似地，如果查询查找标记为“复仇者联盟”的电影中的所有演员，查询也将返回许多扮演超级英雄的演员。然而，如果查询带有“浪漫”标签的所有电影演员，则不太可能返回许多超级英雄演员。因此，我们想要创建一个类似于“复仇者联盟”但不同于“浪漫”的“漫威漫画”的矢量化表示。有了这样的矢量化，Neo 在看到“漫威”电影的查询后，将有更好的机会对“复仇者联盟”电影的查询做出良好的预测，从而给 Neo 更多的泛化机会。

Neo 的行向量编码需要两个步骤(图 7)。在查询优化之前，一个训练步骤使用专门的神经网络学习嵌入。在查询优化过程中，移除专用神经网络的输出层，创建一个截断的网络，将输入映射到嵌入向量[34]。

• Training

为了生成行向量，我们使用 word2vec——一种自然语言处理技术，用于嵌入关于单词集合的上下文信息[37]。我们使用现成的 word2vec 实现[47]在数据库中构建每个值的嵌入。我们在图 7 的上半部分描述了这个过程。

我们首先构建一个三层神经网络，称为嵌入网络，具有相等大小的输入和输出层。神经网络将被训练成将数据库中的每个 one-hot 编码值映射到表示该值上下文的输出向量。例如，图 7 的上半部分例子 1 显示了如何训练嵌入网络将“A”的输入映射到表示“C”和“E”的输出向量，对应于示例表中的第一行。对于第一行，还训练嵌入网络将“C”映射到表示“A”和“E”的输出向量，以及将“E”映射到表示“A”和“C”的输出向量。这个过程对数据库中的每一行重复(例如，例子 2)。注意，嵌入网络永远不会达到高水平的准确性：“A”可能出现在多个上下文中，这使得这是不可能的。该算法的目标是捕获数据库值与其上下文之间的统计关系。

• Query optimization

图 7 的下半部分描述了 Neo 如何在查询优化期间构建行向量编码。对嵌入网络进行训练后，去掉输出层，得到两层网络(表示从嵌入层到输出层转换的权重也可以丢弃)。Neo 可以使用这个截断的网络通过输入层传递数据库值并记录嵌入层的值来构建数据库值的矢量化表示。

为了编码查询谓词，我们将谓词算子(例如 LIKE 或!=)的信息与嵌入的向量结合起来。在最简单的情况下，查询谓词的形式是 tbl.attr OP VALUE，例如，actor.name =“Robert Downey Jr”。对于这些简单的情况，查询谓词可以通过将谓词算子(例如，=)的 one-hot 编码与谓词值(例如，“Robert Downey Jr”)的嵌入向量连接起来进行编码。这个连接的向量取代了 1- hot 编码(3.2 节)中使用的简单的 0 或 1。

嵌入向量可以组合和搜索，以处理通配符 LIKE 查询或复杂的逻辑查询(例如，ANDs, ORs)。例如，Neo 通过在数据库中搜索匹配的示例，然后使用该匹配的嵌入值来处理通配符查询[34]。可以通过对数据库进行部分非规范化来改进嵌入，从而允许 word2vec 模型捕获跨表相关性。我们的 word2vec 训练过程是开源的，可以在 GitHub 上获得[1]。

• Example

接下来，我们在 IMDB / JOB 数据集上探索一个训练好的 word2vec 模型示例[26]。在整个 IMDB 数据集上训练行向量模型后，我们使用 t-SNE 将演员姓名空间的嵌入向量投影到二维空间中进行绘图[58]。图 8 中绘制的结果展示了行向量如何捕获跨数据库表的语义相关性的可视化示例。如图所示，各种语义组(例如，中国演员，科幻电影演员)聚集在一起。直观地说，这提供了有用的信号来估计给定类似谓词的查询延迟：由于图 8 中的许多集群是线性可分的，它们的边界可以通过机器学习算法来学习。换句话说，由于具有相似语义值的谓词(例如，两个美国演员)可能具有相似的相关性(例如，在美国电影中)，表示查询谓词的语义值允许值网络识别相似的谓词，从而更好地推广到未见过的谓词。

实验

我们使用合成和现实世界的数据集来评估 Neo 的性能，以回答以下问题：(1)与商业的高质量优化器相比，Neo 的性能如何；(2)Neo 对新查询的泛化效果如何；(3)Neo 的训练和执行产生多少开销；(4)不同的编码策略如何影响查询延迟；(5)其他参数(例如搜索时间或损失函数)如何影响整体性能；最后，(6)Neo 对估计误差的鲁棒性如何。除非另有说明，否则查询将在具有 32GB RAM、Intel Xeon CPU E5-2640 v4 和固态驱动器的服务器上执行。每个 DBMS 都是根据分发组织提供的“最佳实践”指南配置的。

6.1 Setup

我们在许多不同的数据库系统上评估 Neo，使用三种不同的基准：

1. JOB：连接顺序基准[26]，包含一组由复杂谓词组成的互联网电影数据库(IMDB)上的查询，用于测试查询优化器。

2. TPC-H：标准 TPC-H 基准[45]，比例系数为 10。

3. Corp：一个 2TB 的数据集以及来自内部仪表板应用程序的 8000 个唯一查询，由一家大公司提供(在匿名的条件下)。

除非另有说明，否则所有实验都是通过将 80%的可用查询随机放入训练集，并使用另外 20%的可用查询作为测试集来进行的。在 TPC-H 的情况下，我们基于基准查询模板生成了 80 个训练查询和 20 个测试查询，而没有在训练查询和测试查询之间重用模板。

每个结果都是 50 个随机初始化运行的中位数。神经网络用 Adam 进行训练[21]。层归一化[5]用于训练稳定性。激活函数是“leaky ReLUs”[16]。我们使用 250ms 的搜索时间截止。网络体系结构如图 5 所示，我们在 JOB 的一个小子集上测试了几个变体后选择了图 5 的结构。除了计划级编码的大小取决于所选择的编码策略。行向量是使用部分逆归一化构建的[34]。

我们将 Neo 与两个开源(PostgreSQL 11.2, SQLite 3.27.1)和两个商业(Oracle 12c, Microsoft SQL Server 2017 for Linux)数据库系统进行比较；具体来说，我们训练 Neo 为每个系统构建查询计划，然后将 Neo 的查询计划与每个系统的查询优化器生成的查询计划进行比较。由于 Microsoft SQL Server 和 Oracle 的许可条款[46]，我们只能相对地展示性能。

对于 Neo 的初始经验收集，我们总是使用 PostgreSQL 优化器作为专家。我们将目标系统定义为 Neo 正在为之创建查询计划的系统：也就是说，如果 Neo 正在构建在 Oracle 上执行的计划，我们将 Oracle 称为目标系统。为了训练 Neo，我们首先使用 PostgreSQL 优化器为训练集中的每个查询创建查询计划。然后，我们通过查询提示强制目标系统服从建议的查询计划，从而在目标执行引擎(例如 Oracle)上测量该计划的执行时间。接下来，我们开始训练：Neo 训练一个价值网络来预测其经验集中的完整和部分计划的延迟，然后使用该价值网络来构建新的查询计划。这些新的查询计划随后由底层 DBMS 执行，它们产生的延迟被添加到 Neo 的经验中。我们重复这个过程 100 次。

6.2 Overall Performance

图 9 显示了 Neo 在每个测试工作负载上经过 100 次训练迭代后的相对性能，在 holdout 数据集上使用 R-Vector 编码(越低越好)。例如，对于 PostgreSQL 和 JOB 工作负载，Neo 生成的查询只比原始 PostgreSQL 优化器创建的查询花费平均执行时间的 60%。由于 PostgreSQL 优化器用于收集 Neo 的初始专业知识，因此这证明了 Neo 在现有开源优化器的基础上进行改进的能力。

此外，对于 SQL Server 和 JOB 和 Corp 工作负载，Neo 生成的查询计划也比 SQL Server 商业优化器创建的计划快 10%(注意，这些计划是在 SQL Server 上执行的)。重要的是，SQL Server 优化器包括一个多阶段搜索过程和一个 100 输入动态调整的成本模型[15,42]，预计将比 PostgreSQL 的优化器先进得多。然而，通过仅使用 PostgreSQL 的优化器来引导，Neo 最终能够在自己的平台上超越或匹配 SQL Server 优化器的性能。Oracle 也发现了类似的结果。请注意，更快的执行时间完全基于更好的查询计划(即，不修改底层执行引擎)。唯一的例外是，在 TPC-H 工作负载上，Neo 的性能没有超过这两个商用系统。我们怀疑 SQL Server 和 Oracle 都已经调到了 TPC-H，因为它是最常见的基准之一。

总的来说，这个实验证明了 Neo 能够创建计划，这些计划和开源优化器一样好，有时甚至比开源优化器更好。然而，图 9 只比较了 Neo 在第 100 次训练后的中位数表现。这自然提出了以下问题：(1)与较少数量的训练集相比，性能如何，以及将模型训练到足够质量需要多长时间(在下一小节中回答)，以及(2)优化器对各种估计误差的鲁棒性如何(在第 6.4 节中回答)。

6.3 Convergence Time

为了分析收敛时间，我们测量了每次训练迭代后的性能，总共进行了 100 次完整迭代。我们首先报告了训练迭代方面的学习曲线，以便于不同系统之间的比较(例如，MS SQL Server 的训练集可能比 PostgreSQL 运行得快得多，仅仅是因为 MS SQL Server 的执行引擎更好地进行了调整)。然后，我们报告挂钟时间，在不同的系统上训练模型。最后，我们回答了我们的自引导方法对训练时间有多大帮助的问题。

6.3.1 Learning Curves

我们测量了 Neo 在每个数据集上相对于目标系统的优化器的性能(即，在每个图中，性能为 1 相当于目标引擎的优化器)：对训练查询集进行完整的传递(从经验中重新训练网络，为每个训练查询选择一个计划，执行该计划，并将结果添加到 Neo 的经验中)。图 10 描述了 50 次运行：实线表示中位数，阴影区域表示最小值和最大值。对于除 PostgreSQL 之外的所有 DBMSes，我们额外绘制了由 PostgreSQL 优化器生成的计划在目标引擎上执行时的相对性能(例如，在 Oracle 上执行 PostgreSQL 计划)。

• Convergence

每个图都展示了类似的行为：在第一次迭代之后，Neo 的性能很差(几乎比目标系统的优化器差 2.5 倍)。然后，经过几次迭代，Neo 的性能急剧提高，直到趋于平稳。我们注意到 Neo 能够在 9 次训练迭代(即，训练迭代的次数，直到中位数运行越过代表 PostgreSQL 的线)中改进 PostgreSQL 优化器。匹配商业优化器(MS SQL Server 或 Oracle)的性能需要更多的训练迭代，这并不奇怪，因为商业系统要复杂得多。

• Variance

除了 TPC-H 之外，对于所有工作负载，不同训练迭代之间的差异都很小。我们假设 TPC-H 的均匀数据分布使得 R-Vector 嵌入不太有用，因此需要更长的时间来相应地调整模型。此行为在非合成数据集中不存在。

6.3.2 Wall-Clock Time

到目前为止，我们分析了 Neo 在训练迭代方面变得有竞争力需要多长时间；接下来，我们将分析 Neo 在 wall-clock time(实时)方面具有竞争力所需要的时间。我们分析了 Neo 达到两个里程碑所需的时间：一个策略生成的查询计划与 (1)由 PostgreSQL 生成的计划相同，但在目标执行引擎上执行，以及 (2)由目标系统的优化器生成的计划并在目标系统的执行引擎上执行。结果绘制在图 11a 中：左柱和右柱分别表示里程碑 1 和里程碑 2，分为训练神经网络所花费的时间和执行查询所花费的时间。注意，查询执行步骤是并行的，在不同节点上同时执行查询。

不出所料，Neo 需要更长的时间才能与更先进的商业优化器竞争。然而，对于每个引擎，学习一个优于 PostgreSQL 优化器的策略只需要不到两个小时。此外，Neo 能够在半天内达到或超过每个优化器的性能。注意，这个时间不包括训练查询编码的时间，在 1-Hot 和 Histogram 的情况下，这个时间可以忽略不计。然而，对于 R-Vector，这需要更长的时间(参见 6.7 节)。

6.3.3 Is Demonstration Even Necessary?

由于收集演示数据引入了额外的复杂性，因此很自然地要问演示是否必要：是否有可能从零知识中学习到一个好的策略?虽然先前的工作[35]表明，现成的深度强化学习技术可以在没有演示数据的情况下学习找到最小化成本模型的查询计划，但基于查询延迟(即端到端)学习策略是困难的，因为一个糟糕的计划可能需要数小时才能执行。不幸的是，随机选择的查询计划表现得非常差(即差 100 到 1000 倍[26])，可能会以类似的因素增加 Neo 的训练时间[36]。

我们试图解决这个问题通过选择一个特定的查询超时 t(如 5 分钟)，和终止查询当执行延迟超过 t。然而，这种方法破坏了大量的新使用的信号学习：延迟 7 分钟的连接模式与延迟 1 周的连接模式获得相同的奖励，因此 Neo 无法了解到 7 分钟计划中的连接模式比 1 周计划中的连接模式有所改进。结果，即使经过了超过三周的训练，我们也没有达到与 PostgreSQL 优化器相当的结果。

6.4 Robustness

在这里，我们测试了替代查询编码(例如，1-Hot)的有效性，Neo 处理专门为展示新行为而发明的未见查询的能力，以及 Neo 对噪声输入的弹性。

6.4.1 Query Encoding

图 11b 显示了 Neo 在不同查询编码的情况下跨 JOB 数据集的每个 DBMS 的性能。在这里，我们包括两种 R-Vector 编码：部分逆归一化[34]，其中 R-Vector 在部分逆归一化的数据库上训练，以及没有任何逆归一化化的变体(后缀为“no joins”)。正如预期的那样，1-Hot 编码始终表现最差，因为 1-Hot 编码包含的谓词信息最少。Hist 编码虽然做了朴素的一致性假设，但提供了足够的谓词信息来提高 Neo 的性能。在每种情况下，R-Vector 编码产生最佳的整体性能，而“no joins”变体稍微落后。我们假设这是因为 R-Vector 编码比其他编码包含更多关于底层数据库的语义信息。

6.4.2 On Entirely New Queries

之前的实验证明了 Neo 能够将查询泛化到随机选择的测试集中，该测试集来自与训练集相同的工作负载。虽然这表明 Neo 可以处理以前未见过的谓词和对连接图的修改，但这并不一定表明 Neo 能够泛化到一个全新的查询。为了测试 Neo 在新查询上的行为，我们创建了一组 24 个额外的查询，我们称之为 Ext-JOB[2]，它们在语义上与原始 JOB 工作负载不同(没有共享谓词或连接图)。

在对 Neo 进行了 100 回合的 JOB 查询训练后，我们评估了 Neo 在 Ext-JOB 查询上的表现。图 12a 显示了结果：实线的高度表示在未见过的查询上生成 Neo 的计划的平均归一化延迟。首先，我们注意到，使用 R-Vector 特性，为 Ext-JOB 数据集中完全看不见的查询选择的执行计划仍然优于或匹配目标系统的优化器。我们假设 R-Vector 特征和 Hist/1-Hot 特征之间的较大差距是由于 R-Vector 捕获了关于查询谓词的信息，这些信息泛化到全新的查询。

• Learning new queries

由于 Neo 能够从查询执行中逐步学习，我们在 5 次额外的训练迭代(包括 Ext-JOB 查询的经验)之后评估了 Neo 在 Ext-JOB 查询上的性能，如图 12a 中的模式条所示。一旦 Neo 多次看到每个新查询，Neo 的性能就会提高，因为它已经学会了如何处理以前未见过的查询引入的新模式。当面对新的查询时，Neo 的性能最初会下降，但 Neo 会适应这些新的查询。这展示了基于深度学习的查询优化器在跟上实际查询工作负载变化方面的潜力。

6.4.3 Cardinality Estimates

基数估计和查询优化之间的紧密关系得到了很好的研究[6,39]。然而，有效的查询优化器必须考虑到，随着连接数量的增加，大多数基数估计的准确性往往会显著降低[26]。虽然深度神经网络通常被认为是黑盒，但在这里，我们展示了 Neo 能够学习何时信任基数估计，何时忽略它们。

为了测量 Neo 对基数估计误差的鲁棒性，我们在每个树节点上训练了两个带有附加特征的 Neo 模型。第一个模型接收 PostgreSQL 优化器的基数估计(PostgreSQL)，第二个模型接收真实基数(true cardinality)。然后，当连接数≤3 和> 3 时，我们在 JOB 工作负载中优化查询时，绘制了两个模型在遇到的每个状态下的输出直方图，引入了人为错误。

图 13a 和图 13b 分别显示了对于≤3 或>3 连接的状态，PostgreSQL 模型的值网络预测直方图。图 13a 显示，当最多有 3 个连接时，基数估计误差从 0 个数量级增加到 2 个数量级和 5 个数量级，导致分布方差增加：当连接数最多为 3 个时，Neo 学习的模型随着 PostgreSQL 的基数估计而变化。然而，在图 13b 中，我们看到，当连接数大于 3 时，网络输出的分布几乎没有变化：当连接数大于 3 时，Neo 学会忽略 PostgreSQL 的基数估计。

图 13c 和 13d 显示，当 Neo 的值模型以真实的基数作为输入进行训练时，Neo 学习的模型无论连接的数量如何，都会随基数变化其预测。换句话说，当提供真正的基数时，Neo 学会依赖基数信息，而不管连接的数量。这表明 Neo 能够学习哪些输入特征是可靠的，即使这些特征的可靠性取决于诸如连接数量之类的因素。

6.4.4 Per Query Performance

接下来，我们在查询级别分析 Neo 的性能。在 Neo 和 PostgreSQL 计划(在 PostgreSQL 上执行)之间的 JOB 工作负载中每个查询的秒级绝对性能改进(或回归)如图 14(紫色)所示。虽然 Neo 将一些查询的执行时间提高了 40 秒，但也会使一些查询的执行时间变差(例如，查询 24a 变慢了 8.5 秒)。

与传统的优化器相比，Neo 的优化目标可以很容易地改变。到目前为止，我们的目标始终是优化总工作负载成本，即所有查询的总延迟。但是，我们也可以更改优化目标，以优化每个查询的相对改进(图 14 中的绿色条)，如第 4 节所讨论的那样。这隐含地惩罚了查询性能在基线上的变化(例如，PostgreSQL)。当使用这个优化目标进行训练时，总工作负载时间仍然会加快(缩短 289 秒，而不是近 500 秒)，并且除了一个查询之外，所有查询的性能都比 PostgreSQL 基线有所提高(29b 回归了 43 毫秒)。这提供了 Neo 响应不同优化目标的证据，允许它针对不同的场景进行定制。

Neo 的损失函数可以进一步定制，根据查询对用户的重要性对查询进行不同的加权，即查询优先级。还可以构建直接感知服务水平协议(SLAs)的优化器。我们把这类调查留给今后的工作。

6.5 Value Network Accuracy

Neo 的价值网络负责准确预测部分和完整查询计划的最终延迟。在使用 PostgreSQL 对 JOB 数据集进行训练期间，我们评估了值网络的准确性。在每次迭代之后，我们测量了价值网络预测的均方误差(MSE)与 (1)在前一次迭代中和 (2)在最后一次迭代中 产生的计划的真实延迟。图 12c 显示了结果。最初，价值网络在估计前一次迭代和最后一次迭代的延迟方面做得相对较差。然而，随着训练的继续，两条曲线会收敛。两条曲线的收敛——值网络在最近一次迭代与最后一次迭代上的精度——表明策略正在变得稳定[54]，这是一个理想的特性，通常(但不一定)与减少的运行时间方差相关。

6.6 Search

Neo 使用训练好的值网络搜索查询计划，直到一个固定的时间截止(章节 4.2)。图 12b 显示了具有特定连接数(从 JOB 数据集中随机选择，在 PostgreSQL 上执行)的查询的性能如何随着搜索时间的变化而变化。注意，x 轴会跳过一些值(JOB 数据集没有包含 13 个连接的查询)。这里，查询性能是相对于观察到的最佳性能给出的。例如，当连接数为 10 时，只要截止时间大于 120ms, Neo 就会找到最佳观察计划。我们还测试了显著延长搜索时间(至 5 分钟)，发现无论查询中的连接数有多少(JOB 数据集中最多 17 个)，这样的扩展都不会改变性能。

连接数量和对搜索时间的敏感性之间的关系并不奇怪：具有更多连接的查询具有更大的搜索空间，因此需要更多的时间来优化。虽然在许多情况下，用 250ms 优化一个包含 17 个连接的查询是可以接受的，但当情况并非如此时，其他选项[59]可能更可取。

6.7 Row Vector Training Time

Neo 使用开源 gensim 包构建其 R-Vector 编码[47]。图 11c 显示了在每个数据集上训练行向量所花费的时间，包括“连接”(部分逆归一化)和“无连接”(归一化)变体[34]。训练 R-Vector 编码的时间与数据库的大小有关。对于 JOB 数据集(≈4GB)，“no joins”变体在 10 分钟内训练，而 Corp 数据集(≈2TB)的“no joins”变体需要两个小时的训练。“joins”变体需要更长的训练时间，例如三个小时(JOB)到一天多(Corp)。

在某些情况下，构建行向量可能是禁止的。然而，与 Hist 相比，我们发现“join”变体(平均而言)使查询时间快了 5%，而“no joins”变体(平均而言)使查询时间快了 3%。根据多处理级别、查询到达率等，行向量可能会很快“自付费用”：例如，在 Corp 数据集上的“join”变体的训练时间在 540 小时的查询处理后“付费”，因为行向量将查询处理速度提高了 5%，需要 27 小时的训练。由于公司经常同时执行 8 个查询，这相当于只有三天。“no joins”的变体(提高 3%的性能，需要 217 分钟的训练)在 15 小时后“付费”。

我们不分析行向量在不断变化的数据库中的行为。根据数据库的不同，行向量可能会很快变得“过时”，或者在很长一段时间内保持相关性。新技术[13,61]表明，当底层数据发生变化时，重新训练词向量模型可以快速完成，但我们将这些方法的研究留给未来的工作。

相关工作

查询优化已经研究了四十多年[11,51]。然而，查询优化仍然是一个未解决的问题[30]，特别是由于难以准确估计基数[26,27]。LEO 优化器首先引入了从错误中学习的查询优化器的概念[53]。在后续工作中，CORDS[19]在查询执行之前使用数据样本主动发现任何列之间的相关性。

自提出[60]以来，深度学习在数据库研究中得到了广泛应用。例如，最近的工作[20,57]展示了如何利用强化学习进行 Eddies-style 的细粒度自适应查询处理。SkinnerDB 系统[56]展示了如何在自适应查询处理系统中应用遗憾边界强化学习来动态改进单个查询的执行[56]。[43]使用强化学习来构建传统优化器的状态表示。[44]提供了查询驱动的混合模型，作为选择性学习的直方图和抽样的替代方案。[22,28]提出了一种深度学习方法来估计基数，专门用于捕获连接交叉相关性。word2vec 风格的嵌入已被应用于数据探索[14]和错误检测[17]。与我们最接近的作品是[25,35]，它提出了一种基于学习的方法，专门用于连接排序，并且仅适用于给定的成本模型。Neo 的关键贡献在于它为数据库查询优化问题提供了一个端到端、持续学习的解决方案。我们的解决方案不依赖于任何手工制作的成本模型或数据分布假设。

这篇论文建立在我们自己的团队最近的进展之上。ReJOIN[35]提出了一种用于连接顺序枚举的深度强化学习方法，在[36]中被推广到更广阔的视野。Decima[32]利用图神经网络提出了一种基于强化学习的调度器。SageDB[23,24]提出了构建一种新型数据处理系统的愿景，该系统大量使用已学习的组件。本文是实现这一总体愿景的第一步。

结论

本文介绍了第一个端到端学习优化器 Neo，它使用深度神经网络生成高效的查询执行计划。Neo 通过结合强化学习和搜索策略迭代地提高其性能。在四个数据库系统和三个查询数据集上，Neo 始终优于或匹配现有的商业查询优化器(例如，Oracle 和 Microsoft 的)，这些优化器已经经过了几十年的调整。

在未来，我们计划研究将学习到的模型推广到不可见模式的方法(例如使用迁移学习[8])。我们感兴趣的是在从更原始和高级的商业优化器中启动时测量 Neo 的性能。关键的是，Neo 忽略了许多对实现最佳查询性能至关重要的数据库状态：缓存状态、并发查询、同一服务器上的其他应用程序等。传统的优化器往往也会忽略这些因素，而 Neo 为构建自动适应这些外部因素的查询优化器奠定了基础——这样做可能只需要找到适当的方法将这些因素编码为价值网络的输入，或者可能需要更多的研究。