[fntdbs2013] The Design and Implementation of Modern Column-Oriented Database Systems

1. 行式存储 vs 列式存储

在数据库存储引擎侧通常有两类存储模型：
● 行式存储NSM（N-ary Storage Model）
● 列式存储DSM（Decomposition Storage Model）

1.1 NSM

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

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

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

1.1.1 优点

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

1.1.2 缺点

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

1.2 DSM

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

1.2.1 优点

非常适用于大量复杂查询的数据分析场景（OLAP）：
● 1、遍历整张表
● 2、输出指定列时，只需要扫描相关的列
● 3、列的分组、排序、聚合
● 4、每一列的数据都是相同类型的，彼此间相关性更大，对列数据压缩的效率较高

1.2.2 缺点

列存在更新场景明显存在缺陷：
每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

1.4 总结

2. What is a column store?

Column stores are relational databases that store data by column rather than by row. Whereas a traditional row-based store stores all attributes of one row together, followed by the attributes of the next row, and so on, a column-based stored uses one logical file per attribute (column) . The column-oriented layout makes it efficient to ++read just the columns you need for a query, without pulling in lots of redundant data++ .

Time cost can be separated into：
● seek times 寻道次数
● tranfer time 传输时间

3. Making column stores fast

仅仅将数据存储在列中，并不足以让基于列的存储获得全部性能。

根据论文中的这些技术特性，我们逐步分析 Vectorized processing, late materialization, compression。

4. Vectorized processing

4.1 概念

4.1.1 tuple-at-a-time

将关系代数中每一种操作抽象为一个 Operator，将整个 SQL 构建成一个 Operator 树，从根节点到叶子结点自上而下地递归调用 next() 函数。一次处理一行数据。

4.1.2 column-at-a-time

一次处理一列，处理包括：存储、查询等操作

4.2 Database strategies for the query execution layer

4.2.1 Volcano-style iterator model: tuple-at-a-time

火山式迭代器模型：元组-时间

4.2.2 Full materialization

In full materialization,each query operator works in isolation, fully consuming an, input from storage (disk, or RAM) and writing its output to storage. therefore may cause excessive resource utilization in queries that generate large intermediate results. maybe exceeding memory size.
在完全物化中，每个查询操作者都是孤立工作的，完全消耗存储（磁盘或RAM）中的输入，并将其输出写入存储。因此，在产生大量中间结果的查询中，可能会造成过度的资源利用。 最后也许会超出内存限制而出现问题。

4.2.3 Vectorized execution

1. This model separates query progress control logic from data processing logic.(将查询进度控制逻辑与数据处理逻辑分开)
2. returns a vector of N tuples as opposed to only a single tuple(每个操作符的next()方法返回N个图元的矢量)
3. avoidance of material-ization of large intermediates.(避免产生大量中间结果)

4.2.4 Block-oriented and Vectorized processing

By passing cache-line sized blocks of tuples between operators, and operating on multiple values at a time, rather than using a conventional tuple-at-a-time iterator, column-stores can achieve substantially better cache utilization and CPU efficiency.
论文中阐述了一种观点： 在面向块和矢量化处理的视线中，通过在运算符之间传递 缓存行 大小的 元组 块，并且一次对多个值进行操作，而不是使用传统的 一次一个元组 的迭代器，列存储可以实现大幅提高缓存利用率和CPU效率。

4.3 Advantage with vectorized processing

4.3.1 Reduced interpretation overhead

The amount of function calls performed by the query interpreter goes down by a factor equal to the vector size compared to the tuple-at-a-time model.
减少了解释的开销, 与 tuple-at-a-time 模型相比，查询解释器执行的函数调用量减少了一个与矢量大小相等的系数。 在TPC-H Q1的查询中可以将性能提高两个数量级。

4.3.2 Better cache locality

缓存局部性
In particular, columns data / arrays are contiguous memory blocks, so large chunks of them will be loaded into the cache upon first access. This makes it comparatively quick to access future elements of the array.
列数据是连续的，分配的内存块也是连续的，所以在第一次访问时，大块的内存块会被加载到高速缓存中。这使得后续访问数组中的元素变得相对较快。

4.3.3 Compiler optimization opportunities

编译器优化的可能性：自动内存预取、触发编译器来生成SIMD指令、有效使用 CPU 缓冲机制

4.3.4 Parallel memory access

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

4.4 SIMD

垂直计算优于水平计算

垂直计算

水平计算

4.5 Vectorized Processing 相比 tuple-at-a-time 的优势

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

5. Compression

5.1 Compression Perspectives

Compression algorithms perform better on data with low information entropy (i.e., with high data value locality), and values from the same column tend to have more value locality than values from different columns.
同一列的数据放一起信息熵要远低于来自不同列的数据。信息熵越低，数据越高度有序。

Compression algorithms perform better on data with low information entropy (i.e., with high data value locality), and values from the same column tend to have more value locality than values from different columns.
压缩算法在信息熵低 (即具有高数据值局部性) 的数据上表现更好；来自同一列的值往往比来自不同列的值有更多的值局部性。value locality的意思就是某个数据 (数据的内容或者逻辑地址) 被访问地更频繁。

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

5.2 Compression Advantage

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

5.3 Compression algorithms

5.3.1 Run length encoding

Run length encoding: RLE, which uses (value, start position, run length) triples.

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

5.3.2 Bit-Vector Encoding

位向量编码算法
Bit-vector encoding, so-called bit-map indices, useful when columns have a limited number of possible data values. Each possible data value has an associated bit-vector, with the corresponding bit in the vector set to one if the column attribute at that position has the chosen value.

5.3.2.1 举例1

例如：1132231
可以被如下3个bit-strings 所表示：
bit-string for value 1: 1100001
bit-string for value 2: 0001100
bit-string for value 3: 0010010

适用于低基数的列，相对于B树索引，它对count, and, or操作更有效，位图索引位存放的是0,1的bit，相对于B树索引，占字节数特别少。不适合update、insert、delete频繁的列：因为一个数据的更新可能会导致2个位图向量的更新。

5.3.2.2 举例2

5.3.3 Dictionary

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

关于字典的Paper, 可以看看这个。
Dictionary Compression for a Scan-Based, Main-Memory Database System https://publications.systems.ethz.ch/sites/default/files/publications/BernetJanickSpring2010.pdf

5.3.3.1 举例

6. Late Materialization

6.1 什么是物化？

6.2 延迟物化

把这个物化的时机尽量的拖延到整个查询生命周期的后期。

把从各个列中获取的数据重新组装为行的过程称之为 tuple construction，late materialization 的目的就是尽可能推迟 tuple construction 的时机。

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

6.3 通过延迟物化这个技术特性会带来了什么收益?

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

6.4 一个 select-project-join query 的延迟物化的例子

SQL:

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

6.4.1 行存做法

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

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

延迟物化的做法是：

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

6.4.3 Earlymaterialization vs Late materialization

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

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

6.4.4 Late materialization 带来的好处

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

6.4.5 Late materialization 的缺点

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

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

6.4.6 Late materialization 给性能带来的提升

7. Joins

7.1 Efficient join implementations

7.1.1 Hash-join

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

7.1.2 Jive-Join

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

7.1.3 Invisible Join

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

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

7.1.4 更多Join实现

当然还有BroadcastJoin，LookupJoin，SortJoin…

7.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语义的一致性，我们对数据结构再次排序，这次是按最初添加到连接输出的列，将当前数据结构恢复为原始连接顺序（以便与另一个表的连接输出相匹配）：

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

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

8. Summary

8.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；可以直接在压缩列做计算

8.2 写在最后

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！