浏览混合列/行导向 DBMS 方案

原文地址：http://dbmsmusings.blogspot.com/2009/09/tour-through-hybrid-columnrow-oriented.html
原文作者：Daniel Abadi
发表日期：2009 年 9 月 3 日，星期四

最近有很多关于混合列存储/行存储数据库系统的讨论。这可能是由于在过去一个月中发布了许多类似的公告，例如 Vertica 最近发布的包含FlexStore的 3.5 版本、Oracle最近披露Oracle Database 11g 第 2 版使用面向列的存储来实现卓越的压缩，以及 VectoreWise最近的 decloaking该公司还宣布了一个可选的混合存储层。此外，Curt Monash 和 Philip Howard 等分析师预测该领域的进一步发展（参见此处和此处）。

令我惊讶的是，我们花了这么长时间才开始看到混合系统的商业应用。几十年来，研究界一直在发表关于混合系统的论文，其中直接的建议可以很容易地在 8 年前开始发表的商业系统中实施。

构建混合系统的不同方法会产生非常不同的性能属性并解决不同的问题集。因此，随着越来越多的混合系统在商业上可用，并且随着越来越多的公司考虑开发自己的混合系统，人们了解各种混合方案之间涉及的不同权衡是很重要的。我在这篇文章中的目标是向不属于 SIGMOD/VLDB 研究社区的人们介绍三种由不同研究工作采用的构建混合系统的著名方法，并提供研究论文的指针，读者可以在其中找到更多详细信息. 每种方法都有自己的优点和缺点，我将尝试在每种情况下列出权衡的双方。

方法 1：PAX

PAX 方案于 2001 年在 Natassa Ailamaki、David DeWitt、Mark Hill 和 Marios Skounakis 的 VLDB 论文“缓存性能的编织关系”中发表。基本思想如下：而不是在磁盘块中逐行存储数据，逐列存储。这与“纯”列存储不同，后者将每列存储在完全独立的磁盘块中。关键区别在于，如果您有一个具有 10 个属性的表，那么在“纯”列存储中，来自每个原始元组的数据分布在 10 个不同的磁盘块中，而在 PAX 中，每个元组的所有数据都可以在一个单个磁盘块。由于磁盘块是可以从磁盘读取数据的最小粒度，因此在 PAX 中，即使查询仅访问 10 列中的 1 列，也不可能仅从磁盘读取这一列，因为每个磁盘块包含表的所有 10 个属性的数据。

要理解为什么这是一个好主意，需要一些上下文。在撰写本文时，列存储（本文中称为“DSM 模型”）对商业领域的影响非常有限（有 Sybase IQ，但当时它只是一个小众产品）。人们普遍认为，DSM模型未能起飞的原因是由于元组重建成本高。

假设一个查询访问了表中十分之三的列，并且需要一些运算符（如聚合），要求对这三个列中的每一列进行完全扫描。行存储必须进行完整的表扫描，除了读取 3 个相关列之外，还浪费了一些 I/O 来读取 7 个不相关的列。但至少它会按顺序读取整个表格。列存储只需读取 3 个相关列，但必须在 3 个列之间来回查找，进行元组重建。在 2001 年，服务器的内存容量远不及今天的容量，因此无法进行广泛的预取（即，不是从第 1 列读取一个块，然后从第 2 列读取一个块，然后从第 3 列读取一个块，然后再读取下一个块）从第 1 列阻止，等等，预取允许您从第 1 列读取 n 个块，然后从第 2 列读取 n 个块，依此类推，允许在大量顺序读取中分摊寻道成本，但您需要足够的内存来将内存中每列的 n 个块保存在一次）。考虑到相对于顺序访问而言，查找成本是多么昂贵，在系统内存增加到最近的水平以允许大量预取之前，列存储没有起飞并不是偶然的。（当需要物化较少的元组时，延迟物化延迟元组重建直到查询结束时的研究也有帮助）。考虑到相对于顺序访问而言，查找成本是多么昂贵，在系统内存增加到最近的水平以允许大量预取之前，列存储没有起飞并不是偶然的。（当需要物化较少的元组时，延迟物化延迟元组重建直到查询结束时的研究也有帮助）。考虑到相对于顺序访问而言，查找成本是多么昂贵，在系统内存增加到最近的水平以允许大量预取之前，列存储没有起飞并不是偶然的。（当需要物化较少的元组时，延迟物化延迟元组重建直到查询结束时的研究也有帮助）。

