专栏首页码农知识点为什么列式存储广泛应用于OLAP领域?

为什么列式存储广泛应用于OLAP领域?

四畳半神話大系

前言

233酱工作中开始接触Presto等大数据分析场景下的内容,列式存储属于OLAP中重要的一环。这周主要花时间搜索阅读网上的相关资料,发现一众大数据、数据库开发等大佬们的总结文章,如知乎专栏:「分布式数据系统小菜」、「数据库内核」、「Presto」、「尬聊数据库」...这对我这种想要入门的小白是很好的读物。本篇文章是我主要基于上述专栏中的一些资料的笔记总结,因为能力有限,很难跳脱于本文参考资料的总结。希望本篇文章能对和我一样的小白起到科普作用,想要了解更多的小伙伴请移步以上专栏。另外,对OLAP/Presto等感兴趣的小伙伴也欢迎和233酱多多交流,一起学习进步,求抱大腿,hhh~~

什么是OLAP

OLAP(Online analytical processing)指联机分析处理。从字面意思上我们可以看出有「分析」二字,如:统计,报表,聚合类操作。你说Mysql不也是能做吗?OLAP还有一侧重点,指大数据量的在线分析,如PB级,TB级以上。 下表是对OLTP和OLAP的简单总结。

我们也可以通过两者的benchmark直观感受下评判性能的不同侧重点。

对于OLTP来说,有sysbench和tpcc测试套件。sysbench的lua脚本中的sql语句如下:

SELECT c FROM sbtest10 WHERE id=4352
SELECT c FROM sbtest10 WHERE id BETWEEN 5046 AND 5046+99 ORDER BY c

对于OLAP来说,有tpch和tpcds 2种。tpcds的 sql语句举例如下:

SELECT
  "c_last_name"
, "c_first_name"
, "ca_city"
, "bought_city"
, "ss_ticket_number"
, "extended_price"
, "extended_tax"
, "list_price"
FROM
  (
   SELECT
     "ss_ticket_number"
   , "ss_customer_sk"
   , "ca_city" "bought_city"
   , "sum"("ss_ext_sales_price") "extended_price"
   , "sum"("ss_ext_list_price") "list_price"
   , "sum"("ss_ext_tax") "extended_tax"
   FROM
     ${database}.${schema}.store_sales
   , ${database}.${schema}.date_dim
   , ${database}.${schema}.store
   , ${database}.${schema}.household_demographics
   , ${database}.${schema}.customer_address
   WHERE ("store_sales"."ss_sold_date_sk" = "date_dim"."d_date_sk")
      AND ("store_sales"."ss_store_sk" = "store"."s_store_sk")
      AND ("store_sales"."ss_hdemo_sk" = "household_demographics"."hd_demo_sk")
      AND ("store_sales"."ss_addr_sk" = "customer_address"."ca_address_sk")
      AND ("date_dim"."d_dom" BETWEEN 1 AND 2)
      AND (("household_demographics"."hd_dep_count" = 4)
         OR ("household_demographics"."hd_vehicle_count" = 3))
      AND ("date_dim"."d_year" IN (1999   , (1999 + 1)   , (1999 + 2)))
      AND ("store"."s_city" IN ('Midway'   , 'Fairview'))
   GROUP BY "ss_ticket_number", "ss_customer_sk", "ss_addr_sk", "ca_city"
)  dn
, ${database}.${schema}.customer
, ${database}.${schema}.customer_address current_addr
WHERE ("ss_customer_sk" = "c_customer_sk")
   AND ("customer"."c_current_addr_sk" = "current_addr"."ca_address_sk")
   AND ("current_addr"."ca_city" <> "bought_city")
ORDER BY "c_last_name" ASC, "ss_ticket_number" ASC
LIMIT 100

显然,tpcds的查询复杂度相比oltp高非常多。

为什么行式存储不适用于OLAP领域

行式存储是指数据的存储是以行为单位,一行的数据在物理block上紧挨在一起存储。

行式存储

好处:操作一行的数据方便。

(虽然听起来像一句废话:)

我们以行存代表Mysql为例,Innodb的聚簇索引(B+树)示意图如下:

其中Intern Page上存储的是索引数据,Leaf Page上存储的完整的行数据。

行存能保证数据的修改是原地更新的,对读取行数据友好,易于随机IO。IO的单位通常是以页为单位(如16KB),也可以通过内存缓存/SSD等方式优化IO。

缺点:对于分析类sql,通常只需要关联一行中的几个列数据,行存会导致读取大量无关的列数据,IO浪费,CPU缓存失效...

为什么列式存储适用于OLAP领域

列式存储是指数据的存储是以列为单位,一列的数据在物理block上紧挨在一起存储。

显然,如果我们查询:

select count(*) from table where name = '233';

只需要从中按需读取name一列进行分析总数就可以了,看样子节省了不少I/O。但列式存储只有这一个必杀技吗?

