行和列的区别 列式存储和行式存储它们真正的区别是什么

这篇文章是“列店与行店:它们到底有多大的不同？看完论文，作者许明明。原文链接:https://zhuanlan.zhihu.com/p/54433448

总结

从论文的题目可以看出，这篇论文并不是对一种新技术和新架构的陈述，而是多了一点论证。它的主要目的是找出为什么对于分析类查询，列存储比行存储好得多。有什么好的？一般认为原因是:

分析类查询往往只查询一个表里面很少的几个字段，Column-Store只需要从磁盘读取用户查询的Column，而Row-Store读取每一条记录的时候你会把所有Column的数据读出来，在IO上Column-Store比Row-Store效率高很多，因此性能更好。

本文的目的是告诉大家，Column-Store在存储格式上的优势只是一个方面，没有其他优化措施在查询引擎上的配合，它的性能不会很好。本文认为列存储在查询引擎级别有以下主要优化措施:

块遍历压缩延迟物化Invisible Join

其中，前三点是前人总结出来的，并在现有的专栏商店上实现的，最后一点是本文的创新之处。我们先来看看这些优化方法的细节，最后再来看看它们优化效果的对比。

四种优化策略的详细块遍历

与每元组迭代相比，块迭代实际上是一个批处理操作。单记录遍历的问题是，对于每一条数据，我们需要从行数据中提取所需的列，然后调用相应的函数来处理它。函数调用次数与数据片数是1:1，在数据量较大的情况下，这是一个相当大的开销。块遍历，因为一次处理多条数据，减少了函数调用的次数，当然可以提高性能。

这种提升性能的方法是在行-Store中通过逐案实现的，但是对于列-Store形成了共识，大家都有。而且如果列的值是字节范围的，比如数字类型，那么Column-Store可以进一步提高性能，因为当查询引擎想从一个Block中取其中一个值进行处理时，可以直接使用数组下标来获取数据，进一步提高性能。此外，以数组方式访问数据使我们能够使用现代CPU的一些优化措施，如SIMD，以实现并行执行并进一步提高性能。

压缩

压缩是一种优化的方法，对于列存储比行存储更有效。原因很简单。我个人对压缩的理解是:

对数据进行更高效的编码, 使得我们可以以更少的空间表达相同的意思。

更高效编码的前提是，这个数据必须有一定的规律性，比如有很多同类型的数据。而列存储恰好符合这一特点，因为列存储将同一列，即同一类型的数据存储在一起，比行存储在一条记录中存储不同类型的字段值更有规律，更有规律意味着更高的压缩率。

但是为什么压缩能带来高效的查询呢？压缩首先减少硬盘上的存储量空，但是硬盘不值钱。其真正的意义在于，数据在硬盘空中占用的空间越小，查询引擎花在IO上的时间就越少。同时要记住，数据压缩后，很多情况下都需要解压，所以压缩比不是我们唯一追求的，因为后面解压需要时间，所以压缩比和解压速度通常是有权衡的。

高压缩比的典型如Lempel-Ziv, Huffman, 解压快的典型如: Snappy, Lz2

上面提到的解压在某些场景下可以完全避免。例如，对于用游程编码压缩的数据，我们可以直接对数据压缩格式做一些计算:

Run-Length的大概意思是这样的, 对于一个数字序列: 1 1 1 1 2 2 2, 它可以表达成 1x4, 2x3

这样，无论计数、求和等。，不需要解压缩就可以直接计算数据，并且由于扫描的数据比未压缩的数据少，所以可以进一步提高性能。还提到，优化列存储中压缩应用的最佳方案是对数据进行排序。原因很简单，因为不排序的话，数据就没那么“规则”，就达不到最佳压缩比。

延迟物化

要理解后期物化，首先解释什么是物化:为了使底层存储格式与用户查询所表达的含义相匹配，在查询生命周期的某一点，数据必须转换为行的形式，这就是列存储中的物化。

从列存储到行显示

理解了物化的概念之后，延迟物化就很好理解了，就是延迟物化到整个查询生命周期的后期。延迟物化是指在查询执行前的一段时间，查询执行的模型不是关系代数，而是基于Column的。让我们举一个例子，比如下面的查询:

从人员位置id >中选择名称；10andage & gt20

天真的方法是从文件系统中读取三列数据，立即将其具体化为多行人员数据，然后应用两个过滤条件:ID >: 10和年龄>:20。过滤后，从数据中提取名称字段。作为最终结果，一般转换过程如下:

早期物化

