英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
SageDB: A Learned Database System
Tim Kraska1,2 Mohammad Alizadeh1 Alex Beutel2 Ed H. Chi2 Jialin Ding1 Ani Kristo3 Guillaume Leclerc1 Samuel Madden1 Hongzi Mao1 Vikram Nathan1
1Massachusetts Institute of Technology 2Google 3Brown University
摘要
现代数据处理系统被设计为通用的，因为它们可以处理各种不同的模式，数据类型和数据分布，并且旨在通过使用优化器和成本模型来提供对该数据的有效访问。这种通用性质导致系统无法利用特定应用程序和用户数据的特性。通过SageDB，我们提出了一种新型数据处理系统的愿景，该系统通过代码综合和机器学习高度专注于应用程序。通过建模数据分布，工作负载和硬件，SageDB可以了解数据结构以及最佳访问方法和查询计划。通过代码综合，这些学到的模型基本上嵌入在数据库的每个组件中。因此，SageDB从数据库系统目前的开发方式中进行了彻底的分离，在数据库，机器学习和编程系统中引发了许多新问题。
引言
数据库系统具有自动选择有效算法的悠久历史，例如基于数据统计的合并与散列连接。然而，现有数据库仍然是通用系统，并且不是针对用户的特定工作负载和数据特征逐个设计的，因为手动这样做会耗费大量时间。然而，专业解决方案可以更加高效。例如，如果目标是构建高度调整的系统以存储和查询具有连续整数密钥（例如，密钥1到100M）的固定长度记录的范围，则不应使用常规索引。使用B 树进行此类范围查询没有多大意义，因为密钥本身可以用作偏移量，使其成为一个常量的O（1）操作来查找范围的第一个键.1确实，一个简单的在现代桌面上将100M整数加载到一个射线并在一个范围内执行求和的C程序运行大约300ms，但在现代数据库（Postgres 9.6）中执行相同的操作大约需要150秒。对于不了解特定数据分布的通用设计，这代表500x开销。
类似的好处扩展到排序或连接等操作。 对于排序，如果我们知道密钥来自密集的整数域，我们可以基于主键简化传入记录的排序，因为密钥可以再次用作抵消以将数据直接放入已排序的 对于这个特定的数据实例，减少了从O（N log N）到O（N）的排序复杂性。 连接密集整数键也简化了查找，只需要使用键作为偏移量进行直接查找。 插入和并发控制也可能变得更容易，因为我们不需要保持索引结构同步。
也许令人惊讶的是，对其他数据模式也可以进行相同的优化。例如，如果数据仅包含偶数或遵循任何其他确定性分布，我们可以应用类似的优化。简而言之，我们可以使用精确数据分布的知识来优化数据库使用的几乎任何算法或数据结构。这些优化有时甚至可以改变众所周知的数据处理算法的复杂性。当然，在大多数实际使用案例中，数据并不完全遵循已知模式，并且通常不值得为每个用例设计专门的系统。但是，如果可以了解数据的数据模式，相关性等，我们认为我们可以自动合成索引结构，排序和连接算法，甚至整个查询优化器，利用这些模式获得性能提升。理想情况下，即使对模式的不完全了解，也可以改变算法的复杂性类别，如上例所示。
在本文中，我们介绍了SageDB的愿景，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可以看作是指向包含具有特定键的记录的页面的模型，需要扫描页面以返回实际满足查询的所有记录。 从这个意义上讲，B-Tree已经将执行性能换算为准确性[19]。 基于学习的模型将更灵活地探索这种权衡。
最后，积极使用综合和代码生成将使我们能够自动创建有效的数据结构，将模型与更传统的算法结合起来。 在这里，我们的目标是（1）根据用户的数据分布生成代码，（2）使用嵌入式机器学习模型合成数据库组件，从而平衡给定内存，延迟和计算之间的权衡 用例，同时提供与传统组件相同的语义保护。
构建SageDB需要彻底背离数据库系统当前开发的方式，并涉及数据库，机器学习和编程系统的挑战。 SageDB目前正在作为麻省理工学院新的人工智能数据系统（DSAIL）的一部分开发，该实验室由一个跨学科团队组成，他们在所有这些领域都具有专业知识。 我们的重点是构建新的分析（OLAP）引擎，但我们相信该方法对OLTP或混合工作负载也具有显着优势。 本文的其余部分概述了SageDB的整体架构，个别挑战并提出了一些有希望的初步结果。
模型驱动方法
SageDB背后的核心思想是构建一个或多个关于数据和工作负载分布的模型，并基于它们自动为数据库系统的所有组件构建最佳数据结构和算法。我们称之为“数据库综合”的这种方法将使我们能够通过专门将每个数据库组件的实现专门用于特定数据库，查询工作负载和执行环境来实现前所未有的性能。
定制的类型
目标的定制远远超出了当前使用的有关算法的数据，硬件或性能的统计数据和模型，可大致分为以下几个级别：
通过配置进行自定义：最基本的自定义形式是配置系统，即旋钮调整。 大多数系统和启发式设备都有大量的设置（例如，页面大小，缓冲池大小等）。 传统上，数据库管理员会调整这些旋钮以将通用数据库配置为特定用例。 从这个意义上说，索引的创建，找到正确的分区方案，或者为性能创建物化视图也可以被视为找到系统的最佳配置。 毫不奇怪，基于工作负载和数据特征自动调整这些配置[37,34,7,9,35]已经有很多工作。
通过算法拣选进行自定义：虽然配置系统很大程度上是静态的，但数据库使用查询优化器根据有关数据和配置（例如，可用索引）的统计信息动态“定制”特定查询的执行策略有很长的历史。也就是说，查询优化器决定最佳执行顺序（例如，谓词下推，连接排序等），并从一组可用算法中选择最佳实现（例如，嵌套循环连接与哈希连接）。 这种声明性方法允许用户在高级别上指定查询，而系统计算出如何最好地实现它，是数据库社区最重要的贡献之一。
通过自我设计进行定制：自行设计的系统依赖于在系统中映射关键设计决策的可能空间的概念，并自动生成最适合工作负载和硬件的设计[15]。 这里可能设计的空间由第一主要组件的所有组合和调整定义，例如围栏指针，链接，时间分区等，它们一起形成“数据结构的周期表”[14]。 这远远超出了算法选择或配置系统，因为这些原语的新组合可能会产生以前未知的算法/数据结构，并且可以带来显着的性能提升[15]。
通过学习定制：与自我设计相比，学习系统通过学习模型替换核心数据系统组件。 例如，在[19]中我们展示了如何用模型替换索引，而[21]展示了如何学习特定于工作负载的调度策略。 模型可以捕获传统数据结构和算法很难支持的数据和工作负载属性。 结果，在某些条件下，这些数据结构可以提供最佳情况复杂性，例如O（N）而不是O（N log N），并且产生比通过自设计定制更高的性能增益。 此外，它们将计算类型从传统的控制流重型计算改为数据依赖型计算，这通常可以更有效地在CPU和即将到来的ML加速器上执行。
这些不同类型的定制可以被组合到一起。 特别是，通过自学设计和通过学习定制的定制是相辅相成的，因为学习模型通常必须与更传统的算法和数据结构相结合，以提供相同的语义保证。 更有趣的是，模型可以在数据库系统的不同组件之间共享。 从这个意义上讲，我们在本文中论证，通过学习进行定制是最强大的定制形式，并概述了SageDB如何将模型深入嵌入到所有算法和数据结构中，使模型成为数据库的大脑（参见图2）。
分配的力量
为了说明学习和模型合成算法与这些数据结构模型的强大能力，请考虑以下思想实验：假设我们在具有属性X1,hellip;Xm的表R1上具有经验累积分布函数（CDF）的完美模型（即，没有预测错误）：
MCDF = FX1,...Xm(x1,...xm) = P(X1 le; x1,...,Xm le; xm)
为简单起见，我们使用CDF来指代实际存储在数据库中的数据的经验CDF（即数据的实例），而不是用于该数据的生成函数的理论CDF。 对于分析，我们主要关注经验CDF，但是，对于更新/插入繁重的工作负载，基础CDF起着更重要的作用。 尽管本文主要关注分析，但最后我们将讨论这个主题。
优化器：首先，最明显的是，这样的模型显着地简化了查询优化，因为基数估计基本上是免费的（即，基数估计仅仅是概率质量估计）。 这使得关于最佳连接排序的决策变得更加容易，但是，随着关于查询优化的文献的长期历史已经表明，计算和维护紧凑且准确的多维分布是一个关键挑战，我们将在后面更详细地讨论。
索引：正如我们在[19]中所示，这样的模型也可用于实现点或范围索引。 假设我们在主键X1上有一个索引组织表，它将X1中的数据存储在磁盘上的连续区域和长度为l的固定大小的记录中。 在这种情况下，我们可以通过计算小于给定主键k的概率质量并将其乘以记录总数N和每个记录的大小来计算每个记录的偏移量：
FX1,...Xm (key, infin;2..., infin;m) lowast; N lowast; l
在这种情况下，我们还说MCDF 预测了密钥k的位置。 请注意，此索引支持范围请求，因为它返回的第一个键等于或大于查找键。 假设我们可以在恒定时间内在CDF中执行查找（我们在下面讨论这个假设），这使得任何键的查找都是O(1) 操作，而传统的树结构需要O(logN) 操作。
有趣的是，CDF也可以用于二级索引或多维索引。 但是，在这些情况下，我们不仅需要为索引构建CDF模型，还需要优化存储布局（有关更详细的讨论，请参阅第3节）。
压缩：此外，CDF还可用于压缩数据。 为简单起见，我们假设我们有一个排序列，即lt;attr，r-idgt; -pairs，以及仅在列attr上的CDF模型。 如果我们可以反转CDF - 即，计算列中的位置，列的值 - 那么这个反向CDF模型有效地允许我们完全避免存储attr的值。 该方案可以最好地视为更高级别的熵压缩。 但是，DBMS环境中的美妙之处在于，用于索引，查询优化等的相同模型可能会被重用于压缩。
执行：类似地，CDF模型可以帮助部分或全表连接或排序。 例如，对于排序，贝叶斯定理可用于为表的任何给定子集“重写” MCDF以实现新模型MCDF，其可用于预测排序数组内的每个记录的位置，将排序转换为O（ N）操作。 对于连接，我们需要每个表都有一个MCDF模型，然后可以使用该模型“预测”任何连接键的位置，类似于索引情况。 此外，某些聚合（如计数）也会变得免费，因为系统可以直接使用模型来回答它们，甚至无需访问数据。
高级分析：CDF还可用于许多数据立方体操作和近似查询答案。 例如，大多数OLAP查询涉及求和和计数。 因此，在许多情况下，我们可以使用CDF模型直接（大致）回答这些查询。 此外，这种模型可以直接用作机器学习模型的一部分，或者帮助更快地建立预测模型; 最后，大多数机器学习模型都是关于分配的。 但是，有一点需要注意：机器学习通常是关于普遍性，而不是经验CDF。
讨论：这个使用CDF模型的思想实验表明，这种模型可以嵌入到数据库系统中的深度以及它可以提供的好处。 但这不仅仅与CDF有关。 例如，查询优化器还需要一个成本模型来估计给定计划的执行时间，该计划可以是传统的手动调整模型或学习模型。 而且，在某些情况下，学习整个算法是有意义的。 例如，即使有关于输入设计的完美信息，具有低复杂度的近似最优调度算法也是非常困难的。 在这种情况下，学习数据/查询特定算法可能提供一个有趣的替代方案。
如何选择模型
一个关键的挑战是为SageDB的大脑选择合适的模型。 答案非常简单：有效。 在某些情况下，直方图可能就足够了; 在其问题中，神经网络可能是正确的方法。 然而，到目前为止我们发现的是直方图通常太粗糙或太大而无法使用。 另一方面，至少对于CPU而言，深度和宽度神经网络通常太昂贵而不实用，尽管随着TPU和其他神经处理器的发展，这可能在未来发生变化。
截至今天，我们发现我们经常需要生成特殊模型才能看到显着的好处。作为生成模型的一个例子，考虑[19]中提出的RMI结构（见图1）。对于一维情
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[19896]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
