SageDB: A Learned Database System

type

status

date

slug

summary

SageDB：一个学习型数据库系统

ABSTRACT

现代数据处理系统被设计为通用的，因为它们可以处理各种不同的模式、数据类型和数据分布，并旨在通过使用优化器和成本模型来提供对数据的有效访问。这种通用性质导致系统无法利用特定应用程序和用户数据的特性。通过 SageDB，我们提出了一种新型数据处理系统的愿景，该系统通过代码合成和机器学习高度专业化于应用程序。通过对数据分布、工作负载和硬件进行建模，SageDB 可以了解数据的结构以及最佳访问方法和查询计划。这些学习模型通过代码合成深深嵌入到数据库的几乎每个组件中。因此，SageDB 与当前数据库系统的开发方式截然不同，在数据库、机器学习和编程系统中提出了许多新问题。

1. INTRODUCTION

数据库系统在根据数据统计自动选择高效算法（例如合并与散列连接）方面有着悠久的历史。然而，现有的数据库仍然是通用系统，并不是针对用户的特定工作负载和数据特征进行个案设计，因为手动这样做会非常耗时。然而，专业的解决方案可以更加有效。例如，如果目标是构建一个高度调整的系统来存储和查询具有连续整数键（例如键 1 到 100M）的固定长度记录范围，则不应使用传统索引。使用 B+Tree 进行此类范围查询没有多大意义，因为键本身可以用作偏移量，使其成为查找范围的第一个键的常量 O(1) 操作。1 事实上，一个简单的将 100M 整数加载到数组中并在一定范围内执行求和的 C 程序在现代桌面上运行大约需要 300 毫秒，但在现代数据库 (Postgres 9.6) 中执行相同的操作大约需要 150 秒。对于不了解特定数据分布的通用设计来说，这意味着 500 倍的开销。

类似的好处也适用于排序或连接等操作。对于排序，如果我们知道键来自密集整数域，我们可以简化基于传入记录在主键上的排序，因为该键可以再次用作偏移量，将数据直接放入排序数组中，从而将这个特定数据实例的排序复杂度从 O(N log N ) 降低到 O(N )。密集整数键上的连接也简化为查找，只需要使用键作为偏移量进行直接查找。插入和并发控制也可能变得更容易，因为我们不需要保持索引结构同步。

也许令人惊讶的是，对于其他数据模式也可以进行相同的优化。例如，如果数据仅包含偶数或遵循任何其他确定性分布，我们可以应用类似的优化。简而言之，我们可以通过了解确切的数据分布来优化数据库使用的几乎任何算法或数据结构。这些优化有时甚至可以改变众所周知的数据处理算法的复杂性类别。当然，在大多数现实世界的用例中，数据并不完全遵循已知的模式，并且通常不值得为每个用例设计专门的系统。然而，如果能够学习数据的数据模式、相关性等，我们认为我们可以自动合成索引结构、排序和连接算法，甚至利用这些模式来提高性能的整个查询优化器。理想情况下，即使对模式的了解不完善，也可以改变算法的复杂性类别，如上面的示例所示。

在本文中，我们展示了 SageDB 的愿景，这是一种新型数据管理系统，专门利用其存储的数据分布及其服务的查询。先前的工作探索了使用学习来调整旋钮[37,34,7,9,35]，选择索引[12,4,36]分区方案[6,2,27,28]或物化视图（参见[ 5]总体概述）但我们的目标不同。我们认为学习组件可以完全取代数据库系统的核心组件，例如索引结构、排序算法，甚至查询执行器。这可能看起来违反直觉，因为机器学习无法提供我们传统上与这些组件相关联的语义保证，并且因为传统上认为机器学习模型的评估成本非常昂贵。这份愿景文件认为，这些明显的障碍并不像看上去那么有问题。

在性能方面，我们观察到越来越多的设备配备了用于机器学习的专用硬件。例如，iPhone有“神经引擎”，谷歌的手机有“视觉核心”，谷歌的云有云TPU，微软开发了BrainWave。由于更容易扩展机器学习所需的简单（数学）运算，因此这些设备已经提供了令人惊叹的性能。例如，Nvidia 的 TESLA V100 产品能够执行 120 TeraFlops 的神经网络运算。还有人指出，到 2025 年，GPU 的性能将提高 1000 倍，而 CPU 的摩尔定律基本上已经失效了 [1]。通过用神经网络取代分支繁重的算法，DBMS 可以从这些硬件趋势中受益。

类似地，提供相同的语义保证通常非常容易。例如，B-Tree 可以看作是一个模型，它指向包含具有特定键的记录的页面，需要扫描该页面以返回实际满足查询的所有记录。从这个意义上说，BTree 已经牺牲了执行性能来换取准确性 [19]。基于学习的模型将具有更大的灵活性来探索这种权衡。