延迟物化的方法会先对Column数据直接应用两个过滤条件，而不需要拼出行数据，从而得到两个满足过滤条件的位图，然后对这两个位图进行按位and运算，得到同时满足这两个条件的所有位图，因为最终用户只需要name字段，所以下一步就是用这些位置过滤name字段的数据，得到最终结果。如下图:

延迟物化

你发现了吗？在整个过程中，我们根本没有进行物化操作，可以大大提高效率。

总而言之，延迟物化有四个好处:

关系代数里面的 selection 和 aggregation 都会产生一些不必要的物化操作，从一种形式的tuple, 变成另外一种形式的tuple。如果对物化进行延迟的话，可以减少物化的开销，甚至直接不需要物化了。如果Column数据是以面向Column的压缩方式进行压缩的话，如果要进行物化那么就必须先解压，而这就使得我们之前提到的可以直接在压缩数据上进行查询的优势荡然无存了。操作系统Cache的利用率会更好一点，因为不会被同一个Row里面其它无关的属性污染Cache Line。块遍历 的优化手段对Column类型的数据效果更好，因为数据以Column形式保存在一起，数据是定长的可能性更大，而如果Row形式保存在一起数据是定长的可能性非常小。 Invisible Join

最后，本文提出了一种创新的绩效优化措施:隐形连接。不可见连接针对的是数据仓库中的星型模式。如果用户查询满足以下模式，则可以应用不可见连接:

利用事实表的里面的外键跟维度表的主键进行JOIN的查询的, 最后select出一些column返回给用户。

所谓星型模型是指一个事实表，通过外键被一堆维度表包围。

星形模式

为了介绍隐形连接的思想，我们应该首先介绍两种传统的方案，通过比较可以看出隐形连接方案的优势。

传统方案1:根据选择性按顺序加入

传统的方案一是最简单的，根据选择性从大到小连接表:

传统方案1:根据选择性加入。传统方案二:延迟物化

方案二更有意思。它采用了延迟物化的策略。它不是JOINing，而是对维度表上的数据进行过滤，得到对应表的POSITION，然后把表的主键和事实表的外键连接起来，这样就可以得到两种POSITIONs:事实表的POSITION和维度表的position。然后我们通过这些位置提取数据，完成一次连接。我们可以通过重复上述操作来完成整个查询。

传统方案2:延迟物化不可见连接的详细说明

以上两种方案各有缺点:

传统方案一因为一开始就做了JOIN，享受不了延迟物化的各种优化。传统方案二在提取最终值的时候对很多Column的提取是乱序的操作，而乱序的提取性能是很差的。

下面正式介绍一下我们的主角:隐形JOIN

隐形JOIN实际上是对传统方案2的优化。传统方案二的本质在于延迟物化。但是因为大量的值是无序提取的，所以性能仍然不是最好的。隐形JOIN可以进一步减少这种无序值的提取，具体思路如下:

把所有过滤条件应用到每个维度表上，得到符合条件的维度表的主键。遍历事实表，并且查询第一步得到的所有外键的值，得到符合条件的bitmap, 这里会有多个bitmap，因为维度表可能有多个。对第二步的多个bitmap做AND操作，得到最终事实表里面符合过滤条件的bitmap。根据第三步的事实表的bitmap以及第一步的符合条件的维度表的主键值，组装出最终的返回值。

如果是这样的话，隐形JOIN可能并不比上面的第二种方案好多少。本文认为许多时间维度表中满足过滤条件的数据往往是连续的。连续性的优点是它可以将查找连接转换为值范围检查，这比查找连接更快。原因很简单。范围检查只需要算术运算，不需要做查找，所以可以大大提高性能。

性能比较

从文中提供的性能对比图来看，这些主要优化策略中延迟物化的效果最好，可以提高性能3倍以上；压缩的优化效果第二:两次以上；再次隐形JOIN:50%到70%；块遍历可以达到5%到50%的性能。

四种优化策略的效果比较

如果删除这些优化方法，列存储的性能与普通的行存储没有什么不同。

总结

阅读本文的最大收获是了解了哪些因素使得列存储在分析类查询时明显优于行存储:延迟物化、压缩、不可见连接和块遍历。

特别佩服本文的是，很多人认为列存储在分析场景上比行存储性能更好是很自然的:IO更少，但本文对各种场景进行了详细的测试和演示，并将类似的性能优化方法应用到行存储上进行测试和比较，打破了分析的断裂。最后告诉我们:

Column-Store的优点不止在于它的存储格式，查询引擎层的各种优化也同样关键，而由于Row-Store本身存储格式的限制，即使在Row-Store上使用这些优化，效果也不好。