写点什么

StarRocks 技术内幕 | 基于全局字典的极速字符串查询

作者:StarRocks
  • 2022 年 8 月 16 日
    北京
  • 本文字数:6054 字

    阅读完需:约 20 分钟

StarRocks 技术内幕 | 基于全局字典的极速字符串查询

作者:冯浩桉,StarRocks 核心研发工程师,StarRocks Committer

在数据库和存储系统中,String 类型数据广泛存在。为了提升 String 的处理效率和节省存储资源,出现了很多针对 String 类型进行优化的技术手段,例如提升处理效率的各类字典应用,提升存储效率的字典编码压缩技术。

本文主要针对 StarRocks 基于全局字典做的低基数 String 查询优化,揭秘其技术内幕。


#01

为什么要引入低基数字典优化

我们先看下两个 SQL 的对比,表 Lineorder 是 SSB100G 数据集,lo_shippriority 为低基数 int 列,l_shipmode 为低基数 String 列



mysql> select count(cnt) from ( select count(*) cnt from lineorder group by lo_shippriority) tb;+------------+| count(cnt) |+------------+| 1 |+------------+1 row in set (3.51 sec)
mysql> select count(cnt) from ( select count(*) cnt from lineorder group by lo_shipmode) tb;+------------+| count(cnt) |+------------+| 7 |+------------+1 row in set (9.33 sec)
复制代码


可以看到,处理相同数据量的情况下,String 类型的处理时间差不多是 int 类型的 3 倍。

如果能使用整数类型来替代 String 类型进行数据处理,能够显著提升系统的性能!

对于利用整型替代字符串进行处理,通常是使用字典编码进行优化。一个 SQL 从输入到输出结果,往往会经过这几个步骤,几乎每一个阶段都可以使用字典优化:Scan,Filter,Agg,Join,Shuffle,Sort。

以 Filter 和 Agg 为例:

  • Filter (过滤操作)


对于 Filter 阶段来说,如果某一个列是用字典编码的,我们就可以直接使用编码之后的整数进行比较,而不是直接用 String 进行比较操作。大多数情况下,整数之间的 Compare 性能会高于字符串之间的性能。

  • Agg (聚合操作)

对于 Agg 操作,如果使用了字典编码,我们在聚合中可以使用编码之后的值作为聚合的 Key。如此一来,在聚合操作的 Hash 表构建和查找过程中,可以减少 Hash 表中 Key 的比较代价,同时也能够加快 Hash 值计算,节省内存空间,可以提升聚合操作的速度。

因此如果我们使用字典的编码方式把字符串转变成整型,在 SQL 执行的很多阶段,都可以起到正向加速的效果。

使用整型来替代 String 类型进行加速计算,业界通常使用的手段是使用字典优化。但是对于一个复杂系统来说,想要充分利用字典优化,并不是一件容易的事情。


#02

为什么需要全局字典

在一个分布式执行引擎中,一个 SQL 的执行过程是复杂的。一个查询会存在多个执行阶段,可能会涉及到多个机器多个任务之间的数据交换。如果想充分利用字典优化,那么需要考虑很多的情况:

  • 在执行过程中,字典要保证全局性。也就是说在不同的节点之间同样需要维护一个字典。字典数据始终贯穿 SQL 执行的整个生命周期,如果不是全局字典,那么加速只能在局部进行。例如如果两个执行节点的字典编码不一致,那么在网络传输过程中需要同时把字典传给对端机器,或者是需要提前把字典码转为字符串再通过网络发送。如果能保证一个字典的全局性,在网络传输中就可以直接使用字典码而不再需要传输字典。

  • 查询规划器规划出使用全局字典最高效的方式,如果一个 SQL 在执行过程中没有网络 Shuffle,也不存在潜在应用字典优化的操作,那么不再采用字典优化。例如`insert into t1 select * from t2;` 这样的 SQL,中间既不存在数据网络 Shuffle,也不存在可能会应用到低基数优化的算子。那么这样的 SQL 就不适合使用低基数优化。

对于一个复杂的、支持实时数据更新的分布式数据库,做到以上两点,并不容易。所以很多的分布式系统,只是用了字典来做局部加速,并没有做全局加速。



#03

如何高效构建全局字典

