【DB】列式存储 & OLAP
对于分析型场景，列式存储本质上优于行式存储。其中关键的几大杀器是：编码压缩（compression）、向量化查询处理（vectorized query processing）、隐式连接（invisible join）、延迟物化（late materialization）等。
而这些技术的应用，需要从存储层到盘算层的全面支持才行，显然，目前主流的行式存储并不具备这样的条件。
1、编码压缩
列式存储的数据属于同一种范例，如数值范例，字符串范例等。相似度很高，试用符合的编码压缩可减少数据的存储空间，进而减少IO进步读取性能。
C-Store中针对数值范例的数据是否排序、区分度（Number of Distince Values）排列组合出4种环境，并给出了一些编码方案。
[*]有序且区分度不多
可以使用一系列三元组(v,f,n)对列数据编码，表示值 v 从第 f 行出现，一共有 n 个（即 f 到 f+n−1 行）。如：数值 2 出现在 10-15行，则编码为 (2,10,6)。
[*]无序且区分度不多
可以使用位图构造每个列取值出现的行位置，如：一列的数据为0,0,1,1,1,0,0,2,2，
则编码为 (0, 110001100)、(1, 001110000) 和 (2,000000011)
同时对稀疏的位图可进一步进行行程编码（Run Length Encoding，RLE)压缩数据。
[*]有序且区分度多
这时候可以使用等差数列（每个数值表示为前一个数值加上一个变化量）来减小数据的存储。如：对于一列数据 1,4,7,7,8,12，
可以表示为序列 1,3,3,0,1,4。
[*]无序且区分度多
这种环境数据的规律性不强，没有很好的编码方式。
其他场景的编码还有varint、字符串字典编码（Dictionary Encoding）等，这些轻量级的编码技术仅需要多付出一些CPU，就可以节流不小的IO。
对于复杂范例，嵌套范例的可以使用Google Dremel提出Striping/Assembly算法（开源Parquet），使用Definition Level+Repetition Level做编解码。一些数值范例有时也可以实验大一统的用bitshuffle做转换，共同压缩效果也不错，例如KUDU和百度Palo（Doris）中有应用。
同时，对于有些压缩/编码算法，好比RLE算法，针对压缩后的数据无需解压就可以直接做谓词下推，加速盘算速度。如：AAAAABBCCCDDDDA --> A5B2C3D4A1，如果要以where col = 'C’过滤数据，平均盘算复杂度即是总行数/列的基数，列基越大过滤越快（当然副作用是结果集很大）；别的，如果输出的列数据是排过序的，那where col = 'C’过滤数据的盘算复杂度降为log(总行数/列的基数)，速度更快。
在编码底子上，还可以进行传统的压缩，如snappy等支持流式处理、吞吐量高的压缩算法。
2、向量化实行
向量化是指一个CPU指令可以同时处理多条数据，如下图:
https://i-blog.csdnimg.cn/direct/251ecceb8fe247589d4ffef3341a529c.png
当把 v1 和 v2 数组中的数据分别加载到寄存器 XMM0 和 XMM1 中时，可以通过一条指令就完成两个数组的和vec_res盘算。
这需要 CPU 对向量化指令的支持，如 SSE2, AVX 等。
在软件层面上，向量化代码的书写方式体现在：先准备好待处理的批量数据，然后在对批量数据在一个 for 循环内做简单操作。
对于一个实现两个 int 相加的 expression：
[*]没有向量化的代码书写方式：class ExpressionIntAdd extends Expression {
Datum eval(Row input) {
int left = input.getInt(leftIndex);
int right = input.getInt(rightIndex);
return new Datum(left+right);
}
}
[*]向量化后的代码书写方式：class VectorExpressionIntAdd extends VectorExpression {
int[] eval(int[] left, int[] right) {
int[] ret = new int;
for(int i = 0; i < input.length; i++) {
ret = new Datum(left + right);
}
return ret;
}
}
对比向量化之前的版本，向量化之后的版本不再是每次只处理一条数据，而是每次能处理一批数据，而且这种向量化的盘算模式在盘算过程中也具有更好的数据局部性。这样可以让盘算更多的停顿在函数内，而不是频繁的交互切换，进步了CPU的流水线并行度，而且还可以使用SIMD指令，例如AVX指令集来实现数据并行处理。
向量化实行引擎以列存为条件，每次从磁盘上读取一批列，这些列以数组情势构造。每次operator（如实际实行中的scan扫表算子，agg聚合算子）的next操作都通过for循环处理列数组。这么做可以大幅减少next的调用次数。相应的CPU的利用率得到了进步，别的数据被构造在一起。可以进一步利用CPU硬件的特性，如SIMD，将所有数据加载到CPU的缓存当中去，进步缓存命中率，提升效率。在列存储与向量化实行引擎的双重优化下，查询实行的速度会有一个非常巨大的飞跃。但是向量化也会带来额外的开销，就是物化中间结果（materlization），以牺牲物化的开销换取更高的盘算性能。
3、延迟物化
物化指的是在SQL的实行过程中，获得最终数据的所处实行机遇。如：
select R.b from R where R.a=X and R.d=Y
延迟物化是指只有在算出过滤条件所对应的准确记录时，才去取记录所对应的结果值b.
https://i-blog.csdnimg.cn/direct/e14c1d1eed924571a15041d1c160ffad.png
对于OLAP场景，延迟物化的利益有：
[*]许多聚合与选择盘算，压根不需要整行数据，过早物化会浪费严重；
[*]许多列是压缩过的，过早物化会导致提前解压缩，但许多操作可以直接下推到压缩数据上的；
[*]面向真正需要的列做盘算，CPU的cache效率很高（100%），而行存由于非须要列占用了cache line中的空间，cache效率显然不高；
[*]针对定长的列做块迭代处理，可以当成一个数组来操作，可以利用CPU的许多优势（SIMD加速、cache line适配、CPU pipeline等）；相反，行存中列范例往往不一样，长度也不一样，还有大量不定长字段，难以加速。
4、隐式连接
对于多表Join，传统的做法一样平常是找到过滤性最强的维度表来关联事实表并过滤，然后再与其他维度表一一关联，得到最终的结果。
而隐式连接重要分三个步骤：
对于SQL：
SELECT c.nation, s.nation, d.year,
sum(lo.revenue) as revenue
FROM customer AS c, lineorder AS lo,
supplier AS s, dwdate AS d
WHERE lo.custkey = c.custkey
AND lo.suppkey = s.suppkey
AND lo.orderdate = d.datekey
AND c.region = 'ASIA'
AND s.region = 'ASIA'
AND d.year >= 1992 and d.year <= 1997
GROUP BY c.nation, s.nation, d.year
ORDER BY d.year asc, revenue desc;
1.下推相关条件到各个维度表，提炼出被事实表关联的主键列表（也就是事实表的外键），并构建对应的hash table（key是外键值，value是外键在维度表中的position）；
https://i-blog.csdnimg.cn/direct/cfc8ed13b95a4e288e23e48c8849a149.png
Figure 2: The rst phase of the joins needed to execute Query 3.1 from the Star Schema benchmark on some sample data
2.对多个事实表以外键关联维度表的列进行探测，查找对应的hash table，过滤出多个position list（与被关联的列相关），然后对多个position list求交集（好比bitmap的AND盘算等），得到一个最终的position list；
https://i-blog.csdnimg.cn/direct/5ebeb8a298b246cd9c06b3d53617c641.png
Figure 3: The second phase of the joins needed to execute Query 3.1 from the Star Schema benchmark on some sample data
3.基于前面的position list，最终从事实表中找到需要投影的其他列，而通过hash table从维度表找到需要投影的其他列，hash table中的value是维度表中的position，所以可以快速定位维度表的其他列。
https://i-blog.csdnimg.cn/direct/b9c849175b79498f92b25bb534523e6f.png
Figure 4: The third phase of the joins needed to execute Query 3.1 from the Star Schema benchmark on some sample data
这里的“隐式”是指，没有通过传统的join方式（两两表迭代，生成两个表团结在一起的宽行数据，再做过滤）来实现join，而是通过维持不同列的相同行之间的position对应关系来完成多个表join。与倒排索引很类似。
除此之外，动态代码生成、块IO（相比page IO,一次读取的数据量更大）,针对块建立的稀疏索引（由于块较大，索引量小，可尽可能将索引数据加载到内存），倒排索引，Join索引等都可加速基于列式存储的SQL实行效率。
但是仅仅将数据按照列式存储就可以解决所有标题了吗？
列式存储本质上方便的是列式数据的读取，但当SQL的查询结果是需要行相关的数据时，怎样兼顾列式存储重构出行的数据，这和列式存储的存储格式和索引结构有很大关系。
存储格式和索引结构
典型的列式存储数据库体系有Microsoft SQL Server、C-Store (2005) / Vertica、Dremel、Apache Kudu、MonetDB等。文末的参考资料中分别对其存储结果有一些先容。这里我列举一下Apache ORC文件格式帮助对列式的存储格式和索引结构有所了解。
Apache ORC的分区索引结构如下：
https://i-blog.csdnimg.cn/direct/c2d4f479459d4fd68ebd7ae06e3b7da3.png
ORC将数据结构分成以下 3 个层级，在每个层级上都有索引信息来加速查询。
File Level：即一个 ORC 文件，Footer 中生存了数据的 meta 信息，还有文件数据的索引信息，例如各列数据的最大最小值（范围）、NULL 值分布、布隆过滤器等，这些信息可用来快速确定该文件是否包含要查询的数据。每个 ORC 文件中包含多个 Stripe。
Stripe Level 对应原表的一个范围分区，里面包含该分区内各列的值。每个 Stripe 也有自己的一个索引放在 footer 里，和 file-level 索引类似。
Row-Group Level ：一列中的每 10000 行数据构成一个 row-group，每个 row-group 拥有自己的 row-level 索引，信息同上。
ORC 里的 Stripe 就像传统数据库的页，它是 ORC 文件批量读写的基本单位。
其中Row-Group的概念方便对行数据的重新整合。数据分区、分区内索引、行列混合等这些思想都可见于分布式存储体系中。
后记
本文扼要总结了列式存储的利益，Apache ORC的存储格式等。旨在帮助你我对OLAP场景下的列式存储有一个初步熟悉。更深一步的话题：如列式存储到底是怎样实现的，CRUD过程是怎样的，涉及的分布式存储标题又是怎样解决的…开头的一些专栏和文末参考资料中有一些论述。由于233酱离数据库开辟还很远，就不进一步尬聊了。。
文中有不懂的地方接待和233酱交流，一起进步。后面233酱也打算分享更多OLAP相关的知识，如Presto。不是这种总结条记的方式。期待与你再次相遇～
参考资料：
[*]为什么列式存储广泛应用于OLAP范畴？
.https://zhuanlan.zhihu.com/p/144926830
.https://zhuanlan.zhihu.com/p/35622907
.https://zhuanlan.zhihu.com/p/54484592
.https://zhuanlan.zhihu.com/p/100933389
.https://www.bilibili.com/video/BV1Bt411v7ST
.https://www.the-paper-trail.org/post/2013-01-30-columnar-storage/
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]