Column-Stores vs. Row-Stores: How Different Are TheyReally?一文中在行式存储中模拟了列式范式设计:

通过将表结构垂直拆分以及全列建索引,就可以在查询时,只查询部分列对应的数据,从而加快分析速度。

最终实验得出:在行式存储上就算以column-oriented方式来设计数据的物理结构,面对分析型场景还是无法与列式存储抗衡。对于分析型场景,列式存储在本质上优于行式存储。

其中关键的几大杀器是:编码压缩(compression)、向量化查询处理(vectorized query processing)、隐式连接(invisible join)、延迟物化(late materialization)等。压缩带来的性能提升要看真实数据,最多时有一个数量级之多,延迟物化提高3倍,块迭代和隐式连接提升约1.5倍。而这些技术的应用,需要从存储层到计算层的全面支持才行,显然,目前主流的行式存储并不具备这样的条件。

下面我将简单介绍下这些技术。

编码压缩

列式存储的数据属于同一种类型,如数值类型,字符串类型等。相似度很高,试用合适的编码压缩可减少数据的存储空间,进而减少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等支持流式处理、吞吐量高的压缩算法。

向量化执行

向量化是指一个CPU指令可以同时处理多条数据,如下图:

当把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[input.length];
                for(int i = 0; i < input.length; i++) {
                        ret[i] = new Datum(left[i] + right[i]);
                }
                return ret;
        }
}

对比向量化之前的版本,向量化之后的版本不再是每次只处理一条数据,而是每次能处理一批数据,而且这种向量化的计算模式在计算过程中也具有更好的数据局部性。这样可以让计算更多的停留在函数内,而不是频繁的交互切换,提高了CPU的流水线并行度,而且还可以使用SIMD指令,例如AVX指令集来实现数据并行处理。

向量化执行引擎以列存为前提,每次从磁盘上读取一批列,这些列以数组形式组织。每次operator(如实际执行中的scan扫表算子,agg聚合算子)的next操作都通过for循环处理列数组。这么做可以大幅减少next的调用次数。相应的CPU的利用率得到了提高,另外数据被组织在一起。可以进一步利用CPU硬件的特性,如SIMD,将所有数据加载到CPU的缓存当中去,提高缓存命中率,提升效率。在列存储与向量化执行引擎的双重优化下,查询执行的速度会有一个非常巨大的飞跃。但是向量化也会带来额外的开销,就是物化中间结果(materlization),以牺牲物化的开销换取更高的计算性能。

延迟物化

物化指的是在SQL的执行过程中,获得最终数据的所处执行时机。如:

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

延迟物化是指只有在算出过滤条件所对应的准确记录时,才去取记录所对应的结果值b.

对于OLAP场景,延迟物化的好处有:

  • 很多聚合与选择计算,压根不需要整行数据,过早物化会浪费严重;
  • 很多列是压缩过的,过早物化会导致提前解压缩,但很多操作可以直接下推到压缩数据上的;
  • 面向真正需要的列做计算,CPU的cache效率很高(100%),而行存因为非必要列占用了cache line中的空间,cache效率显然不高;
  • 针对定长的列做块迭代处理,可以当成一个数组来操作,可以利用CPU的很多优势(SIMD加速、cache line适配、CPU pipeline等);相反,行存中列类型往往不一样,长度也不一样,还有大量不定长字段,难以加速。

隐式连接

对于多表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);

2.对多个事实表以外键关联维度表的列进行探测,查找对应的hash table,过滤出多个position list(与被关联的列相关),然后对多个position list求交集(比如bitmap的AND计算等),得到一个最终的position list;

3.基于前面的position list,最终从事实表中找到需要投影的其他列,而通过hash table从维度表找到需要投影的其他列,hash table中的value是维度表中的position,所以可以快速定位维度表的其他列。

这里的“隐式”是指,没有通过传统的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的分区索引结构如下:

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。不是这种总结笔记的方式。期待与你再次相遇~


参考资料:

[1].https://zhuanlan.zhihu.com/p/144926830

[2].https://zhuanlan.zhihu.com/p/35622907

[3].https://zhuanlan.zhihu.com/p/54484592

[4].https://zhuanlan.zhihu.com/p/100933389

[5].https://www.bilibili.com/video/BV1Bt411v7ST

