黄峰，Kyligence?公司高级研发工程师，目前主要负责?Kyligence?企业级产品的开发以及维护工作。

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

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

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

　　列存格式?=?列存数据库

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

　　由于考虑成本效率的因素，计算机中的存储常被设计成多级存储的结构，所以数据不单在磁盘上有特定的存储格式，在内存中，甚至?L1，L2，L3?缓存中同样有其独特的布局方式。考虑到存储端复杂的情况，如何结合?OLAP?场景的?workload，从而针对不同的硬件特点设计数据布局，是列存数据库在存储端需要考虑的核心问题;

　　有了在不同存储层的数据存储布局之后，数据如何在不同存储层之间流动，比如，如何从磁盘加载数据到内存，什么时候进行加载，这些都是存取方法?[2]?(Access?Method)所涉及的内容;

　　数据结构配上合适的算法才能横行江湖，计算和数据组织方式往往紧密耦合，彰显团结的力量。如何结合列存的特点设计一个高效的执行引擎，为?Join，Sort，Groupby?等关系算子提供一种更为高效的算法，都是列存数据库需要考虑的问题。

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

　　01

　　存储格式

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

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

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

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

　　对数据类型不感知，从而无法对具体类型做编码优化，限制了列存的存储高效性;

　　没有索引辅助过滤数据(如：谓词下推)，造成数据读取效率低下。

　　站在前人的肩膀上，后续的?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?也不甘落后，存储的故事又拉开了一张大幕，世界就是这样精彩!

　　02

　　存取方式

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

　　数据是怎么从磁盘读到内存的？(例如?MySQL?加载数据的时候，是通过全表扫描，还是通过索引扫描)

　　数据在内存的布局是怎样的？

　　数据又是怎么写回磁盘的？

　　等一系列过程。

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

　　内存中的数据表是不是也可以是列式的？

　　数据是不是可以懒加载(延迟物化)？

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

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

　　selectb?fromR?wherea?=X?andd?=Y

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

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

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

　　03

　　执行引擎与关系算子

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

　　执行引擎

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

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

　　select*fromR?wherea?=1

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

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

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

　　publicclassTableScanimplementIterator{?voidopen{?tableFile.open;?}?Row?next{?if(?(row?=?tableFile.nextRow)?!=?EOF){?returnrow;?}?returnEOF;?}?voidclose{?tableFile.close;?}?}

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

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

　　关系算子

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

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

　　举个例子，对于如下?SQL：

　　SELECTemp.age,?dept.name?FROMemp,?dept?WHEREemp.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?的方法进行优化。

　　04

　　总结

　　综上，我们从大数据存储格式的变迁;存取方式中?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.