行存存储 vs 列存存储
简介
在 OLAP 场景下，我们通常倾向于使用列存（Column-Store）而不是行存（Row Store），做出这种决定的原因很直接：因为列存的 I / O 效率比行存更高，查询数据时，只需要从磁盘（或内存）中读取必要的列即可，具备更好的查询性能。
但列存带来的性能提升，到底是因为其在内部架构的基本原理导致的，还是由于列存这一设计思想而导致的？我们是否可以在传统的行存数据库中应用一些具备列存特性的优化，从而使其性能和列存别无二致？
根据列存的特性，我们可以对行存进行一定的优化，如
- 垂直分表，逐列分为若干个包含两列（主键、列值）的表，同样可以达到列存的“按需读取”的效果
- 全表的索引，为表的每一列都建立索引，保证查询计划中只存在 IndexScan，这样在查询过程中可以完全避免回表
- 物化视图，针对所有查询做物化视图，以获取最佳的查询性能。
经过模拟实验，作者得出了结论，在进行了以上优化后，OLAP 场景下行存的查询性能依然无法与列存匹敌。因为列存存在如下几个可以提高查询性能的关键优化：
- 延迟物化，从磁盘读取到的列在查询计划中尽可能晚地连接成行
- 块迭代（Block Iteration），在多个 Operator 之间通过块（Block）方式批量传递一列的多个数据
- 数据压缩，根据列存的数据特性可以进行压缩，如性别“男”“女”可以用位图 1、0 来代替
- 隐式连接（作者提出的一种 join 方式）
作者通过逐个移除 C-Store 中上述的优化手段，得出了结论
- 压缩带来的性能提升要看具体的数据，最多时可以提升一个数量级
- 延迟物化可以提升 3 倍
- 块迭代和隐式连接可以提升约 1.5 倍
行存的优化
上文提到了可以基于基于列存的设计思想来对行存系统进行优化，下面介绍下三种优化方式
垂直分表
模仿列存的一个简单粗暴的方法就是把表的每一列都垂直拆分，拆分之前，一行数据是连续存储的，但是拆分之后一行的数据可能分散在磁盘各处，因此需要额外的机制来把某行记录的每一列联系起来（列存则不需要这种机制，因为列存数据写入会使用一个统一的 Sort Key，使得记录是“对齐”的）。
第一反应可能需要在每个表中增加主键字段，但是主键字段可能会比较大，并且很多时候主键是复合主键，所以可以改为向每个表添加一个整数类型的 “Position” 列，用于标识其所属的行。
最终拆下来，一个 n 列的表会被拆分成共计 2n 列的 n 张表。
一旦列数目增加，连续 Join 会使得查询更加复杂。
全表索引
垂直分表的方案存在两个问题
- 它需要在每一列上增加一个 Position 列用来还原之前的记录，这会浪费盘空间和磁盘带宽；
- 行存数据库物理存储一条记录时，会额外存储记录头信息，垂直分表产生了海量“短”记录，从而带来的海量记录头信息，进一步导致了磁盘空间的膨胀。
为了解决以上问题，作者考虑 Index-Only 的方式，原来的表数据依然采用原汁原味的行存，但是在每一列上都建立二级索引。最终查询时，通过对应字段的索引来过滤出各种主键列表，然后做合并计算，完全避免了对原始表的扫描。
和垂直分表的方式相比，虽然每个二级索引都额外存储了Row ID，但是索引结构中就不含有记录头信息，可以少占用一些磁盘空间。
物化视图
完全根据预定义的 SQL 来生成确定的物化视图，且其中不会关联多余的列。显然这种方式查询性能很好，I/O 效率高，但这种方法又只能应付极其极其极其有限的场景。
列存的优化
数据压缩
压缩，就是将相似度很高、信息熵很低的数据放在一起，用更小的空间表达相同的信息量，压缩带来的优势有：
- 更少的磁盘空间占用，不过磁盘已经越来越便宜了，我们不差钱，我们更看重的是
- 提高性能，显然在从磁盘上读取压缩后的数据时，I / O 效率会更高
当然追求极致压缩也是不可取的，如果压缩后的数据无法被查询引擎直接识别，反而会额外带来解压的代价，因此可以考虑“轻量级”一点的压缩方案，使得查询引擎可以直接识别/操作压缩后的数据，这样子避免了解压过程，进一步提高了查询性能。
如：RLE（Run-Length Encoding）压缩算法，（AAAAAAAAAAAAAAAA -> 16A），如果遇到了 SUM，AVG 操作符，可以免解压直接得出结果。
当然行存也是可以压缩的（见 InnoDB Row Formats），MySQL 提供了若干种压缩级别的行存方案，不过行存的压缩效率和列存的压缩效率存在本质上的差距，因为列存的数据往往类型相同，相同的特征更多，更容易被压缩；行存中一列数据周围因为可能存在关联不大的其他列，会显著提高压缩的复杂度。
如果一列的数据是被排序过的（更低的熵），压缩起来会更加容易，这一点是行存无法达到的。
延迟物化
在实际编写代码查询数据库时，我们用对象（原文 Entity，现在大家基本都用面向对象编程，我就用对象这个说法了）承载查询出来的数据，一条查询结果（一行数据）对应一个对象。
在列存中，一个表的字段是分散存储的，而承载查询结果的对象可能涵盖了多个表的多个字段，所以如何把列存存储的数据从磁盘中取出，并组织构建成行存的形式（一个对象）是列存数据库需要频繁进行的一个操作，这个操作就叫做物化。（列转行）
既然标题叫“延迟物化”，那么说明物化的时机是可以选择的：
- 早期物化，会第一时间就把列数据从磁盘中取出来，转化为行存的形式，然后按部就班根据 SQL 执行一个个 Operator。
- 延迟物化则可以将物化的时机放到查询计划执行的后期，先不拼出行式数据，直接在 Column 数据上分别应用两个过滤条件，从而得到两个满足过滤条件的 bitmap，然后再把两个 bitmap 做位与的操作得到同时满足两个条件的所有的 bitmap，之后只需要根据 bitmap 即可查询必要的记录。
作者提出，延迟物化有以下优势
- selection 和 aggregation 操作很有可能不需要整行数据，延迟物化会避免不必要的资源浪费；
- 如果数据是被压缩过的，早期物化就必须对数据进行解压，反而对冲了压缩存储带来的性能优势；
- 列式的内存组织形式对 CPU Cache 非常友好，从而提高计算效率，相反行存的组织形式因为非必要的列占用了 Cache Line 的空间，Cache 效率低；
- 块遍历的优化手段对 Column 类型的数据效果更好，因为数据以 Column 形式保存在一起，数据是定长的可能性更大，而如果 Row 形式保存在一起数据是定长的可能性非常小（因为一行数据但凡有一个字段是非定长的，比如 VARCHAR，那么整行数据都是非定长的）。
延迟物化 vs 早期物化
不过延迟物化并非一定胜过早期物化，因为将条件直接应用在列上并获得 bitmap 一定伴随着扫描磁盘的行为，也是存在代价的。
文章 Materialization Strategies in a Column-Oriented DBMS 提出，如果一条 SQL 中某个列上存在多个谓词，那么查询计划中就有可能需要扫描该列多次（来获取若干个 bitmap），就算查询计划安排合理（第一次就从磁盘中读到 buffer 里，后续就不用反复磁盘扫描了），也会带来额外的 CPU 计算代价，相反早期物化第一时间就将目标列转化成中间态的形式，随着 Opeartor 执行自然过滤数据，避免了额外的计算开销。
假设有个极端查询：
1
SELECT Name，Age FROM Employee WHERE Age > 18 AND Age < 88 AND Age != 26
这种场景下延迟物化反而导致了更多的扫描次数。
块迭代
一般来说，查询计划处理模型有三种（根据 CMU 的课程，https://15445.courses.cs.cmu.edu/fall2021/notes/11-queryexecution1.pdf）：
- 迭代器模型（又称火山模型）：火山模型是一个发展比较成熟的查询计划处理模型，该模型将关系代数中每一种操作抽象为一个 Operator，将整个 SQL 构建成一个 Operator 树，从根节点到叶结点自上而下地递归调用 next() 函数，每次 next() 只返回一条数据。
- 物化模型（Materialization Model）：每个 Operator 一次处理所有的输入，处理完之后将所有结果一次性输出，物化模型更适合 OLTP 负载，查询每次只访问小规模的数据。这种处理模型需要尽可能地进行一些条件下推，以免最下层的 Operator 把整张表都捞出来。
- 批量模型（Vectorized / Batch Model）：是以上两者的一个折中，每个 Operator 的 next() 都会返回一批数据，具体的数据量可以根据实际的硬件条件来决定。
Block Iteration 这种说法表达的就是批量处理模型。行存和列存都可以采用这种查询处理模型，然而列存天然更加适合批量处理模型。
列存在使用批量处理模型时，多条数据的同一列是连续存储的，可以认为这些数据是以数组的方式存储的（如果数据类型是定长的），基于这样的特征，当该列数据需要进行某一同样操作，可以使用 SIMD 进一步提升计算效率，即便运算的机器上不支持 SIMD，也可以通过一个循环来高效完成对这个数据块各个值的计算。
批量模型和列存的结合能够充分利用底层 CPU 的向量化计算能力，因此批量模型基本都被称作是“向量化”了。