无论如何，PAX 能够实现列存储的 CPU 效率，同时保持行存储的磁盘 I/O 属性。对于那些没有详细了解列存储的人来说，这可能看起来很奇怪：大多数列存储推销其产品的方式是强调磁盘 I/O 效率优势（您只需从磁盘读取特定查询）。为什么列存储需要与行存储等效的磁盘访问模式？好吧，事实证明，列存储也有一个经常被忽视的显着 CPU 效率。PAX 论文检查的 CPU 效率方面是缓存命中率和内存带宽要求。事实证明，将列数据按顺序存储在一个块中允许缓存行仅包含来自一列的数据。由于大多数 DBMS 运算符一次只对一两列进行操作，因此缓存中填充了该操作的相关数据，从而减少了由于缓存未命中导致的 CPU 效率低下。此外，只有任何特定操作的相关列才需要从内存中传送。

底线：

PAX 的优势：

• 提供列存储的大部分 CPU 效率
• 允许面向列的压缩方案，由于增加了数据局部性（来自同一属性域的数据连续存储），因此可以提高压缩率。这可以提高性能，因为可以压缩的数据越多，从存储中读取数据所需的时间就越少。
• 理论上在行存储系统中实现相当容易，以获得一些列存储优势。我说“理论上”是因为在 Oracle 11gR2 之前没有商业行存储系统真正做到这一点（据我所知）。

PAX 的缺点

• 与行存储等效的 I/O 属性（不计算压缩），因为无关列仍然必须从与任何特定查询所需列相同的块中的存储中读取。在 2001 年，这是一个优势。今天，对于典型的分析工作负载，这是一个很大的缺点。（对于较少面向扫描的工作负载，例如元组查找和大海捞针查询，这仍然是一个优势）。
• 现代处理器上的缓存预取功能使 PAX 的一些缓存效率过时（PAX 不再对缓存命中率产生很大影响）。但是，它仍然降低了对内存带宽的需求，并且列存储的其他 CPU 优势，例如向量化处理，仍然可以在 PAX 中实现。

方法2：破碎的镜子

该方案于 2002 年发表在 Ravi Ramamurthy、David DeWitt 和 Qi Su 的 VLDB 论文“A Case for Fractured Mirrors”中。（是的，您没看错。由 DeWitt 领导的威斯康星大学 DBMS 小组撰写了两篇关于混合列存储/行存储系统的开创性论文。）该方法基本上如下：您将复制所有数据无论如何，以实现高可用性和/或灾难恢复。为什么不在每个副本中使用不同的存储布局？这样，如果您有元组查找或大海捞针查询，您可以将其发送到行存储副本。如果查询更面向扫描（例如聚合或汇总查询），则将其发送到列存储副本。论文中的实现稍微复杂一些（为了避免歪斜，每个节点都包含部分列存储和部分行存储），

大多数人都同意（我认为）对于元组查找查询，行存储比列存储快一个数量级以上，而对于扫描，列存储（至少）比行存储快一个数量级以上面向查询。以下是得出这个结论的方法：要在行存储中查找元组，只需读取包含该元组的一个块（假设行存储和列存储的所有相关索引都是在记忆中）。在列存储中，需要为每个属性读取一个块。假设表中有10多个属性，这已经是一个数量级以上了。另一方面，对于扫描查询，如果一个查询访问不到 10% 的表属性（常见情况），列存储相对于行存储立即获得一个数量级的改进（为了磁盘效率）。此外，许多人认为（见here和here）列存储在 CPU 效率方面获得了额外的数量级改进。

