StarRocks 技术内幕 | 基于全局字典的极速字符串查询-低调大师

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

2022-08-16 404

作者：冯浩桉，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 人，吸引几十家国内外行业头部企业参与共建。

微信关注我们

原文链接：https://my.oschina.net/u/5658056/blog/5566031

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

增强分析在百度统计的实践

导读：增强分析是近年来新兴起的一个方向，正成为数据和分析技术的主要趋势。本文结合作者实践经验，介绍了对于增强分析的理解和在实际工作中的展开点，包括基于自然语言的分析接口、核心功能的智能助手、业务洞察及建议，也希望在这个方向上能和大家有更多探讨。全文4209字，预计阅读时间11分钟。 01 什么是增强分析知名调研机构Gartner发布的2019年十大数据和分析技术趋势，着重提到了增强分析（「Augmented Analysis」）。其实早在2017年，Gartner就发表了题为「Augmented Analytics Is the Future of Data and Analytics」的报告。按照Gartner的定义「Augmented analytics is the use of enabling technologies such as machine learning and AI to assist with data preparation, insight generation and insight explanation to augment how peop...

2022-08-16

512

随着微服务体系在生产环境落地，也会伴随着一些问题出现，比如流量过大造成某个微服务应用程序的性能瓶颈、CPU利用率高、或内存泄漏等问题。要找到问题的根本原因，我们通常都会通过日志、进程再结合代码去判断根本原因。对于微服务庞大的业务，这必定会很耗时，而且也很难及时找到关键问题点。本文将介绍一个持续性能分析平台 Pyroscope，它能够帮助我们快速找到内存泄漏、CPU利用率高的代码。什么是 Pyroscope？ Pyroscope 是一个开源的持续性能分析平台。它能够帮你：查找代码中的性能问题解决 CPU 利用率高的问题定位并修复内存泄漏了解应用程序的调用树跟踪随时间的变化 Pyroscope 可以存储来自多个应用程序长期的分析数据；可以一次查看多年的数据或单独查看特定的事件；较低的 CPU 使用；数据压缩效率高，磁盘空间要求低；快捷的 UI 界面； Pyroscope 架构 Pyroscope 由两个主要组件支撑运行：Pyroscope Server 和 Pyroscope Agent。 Pyroscope Agent：记录并汇总您的应用程序一直在执行的操作，然后将该数据...

2022-08-16

414

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。