Column-Stores vs. Row-Stores: How Different Are They Really?

[mrdrivingduck]

abadi-sigmod08.pdf

[mrdrivingduck]

在分析性负载下，列式存储比行式存储在性能上高出一个维度。原因看似很简单：列式存储的 I/O 效率更高，只需要从磁盘上取出需要的属性即可。那么是否可以有这样的假设：如果使用行式存储来模仿列式存储，是否可以获得性能提升呢？

这个假设是错误的。本文不仅从存储层的角度，还从执行器的角度对比了行存和列存的区别。对于列式存储，本文还评估了不同面向列存的查询执行技术对性能的影响大小。

结论：用行存模拟列存的方式来获得 AP 负载上的性能收益是不太现实的。只有在存储层和查询执行层 同时 做出改变才可以充分发挥列式存储的优势。

[mrdrivingduck]

Introduction

第一个问题

近年来不断推出的列式存储数据库声称它们在 AP 负载下降维打击行式存储。但列式存储的潜能到底有多大呢？这种降维打击的来源，是主要来自于列式存储数据库内部的实现，还是来自于一个更加面向列的物理存储设计？如果来自后者，那么使用行式存储在物理上模拟列式存储是否也可以在 AP 负载上获得收益呢？

本文使用行式存储来模拟了以下几种物理结构，使存储结构尽可能接近于列存：

• 垂直分区：将一个行存表拆分为一大堆具有两个列的表（ctid, 列值），每个表代表一个列
• Index-only：为查询用到的所有列建立索引，从而可以 index-only scan，无需回表
• 物化视图：只包含需要返回给查询的元组，这是行存的最佳情况

经过实验，尽管上面的方案模拟了列式存储的物理存储结构，但查询执行性能依旧很差。本文证明了列式存储数据库的在 AP 上的优势更多来自于内部设计，而不是物理存储结构的转变。

第二个问题

在列存数据库中，提出了多种对查询执行的优化技术。其中哪一种技术对性能提升帮助最大？

• 延迟物化：从磁盘上读取的列值以尽可能晚的时机被 join 成行元组
• 向量化执行：一列中的多个值作为一个 block 在算子之间传递
• 列压缩
• Invisible join（本文提出的新算法）

本文在同一款数据库上分别 单独 测试了以上技术。结论：如果压缩可用，那么压缩能够提升最大的性能；其次是延迟物化；再之后是向量化执行和 invisible join。

[mrdrivingduck]

Benchmark

数据集选用的是继承自 TPC-H 的 SSBM benchmark。包含了一个带有 17 个列的事实表，其中 2 列作为组合主键，其它列作为外键关联到其它的维度表。

[mrdrivingduck]

Row-Oriented Execution

垂直分区（Vertical Partitioning）

行存模仿列存最直接的方式：把每个列的数据单独存放在一张行存表里。需要一定的机制，使得属于同一行数据的不同列值能够被关联起来。最简单的方式是为存放每列的表加一列 position。这种方法在实际上为一个物理表的每一个列都创建了一个带有两列的表，一列存放该列值在行表中的位置，一列存放列值。

当查询需要 fetch 多个列时，将会被重写，多个列之间使用 position 来进行 join。不管是用 hash join，还是在 position 列上建索引然后进行 index join，性能都不怎么样。

两个局限：

1. 每一列都要存放额外的 position，浪费了 I/O 带宽
2. 在行存中，每个元组都需要存放一个相对较大的 header，浪费空间

Index-Only Plans

原表还是按行存存放，在表的每一列上建立非聚簇的 B+ Tree 索引。虽然索引也会保存类似 position 的东西，但是至少不会保存重复的列值。由于索引中不存放 header，因此上一种方法中的开销没有了。

问题：如果查询中对某一列没有过滤条件，那么全索引扫描将比全表扫描慢。

Materialized Views

为每一个查询创建一个最小元组集，但需要预知每一个查询。因此使用场景受限。

[mrdrivingduck]

Column-Oriented Execution

压缩（Compression）

直观上来说，列式存储的数据比行式存储的数据更利于压缩，尤其适用于 低信息熵 的数据（重复率较高的数据？）。如果数据是按顺序排列的，那么能够被更好地压缩。压缩能够减少数据从磁盘转移到内存或从内存转移到 CPU 的时间。因此，一些轻量级的压缩算法会比重量级的压缩算法更适合，牺牲一定的压缩率来保证解压缩的性能。如果执行器能够直接对压缩后的数据进行操作，那么解压缩的过程将可以被跳过。

行存和列存压缩的区别在于，如果一个列是有顺序的，那么连续的重复值可以被压缩。列存很方便做这样的压缩，但行存会受到其他列的影响。如果被执行器访问的较多列都是有序的，那么压缩可以极大地影响性能。

延迟物化（Late Materialization）

列式存储中，同一个实体（同一行）的信息会被存放在磁盘上的多个地方；而行式存储中，一行数据通常存放在一起。然而：

1. 大部分查询需要访问同一个实体的超过一个属性
2. 大部分的标准输出（ODBC/JDBC）是按行来访问 DB 的

所以在大部分查询中，属于同一行的多列数据需要被组装成行（构造元组）。较为简单的列存实现，会将所有需要的列提出来并组装成元组，然后执行普通的行存算子。但更新的系统选择把列形式的数据保持到尽可能晚的时候，先尽量对单独的列进行操作。为了匹配在不同列之间的操作，通常需要有一个中间的 position 列表。

• 输入：一个列上的过滤条件
• 输出：该列上满足过滤条件的元组位置

根据列上的选择率大小，position 列表可以是 bitmap，也可以是一个数组。多个列上的过滤列表进行与运算后，得到了一个单独的 position 列表。这个列表再被用于之后的元组构造。

优势：

1. 防止产生很多本不需要产生的元组
2. 避免了提前解压被压缩好的列数据
3. 直接对列数据进行操作具有更好的 cache 性能
4. ？

向量化执行（Block Iteration）

行存的执行引擎通常为 tuple-at-a-time。已有工作指出，如果一大堆元组能够被一次调用操作，那么处理每个元组的开销就可以被分摊得足够小。如果列是定宽的，那么不需要做属性提取，可以直接向上层算子返回一个数组。这样可以最小化每个元组的开销，还可以更好地利用现代 CPU 的并行性。

Invisible Join

困死了 😪