如果您相信上述论点，那么对于混合工作负载使用像破碎镜像这样的方案至关重要。鉴于人们经常将混合工作负载视为企业数据仓库中的一个关键问题，令人惊讶的是花了多长时间才看到研究论文中所写的商业实施。

破碎镜的优点：

• 每个单独的查询都会被发送到该查询的最佳存储。因此，对于那种类型的存储有问题的查询，性能比纯行存储或纯列存储要好一个数量级。

破碎镜的缺点：

• 所有数据都需要复制。显然，在大多数情况下，无论如何您都会复制数据。但是，如果您已经将复制用于其他目的（例如以不同的排序顺序存储数据），那么您需要增加复制因子或删除一些额外的排序顺序以实现破碎镜像。
• 如果您真的想充分利用这种方法，您需要扩展研究论文中提出的内容，并拥有行存储和列存储系统的完整实现（因为列存储具有非常不同的查询执行引擎和查询优化器而不是行存储）。这显然是很多代码，并且阻止了大多数公司使用断裂的镜像方法。我很困惑为什么唯一一家拥有合法行存储和列存储 DBMS 产品（带有 ASE 和 IQ 的 Sybase）的公司还没有实施断裂镜像方法。

方法 3：细粒度混合Hankins 和 Patel

的VLDB 2003 论文和Cudre-Mauroux、Wu 和 Madden的CIDR 2009 论文是这种方法的示例。在这里，单个表可以分为面向行和面向列的存储。例如，如果经常一起访问两列（例如 order-date 和 ship-date），则可以将它们存储在一起（按行）。其余列可以单独存储。这可以在磁盘块内、表内甚至跨​​表的稍大粒度的情况下完成。例如，如果一个表经常通过元组查找访问（例如客户表），那么它可以存储在行中；而通常扫描的其他表（例如lineitem）可以存储在列中。

• 细粒度杂交的优势
  如果正确决定哪些属性（和/或表）应该存储在行中，哪些属性应该存储在列中，那么您可以获得断裂镜像的所有性能优势，而不会产生额外的复制劣势。

细粒度混合的缺点

• 根据您开始使用的 DBMS 系统，实施起来可能很复杂。本质上，您必须同时拥有面向行和面向列的执行引擎，优化器必须了解行存储和列存储之间的差异，并且必须适当更新索引代码。事实证明，在已经支持早期实现（早期实现是指在查询计划中早期从列存储重建行的能力）的列存储中实现比在其他类型的系统中更容易实现。这是因为早期实现要求查询运算符能够处理面向列格式和面向行格式的输入（如果元组尚未具体化，它将采用列格式，否则它将采用面向行格式）。
• 它需要一些关于查询工作负载的知识。否则将做出关于元组布局的错误决策，导致性能欠佳。

商业可用性

Oracle、Vertica 和 VectorWise 已宣布使用其中一种方案的混合系统（我对这些实现中的任何一种都没有内部知识，只知道在所有情况下公开发布的内容）。看来 Oracle（请参阅Kevin Closson在他的一篇博客文章的评论线程中对我的问题的有用回复）和 VectorWise 使用第一种方法 PAX。Vertica 使用细粒度混合（方法 3），但如果他们愿意，他们可能也可以使用其面向行的存储方案来实现碎片镜像（方法 2）。鉴于碎片镜像论文的三分之二的作者已经在微软重聚，如果微软最终实施碎片镜像混合方案，我不会感到惊讶。

结论

有近十年的延迟，但我们终于开始看到混合行/列商店进入市场。行存储和列存储具有非常不同的性能特征，并且它们往往在替代方案擅长的地方挣扎。随着工作负载变得越来越复杂，混合系统的重要性将增加。

参考文献：

《Oracle 11gR2 已发布 - 并带有面向列的存储选项》：
https://www.modb.pro/db/413309

《注意 VectorWise》：https://www.modb.pro/db/413511

《帕克思分析？行存储和列存储开始组合在一起》：https://www.modb.pro/db/414595

Data Morphing- An Adaptive, Cache-Conscious Storage Technique.pdf：https://www.modb.pro/doc/64115