最后，积极使用综合和代码生成将使我们能够自动创建高效的数据结构，将模型与更传统的算法相结合。这里，我们的目标是（1）生成适合用户数据分布的代码，以及（2）使用嵌入式机器学习模型合成数据库组件，该模型平衡给定用例的内存、延迟和计算之间的权衡，同时提供与传统组件相同的语义保证。

构建 SageDB 需要彻底改变当前数据库系统的开发方式，并涉及来自数据库、机器学习和编程系统的挑战。 SageDB 目前正在作为麻省理工学院新的人工智能数据系统实验室 (DSAIL) 的一部分进行开发，该实验室由一支在所有这些领域拥有专业知识的跨学科团队组成。我们的重点是构建新的分析 (OLAP) 引擎，但我们相信该方法对于 OLTP 或混合工作负载也具有显着优势。本文的其余部分概述了 SageDB 的整体架构、个别挑战，并提出了一些有希望的初步结果。

2. MODEL-DRIVEN APPROACH

SageDB背后的核心思想是构建一个或多个关于数据和工作负载分布的模型，并基于它们自动为数据库系统的所有组件构建最佳的数据结构和算法。这种我们称之为“数据库综合”的方法将使我们能够通过将每个数据库组件的实现专门针对特定的数据库、查询工作负载和执行环境来实现前所未有的性能。

2.1 Types of Customization

所提出的定制远远超出了目前使用的有关数据、硬件或算法性能的统计和模型，大致可以分为以下几个级别：

通过配置进行定制：定制的最基本形式是配置系统，也称为旋钮调整。大多数系统和启发式方法都有大量的设置（例如页面大小、缓冲池大小等）。传统上，数据库管理员调整这些旋钮来将通用数据库配置为特定的用例。从这个意义上说，创建索引、找到正确的分区方案或创建性能的物化视图也可以被视为找到系统的最佳配置。毫不奇怪，在基于工作负载和数据特征的配置[37,34,7,9,35]的自动调整这些方面已经做了很多工作。

通过算法选择进行定制：虽然配置系统很大程度上是静态的，但数据库长期以来一直使用查询优化器根据数据统计和配置（例如可用索引）动态“定制”特定查询的执行策略。系统。也就是说，查询优化器决定最佳执行顺序（例如，谓词下推、连接排序等），并从一组可用算法中选择最佳实现（例如，嵌套循环连接与哈希连接）。这种声明性方法允许用户在高级别的查询上指定，而系统则找出如何最好地实现它，这是数据库社区最重要的贡献之一。

通过自我设计进行定制：自我设计的系统依赖于映射系统中关键设计决策的可能空间并自动生成最适合工作负载和硬件的设计的概念[15]。这里，可能的设计空间是由第一原理组件的所有组合和调整来定义的，例如栅栏指针、链接、时间分区等，它们一起形成“数据结构周期表”[14]。这远远超出了算法选择或配置系统的范围，因为这些原语的新组合可能会产生以前未知的算法/数据结构，并可能带来显着的性能提升[15]。

通过学习进行定制：与自我设计相反，学习系统通过学习模型替换核心数据系统组件。例如，在[19]中我们展示了如何用模型替换索引，而[21]展示了如何学习特定于工作负载的调度策略。模型使得捕获数据和工作负载属性成为可能，传统的数据结构和算法很难很好地支持。因此，在某些条件下，这些数据结构可以提供最佳情况的复杂性，例如 O(N ) 而不是 O(N log N )，并且比通过自行设计进行定制获得更高的性能增益。此外，它们将计算类型从传统的控制流密集型计算改为以数据依赖性为中心的计算，这些计算通常可以在 CPU 和即将推出的 ML 加速器上更有效地执行。

这些不同类型的定制可以组合起来。特别是，通过自我设计的定制和通过学习的定制是齐头并进的，因为学习的模型通常必须与更传统的算法和数据结构相结合，才能提供相同的语义保证。更有趣的是，模型可以在数据库系统的不同组件之间共享。从这个意义上说，我们在本文中认为，通过学习进行定制是最强大的定制形式，并概述了 SageDB 如何将模型深度嵌入到所有算法和数据结构中，使模型成为数据库的大脑（见图 2）。

2.2 The Power of Distributions