为了充分利用字典加速,首先需要解决的问题就是全局字典构建和维护问题。


1、通常的分布式字典构建方式

对于很多系统来说,通常构建全局字典的方式有两种:

1. 用户指定 Schema,用户在建表的时候,指定对应的列为低基数列

因为用户指定了低基数,那么可以在数据导入的时候,构建全局字典,因为知道了基数范围,全局字典很好维护,按着特定的规则去生成就好了,存储的代价也不高。 

但是这么做,主要存在的问题在于: 

  • 对用户不友好,需要用户指定 Schema,当基数存在变化,比如基数变高后,不方便维护

  • 无法提升已经运行的系统的性能,必须得重建表并且重新导入数据后才能使用。 

2. 导入时候构建全局字典 

导入数据时,通过中心节点维护全局字典。每次遇到新的的字符都要通过中心节点创建一个新的字典码。但是这么做的主要问题是中心节点很容易会成为瓶颈。另外中心节点因为需要同时处理维护并发控制。

因为维护和构建字典对于很多系统来说都是一个比较困难的事情,因此很多系统,只是在局部使用了局部字典来进行加速,并不支持字典的全局加速。


2、StarRocks 全局字典的构建


对于 StarRocks 的全局字典的构建,主要有以下考虑:

  • 自适应,不需要用户通过 Schema 指定特定低基数列,而是根据数据特性,自动选择优化策略。

  • 尽可能避免单点问题,比如数据导入的时候遇到新的字符串,先通过中心节点更新全局字典。

数据存储上的字典优化 

首先先来看下 StarRocks 的数据存储的结构。

StarRocks 的基本存储单元为 Segment,每个 Segment 的存储结构如下图所示:



StarRocks 的存储结构天然为低基数字符串做了字典编码。对于 Segment 上的低基数字符串列会有以下特点:

  • Footer 上会存储有这个 Column 特有的字典信息,包括字典码跟原始字符串之间的映射关系;

  • Data page 上存储的不是原始字符串,而是整数类型的字典码(整型)。

简单的示意图如下:



当处理低基数 String column 的时候,直接使用编码后的字典码,而不是直接处理原始的 String 值。当需要原始的 String 值时,使用字典码就可以很方便地在这个列的字典信息里面拿到原始 String 值。这么做带来的明显好处是:

  • 减少了磁盘 IO。

  • 可以提前做一些过滤操作,提升处理速度。

全局字典的构建

StarRocks 支持 CBO 优化器,并且存在一套统计信息机制,那么就可以通过统计信息来收集全局字典。我们通过统计信息,筛选出潜在的低基数列,再从潜在的低基数列的元数据中读取字典信息,然后做去重/编码操作,就可以收集到全量的字典了。

全局字典的正确性保证

对于低基数列来说,那么肯定会出现一种情况,在某次导入中导入了新的 String (这个 String 不在全局字典的集合内),那么这个时候,原先已经构建的全局字典就没有办法包含所有的字符串的值。因此 StarRocks 需要维护全局字典的有效性。

全局字典可能失效只会出现在导入, StarRocks 支持了很多类型的数据导入方式,而所有的导入都有两个共同点

  • 导入产生新的 Segment。

  • 通过 Master FE 提交事务。

对于低基数列,所有 Segment 中都必定存在局部字典信息,那么对于一个新的导入,在产生新的 Segment 时,会有几种情况。

  • 如果新生成的 Segment 没有了局部字典,那么说明这个列很可能是一个高基数列,此时不再适合全局字典优化;

  • 新生成的 Segment 有局部字典,而且局部字典中的所有 String 是全局字典的子集,这种情况下可以直接使用旧的字典;

  • 新生成的 Segment 有局部字典,而且局部字典所有的 String 值,部分不在全局字典里,此时全局字典失效已经生效,需要重新生成全局字典。

无论出现了上面的哪种情况,在向 FE 中心节点提交的时候,带上这个对应的信息,我们就都能保证全局字典的正确性。

因为每次导入都是产生新的版本,而查询是支持 MVCC 的,每次查询都会带有一个固定的查询版本号。在某一时刻中,如果出现一个新的版本数据,那么对这个版本出现之前的所有查询都是不可见的。因此我们查询中如果有新的导入,那么已发起的查询也是不受影响的。


