干货分享，现代列式数据库系统如何设计与实现？

列存四先驱和 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 在物理上的表示）。
目前主要有两种关于向量化执行引擎的实现方法：

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

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

向量化执行流程

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

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

3.2 向量化执行的优势
1. 降低解释开销

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

2. 缓存局部性

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

3. 编译器优化的可能性

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

4. 并行内存访问

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

3.5 向量化执行比传统模式的优势
减少了函数调用的开销（调用次数减少 N 倍）
通过调整向量大小来提高缓存局部性能力
避免分支预测，提高并行内存访问速度
编译器有机会进行编译器优化，可以利用 SIMD 指令集加速计算
基于块的算法优化
可以以更小的代价做 Profiling(面向性能分析开销)
适应性执行：动态选择最优实现(多臂老虎机问题)