IT技术之家

首页 > 大数据

大数据

行式存储和列式存储的区别_正在沿着IT树往上爬_行式存储和列式存储的区别

发布时间:2022-10-24 20:49:02 大数据 0次 标签:大数据
行存储和列存储的区别...

文章目录

存储方式简单对比列式存储和行式存储它们真正的区别概述四大优化策略详解块遍历压缩延迟物化隐式链接 总结

存储方式


行式存储就是每一行的所有数据存在一个block中,各个block之间连续存储;
列式存储就是每一列的所有数据存在一起,不同列之间可以分开存储。

简单对比

Row-StoreColumn-Store
写入每一行的所有字段都存在一起,优点:对数据进行插入和修改操作很方便当一条新数据到来,每一列单独存储,缺点:插入和修改操作麻烦
查询查询时即使只涉及某几列,所有数据也都会被读取;优点:适合随机查询;在整行的读取上,要优于列式存储;缺点:行式存储不适合扫描,这意味着要查询一个范围的数据查询时只有涉及到的列会被读取;缺点:查询完成时,被查询的列要重新进行组装
寻道范围读取数据的时候硬盘寻址范围很大由于仅对需要的列进行查找,因此硬盘寻道范围小
索引缺点:要加速查询的话需要建立索引,建立索引需要花费很多时间。优点:任何列都能作为索引(每一列单独存储,查询个别列的时候,可以仅读取需要的那几个列,相当于为每一列都建立了索引)
压缩缺点:不利于压缩把一列数据保存在一起,而一列的数据类型相同 ;优点:利于压缩
空间按行存储,不利于压缩,压缩比较差,占空间大列式存储的时候可以为每一列创建一个字典,存储的时候就仅存储数字编码即可,降低了存储空间需求
聚合不利于聚合操作按列存储,利于数据聚合操作
应用MySQL中的iInnoDB和MyISAM存储引擎是行式存储MySQL中的infobright存储引擎是列式存储
使用场景OLTP(存储关系型数据,用于使用数据的时候需要经常用到数据之间的依赖关系的场景,即读取的时候需要整行数据或者整行中大部分列的数据,需要经常用到插入、修改操作)OLAP(分布式数据库和数据仓库,适合于对大量数据进行统计分析,列与列之间关联性不强,仅进行插入和读取操作的场景)
    列式存储是非关系型数据库中的一种,非关系型数据库的目的在于去掉关系数据库的关系型特性,使得数据之间无关系,使得扩展性高。非关系型数据库一般具有大数据量、高性能的特点,典型的有Key-Value键值存储数据库等。行存储、列存储,最终都需要把数据存到磁盘块。行存储优点很明显,更新快、单条记录的数据集中,适合事务。但缺点也很明显,查询慢。列存储的优势其实是在查询和聚合运算。之所以说行存储适合事务,其实是相对的,是因为列存储非常不适合事务。试想一下,你更新一个表的若干个数据,如果要在不同块中更新,就可能产生多次更新操作。更新次数越多,保证一致性越麻烦。在单机环境我们可以上锁,可以用阻塞队列,可以用屏障……但是分布式场景中保证一致性(特别是强一致性)开销很大。因此我们说行存储适合事务,而列存储不适合。

列式存储和行式存储它们真正的区别

参考文献:《Column-Stores vs. Row-Stores: How Different Are They Really?》

概述

对于分析类的查询为什么Column-Store比Row-Store好那么多?好在哪里?一般认为原因是:

分析类查询往往只查询一个表里面很少的几个字段,Column-Store只需要从磁盘读取用户查询的Column,而Row-Store读取每一条记录的时候你会把所有Column的数据读出来,在IO上Column-Store比Row-Store效率高很多,因此性能更好。

通过《Column-Stores vs. Row-Stores: How Different Are They Really?》这篇论文,可以知道Column-Store在存储格式优势只是一方面,如果没有查询引擎上其它几个优化措施的配合,性能也不会太好的,这篇论文认为Column-Store在查询引擎层有以下几种大的优化手段:
面向列的系统中优化:

延迟物化(Late Materialization )块遍历(Block Iteration )压缩(Compression )隐式连接(Invisible Joins)

四大优化策略详解

块遍历

