干货分享，现代列式数据库系统如何设计与实现？ | StoneData 论文选读

作者：袁洋 | StoneData 技术架构师

审核：王博

论文链接：columnstoresfntdbs.pdf (harvard.edu)

列存四先驱和 MIT 知名教授 Samuel Madden 于 2013 年在某期刊上写的一篇当时列存相关技术的综述。文章还挺全面也很经典，通过剖析三个经典的现代列存的数据库 C-store、MonetDB、VectorWise，阐述了各项单独技术的来龙去脉和相辅相成的关系。

行式存储 vs 列式存储

在数据库存储引擎侧通常有两类存储模型：

• 行式存储 NSM（N-ary Storage Model）
• 列式存储 DSM（Decomposition Storage Model）

1.1 NSM

一般是将一行数据完整的从头到尾连续存储（超长的字段一般会单独存储，行内记录逻辑地址），连续多行构成一个页，页的尾部通常会存储索引来解决 record 不定长时的快速查找问题。

以行为单位存储，再配合以 B+ 树或 SS-Table 作为索引，就能快速通过主键找到相应的行数据。

行式存储对于 OLTP 场景是很自然的：大多数操作都以实体（entity）为单位，即大多为 增删改查 一整行记录，显然把一行数据存在物理上相邻的位置是个很好的选择。

优点

行存在 insert/update/delete/point lookup query (点查)的场景是占优的：因为涉及的行数据是连续存储的，理论上不存在读写放大。

缺点

在读取时，由于会读取大量无效列数据，譬如 select name from R where age < 40，那么对于每次 age 的遍历，除了会将无用的其他数据一起读入，每次读取 record，都可能会引起 cache miss。对 cpu cache 非常不友好。

1.2 DSM

在存储时将多行数据的相同 column 连续存储在一起，相同 column 的数据组成一个一个的块(Block)。

优点

列式存储非常适用于大量复杂查询的数据分析场景，列式数据库相较于传统的行式数据库具有以下优点：

（1）更高的查询效率。由于数据按列存储，当需要查询某一列的数据时，列式数据库只需要读取该列的数据，而不需要读取整行数据，因此查询速度更快。

（2）更好的数据压缩。由于同一列的数据类型相同，因此可以采用更加有效的数据压缩方式，减少存储空间的占用。

（3）更快的并行处理能力。列式数据库可以同时处理多个列，因此可以更好地利用多核处理器和并行计算资源，提高数据处理效率。

缺点

列存在更新场景明显存在缺陷：

每 insert/update/delete 一行数据，需要同时修改多个列(会去更新存在不同位置的 column)，带来 IO 放大，且为随机 IO。

1.3 PAX：一个 Cache 友好高效的行列混存方案

可以看到，NSM 和 DSM 都有各自的优劣，所以如何将它们和优点结合起来，就是 PAX 考虑的问题。

• NSM 能更快速的取出一行记录，这是因为一行的数据相邻保存在同一页
• DSM 能更好的利用 CPU Cache 以及使用更紧凑的压缩

PAX 全称是 Partition Attributes Across，它的核心思路是：尝试将 DSM 的一些优点引入 NSM，将两者的优点相结合。将一个页划分成多个 minipage，minipage 内按列存储，而一页中的各个 minipage 能组合成完整的若干 relation。

假设有 n 个 attributes，PAX 就会将 page 分成 n 个 mini pages，然后将第一个 attribute 的放在第一个 mini page 上面，第二个放在第二个 mini page，以此类推。

在每个 page 的开头，会存放每个 mini page 的 offset，mini page 对于 Fixed-length attribute 的数据，会使用 F-minipage ，而对于 variable-length attribute 的数据，则会使用 V-minipage。对于 F-minipage 来说，最后会有一个 bit vector 来存放 null value。而对于 V-minipage 来说，最后会保存每个每个 value 的在 mini page 里面的 offset。

一篇关于 PAX 的 paper 供大家进一步学习和研究。

Paper: https://www.vldb.org/conf/2001/P169.pdf

怎么让列式数据库更快

仅仅将数据存储在列中，并不足以让基于列的存储获得全部性能。该论文中花了大量篇幅来分析几个关键的列存数据库加速技术， 如下图所示

根据论文中的这些技术特性，下面我们逐步分析向量化计算，数据压缩，延迟物化 ，连接优化几个部分。

