关于数据库:StarRocks-技术内幕-基于全局字典的极速字符串查询

43次阅读

共计 7209 个字符，预计需要花费 19 分钟才能阅读完成。

作者：冯浩桉，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，当基数存在变动，比方基数变高后，不不便保护
  • 无奈晋升曾经运行的零碎的性能，必须得重建表并且从新导入数据后能力应用。
  1. 导入时候构建全局字典 

导入数据时，通过核心节点保护全局字典。每次遇到新的的字符都要通过核心节点创立一个新的字典码。然而这么做的次要问题是核心节点很容易会成为瓶颈。另外核心节点因为须要同时解决保护并发管制。

因为保护和构建字典对于很多零碎来说都是一个比拟艰难的事件，因而很多零碎，只是在部分应用了部分字典来进行减速，并不反对字典的全局减速。

 

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 人，吸引几十家国内外行业头部企业参加共建。

正文完
数据库
发表至： 数据库
2022-08-16
 0
关于数据库:MySQL笔记八之SELECT之LIKE模糊查找
关于数据库:Nebula-Graph-源码解读系列｜客户端的通信秘密fbthrift
关于数据库:StarRocks-Contributor-人数破百极速统一你我协力
关于数据库:PingCAP-唐刘一个咨询顾问对-TiDB-Chat2Query-Demo-提出的脑洞