论文链接点击文末阅读原文获取
在数据库存储引擎侧通常有两类存储模型：
行式存储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 以及使用更紧凑的压缩
怎么让列式数据库更快
仅仅将数据存储在列中，并不足以让基于列的存储获得全部性能。该论文中花了大量篇幅来分析几个关键的列存数据库加速技术， 如下图所示
根据论文中的这些技术特性，下面我们逐步分析向量化计算，数据压缩，延迟物化 ，连接优化几个部分。
向量化计算
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的查询中可以将性能提高两个数量级。
3.5 向量化执行比传统模式的优势
减少了函数调用的开销（调用次数减少N倍） 通过调整向量大小来提高缓存局部性能力 避免分支预测，提高并行内存访问速度 编译器有机会进行编译器优化，可以利用 SIMD 指令集加速计算 基于块的算法优化 可以以更小的代价做 Profiling(面向性能分析开销)
数据压缩
4.1 Compression Perspectives
4.2 压缩带来的优势
按列压缩压缩率远高于按行压缩，如果数据是排序的压缩率会更高 数据库系统的终极目标是性能而不是压缩率。但是数据被压缩后能减少磁盘IO，减少从内存到CPU带宽的使用。从而进一步提高了性能 一些压缩算法会把数据压缩为固定宽度（fixed-width）数组，这样就可以进一步利用 SIMD 来加速 基于频率的分段压缩，每一段数据有更低的信息熵
4.3 压缩算法
4.3.1 RLE, 游程长度压缩算法
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 字典编码算法
字典编码就是生成一个“原始值替代值”的对照字典。为了起到压缩的作用, 替代值的长度小于原始值的长度。存储的时候, 只存储替代值而不是原始值, 从而压缩了存储空间
字典编码算法把唯一值编入字典，每一个唯一值都匹配一个序号，而序号用于索引字典，通过存储序号来压缩数据。如果数据表中存在大量的重复/频繁值，那么使用字典编码压缩率高，效果非常好。
延迟物化
5.1 什么是物化？
5.2 延迟物化
而元组物化有两种方案, 分别是提前物化: 在提交查询之前物化元组; 延时物化: 尽量推迟物化元组的时间, 在查询中间的某个时刻物化元组。对于列数据库来说, 提前物化需要解压所有已经压缩的数据, 其时间和空间的开销是很大的。同时, 提前物化会涉及到很多不必要的列, 有悖列数据库按列存储、按需取用的初衷。因此, 在列数据库领域, 提出了延时物化的思想。
把从各个列中获取的数据重新组装为行的过程称之为 tuple construction，延迟物化的目的就是尽可能推迟 tuple construction 的时机。把这个物化的时机尽量的拖延到整个查询生命周期的后期。
延迟物化意味着在查询执行的前一段时间内，查询执行的模型不是关系代数，而是基于 Column 的。
5.3 延迟物化的收益?
减少物化的tuple数量
降低IO、网络、计算压力
可以在列存(压缩)数据上进行高效计算
减少内存访问带来的开销
在扫描数据相对较少的情况下，需要 cache 的数据量更少，此时也会提高整个计算的 cache 命中率，减少 cpu 的消耗
5.4 一个 延迟物化的例子
SQL:
select name from person where id > 10 and age > 20
5.4.1 行存做法
5.4.2 列存上，延迟物化的做法
延迟物化的做法是：
直接在每一个Column 数据上分别应用过滤条件，从而得到两个满足过滤条件的 bitmap
然后再把两个 bitmap 做位与操作得到同时满足两个条件的所有的 bitmap
因为最后需要的是 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 (散列连接，典型连接算法) 为例，column store 可以让 probe 探测表更紧凑（会产生更紧凑的散列表，从而在探测期间 during probing 产生更好的访问模式） a smaller hash table leads to less cache misses更小的散列表导致了更少的缓冲区丢失
6.2 Jive-Join
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 列式存储优点
数据压缩，确定一列数据的规律
查询时可以时读的数据量更少，在IO密集型计算中获得更多的性能优势
相同类型压缩效率更高
可以针对不同类型使用不同的压缩算法。LZ4，run-length encoding，delta encoding
高效的压缩可以减少磁盘IO数据量，但是高效的压缩都必须遵循某种特殊的规律，比如数据的长度，类型等一致；基于列式的查询数据库正好遵循这一点；此外，某些特别的数据压缩格式，比如 RUN-Length编码，甚至可以在不做解压时便可以对数据过滤，减少无关的IO
数据选择优势大
可以选择特定的列做计算而不是读所有列
对聚合计算友好
更容易向量化
向量化基于SIMD (single instruction multiple data) 。对于现代多核CPU，其都有能力用一条指令执行多条数据
向量化对数据格式有要求：要处理的数据需要是连续内存；需要明确数据类型
执行模型要求：数据需要按批读取；函数的调用需要明确数据类型
列存数据库本身按列存储和读取，可以保证数据按批读取，在内存中连续；可以根据列的类型定义数据读写逻辑；函数按列类型处理
更适合做延迟物化
物化: 将列数据转换为可以被计算或者输出的行数据或者内存数据结果的过程，物化后的数据通常可以用来做数据过滤，聚合计算，Join
缓存友好；节省CPU 内存带宽；可以利用到执行计划和算子的优化，例如filter；可以直接在压缩列做计算
7.2 写在最后
实际上，列存数据库不只是列式存储的存储格式问题，底层存储的变化往往牵一发而动全身，如何适应性的修改计算引擎、存储引擎、存取方式等来达到更高更快的性能，并适应不同的 workload 或者硬件发展的趋势，都是基于列式存储数据库要关心的问题。
推荐阅读
技术分享 | StoneData 的身份认证与访问控制策略：构建安全可靠的数据分析环境
技术分享 | StoneData 中的动态过滤
技术分享｜StoneData 向量化计算（下）