为了说明通过模型学习和综合算法和数据结构的力量，请考虑以下思想实验：假设我们有一个完美的模型，用于表 R1 上的经验累积分布函数 (CDF)，其属性为 X1, ..., Xm (即不存在预测错误）：

M_{CDF} = F_{X1},...X_m (x_1,...x_m) = P (X_1 ≤ x_1,..., X_m ≤ x_m)

为简单起见，我们使用 CDF 来指代实际存储在数据库中的数据（即数据的实例）的经验 CDF，而不是该数据的生成函数背后的理论 CDF。对于分析，我们主要关心经验 CDF，但是，对于更新/插入繁重的工作负载，底层 CDF 起着更重要的作用。尽管本文主要关注分析，但我们将在最后讨论该主题。

优化器：首先，也是最明显的，这样的模型显着简化了查询优化，因为基数估计基本上是免费的（即基数估计只不过是概率质量估计）。这使得关于最佳连接顺序的决策变得更加容易，尽管正如查询优化文献的悠久历史所表明的那样，计算和维护紧凑且准确的多维分布是一个关键挑战，我们稍后将更详细地解决这个挑战。

索引：正如我们在[19]中所示，这样的模型也可以用于实现点索引或范围索引。假设我们有一个主键

X_1

上的索引组织表，该表在磁盘上的连续区域中存储按

X_1

排序的数据以及长度为 l 的固定大小记录。在这种情况下，我们可以通过计算小于给定主键 k 的概率质量并将其乘以记录总数 N 和每条记录的大小来计算每条记录的偏移量：

F_{X1},...X_m（key，∞_2..., ∞_m）* N * l

在这种情况下，我们也说

M_{CDF}

预测了密钥 k 的位置。请注意，该索引支持范围请求，因为它返回等于或大于查找键的第一个键。假设我们可以在恒定时间内在 CDF 中执行查找（我们在下面讨论的假设），这使得任何键的查找都是 O(1) 操作，而传统的树结构需要 O(log N ) 操作。

有趣的是，CDF还可以用于二级索引或多维索引。然而，在这些情况下，我们不仅需要为索引构建 CDF 模型，还需要优化存储布局（更详细的讨论请参阅第 3 节）。

压缩：此外，CDF还可以用于压缩数据。为简单起见，假设我们有一个排序列，即 <attr,r-id> 对，以及仅在列 attr 上的 CDF 模型。如果我们可以反转 CDF，即针对列中的位置计算该列的值，那么这种逆 CDF 模型实际上可以让我们完全避免存储 attr 的值。该方案最好被视为更高级别的熵压缩。然而，DBMS 环境中的美妙之处在于，用于索引、查询优化等的相同模型可以重复用于压缩。

执行：同样，CDF 模型可以帮助部分或全表连接或排序。例如，对于排序，贝叶斯定理可用于“重写”表的任何给定子集的

M_{CDF}

，以实现新模型

\hat{M}_{CDF}

，该模型可用于预测排序数组中每个记录的位置，将排序变成 O (N)操作。对于连接，我们需要为每个表建立一个

M_{CDF}

模型，然后可以使用该模型来“预测”任何连接键的位置，类似于索引情况。此外，某些聚合（例如计数）也变得免费，因为系统可以直接使用模型来回答它们，甚至无需访问数据。

高级分析：CDF 还可用于许多数据立方体操作和近似查询答案。例如，大多数 OLAP 查询都涉及求和和计数。因此，在很多情况下，我们可以使用 CDF 模型来直接（近似）回答这些查询。此外，这样的模型可以直接用作机器学习模型的一部分，或者有助于更快地构建预测模型；最后，大多数机器学习模型都是关于分布的。然而，有一个警告：机器学习通常是关于泛化性，而不是经验 CDF。

讨论：这个使用 CDF 模型的思想实验展示了这种模型可以嵌入到数据库系统中的深度以及它可以提供哪些好处。但这不仅仅是CDF 的问题。例如，查询优化器还需要一个成本模型来估计给定计划的执行时间，该模型可以是传统的手动调整模型或学习模型。此外，在某些情况下，学习整个算法是有意义的。例如，即使有关于输入的完美信息，设计一个低复杂度的近乎最优的调度算法也是极其困难的。在这种情况下，学习数据/查询特定的算法可能会提供一个有趣的替代方案。

2.3 What Models Should be Used

一个关键的挑战是为 SageDB 的大脑选择正确的模型。答案出人意料地简单：只要有效就行。在某些情况下，直方图可能就足够了；在其他情况下，神经网络可能是正确的方法。然而，到目前为止我们发现直方图通常粒度太粗或太大而无用。另一方面，至少对于 CPU 来说，深度和广度的神经网络通常成本太高而不实用，尽管随着 TPU 和其他神经处理器的进步，这种情况未来可能会改变。

截至今天，我们发现我们经常需要生成特殊模型才能看到显着的好处。作为生成模型的示例，请考虑 [19] 中提供的 RMI 结构（参见图 1）。对于一维情况，RMI的核心思想非常简单：（1）在数据上拟合一个简单的模型（线性回归、简单神经网络等）； (2) 使用模型的预测来选择另一个模型，即专家，它可以更准确地对数据子集进行建模； (3)重复该过程，直到最后一个模型做出最终预测。由于 RMI 使用模型层次结构将问题空间划分为子区域，每个子区域都有自己的专家模型，因此 RMI 类似于专家的层次结构混合 [16]；然而，RMI 不是树，而是有向无环图。在[19]中，我们表明 RMI 模型可以显着优于最先进的索引结构，并且非常容易训练。同时，这种类型的模型可能不会被用作预测模型的一部分，因为它有过度拟合的倾向；它为经验分布创建了 P (X ≤ t) 的良好表示，但不一定是基础数据分布。

然而，RMI 只是一个起点。例如，可以使顶层模型或底层模型更加复杂，用其他类型的模型替换特定级别阶段的部分模型，使用量化，改变特征表示，将模型与其他数据结构结合起来等等在。因此，我们相信，我们将看到关于如何最有效地为数据库组件生成模型的新想法的爆炸式增长，以实现给定工作负载的精度、低延迟、空间和执行时间之间的适当平衡（参见第 4-5 节）。

2.4 Architecture Overview

SageDB的整体架构如图2所示。如上所述，我们的关键思想是为特定应用程序构建或选择（“综合”）数据处理引擎的每个组件的最佳实现。

这种综合是通过首先学习一个或多个数据分布、工作负载和硬件模型来完成的。虽然理论上单个“主”模型可能就足够了，但实际上我们希望创建多个模型来平衡执行时间与准确性。与 RMI 一样，我们预计许多模型架构与当前机器学习文献中用于感知等任务的大型深度网络有很大不同。这组综合组件构成了 SageDB 的“大脑”。

目前我们的组件（例如索引结构）“仅”使用这些模型。然而，我们的宏伟愿景是系统综合专门用于数据、工作负载和硬件的各个组件，并且组件的具体选择及其交互也将取决于环境。例如，在更新密集型设置中，可以选择与更加集中于分析的环境中不同的模型和组件，或者在分布式设置中，可以选择更适合批量和分布式更新的模型。

各个组件通常可以共享先前学习的模型（例如，优化器和索引都可以使用相同的分布）。在某些情况下，组件本身可能是完全学习的（例如，参见第 4.3 节作为示例）或形成模型和某些生成代码之间的混合体。因此，虽然图 2 中模型和算法有明显的分离，但我们期望在实践中实现更流畅的过渡。例如，强化学习技术可能在许多领域（例如查询优化）中至关重要，它在建模和综合之间创建了一个更具迭代性的过程。

接下来，我们将更详细地概述一些关于如何将学习方法和模型用于各种数据库组件的初步结果。

3. DATA ACCESS

存储布局和索引结构是保证高效数据访问的最重要因素，正如本节将展示的那样，两者都可以通过数据和工作负载模型来增强。

3.1 Single Dimensional Indexes

索引结构已经是模型，因为它们“预测”给定键的值的位置。作为一个示例，考虑一种内存存储，其中所有数据都存储在一个按时间戳排序的连续数组中。在此设置中，由于缓存效应，高效缓存的 B 树通常比简单搜索提供更好的性能，并且可以将其视为从查找键到已排序记录数组内的位置的映射。因此，B 树是一个模型，在 ML 术语中是回归树：它将键映射到位置，因此，我们可以用任何其他类型的模型替换索引。虽然人们可能想知道，其他模型如何保证它们也找到所有相关数据，但它出人意料地简单：必须对数据进行排序以支持有效的范围请求，因此任何错误都可以通过围绕预测的本地搜索轻松纠正。

初步结果：在[19]中，我们表明，通过使用前面提到的 RMI 索引，模型的性能可以比最先进的 B 树实现高出两倍，同时数量级更小（注意，更新的 arXiv 版本包含新结果）。从那时起，我们扩展了这个想法，还支持存储在磁盘上的数据、压缩、插入以及多维数据（参见下一节）。

3.2 Multi-Dim. Indexes and Storage Layout

R 树与多维数据的 B 树类似，它存储数据上的边界框树；树中的每个节点都是一个边界框，其子节点是其中包含的较小边界框。因此，R 树是一种近似模型，它使用此树结构来预测点位于查询边界内的页面。特别是，当数据连续存储在磁盘或内存上时，R-Tree 是一种将查询矩形映射到索引范围 [si, ti] 列表的模型，以便包含位于矩形中的每个点的索引在这些范围的联合中。与 B 树类似，它是一个近似模型，因为稍后必须彻底扫描这些范围以仅查找满足查询的点。

有趣的是，和以前一样，其他模型可以用作 R 树的直接替代品。然而，与一维情况一样，我们需要确保能够有效地“纠正”模型的任何不精确性，即在多维情况下要困难得多，因为不存在明显的存储顺序（回想一下，在一维情况下，我们假设数据按键排序，并且任何不精确都可以通过局部搜索轻松纠正）。因此，学习索引的成功不仅取决于模型的选择，还取决于数据在内存/磁盘中的排列方式，即布局；糟糕的布局可能会导致模型的准确性降低和/或每个查询需要查找的范围很多。

选择布局：布局可以通过投影函数 L : Rd → R 来描述，将维度 d 的每个数据记录映射到确定其在排序中的相对位置的排序键（参见图 3）。这种布局最自然的选择是多维 CDF，即 L(r) = P (X1 < r1, ..., Xd < rd)。不幸的是，这有一个主要缺点：具有相同排序键的两个点在 Rd 中可能彼此相距很远。即使这些点之一周围的一个小查询矩形也会导致排序键范围包含大量无关点。

选择布局：布局可以通过投影函数 L :

R^d

→

R

来描述，将维度 d 的每个数据记录映射到确定其在排序中的相对位置的排序键（参见图 3）。这种布局最自然的选择是多维 CDF，即

L(r) = P (X_1 < r_1, ..., X_d < r_d)

。不幸的是，这有一个主要缺点：具有相同排序键的两个点在

R^d

中可能彼此相距很远。即使这些点之一周围的一个小查询矩形也会导致排序键范围包含大量无关点。

虽然存在许多可能的投影策略，但我们发现，沿着一系列维度连续将点排序和划分为大小相等的单元，会产生一种计算高效、可学习的布局（例如，与 z 顺序相反，z 顺序很难实现）学习）和紧密（即索引范围并集中的几乎所有点都满足查询）。分区的想法并不新鲜：现有的数据库系统允许管理员手动选择多个列进行分区 [13, 23]。我们的贡献是（1）允许非轴对齐且比静态层次结构分区更复杂的投影，（2）使用模型实际进行投影并查找存储上的数据，以及（3）使用数据和查询分布自动学习分区维度和每个分区的粒度，而不需要不精确的手动调整。在粗略层面上，我们的分区也与局部敏感哈希（LSH）[11]有一些相似之处，后者主要用于相似性搜索。与 LSH 一样，通过沿维度序列排序和分区进行投影会创建分区数据空间的多维“单元”。在我们学习的索引中，点按它们占据的单元格的索引排序。

初步结果：我们通过压缩在内存列存储 [33] 上实现学习索引，并将我们的结果与在同一列存储上实现的以下三个基线进行比较（图 4）：

列扫描：对查询中涉及的所有列进行全面扫描。

聚集：聚集索引按提供最佳整体性能的列对数据进行排序（例如，如果所有列的查询频率相同，则这将是最具选择性的维度）。在查询时，如果涉及的列用作谓词的一部分，它首先对排序列执行二分搜索以缩小扫描点的范围。

针对查询工作负载中存在的维度的 R-Tree 索引。

所有基准测试都是单线程的，并使用来自 TPC-H 基准测试的 lineitem 表的数据，该表有 6000 万条记录。所有数据都预先加载到内存中（没有磁盘访问）。查询工作负载由最多三个维度上的随机生成的范围查询组成，并且所有查询都使用相同的三个维度。每个查询的选择性约为 0.25%。执行范围过滤器后，每个查询还在第四个维度上执行 SUM 聚合。图 4 显示，与聚集索引相比，学习索引将范围查询速度平均提高了 34 倍，而空间开销却很小。请注意，R 树的性能比全列扫描差，因为它必须访问索引中的每一列，即使它们没有出现在查询中。

性能分析：当查询过滤器中存在聚集维度时，聚集索引的性能最佳。如果不存在聚集维度，则聚集索引将恢复为全列扫描。另一方面，学习索引是在多个维度上排序。如果我们假设聚集维度也存在于学习索引的排序维度中，则学习索引在两种情况下应该优于聚集索引：

查询对聚集列和学习索引中使用的至少一个其他维度进行过滤。学习索引利用数据按第二维部分排序的事实来限制无关扫描点的数量。

查询的过滤器包含学习索引中的维度，但不包含聚集维度。与执行全列扫描的聚集索引相反，学习索引能够通过仅考虑相关单元来限制扫描点的区域。

为了量化学习索引的性能增益，我们按查询类型细分之前的结果（图 4），查询类型表示每个查询中过滤的维度。学习索引在三个维度上排序，因此为了简洁起见，每个查询类型都由三位二进制数表示：如果查询在学习索引使用的维度序列中的第 i 个维度上进行筛选，则第 i 个最高有效位为 1。例如，查询类型“110”表示对学习索引中使用的第一和第二维度进行过滤的查询，但不对第三维度进行过滤。基线是一个聚集索引，根据学习索引的第一个维度进行排序，这是我们的查询工作负载中最具选择性的维度。

图 5 证实学习索引在几乎所有类型的查询上都优于聚集索引。学习索引相对于聚集索引没有改进的唯一查询类型是当聚集维度是查询中的唯一维度时。在这种情况下，聚集索引能够在与查询匹配的点上优化其扫描，而学习索引必须产生扫描与匹配点位于相同单元格中的无关点的开销。

每种查询类型的所有查询都具有约 0.25% 的相同选择性，以控制结果大小对查询时间的影响。因此，单个维度上的过滤器范围取决于查询中包含多少个其他维度：与类型“100”的查询相比，类型“110”的查询必须在第一个维度上查询更大的范围以达到同样的选择性。这个效果解释了为什么类型为“111”的聚集索引查询明显慢于“110”和“101”，而“110”和“101”又比“100”慢。另一方面，学习索引避免了这种减速，因为它的查询时间随整个查询的范围而变化，而不仅仅是第一个维度的范围。

4. QUERY EXECUTION

上一节概述了学习数据分布（CDF 模型）如何取代传统索引结构，为 TPU/GPU 带来潜在的巨大优势。也许令人惊讶的是，一个非常相似的想法可以用来加速排序、连接甚至分组。

4.1 Sorting

加速排序的基本思想是使用（现有的）CDF 模型 F 将记录大致按排序顺序排列，然后纠正几乎完美排序的数据，如算法 1 所示。取决于模型的执行成本及其精度，这种排序技术比其他排序技术具有显着的性能优势。

例如，假设以下查询： SELECT * FROM customer c ORDER BY c.name，表大小为 N，并且 c.name 上有辅助学习索引，而数据按客户 ID 而非名称的顺序存储。为了按名称快速对数据进行排序，我们将基于名称的 CDF 模型的输出缩放到数组中元素的数量，将基于其键 k 的每个记录放入粗略排序的顺序 (pos = F (k) ∗ N ) 。此时，我们将每个记录映射到输出数组中的一个位置，如果发生冲突，我们将其存储在一些溢出数组中（算法 1 中的第 5-10 行）。为了减少冲突次数，我们可以分配一个比 N 大 m 倍的输出数组（例如，m = 1.37），然后删除此映射末尾的任何空位置。请注意，对于这种情况，预测位置将计算为 pos = F (k) * m * N（算法 1 中的第 6 行）。此外，我们可以按桶排序，而不是按位置桶 = F (k) * N/bs，其中 bs 是桶大小，以进一步减少冲突数量。这里的假设是，如果我们将桶设为多个缓存行，我们可以在存储桶内快速排序，同时减少冲突的机会（例如，我们将比槽位更多的项目映射到存储桶）。类似的想法被用作布谷鸟哈希的一部分[25]。在任何一种情况下，如果我们的模型是非单调的，我们都必须使用高效的局部排序算法（即插入排序，它对于几乎排序数组的工作速度非常快）来纠正任何排序错误（算法 1 中的第 12 行）。最后，我们对溢出数组进行排序（第 13 行），并将排序后的数组与溢出数组合并，同时删除空元素（第 15 行）。

从概念上讲，基于模型的排序与基数排序非常相似。基数排序的复杂度为 O((n) ∗ logb(k))，其中 k 是最大可能值，b 是前缀排序的基础。也就是说，如果我们一次基于 1 个字节（即以 28 为基数）对任意 32 位整数进行 Radix 排序，则复杂度将为 O(4 * N )。我们基于学习的排序的想法是使基 b 接近 k，这将允许在 O(N ) 中进行排序。显然，这忽略了模型的复杂性，在许多现实场景中，模型的复杂性可能会随着 k 和 n 的增加而增加。同时，很容易想到基于模型的排序方法将大大优于基于基数的排序的场景。例如，如果我们有来自一个非常大的域的密钥（即 k 非常大），但大多数密钥都集中在域空间的一小部分区域中。在这种情况下，模型可以学习 CDF 的非常紧凑的表示，因此排序可能接近 O(N )，而传统的基数排序算法会受到域大小过大的影响。对域大小的敏感性也是大多数算法库不实现基数排序而是使用快速排序的变体实现基数排序的原因之一。

图 6 显示了一种学习方法的早期结果，该方法对越来越大的数据大小进行排序，该数据大小由从运行单线程的正态分布中随机采样的 64 位双精度数组成。我们同时使用分桶和 m 倍大的数组分配，并且我们的模型是非单调的，需要算法 1 中第 12 行的修饰步骤。该图比较了 Timsort（Java2 和 Python3 的默认排序算法）和 Quicksort 、来自 C++ 库的 std::sort、基数排序和学习排序。我们报告总排序时间（左）以及排序率（右）。请注意，没有任何实现经过调整以利用 SIMD 或 FMA 指令。可以看出，学习的变体比基于比较的方法具有显着的性能优势，并且比基数排序的执行速度平均快 18%。更有趣的是，学习方法的排序率非常稳定。请注意，在本例中，学习排序方法的 RMI 模型构建时间不包括在内。如果我们基于（对数）数据样本训练一个小型模型，基数排序和学习排序之间的差异将缩小到 10%。

图 7 显示了学习排序在近似排序（算法 1 中的第 5-10 行）、修饰（第 12-13 行）和合并结果（第 15 行）之间的时间分解。我们相信，这一结果显示了学习排序方法的潜力，我们预计这种方法对于分布式排序、大密钥大小以及 GPU/TPU/FPGA 加速器来说是最大的。因此，从正确确定复杂性类别到构建 SIMD 优化实现，仍然存在许多开放研究挑战。

4.2 Joins and other operations

连接可以像排序一样加速。例如，CDF 模型可用于跳过部分数据作为合并排序的一部分。考虑一个列存储，其中两个连接列已排序，并且每列有一个 CDF 模型。现在，在合并连接期间，我们可以使用模型跳过不会连接的数据。

del 跳过不会加入的数据。学习到的模型也有助于改进其他算法。例如，模型可以用作更多高效的哈希函数作为分组的一部分。这里的挑战是，如果没有选择所有键并有效地集成到查询计划中，则调整学习模型。类似地，该模型可以用作基数估计，作为分组或其他操作的一部分，例如，为中间结果分配足够的内存。

4.3 Scheduling

当今的数据库系统使用简单的调度策略，例如先到先服务，因为它们具有通用性且易于实现。然而，针对特定工作负载定制的调度程序可以执行各种优化；例如，它可以优先考虑快速且低成本的查询，选择特定于查询的并行阈值，以及对查询执行中的操作进行排序以避免瓶颈（例如，利用查询结构与其他非依赖阶段并行运行慢速阶段）。这种特定于工作负载的策略在实践中很少使用，因为它们需要专业知识，并且需要花费大量精力来设计、实施和验证。

在 SageDB 中，我们设想了一种新的调度系统，可以自动学习针对数据和工作负载定制的高效调度策略。我们的系统将调度算法表示为神经网络，该神经网络将数据（例如，使用 CDF 模型）和查询工作负载（例如，使用在之前的查询执行上训练的模型）作为输入信息来做出调度决策。我们使用现代强化学习（RL）技术训练调度神经网络，以优化高级系统目标，例如最小平均查询完成时间。

初步结果：我们为批量数据分析作业实现了第一个基于强化学习的调度系统 [21]，并在 Spark [38] 中实现了原型。我们的系统使用图神经网络 [3, 18] 来编码表示为处理阶段的有向无环图 (DAG) 的查询的调度算法。神经网络决定如何在 DAG 之间划分执行器以及如何排序每个 DAG 内阶段的执行。我们通过大量模拟实验来训练神经网络，它安排工作负载，观察结果，并使用策略梯度 RL 算法逐步改进其策略。

图 8 直观地显示了 (a) Spark 默认 FIFO 调度所施加的调度； (b) 最短作业优先（SJF）政策，严格优先考虑短作业； (c) 一个公平的调度程序，可以在作业之间动态划分任务槽； (d) 学习的调度策略，每个策略运行 TPC-H 查询的随机组合。与 Spark 的默认 FIFO 调度程序相比，学习调度程序将平均作业完成时间 (JCT) 提高了 45%，比公平调度程序提高了 19%。它通过以下方式实现加速：(i) 快速完成短作业——注意在前 40 秒内完成的 5 个作业（显示为垂直红线）； (ii) 最大化集群效率。不像 SJF 策略一样，它天真地将任务槽专用于小作业，以便尽早完成它们（但效率低下），学习调度程序在其并行性“最佳点”附近运行作业。通过控制并行度，与 SJF 相比，完成所有作业的总时间减少了 30%。此外，与公平调度不同，它学会在作业之间非均匀地划分任务槽，从而提高平均 JCT。

5. QUERY OPTIMIZER

传统的查询优化器非常难以构建、维护，并且通常会产生次优的查询计划。优化器的脆弱性和复杂性使其成为学习的一个很好的候选者。事实上，最近有几种方法旨在学习更有效的最佳连接顺序搜索策略 [20, 22]，改进基数估计 [17]，或通过强化学习学习整个计划生成过程 [24] 。

然而，他们在很大程度上做出了不切实际的假设。例如，[20]假设基表上的谓词有完美的基数估计，而[17]和[24]都没有显示改进的基数估计是否实际上会带来更好的查询计划。原因是，改进平均基数估计相对容易，但在真正重要的情况下改进基数估计极其困难：当它实际更改连接顺序时或当估计导致“错误”连接算法时被选中。此外，现有的方法还存在初始化问题；它们通常需要大量的训练数据并且不假设任何临时查询。

因此，我们必须开始探索查询优化的替代方法。最值得注意的是，我们试图使传统的成本模型（例如 Selinger 模型 [29]）可微。也就是说，我们从传统的手动调整模型开始，例如[29]中定义的模型，但使其可微分，以便我们可以在每次查询后改进模型，为特定的数据实例定制模型。这种方法的最大优点是，它解决了初始化问题以及模型如何执行即席查询的问题。最初，系统使用标准模型，然后随着时间的推移进行完善。这种方法的初步结果表明，我们确实可以提高模型的质量，但是如果不对基数估计问题做出重大改进，我们就无法获得巨大的收益。

因此，我们开始探索基于混合模型的基数估计方法。核心思想是，尝试在学习数据的基本模式和相关性的模型与捕获特定数据实例的极端（难以学习）异常的异常/离群值列表之间找到最佳平衡。

6. OTHER OPPORTUNITIES

除了查询优化、数据访问路径优化和查询执行之外，以模型为中心的数据库设计还可以提供从近似查询处理 (AQP) 到插入的额外好处，如下所述：

AQP 和数据立方体：CDF 模型为近似查询处理（尤其是数据立方体操作）开辟了全新的可能性。回想一下，多维 CDF 允许我们按属性任意过滤。此外，典型数据立方体的几个维度很可能具有相关性，这是可以学习的。这反过来又可以产生紧凑的模型，可以用来高精度地近似查询。虽然其他作品探索了 AQP 模型的使用 [26, 8]，但关键区别在于 SageDB 使用相同类型的模型进行索引、AQP、查询优化等。

预测建模：类似地，CDF 模型可用于构建数据预测模型。然而，预测模型需要对新数据的泛化性，而我们的模型专注于学习经验分布，其中过度拟合是一件好事。当然，经验数据分布和基础数据分布之间存在密切的联系，可以利用这种联系来加速预测模型的训练。

插入/更新：虽然 SageDB 当前的重点是分析，但更新繁重的工作负载存在巨大潜力。例如，假设来自插入的数据遵循与已存储的数据类似的分布，并且模型对数据进行概括。在这种情况下，无需重新训练（即重新平衡）。对于索引，这意味着插入将变成 O(1) 操作。在[19]中，我们更详细地讨论了更新繁重的工作负载的潜力，尽管显然还有更多的工作要做。

复杂性分析和鲁棒性保证：存在几个有趣的理论问题。最明显的一个是如何为学习的算法和数据结构定义复杂性类别。明显的起点是实例最优性的定义，它定义算法 B 相对于一类算法 A 和数据库 d 来说是实例最优的，如果

cost(B, d) ≤ c · cost(a, d) + c′

因此，通过自我设计和学习进行定制的目标可能可以表述为为给定数据库找到最佳算法的目标。

同样，如果数据分布或工作负载发生变化，我们希望提供最坏情况下的性能保证。例如，在[19]中，我们提出了一种混合学习数据结构，它在最坏的情况下提供了 B 树 O(log N ) 的查找性能。然而，如何更广泛地提供这些保证在很大程度上是一个悬而未决的问题，并且与平滑分析 [30, 31] 和强大的机器学习 [32] 有着密切的联系。

7. CONCLUSION

SageDB 提出了一种构建数据库系统的全新方法，通过使用 ML 模型与程序合成相结合来生成系统组件。如果成功，我们相信这种方法将催生新一代大数据处理工具，它可以更好地利用 GPU 和 TPU，在以下方面提供显着优势：存储消耗和空间，在某些情况下，甚至改变某些数据操作的复杂性类别。我们提出了初步结果和初步设计，展示了这些想法的前景，以及一系列未来方向，突出了我们的方法所带来的重要研究机会。