#04

如何高效使用全局字典

1、CBO 优化器的紧密配合

对于一个简单的聚合 SQL 来说,其执行过程如下:


因为 StarRocks 是个分布式系统,其数据分散在多个后端 BE 实例上,且存在多个副本。Segment 内的字典是一个局部的字典,不能作为全局字典码使用。

对于一个没有使用全局字典优化的 SQL,在 SCAN NODE 扫描 Segment 数据的过程中就需要将对应把局部的字典码(int)解码成原始的 String 返回给上层节点。

如果使用了全局字典优化,我们就不需要 SCAN NODE 节点就进行 Decoded,而是可以将原先的局部字典码(int),直接映射到全局字典中的字典码(int),并在之后的计算处理过程中,均使用全局字典码进行处理。当遇到某些特殊的算子,或者是需要具体的依赖字符串内部信息的时候,再按着全局字典的信息,Decoded 出原始的 String 值,这样可以充分利用到全局字典的加速。

下图展示了 SCAN NODE 使用全局字典后,向上传递的数据使用了 int 编码:


既然我们已经有了全局字典,那么接下来的问题就是更高效地使用好全局字典。 

当存在全局字典的时候,所需要做的比较关键的就是:

  • 将对 String 的操作转化为对 int 的操作时 ,从而提升处理的速度,节省对应的资源。

  • 当遇到无法使用 int 替代 String 的操作时,需要提前将字典码 Decoded 成 String。

举个例子:

lineitem 表中的 l_shipmode 是低基数 String 列

select count(*) from lineitem group by l_shipmode;
复制代码


对于这个 SQL 来说,我们需要的只是聚合之后的行数,因此在整个 SQL 的执行过程中,都可以使用 int 来替代 String 进行处理,并不需要进行 Decoded。



select count(*), l_shipmode from lineitem group by l_shipmode;
复制代码


而对于这个 SQL,需要的不仅仅是聚合后的结果数,还有对应的字符串值。在这里我们需要在结果输出之前,进行 Decoded,将 int 值翻译成 String。

对于第二条 SQL 来说,其执行过程如下所示:



可以看到第二条 SQL 多了个 Decode 节点。

对于低基数 String 列来说,聚合后的行数并不多,这个 Decode 的成本基本可以忽略不计,反而在之前的处理,使用 int 替代 String 所带来的提升是巨大的。

那么,对于查询规划器来说,要做的就是选择最合适的 Decode 时期,最大限度地提升性能。

 select * from lineitem;
复制代码


对于上面的 SQL 来说,使用全局字典,反而会带来额外的解码的开销。对于这样的 SQL,我们的 CBO 优化器需要正确规划,并且不会使用字典。


2、全局字典的字符串函数优化

上面的 SQL 都是简单的例子。如果稍微对 SQL 进行一些改动,比如:

select count(*), l_shipmode from lineitem group by substr(l_shipmode, 1, 3);
复制代码


在这个 SQL 中,需要对 String 列进行 substr 运算,并且按着运算后的值进行聚合,这么一看,那肯定是需要在聚合前,插入一个 Decode 节点来把字典码转为具体的字符串值了,甚至在扫描数据的时候,就需要原始的 String 列了。

对于这条 SQL 来说,使用 int 值替代 String 来进行聚合,所带来的提升是巨大的,我们应该发挥全局字典的最大价值。

对于大多数的字符串函数来说,他们的计算往往有下面的一些特点:

  • 对于固定的输入,输出也是固定,最简单的比如 substring 函数, substring("abc", 1, 2) 的结果一定是 "AB";

  • 大部分 String 操作,都符合上面的定义。

既然对于单个 String 的运算,输出是固定的,那么对于固定集合的 String 的运算,其结果集合也一定是固定的,比如对 {"s1", "s2", "s11" } 进行 substring(str, 1, 2) 运算,其结果也一定是 {"s1", "s2", "s11" }。

很明显,当有了低基数全局字典,全局字典里面的 String 取值,就是固定的集合。因此,我们将对单个 String 的操作,转化为对 String 集合的操作,而这个操作,在 SQL 执行的过程中,只需要执行一次。

以上面的 substr  SQL 为例子,当低基数列 l_shipmode 存在全局字典时,我们运用 substr 对全局字典进行计算,计算的示意图如下:


