前沿观察 | SageDB：一个自学成才的数据库

版权声明：本文由腾讯云数据库产品团队整理，页面原始内容来自于db weekly英文官网，若转载请注明出处。翻译目的在于传递更多全球最新数据库领域相关信息，并不意味着腾讯云数据库产品团队赞同其观点或证实其内容的真实性。如果其他媒体、网站或其他任何形式的法律实体和个人使用，必须经过著作权人合法书面授权并自负全部法律责任。不得擅自使用腾讯云数据库团队的名义进行转载，或盗用腾讯云数据库团队名义发布信息。

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

我们需要什么样的模型

在缺乏在线学习和自适应的情况下，数据库系统设计被用于通用目的，没有充分利用工作负载和手头数据的特定特征。SageDB则是通过学习数据和工作负载的分布来缩小与专用解决方案之间的差距。

考虑一个极端情况：我们希望使用连续整数键来存储和查询固定长度记录的范围。这种情况下使用传统索引没有任何意义，因为连续整数键本身可以用作偏移量。AC程序将100M整数加载到一个数组中，并在一个范围内求和，运行时间约为300ms。在Postgres中执行相同的操作大约需要150秒：通用目的设计多花了500倍的时间。

“我们可以利用精确数据分布优化数据库使用的绝大多数算法或数据结构。这些优化有时甚至可以改变众所周知的数据处理算法的时间复杂度。”

数据分布以（学习的）模型的形式出现。有了这样的模型，作者认为我们可以自动形成索引结构，完成排序和连接算法甚至整个查询优化器，利用数据分布模式来提高性能。

过拟合是很好的选择

什么样的模型有意义？例如，直方图是一个非常简单的模型，但对于此处讨论的用例，要么太粗糙，要么太大而无法使用。另一方面，深度神经网络成本很高（尽管随着硬件的进步，预计会减少这些成本）。结合上述事实和用例，“过拟合”是一个好的选择！我们希望尽可能精确地获得准确数据的细微差别。（迄今为止的研究计划主要集中在分析工作负载上）。

‘截至今天，我们发现经常需要生成特殊模型才能看到显著的性能提升。’

例如，考虑“学习索引结构的案例 ”[1]一文中的RMI模型：

1.在数据上拟合简单模型（线性回归，简单神经网络等）

2.使用模型的预测值来挑选另一个模型，即专家，它可以更准确地模拟数据子集

3.重复该过程，直到叶模型进行最终预测

RMI只是一个起点。例如，还可以使顶部模型或底部模型更复杂、在特定级别阶段用其他类型的模型替换部分模型、使用量化、改变特征表示、将模型与其他数据结构组合等等。因此，我们相信将看到很多新理念爆炸式地出现，这些新理念是关于如何在给定工作负载情况下最有效地为数据库组件生成模型，并在精度，低延迟，空间和执行时间之间实现很好的平衡。

数据访问

去年发表的“学习索引结构的案例”的论文表明，基于RMI的索引可以胜过最先进的B-Tree性能的两倍，同时规模小一些（“ 请注意，更新的arXiv版本包含新的结果 “）。后续工作已将其扩展到磁盘数据存储，压缩插入和多维数据。

对于多维数据，基线是R树（与B树相对）。R-Trees将矩形映射到索引范围列表，使得位于矩形中的每个点的索引包含在这些范围的并集中。我们可以用学习模型替换R-Tree，就像B-Tree一样。使RMI B-Tree有效替换的一个技巧是模型足以使我们“在正确的位置”，然后我们可以围绕预测进行局部搜索以完成工作。对于R-Trees，我们还需要一种能够实现高效本地化搜索的布局。

“虽然存在许多可能的投影策略，但我们发现沿着一系列维度连续排序和分割点到相同大小的单元格会产生一个有效映射，一个可学习的布局（例如，与z顺序相比，这很难学习）和密集（即，索引范围并集中的所有点都满足查询）。”

作者使用压缩在内存中的列存储，实现了上文的学习索引，并将其与完整的列进行扫描，对聚簇索引（按提供最佳整体性能的列排序）和R-Tree进行了比较。基准测试使用lineitem的TPC-H基准测试表中的6000万条记录，查询选择性为0.25％。

基于学习的索引完胜目前最佳性能的实现34倍（注意图表上的日志比例），与集群解决方案相比，其空间开销更小。

进一步的分析表明，学习的索引几乎在每种类型的查询中都胜过聚簇索引 - 例外情况是聚簇索引中的聚簇维度是查询中的唯一维度。

查询执行

这是本文最有趣的部分之一，因为它展示了学习模型如何能够帮助处理这种不起眼的古老的分类案例。排序方法是使用学习模型将记录按正确顺序排列，然后将最新的完善排序数据作为最后一步进行纠正。为此，可以使用有效的局部排序，例如插入排序。

下图显示了从正态分布中随机采样的64位双精度数据，随数据大小分类的学习方法的结果。在比较中，Timsort是Java和Python的默认排序，std::sort来自C ++库。学习后的变体平均比下一个最佳（在这种情况下为Radix排序）快18％。

学习的模型也可用于改善连接。例如，考虑具有两个存储的连接列和每列模型的合并连接。我们可以使用该模型来跳过不会加入的数据（作者没有详细说明在这种情况下，“本地修补”的等价物是如何工作的）。

作者还尝试了工作负载感知调度程序，使用图形神经网络实现基于强化学习的调度

系统：

“我们的系统将调度算法表示为神经网络，其采用关于数据的输入信息（例如，使用CDF模型）和查询工作负载（例如，使用在先前执行的查询上训练的模型）来做出调度决策。”

在10个TPC-H查询的示例中，使用学习算法的调度程序比Spark的默认FIFO调度程序将平均作业完成时间提高了45％。

调度程序学习如何实现这一改进策略是将快速完成短期工作与最大化集群效率相结合，学习在并行性“最佳点”附近运行工作。

查询优化器

传统的查询优化器非常难以构建，维护通常会产生次优的查询计划。优化器的脆弱性和复杂性使很难其成为一个很好的候选者...

从传统成本模型开始并通过学习随着时间的推移对其进行细化的初步实验表明，模型质量可以得到改善，但要获得大幅收益，则需要对基数估算进行重大改进。现在的研究方向（尚未报告结果）是探索基于混合模型的基数估计方法。这些混合模型结合了基础数据模式和相关性的学习模型，以及捕获特定数据实例的极端（并且难以学习）异常/异常值监听。

其他可行性

学习模型在未来可能证明有益的其他建议区域包括近似查询处理，预测建模和包括插入和更新的工作负载。

总结

SageDB提出了一种构建数据库系统的全新方法，它使用机器学习模型与程序相结合来生成系统组件。如果成功，我们相信这种方法将产生新一代大数据处理工具，可以更好地利用GPU和TPU，并在存储消耗和空间方面提供显着优势。

[1]https://blog.acolyer.org/2018/01/08/the-case-for-learned-index-structures-part-i/