块遍历(Block Iteration)是相对于单记录遍历(per-tuple iteration)而言的,其实说白了就是一种批量化的操作。单记录遍历的问题在于对于每个条数据,我们都要从Row数据里面抽取出我们需要的column(针对Row-Store来说),然后调用相应的函数去处理,函数调用的次数跟数据的条数成是 1:1的,在大数据量的情况下这个开销非常可观。而块遍历,因为是一次性处理多条数据,函数调用次数被降下来,当然可以提高性能。

这种提高性能的方法在Row-Store里面是case-by-case实现的(不是一种共识), 而对于Column-Store来说已经形成共识,大家都是这么做的。而如果column的值是字节意义上等宽的,比如数字类型,Column-Store可以进一步提高性能,因为查询引擎要从一个Block里取出其中一个值进行处理的时候直接用数组下标就可以获取数据,进一步提升性能。而且以数组的方式对数据进行访问使得我们可以利用现代CPU的一些优化措施比如SIMD(Single Instruction Multiple Data)来实现并行化执行,进一步提高性能。

压缩

压缩,就是将相似度很高、信息熵很低的数据放在一起,用更小的空间表达相同的信息量。列存的数据往往类型相同,相同的特征更多,更容易被压缩,所以列存系统的压缩优化比行存系统更加有效。

但是为什么压缩就能带来查询的高效呢?压缩首先带来的硬盘上存储空间的降低,但是硬盘又不值钱。它的真正意义在于:数据占用的硬盘空间越小,查询引擎花在IO上的时间就越少(不管是从硬盘里面把数据读入内存,还是从内存里面把数据读入CPU)。同时要记住的是数据压缩之后,要进行处理很多时候要需要解压缩(不管是Column-Store还是Row-Store), 因此压缩比不是我们追求的唯一,因为后面解压也需要花时间,因此一般会在压缩比和解压速度之间做一个权衡。

高压缩比的典型如Lempel-Ziv, Huffman, 解压快的典型如: Snappy, Lz2
前面提到解压缩,有的场景下解压缩这个步骤可以彻底避免掉,比如对于采用Run-Length编码方式进行压缩的数据,我们可以直接在数据压缩的格式上进行一些计算:

Run-Length的大概意思是这样的, 对于一个数字序列: 1 1 1 1 2 2 2, 它可以表达成 1x4, 2x3
这样不管进行 count (4 + 3), sum (1 x 4 + 2 x 3) 等等都可以不对数据进行解压直接计算,而且因为扫描的数据比未压缩的要少,从而可以进一步的提升性能。另外,
对于Column-Store应用压缩这种优化最好的场景是配合 sort 使用,如果数据是经过排序的,则更容易找到相邻数据的同质化特征,获得更好的压缩效果。

延迟物化

物化Materialization 是指为了把底层面向列的存储格式跟要求的行式格式对上,需要在查询的某个阶段转换一下。

理解物化的概念后,延迟物化就很好理解了,意思就是把物化的时机尽量地拖延到整个查询声明的后期。延迟物化意味着在查询执行的前一段时间内,查询执行的模型不是关系代数,而是基于 Column 的。下面看个例子, 比如下面的查询:

SELECT name
FROM person
WHERE id > 10
  and age > 20

一般的做法是从文件系统读出三列的数据,马上物化成一行行的person数据,然后应用两个过滤条件: id > 10 和 age > 20 , 过滤完了之后从数据里面抽出 name 字段,作为最后的结果,大致转换过程如下图:

而延迟物化的做法则会先不拼出行式数据,直接在 Column 数据上分别应用两个过滤条件,从而得到两个满足过滤条件的 bitmap,然后再把两个 bitmap 做位与的操作得到同时满足两个条件的所有的 bitmap,因为最后用户需要的只是 name 字段而已,因此下一步我们拿着这些 position 对 name 字段的数据进行过滤就得到了最终的结果。如下图:

发现没有?整个过程中我们压根没有进行物化操作,从而可以大大的提高效率。

总结起来延迟物化有四个方面的好处:

关系代数里面的 selection 和 aggregation 都会产生一些不必要的物化操作,从一种形式的tuple, 变成另外一种形式的tuple。如果对物化进行延迟的话,可以减少物化的开销(因为要物化的字段少了),甚至直接不需要物化了;如果Column数据是以面向Column的压缩方式进行压缩的话,如果要进行物化那么就必须先解压,而这就使得我们之前提到的可以直接在压缩数据上进行查询的优势荡然无存了;列式的内存组织形式对 CPU Cache 非常友好,从而提高计算效率,相反行式的组织形式因为非必要的列占用了 Cache Line 的空间,Cache 效率低;块遍历的优化手段对 Column 类型的数据效果更好,因为数据以 Column 形式保存在一起,数据是定长的可能性更大,而如果 Row 形式保存在一起数据是定长的可能性非常小(因为你一行数据里面只要有一个是非定长的,比如 VARCHAR,那么整行数据都是非定长的);