向量化计算

3.1 概念

火山模型（Volcano-style execution）是最早的查询执行引擎，也叫做迭代模型 (iterator model)，或 one-tuple-at-a-time。在这种模型中，查询计划是一个由 operator 组成的 DAG，其中每一个 operator 包含三个函数：open，next，close。Open 用于申请资源，比如分配内存，打开文件，close 用于释放资源，next 方法递归的调用子 operator 的 next 方法生成一个元组（tuple，即行 row 在物理上的表示）。

目前主要有两种关于向量化执行引擎的实现方法：

1. 仍然使用火山模型，只不过一次返回一组列。这种模型的优势是仍然使用（火山模型），这个优化器于执行器模型已经很成熟，剩下需要的工作量就在于如何将一次一 tuple 的处理模式，修改为一次向上返回一组列存行值（例如：100-1000 行）处理方式，难度相对较小
2. 将整个模型改造成为层次型的执行模式，这种模式需要将优化好的执行计划树，最终转换为编译执行，即，一次调用下来之后，每一层都完成后才向上返回数据，这样能够最大程度的减少各层次节点间的调用次数，提高 CPU 的有效计算效率

上图描述的就是火山模型实现的行存执行引擎与列存执行引擎，其中左边代表的是当前比较流行的传统行存火山模型，右边代表的是列存实现的火山模型，从上图我们可以看到火山模式是从执行计划树的根节点开始向叶子节点递归调用，然后有叶子节点，通常是各种的扫描节点返回一条符合过滤条件的 tuple 给上层节点处理，每一层节点在处理完该 tuple 之后继续网上层节点传递记录（Agg 节点不是立刻往上层节点返回数据，它需要计算完所有的 Tuple，才能继续往上层节点返回，所以这里 AGG 算子在处理好这个 Tuple 之后，又会往下调用扫描算子返回下一条符合过滤条件的记录）。这样处理完整个表的记录之后，AGG 算子会把数据返回到上一层节点继续处理，在整个过程中需要 AGG 算子缓存中间结果。右边列存执行引擎，执行逻辑基本上与左边行存执行引擎一致，但是每次扫描处理的是一组组以 col 组织的列数据集合，这样我们最为直观的观察就是从上层节点向下层节点的调用次数少了。相应的 CPU 的利用率得到了提高，另外数据被组织在一起。可以利用硬件发展带来的一些收益；如 SIMD, 循环优化，将所有数据加载到 CPU 的缓存当中去，提高缓存命中率，提升效率。在列存储与向量化执行引擎的双重优化下，查询执行的速度会有一个非常巨大的飞跃大约 3-5 倍。

向量化执行流程

1. 将查询进度控制逻辑与数据处理逻辑分开
2. 每个操作符的 next()方法返回 N 个图元的矢量
3. 避免产生大量中间结果
   

论文中阐述了一种观点：在面向块和矢量化处理的视线中，通过在运算符之间传递 缓存行 大小的 元组 块，并且一次对多个值进行操作，而不是使用传统的 一次一个元组 的迭代器，列存储可以实现大幅提高缓存利用率和 CPU 效率。

3.2 向量化执行的优势 

1. 降低解释开销

减少了解释的开销, 与 tuple-at-a-time 模型相比，查询解释器执行的函数调用量减少了一个与矢量大小相等的系数。在 TPC-H Q1 的查询中可以将性能提高两个数量级。

2. 缓存局部性

列数据是连续的，分配的内存块也是连续的，所以在第一次访问时，大块的内存块会被加载到高速缓存中。这使得后续访问数组中的元素变得相对较快。

3. 编译器优化的可能性

自动内存预取、触发编译器来生成 SIMD 指令、有效使用 CPU 缓冲机制

4. 并行内存访问

并行内存访问。通过无序推测生成多个并行未命中的代码的执行速度通常是非矢量化内存查找的四倍

3.5 向量化执行比传统模式的优势

• 减少了函数调用的开销（调用次数减少 N 倍）
• 通过调整向量大小来提高缓存局部性能力
• 避免分支预测，提高并行内存访问速度
• 编译器有机会进行编译器优化，可以利用 SIMD 指令集加速计算
• 基于块的算法优化
• 可以以更小的代价做 Profiling(面向性能分析开销)

