列存数据库:通过采取合适的数据组织结构减小查询加载的数据量,提高查询效率

时间:2021-04-27 14:22:51 作者: MM

黄峰,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.

相关推荐
AI桌面浏览器

热文推荐

  • 48小时热文
  • 每周热文

列存数据库:通过采取合适的数据组织结构减小查询加载的数据量,提高查询效率

Baidu
map