[6].https://www.the-paper-trail.org/post/2013-01-30-columnar-storage/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 什么是Druid

    玩过魔兽世界,暗黑破坏神,Dota,炉石传说,Dota自走棋的朋友,对这个词一定不陌生。

    实时计算
  • 不负责任的聊下 Apache Doris

    应读者的要求,这篇文章简单聊聊 Apache Doris。说实话,Apache Doris 比前面提到的 Impala 、Presto 这些交互式查询引擎还要不...

    哒呵呵
  • 不懂这几个问题,怎么学好数据挖掘!

    关键词:数据挖掘、DataMining、OLAP、Data Warehousing 正文如下: 1、DataMining和统计分析有什么不同? 硬要去区分Dat...

    小莹莹
  • 干货 | 数据挖掘入门必看10个问题

    NO.1 Data Mining 和统计分析有什么不同? 硬要去区分Data Mining和Statistics的差异其实是没有太大意义的。一般将之定义为Da...

    灯塔大数据
  • 【观点】数据挖掘入门必看10个问题

    NO.1 Data Mining 和统计分析有什么不同? 硬要去区分Data Mining和Statistics的差异其实是没有太大意义的。一般...

    小莹莹
  • 《你问我答》第二期 | 解答关于TubeMQ、TBase、Oceanus与数据湖的疑问

    ? 各位小伙伴们大家好,我们又见面啦~ 上一期的《你问我答》中 我们的专家解答了大伙对于腾讯大数据团队的开源项目,以及技术实践等方面的一些疑问 与此同时,我们...

    腾讯大数据
  • 腾讯大数据星火计划--Angel技术沙龙 对外报名正式启动!

    导语:腾讯大数据举办星火计划技术沙龙为广大大数据爱好者提供线下交流活动机会,技术沙龙第一期将于10月13日在深圳腾讯大厦举办,为您揭秘海量机器学习之道与Ang...

    腾讯大数据
  • 腾讯大数据星火计划--Angel技术沙龙 对外报名正式启动!

    ? 导语:腾讯大数据举办星火计划技术沙龙为广大大数据爱好者提供线下交流活动机会,技术沙龙第一期将于10月13日在深圳腾讯大厦举办,为您揭秘海量机器学习之道与A...

    腾讯技术工程官方号
  • OLAP 技术选型:对什么进行选型?

    上图展现的 impala 技术架构,很直观展示了 OLAP 技术核心模块:数据模型、存储格式与数据处理架构;

    zhisheng
  • 久等了,全新TDSQL-A,来了!

    5月18日,腾讯云发布首款分布式分析型数据库TDSQL-A,全力应对海量数据实时分析需求。 这是腾讯云数据库在品牌升级后的首次新品发布。经过多年发展,腾讯积...

    腾讯云数据库 TencentDB
  • 亚洲市值第一,我们全球招人!

    重要的事情说三遍,我们招人,招人,招人! 近期,腾讯云数据库TDSQL团队开放大量岗位机会,面向全球寻找未来同行的数据库工程师大牛。每一位加入的伙伴,都将可在...

    腾讯云数据库 TencentDB
  • 腾讯云TDSQL官宣:全球招人!

    ? 腾讯云TDSQL数据库团队招人了!近期,腾讯云TDSQL团队开放大量岗位机会,面向全球寻找未来同行的数据库工程师大牛。每一位加入的伙伴,都将可在这里获得广...

    腾讯技术工程官方号
  • 关于OLAP数仓,这大概是史上最全面的总结!(万字干货)

    关于数据仓库,早期分享过不少基础类文章,偶然间看到知乎上这篇关于OLAP的深度解读,从技术发展,产品选型,执行优化等方面做了详细的剖析,分享来给大家看看!

    大数据技术架构
  • 腾讯大数据星火计划技术沙龙 对外报名正式启动!

    导语:腾讯大数据举办星火计划技术沙龙为广大大数据爱好者提供线下交流活动机会,技术沙龙第一期将于10月13日在深圳腾讯大厦举办,为您揭秘海量机器学习之道与Ang...

    腾讯大讲堂
  • 浅谈大数据的过去、现在和未来

    相信身处于大数据领域的读者多少都能感受到,大数据技术的应用场景正在发生影响深远的变化: 随着实时计算、Kubernetes 的崛起和 HTAP、流批一体的大趋势...

    王知无-import_bigdata
  • 大数据OLAP系统(1)——概念篇

    OLAP(OnLine Analytical Processing),即联机分析处理。OLAP对业务数据执行多维分析,并提供复杂计算,趋势分析和复杂数据建模的能...

    Spark学习技巧
  • 5个MySQL与Postgre SQL非技术维度的区别

    MySQL流行较多,PostgreSQL功能更全面。其主要原因是,MySQL很早的时候,就支持主从复制,在互联网起步(2000年后第一次互联网大潮)的时候,被广...

    人工智能的秘密
  • 你需要的不是实时数仓 | 你需要的是一款强大的OLAP数据库(下)

    在上一章节《你需要的不是实时数仓 | 你需要的是一款强大的OLAP数据库(上)》,我们讲到实时数仓的建设,互联网大数据技术发展到今天,各个领域基本已经成熟,有各...

    王知无-import_bigdata
  • 为什么ClickHouse分析数据库这么强?(原理剖析+应用实践)

    2020年下半年在OLAP领域有一匹黑马以席卷之势进入大数据开发者的领域,它就是ClickHouse。在2019年小编也曾介绍过ClickHouse,大家可以参...

    PHP开发工程师

扫码关注云+社区

领取腾讯云代金券