对于上图所示的全局字典来说,substring("hello", 1, 2) 和 substring("world", 1, 3)产生的结果集是 {"he", "wo"}。我们会把所有的输出都加入到一个新的字典中,与此同时,我们还得到了两个字典之间的转换关系。

例如字典码 1 的输入在经过这个函数之后会变成新字典的字典码 1。

有了这个映射关系,对输入的数据,进行 substring 操作,那就很简单了,因为我们输入的数据是全局字典码,并不是原始的 String,我们只需要按着 substring 中两个字典之间的转换关系,将对应的字典码通过映射输出成对应的新字典码,就完成了相关函数的计算。



对于这类的字符串函数,并不需要进行 Decode 获取原始 String 来调用函数处理,而且这种映射的方法,对于直接使用字符串进行计算也有一定的性能提升,尤其是对复杂的表达式。


#05

优化效果

我们选取了几组典型的 SQL,对比了开启低基数下的性能。

StarRocks 2.0+后的版本默认会开启低基数字典优化:


set cbo_enable_low_cardinality_optimize = true;
复制代码


对比 SQL:


select count(*),lo_shipmode from lineorder group by lo_shipmode;select count(distinct lo_shipmode) from lineorder;select count(*),lo_shipmode,lo_orderpriority from lineorder group by lo_shipmode,lo_orderpriority;select count(*),lo_shipmode,lo_orderpriority from lineorder group by lo_shipmode,lo_orderpriority,lo_shippriority;select count(*) from (select count(*) from lineorder_flat group by lo_shipmode,lo_orderpriority,p_category,s_nation,c_nation) t;select count(*) from (select count(*) from lineorder_flat group by lo_shipmode,lo_orderpriority,p_category,s_nation,c_nation,p_mfgr) t;select count(*) from (select count(*) from lineorder_flat group by substr(lo_shipmode,2),lower(lo_orderpriority),p_category,s_nation,c_nation,s_region,p_mfgr) t;select count(*),lo_shipmode,s_city from lineorder_flat group by lo_shipmode,s_city;select count(*) from lineorder_flat group by c_city,s_city;select count(*) from lineorder_flat group by c_city,s_city,c_nation,s_nation;select count(*) from lineorder_flat group by lo_shipmode,lo_orderdate;select count(*) from lineorder_flat group by lo_orderdate,s_nation,s_region;
复制代码


对比结果:



从效果上来看,开启低基数优化的 SQL 比没开启低基数优化的 SQL 平均快了 3 倍。


#06

总结

StarRocks 的低基数 String 优化,主要的特点有:

  • 全局的字典加速,作用于 SQL 执行的各个阶段。

  • 基于 CBO 优化器的,自适应选择全局字典的加速策略。

  • 无 Schema,自适应,用户不需要指定特定的低基数列。

  • 对用户透明,不需要重新导数据。

  • 高性能,业界领先水平。

  • 支持场景丰富,兼容大部分 String 处理逻辑。


关于 StarRocks 

StarRocks 创立两年多来,一直专注打造世界顶级的新一代极速全场景 MPP 数据库,帮助企业建立“极速统一”的数据分析新范式,助力企业全面数字化经营。

当前已经帮助腾讯、携程、顺丰、Airbnb 、滴滴、京东、众安保险等超过 110 家大型用户构建了全新的数据分析能力,生产环境中稳定运行的 StarRocks 服务器数目达数千台。 

2021 年 9 月,StarRocks 源代码开放,在 Github 上的星数已超过 3100 个。StarRocks 的全球社区飞速成长,至今已有超百位贡献者,社群用户突破 5000 人,吸引几十家国内外行业头部企业参与共建。



用户头像

StarRocks

关注

新一代极速全场景MPP数据库 2020.08.08 加入

StarRocks一直致力于打造世界顶级的新一代极速全场景MPP数据库,帮助企业建立“极速统一”的数据分析新范式,助力企业数字化经营。当前已帮助腾讯、携程、顺丰、Airbnb等超过110家大型用户构建全新的数据分析能力。

评论

发布
暂无评论
StarRocks 技术内幕 | 基于全局字典的极速字符串查询_数据库_StarRocks_InfoQ写作社区