适应性执行：动态选择最优实现(多臂老虎机问题)

数据压缩

4.1 Compression Perspectives

同一列的数据放一起信息熵要远低于来自不同列的数据。信息熵越低，数据越高度有序。 压缩算法在信息熵低 (即具有高数据值局部性) 的数据上表现更好；来自同一列的值往往比来自不同列的值有更多的值局部性。value locality 的意思就是某个数据 (数据的内容或者逻辑地址) 被访问地更频繁。

通常情况下，数据库系统的底线目标是性能，即尽可能快地处理一个或多个查询，而不是压缩率。压缩通过减少花在 I/O 上的时间来提高性能。

4.2 压缩带来的优势

• 按列压缩压缩率远高于按行压缩，如果数据是排序的压缩率会更高
• 数据库系统的终极目标是性能而不是压缩率。但是数据被压缩后能减少磁盘 IO，减少从内存到 CPU 带宽的使用。从而进一步提高了性能
• 一些压缩算法会把数据压缩为固定宽度（fixed-width）数组，这样就可以进一步利用 SIMD 来加速
• 基于频率的分段压缩，每一段数据有更低的信息熵

4.3 压缩算法

4.3.1 RLE, 游程长度压缩算法

RLE, 游程长度压缩算法, 是一种无损数据压缩的形式, 使用值、起始位置、运行长度三要素。其中同一数据值被存储为单一的数据值和计数，而不是作为原始值存储。如果一列的前 42 个元素含有值 M，也就说起始位置为 1， 42 个 M 的长度， 那么这 42 个元素可以被替换成 (M, 1, 42) 的三要素信息。在列式存储中，由于列的数据是连续的，相同值的情况很常见，因此会出现较多的 RLE encoding 机会。

4.3.2 Bit-Vector Encoding 位向量编码算法

位向量编码是为每一个不同的取值生成一个位向量, 根据位向量( 串)中不同的位置取值 0 或 1 来对应并确定不同的原始值。位向量编码算法其实就是位图索引算法，适用于低基数的列，相对于 B 树索引，它的 count,and,or 操作更有效，位图索引位存放的是 0,1 的 bit，相对于 B 树索引，占字节数特别少,不适合 update、insert、delete 频繁的列-因为要一个数据的更新可能会导致 2 个位图向量的更新。bitmap 的思想就是数据压缩。用一个二进制 bit(0 或者 1)去标记某个元素对应的 value， 这就是 bit + map。适用于低基数的列，相对于 B 树索引，它对 count, and, o r 操作更有效，位图索引位存放的是 0,1 的 bit，相对于 B 树索引，占字节数特别少。不适合 update、insert、delete 频繁的列：因为一个数据的更新可能会导致 2 个位图向量的更新。 举例如下

4.3.3 字典编码算法

字典编码就是生成一个“原始值替代值”的对照字典。为了起到压缩的作用, 替代值的长度小于原始值的长度。存储的时候, 只存储替代值而不是原始值, 从而压缩了存储空间

字典编码算法把唯一值编入字典，每一个唯一值都匹配一个序号，而序号用于索引字典，通过存储序号来压缩数据。如果数据表中存在大量的重复/频繁值，那么使用字典编码压缩率高，效果非常好。

关于字典编码的 Paper, 可以看看这个。

Paper: Dictionary Compression for a Scan-Based, Main-Memory Database System

https://publications.systems.ethz.ch/sites/default/files/publications/BernetJanickSpring2010.pdf

举例如下:

延迟物化

5.1 什么是物化？

物化,即将常用元组或可能会用到的逻辑元组从实际物理存储的状态生成为实体化的元组, 也称为物化, 存储在内存中，是包括一个查询结果的数据库对像，它是远程数据的的本地副本，是一个物理表。在随后查询时, 直接读取已经物化的元组, 以提高查询的效率。

5.2 延迟物化

而元组物化有两种方案, 分别是提前物化: 在提交查询之前物化元组; 延时物化: 尽量推迟物化元组的时间, 在查询中间的某个时刻物化元组。对于列数据库来说, 提前物化需要解压所有已经压缩的数据, 其时间和空间的开销是很大的。同时, 提前物化会涉及到很多不必要的列, 有悖列数据库按列存储、按需取用的初衷。因此, 在列数据库领域, 提出了延时物化的思想。