隐式链接

最后本文提出了一个具有创新性的性能优化措施: Invisible Join。Invisible Join 针对的场景是数仓里面的星型模型(Star Schema), 如果用户查询符合下面的模式就可以应用Invisible Join:

利用事实表的里面的外键跟维度表的主键进行JOIN的查询的, 最后select出一些column返回给用户。
所谓的星型模型指的是一个事实表(fact table), 周围通过外键关联一堆维度表(dimension table)的这么一种模型


为了介绍Invisible Join的思路,我们要先介绍一下两种传统的方案,通过对比我们才能看Invisible Join方案的优点。

传统方案一: 按Selectivity依次JOIN
传统方案一最简单,按照 Selectivity 从大到小对表进行JOIN:

传统方案二: 延迟物化
方案二比较有意思, 它应用了延迟物化的策略,它先不进行JOIN,而是先在维度表上对数据进行过滤,拿到对应表的 POSITION, 然后把表的主键跟事实表的外键进行JOIN,这样我们就可以拿到两类POSITION: 事实表的POSITION和维度表的POSITION, 然后我们通过这些POSITION把数据提取出来就完成了一次JOIN, 重复以上的操作我们就可以完成整个查询。

Invisible Join详解
上面两种方案都各有各的缺点:

传统方案一因为一开始就做了JOIN,享受不了延迟物化的各种优化。传统方案二在提取最终值的时候对很多Column的提取是乱序的操作,而乱序的提取性能是很差的(随机IO)。
下面正式介绍一下我们的主角: Invisible JOIN

Invisible JOIN其实是对传统方案二的一种优化,传统方案二的精髓在于延迟物化,但是受制于大量的值的提取还是乱序的,性能还是不是最好。Invisible JOIN把能这种乱序的值提取进一步的减少, 它的具体思路如下:

    把所有过滤条件应用到每个维度表上,得到符合条件的维度表的主键(同时也是事实表的外键)。遍历事实表,并且查询第一步得到的所有外键的值,得到符合条件的bitmap(s), 这里会有多个bitmap,因为维度表可能有多个。对第二步的多个bitmap做AND操作,得到最终事实表里面符合过滤条件的bitmap。根据第三步的事实表的bitmap以及第一步的符合条件的维度表的主键值,组装出最终的返回值。

如果只是这样的话Invisible JOIN可能比上面的第二种方案好不了多少,论文认为在很多时间维度表里面符合过滤条件的数据往往是连续的,连续的好处在于,它能把lookup join变成一个值的范围检查,范围检查比lookup join要快,原因很简单,范围检查只需要所算数运算就好了,不需要做lookup,因此可能大幅度的提高性能。

性能对比
从论文提供的性能对比数字来看,这几大优化策略里面延迟物化的效果最好,能够提升性能3倍以上;压缩的优化效果次之: 两倍以上;Invisible JOIN 再次之:50% 到 70%;块遍历则能性能 5% 到 50%

而如果把这些优化手段都去掉,Column-Store的性能跟一个普通的Row-Store就没什么区别了。

总结

读这篇论文最大的收获是首先知道了到底哪些因素促使Column-Store对分析类查询性能可以大幅优于Row-Store: 延迟物化、压缩、Invisible Join以及块遍历。

特别佩服这篇论文的是很多人稍微想一下就会觉得Column-Store在分析类场景下性能优于Row-Store是天经地义的: 更少的IO,但是这篇论文详细的对各种场景进行了测试、论证,同时对Row-Store应用类似的性能优化的手段再进行测试、对比,掰开了揉碎了的分析。最终告诉我们:

Column-Store的优点不止在于它的存储格式,查询引擎层的各种优化也同样关键,而由于Row-Store本身存储格式的限制,即使在Row-Store上使用这些优化,效果也不好。

参考自:
https://developer.aliyun.com/article/792679
https://zhuanlan.zhihu.com/p/54433448
http://www.cs.umd.edu/~abadi/papers/abadi-sigmod08.pdf?spm=a2c6h.12873639.article-detail.4.560c6ba5jxcuAH&file=abadi-sigmod08.pdf