列存数据库，不只是列式存储

对 OLAP 场景的查询而言，单个查询往往需要在存储端扫描大量数据，再在内存中进行一些统计分析后，才能输出所需要的统计结果。因此，如果不能像以 Kylin 为代表的 MOLAP 引擎采用预计算的方式来避免数据的实时扫描，对于基于磁盘存储的数仓而言，存储端无疑会因为扫描大量数据造成磁盘吞吐的瓶颈。

既然如此，是否存在别的选择，可以少从存储端加载数据呢？列存数据库正是通过采取合适的数据组织结构，来减小查询加载的数据量，最终提高查询效率。

大数据圈的各位对列式存储一定不陌生，快速浮现你脑海里的想必是 ORCFile，Parquet 等，但其实这些只是数据格式，并不能直接和列存数据库划等号。

列存格式 = 列存数据库

列存数据库^[1]更像是基于列存格式，设计的一套完整的数据库解决方案，而这套解决方案不仅需要考虑数据格式，更要考虑以下因素：

1. 由于考虑成本效率的因素，计算机中的存储常被设计成多级存储的结构，所以数据不单在磁盘上有特定的存储格式，在内存中，甚至 L1，L2，L3 缓存中同样有其独特的布局方式。考虑到存储端复杂的情况，如何结合 OLAP 场景的 workload，从而针对不同的硬件特点设计数据布局，是列存数据库在存储端需要考虑的核心问题；
2. 有了在不同存储层的数据存储布局之后，数据如何在不同存储层之间流动，比如，如何从磁盘加载数据到内存，什么时候进行加载，这些都是存取方法^[2]（Access Method）所涉及的内容；
3. 数据结构配上合适的算法才能横行江湖，计算和数据组织方式往往紧密耦合，彰显团结的力量。如何结合列存的特点设计一个高效的执行引擎，为 Join，Sort，Groupby 等关系算子提供一种更为高效的算法，都是列存数据库需要考虑的问题。

由此可见，为了追求极致的性能，底层存储的变化往往会引发存取方法、执行引擎、关系算子算法实现等多方面的一系列适配性的变化，真可谓环环相扣，好不紧张。下面，我们就依次从这几个方面介绍其所涉及内容。

存储格式

可曾记得把列存的思想引入大数据的先驱者—— RCFile^[3]，它的基本思想是将数据水平切分成一个个行组，在每个行组内除了元数据和行组切分标识以外，数据部分按列来进行连续存储。

这样操作的原因在于 OLAP 的查询虽然一般都会扫描大量行，但只会涉及少量列，通过这样的列存布局方式，能够有效避免无关列的加载，从而达到减小磁盘吞吐的目的。

但似乎先驱者的下场往往不那么尽如人意，RCFile 也没有摆脱这个魔咒。相较传统数仓中的列存而言，RCFile 还是太过粗糙，要学就学全套呀！

Hive 的开发者们总结了 RCFile 的经验教训，指出其核心问题^[4]在于：

1. 对数据类型不感知，从而无法对具体类型做编码优化，限制了列存的存储高效性；
2. 没有索引辅助过滤数据（如：谓词下推），造成数据读取效率低下。

站在前人的肩膀上，后续的 ORCFile，Parquet 都开启了进化之旅，一方面加入一些 Min、Max、Count 等轻量级统计索引来加速查询；另一方面，针对不同场景，采用 RLE，Bitcode，Dictionary Code 等编码方式进行存储优化，比如 RLE，针对的就是取值范围不大，重复度高的数据，假设有一列数据是 AAABBBB，RLE 就会直接采用 A3B4 来表达（其中“3”和“4”代表前一个值出现的次数）。

自此以后，列存格式的风吹遍了整个大数据生态圈，CarbonData 采用多维排序的方式优化数据的列式布局；Druid 在列存之上，通过对维度列进行 Dictionary 编码加 Bitmap 索引的方式加速了数据的筛选和聚合......

当然，存储格式并不是只需关心存储查询的效率问题，将其应用到实际中所需要考虑的问题同样重要。比如，2019 年 4 月，Databricks 公司重磅开源 Delta Lake，给数据添加了 ACID 特性，支持数据的并发读写，Hudi 和 Iceberg 也不甘落后，存储的故事又拉开了一张大幕，世界就是这样精彩！

存取方式

数据存在磁盘上的数据布局叫做存储格式，而存取方式则包括：

• 数据是怎么从磁盘读到内存的？（例如 MySQL 加载数据的时候，是通过全表扫描，还是通过索引扫描）
• 数据在内存的布局是怎样的？
• 数据又是怎么写回磁盘的？

等一系列过程。

这里我们以数据从磁盘加载到内存的过程为例，来探讨列式存储能够给存取过程带来哪些优势。由于数据最终输出时是以行为单位，所以在将列存数据读入内存时，直接定位到要扫描的列，然后按顺序重构一行行数据并交由执行引擎处理，就显得尤为自然，但我们不如想的更深入一步：

1. 内存中的数据表是不是也可以是列式的？
2. 数据是不是可以懒加载（延迟物化）？

对于问题一，Presto、ClickHouse 等实践者通过在内存中使用列存布局，不仅优化了存储效率，也使得向量化计算加速分析查询变为可能；

对于延迟物化^[5]的问题，核心就在于数据是否能等到真正需要它们的时候再加载，例如对于以下查询：

select b from R where a = X and d = Y

是直接如上图左侧所示，将查询涉及到的 a、b、d 列全部加载到内存里构成一行一行数据，然后进行过滤（Filter）和映射（Project）；