把从各个列中获取的数据重新组装为行的过程称之为 tuple construction，延迟物化的目的就是尽可能推迟 tuple construction 的时机。把这个物化的时机尽量的拖延到整个查询生命周期的后期。

延迟物化意味着在查询执行的前一段时间内，查询执行的模型不是关系代数，而是基于 Column 的。

5.3 延迟物化的收益?

1. 减少物化的 tuple 数量
2. 降低 IO、网络、计算压力
3. 可以在列存(压缩)数据上进行高效计算
4. 减少内存访问带来的开销
5. 在扫描数据相对较少的情况下，需要 cache 的数据量更少，此时也会提高整个计算的 cache 命中率，减少 cpu 的消耗

5.4 一个 延迟物化的例子

SQL:

select name from person where id > 10 and age > 20

5.4.1 行存做法

从文件中读出三列的所有数据，物化成行数据：一行行的 person 数据。然后应用两个过滤条件：id > 10 and age > 20，Filter 之后从数据里面抽出 name 字段，作为最后的结果进行 output

5.4.2 列存上，延迟物化的做法

延迟物化的做法是：

1. 直接在每一个 Column 数据上分别应用过滤条件，从而得到两个满足过滤条件的 bitmap
2. 然后再把两个 bitmap 做位与操作得到同时满足两个条件的所有的 bitmap
3. 因为最后需要的是 name 字段，因此拿着这些 position 对 name 字段的数据进行过滤就得到了最终的结果
   

5.4.3 普通物化和延迟物化对比

这两者的权衡在于，虽然延迟加载能够减少数据的加载量，但需要维护原始数据的位置 ，这样才能找到对应行的其他列的值。然而如果筛选条件（person.id > 10 and person.age > 20）不能大量过滤数据，延迟加载反而低效。

对于这种情况，就需要根据一些统计信息选择合适的加载算法，来最大限度的提高效率。

延迟物化带来的好处

• 关系代数里面的 selection 和 aggregation 都会产生一些不必要的物化操作，从一种形式的 tuple, 变成另外一种形式的 tuple。如果对物化进行延迟的话，可以减少物化的开销(因为要物化的字段少了)，甚至直接不需要物化
• 如果数据是被压缩过的，物化的过程就必须对数据进行解压，这会影响压缩带来的好处
• 列式的内存组织形式对 CPU Cache 非常友好，从而提高计算效率，相反行式的内存组织形式因为非必要的列占用了 Cache Line 的空间，Cache 效率低
• 块遍历的优化手段对 Column 类型的数据效果更好，因为数据以 Column 形式保存在一起，数据是定长的可能性更大。而如果 Row 形式保存在一起数据是定长的可能性非常小（因为你一行数据里面只要有一个是非定长的，比如 VARCHAR，那么整行数据都是非定长的）

延迟物化的缺点

延迟物化且多表 Join 连接后， 许多 Join Algorithms 会对左（外）侧输入位置关系排序，右（内）侧输出位置不会排序(准确的说至少有一侧不会被排序)，因为以这种无序的方式从列中提取值需要为每个位置跳转存储， 产生了随机访问，相比顺序访问会产生较大的开销。

对左（外）侧输入位置关系排序也有例外：对两组输入进行排序或重新分区的 Join 算法，不会对左右位置列表进行排序。但无论哪种方式，至少有一组输出位置不会被排序。

从下图可以看出延迟物化在列式数据库优化中可以带来巨大的收益

表连接

6.1 更加有效地表连接

Hash-join

• 以 Hash-join (散列连接，典型连接算法) 为例，column store 可以让 probe 探测表更紧凑（会产生更紧凑的散列表，从而在探测期间 during probing 产生更好的访问模式）
• a smaller hash table leads to less cache misses 更小的散列表导致了更少的缓冲区丢失

Jive-Join

Jive-Join (两次排序) 解决 Unordered positional lookups。基本思想是在我们想要提取的位置列表中添加一个额外的列，这是一个密集有序递增的整数序列。

Invisible Join

在延迟物化缺点部分提到，Join 后，许多 Join Algorithms 会对左（外）侧输入位置关系排序，右（内）侧输出位置不会排序，这是因为左列中的位置通常按顺序迭代，而右列中的位置会被探测以查找连接谓词匹配项。因此需要添加一个排序列。

为了解决这个问题，又提出了一个新的 Join 算法：Invisible Join 隐式连接。

更多 Join 实现

当然还有 BroadcastJoin，LookupJoin，SortJoin...

6.2 Jive-Join

对于 Join 而言，运算的核心在于两表中 Joinkey 的匹配上。对于其他列数据匹配上了就复制，匹配不上就丢弃。结合延迟物化，匹配后再加载其他列数据，从而减小不必要的 IO。

举个例子， 如下 SQL：

SELECT emp.age, dept.name FROM emp, dept WHERE emp.dept_id = dept.id

假设原始数据值如下：

根据上面延迟物化部分我们可以已知，数据的查询过程中，我们先抽出 emp 表的 dept_id 和 dept 表的 id 列数据，进行匹配；并输出匹配结果对应原表的位置信息。(黄色文字部分是指 position 指向的值， 在实际 Join 中不会出现)

会得到如下的数据：

然后根据输出的位置信息，就可以从原始数据中抽取 age、name 列的数据得到 Join 最后的结果。

由于上图右侧输出无序，如果回表查必然造成大量随机 IO ，为了解决这个问题，Jive Join[参考文献 Fast Joins Using Join Indices]采用了对其进行排序之后再查询，即将随机 IO 转化为顺序 IO 的方法进行优化。

实现方式为：在右侧表 position 列上添加一个额外的列(一个密集递增的整数序列)。

排序输出：

最后，为了保持原 SQL 语义的一致性，我们对数据结构再次排序，这次是按最初添加到连接输出的列，将当前数据结构恢复为原始连接顺序（以便与另一个表的连接输出相匹配）：

6.3 Jive-Join 进一步的优化思路

• 不需要完全排序整个列数据, 来减少 join 值中列输出的随机访问性能开销
• 存储介质被分成连续的存储块，块内的随机访问比跨块的随机访问代价小得多
• 因此，只需要在存储（或其近似值）上划分为可以找到这些位置的块。在每个分区内，位置可以保持无序，因为存储块内的随机访问要便宜得多
• 保证块维度的顺序访问，块内的数据可以保持无序，来替代全局列按精确的位置顺序访问。这个也就是一个新的概念: Radix Hash Join：

https://nan01ab.github.io/2019/03/Hash-Joins.html

总结

7.1 列式存储优点

数据压缩，确定一列数据的规律

1. 查询时可以时读的数据量更少，在 IO 密集型计算中获得更多的性能优势
2. 相同类型压缩效率更高
3. 可以针对不同类型使用不同的压缩算法。LZ4，run-length encoding，delta encoding
4. 高效的压缩可以减少磁盘 IO 数据量，但是高效的压缩都必须遵循某种特殊的规律，比如数据的长度，类型等一致；基于列式的查询数据库正好遵循这一点；此外，某些特别的数据压缩格式，比如 RUN-Length 编码，甚至可以在不做解压时便可以对数据过滤，减少无关的 IO

数据选择优势大

1. 可以选择特定的列做计算而不是读所有列
2. 对聚合计算友好

更容易向量化

1. 向量化基于 SIMD (single instruction multiple data) 。对于现代多核 CPU，其都有能力用一条指令执行多条数据
2. 向量化对数据格式有要求：要处理的数据需要是连续内存；需要明确数据类型
3. 执行模型要求：数据需要按批读取；函数的调用需要明确数据类型
4. 列存数据库本身按列存储和读取，可以保证数据按批读取，在内存中连续；可以根据列的类型定义数据读写逻辑；函数按列类型处理

更适合做延迟物化

1. 物化: 将列数据转换为可以被计算或者输出的行数据或者内存数据结果的过程，物化后的数据通常可以用来做数据过滤，聚合计算，Join
2. 缓存友好；节省 CPU / 内存带宽；可以利用到执行计划和算子的优化，例如 filter；可以直接在压缩列做计算

7.2 写在最后

实际上，列存数据库不只是列式存储的存储格式问题，底层存储的变化往往牵一发而动全身，如何适应性的修改计算引擎、存储引擎、存取方式等来达到更高更快的性能，并适应不同的 workload 或者硬件发展的趋势，都是基于列式存储数据库要关心的问题。