还是如上图右侧所示，选择尽量延迟加载，先分别对 a、d 列进行单独加载过滤，决定要输出的行（图中的 01 向量），再把对应行的 b 列加载输出，最后再构建成行数据输出？

这两者的 Tradeoff 在于，虽然延迟加载能够减少数据的加载量，但需要维护原始数据的位置，这样才能找到对应行的其他列的值，然而如果筛选条件（R.a = X and R.d = Y ）不能大量过滤数据，延迟加载反而低效。对于这种情况，就需要根据一些统计信息选择合适的加载算法，来最大限度的提高效率。

执行引擎与关系算子

说完了存储端的故事，让我们转战计算端，唠一唠执行引擎和关系算子与列存之间又有怎样的故事。

1. 执行引擎

首先，来了解一下执行引擎的在 SQL 查询过程中发挥了什么样的作用。

熟悉 SQL 查询引擎的同学应该都清楚，一条 SQL 会经过词法语法解析、语义校验、逻辑执行计划生成优化等一系列步骤，生成最后的物理执行计划，例如，对于如下 SQL：

select * from R where a = 1

其物理执行计划如下图所示：

执行引擎所做的事情就包括，定义 TableScan，Filter 等一系列关系算子（Operator）的实现框架，从而可以组合使用多个关系算子，构建它们之间的数据依赖关系（也就是执行计划），最终实现不同 SQL 的功能。

最经典的执行引擎实现非 Volcano^[6] 莫属了。它把每一个算子抽象成数据的迭代器（Iterator），分别由 Open，Next，Close 构成。其中 Open 做一些初始化的工作，比如 TableScan 如何实现打开对应的表文件；Next 按照特定算子的功能逻辑处理数据，增量式得到输出；Close 清理资源。如下的伪代码就是 TableScan 的一个实现：

public class TableScan implement Iterator{
    void open(){
        tableFile.open();
    }
    Row next(){
        if ( (row = tableFile.nextRow()) != EOF){
            return row;
        }
        return EOF;
    }
    
    void close(){
        tableFile.close();
    }
}

Volcano 的优点在于处理逻辑清晰，每个算子只需关心自己的处理逻辑即可，耦合性低。不过它的缺点也很明显，过多虚函数的调用，导致大量 CPU cache miss，从而影响 CPU 执行效率。

在数据库诞生之初，数据库先贤们奋战在弥补磁盘和 CPU 速度巨大的鸿沟上，CPU 的浪费显得微不足道。然而，在数据库新时代，摩尔定律的失效使得单核性能提升日渐趋缓，OLAP 的发展导致将大量数据加载到内存进行计算，瓶颈慢慢从存储端向 CPU 端倾斜，榨干 CPU 每一滴性能的企图就变得越发强烈，于是 CodeGen，向量化执行^[7]等方法应运而生，它们从不同的方向入手来优化 CPU 的利用率，能够极大的提高执行效率。向量化执行正是利用列式存储的优势，可以一次性对整列数据进行批量处理，减少 CPU 的消耗。

2. 关系算子

有了执行引擎奠定的框架，关系算子只需要一个萝卜一个坑，逐一实现即可，然而算法的世界是层出不穷，千变万化的，比如对于 Join 大家最熟悉的算法就有 BroadcastJoin，LookupJoin，SortJoin 等等， 而列存又会给 Join 算法带来什么样的优化空间呢？

对于 Join 而言，运算的核心在于两表中 Joinkey 的匹配上，而对于其他列数据匹配上了就复制，匹配不上就丢弃。那么结合延迟物化的思想，是否可以等到匹配完成后再加载其他列数据，从而减小不必要的数据加载。

举个例子，对于如下 SQL：

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

我们先抽出 emp 表的 dept_id 和 dept 表的 id 列数据，进行匹配，并输出匹配结果对应原表的位置信息，如下图所示：

其中等于号的左边为 dept_id 和 id 列的数据，等于号的右边为匹配结果对应原表的位置信息，比如第一行 1，2 代表 dept_id 列的第一个值 42 和 id 列的第 2 个值 42，Join 的结果。

然后根据输出的位置信息，就可以从原始数据中抽取 age，name 列的数据得到 Join 最后的结果。当然该算法能够产生明显优化效果的前提是 Join 的结果相较于原始数据比较小，这样才能够有效避免加载过多数据。另外由于上图输出结果的第二列是无序的，如果回表查必然造成大量随机 IO，为了解决这个问题，Jive Join^[8]采用了对其进行排序之后再查询，即将随机 IO 转化为顺序 IO 的方法进行优化。

总结

综上，我们从大数据存储格式的变迁；存取方式中 Early Materialization 和 Late Materialization 的权衡取舍；执行框架向优化 CPU 的方向迈进；关系算子结合存储进行优化等几个方面对列存数据库进行了讲解。

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

参考文献：

[1] The Design and Implementation of Modern Column-oriented Database Systems.

[2] Design Tradeoffs of Data Access Methods.

[3] RCFile: A Fast and Space-efficient Data Placement Structure in MapReduce-based Warehouse Systems.

[4] Major Technical Advancements in Apache Hive.

[5] Materialization Strategies in a Column-oriented DBMS.

[6] Encapsulation of Parallelism in the Volcano Query Processing System.

[7] Vectorization vs. Compilation in Query Execution.

[8] Fast Joins Using Join Indices.

更多 Apache Kylin 最新动态，技术博客以及案例分享，请扫描二维码，关注 Apache Kylin 公众号。