第6.7章：StarRocks查询加速——使用 Bitmap 实现精确去重

一、Bitmap 原理

1.1 传统 Count distinct

StarRocks是基于MPP结构实现的，在使用 count distinct 做精准去重时候，可以保留明细数据，灵活性较高。但是由于在查询执行的过程中需要进行多次数据 shuffle（不同节点间传输数据，计算去重），会导致性能随着数据量增大而直线下降。

** 比如，要通过以下明细数据计算表（dt, page, user_id）每个页面的 UV。**
dtpageuser_id20191206game10120191206shopping10220191206game10120191206shopping10120191206game10120191206shopping101
StarRocks 在计算时，会按照下图进行计算，先根据 page 列和 user_id 列 group by，最后再 count。

由于数据需要进行多次 shuffle，当数据量越来越大时，所需的计算资源就会越来越多，查询也会越来越慢。

select page, count(distinct user_id) as uv from table group by page;

|  page      |   uv  |
| :---:      | :---: |
|  game      |  1    |
|  shopping  |   2   |

1.2 Bitmap 去重的优势

与传统 count distinct方式相比，Bitmap 的优势主要体现在以下两点 ：

1. 节省存储空间：通过用 Bitmap（位图） 的一个 Bit 位表示对应下标是否存在，能节省大量存储空间。StarRocks 采用一种设计的十分精巧的 bitmap，叫做 Roaring Bitmap（压缩位图），相较 Bitmap 会进一步减少内存占用。
2. 加速计算：Bitmap 去重使用的是位运算，所以计算速度相较 COUNT(DISTINCT expr) 更快，而且 bitmap 去重在 StarRocks MPP 执行引擎中还可以并行加速处理，提高计算速度。

1.3 Bitmap使用说明

1. Bitmap index 和 Bitmap 去重二者虽然都使用 Bitmap 技术，但引入原因和解决的问题完全不同。前者用于低基数的枚举型列的等值条件过滤（位图索引），后者则用于计算一组数据行的指标列的不重复元素的个数。（位图）
2. 建表时，指定指标列类型为 BITMAP，使用 BITMAP_UNION 函数进行聚合。
3. StarRocks 的 bitmap 去重是基于 Roaring Bitmap （压缩位图）实现的，roaring bitmap 只能对 TINYINT，SMALLINT，INT 和 BIGINT 类型的数据去重。如想要使用 Roaring Bitmap 对其他类型（例如：String类型）的数据去重，则需要构建全局字典。

1.4 Bitmap 去重示例

以统计某一个页面的独立访客人数（UV）为例：

（1）创建一张聚合表

page_uv

。其中**

visit_users

列表示访问用户的 ID，为聚合列，列类型为 BITMAP，使用聚合函数 BITMAP_UNION 来聚合数据。**

CREATE TABLE `page_uv` (
  `page_id` INT NOT NULL COMMENT '页面id',
  `visit_date` datetime NOT NULL COMMENT '访问时间',
  `visit_users` BITMAP BITMAP_UNION NOT NULL COMMENT '访问用户id'
) ENGINE=OLAP
AGGREGATE KEY(`page_id`, `visit_date`)
DISTRIBUTED BY HASH(`page_id`)
PROPERTIES (
  "replication_num" = "3",
  "storage_format" = "DEFAULT"
);

（2）向表中导入数据，采用 INSERT INTO 语句导入：

INSERT INTO page_uv VALUES
(1, '2020-06-23 01:30:30', to_bitmap(13)),
(1, '2020-06-23 01:30:30', to_bitmap(23)),
(1, '2020-06-23 01:30:30', to_bitmap(33)),
(1, '2020-06-23 02:30:30', to_bitmap(13)),
(2, '2020-06-23 01:30:30', to_bitmap(23));

（3）统计每个页面的 UV。

select page_id, count(distinct visit_users) from page_uv group by page_id;

+-----------+------------------------------+
|  page_id  | count(DISTINCT `visit_users`) |
+-----------+------------------------------+
|         1 |                            3 |
+-----------+------------------------------+
|         2 |                            1 |
+-----------+------------------------------+
2 row in set (0.00 sec)

1.5 Bitmap 全局字典

由于基于 Bitmap 类型的去重机制有一定限制（StarRocks-3.2版本），即 Bitmap 需要使用整数型类型作为输入。如用户期望将其他数据类型作为 Bitmap 的输入，则需要构建全局字典，将其他类型数据（如字符串类型）通过全局字典映射成为整数类型。

二、企业实践经验

2.1 Starrocks & Bitmap介绍

Starrocks是一个分布式列式存储和分析系统，旨在处理大规模数据集。Bitmap（位图）是Starrocks数据库中一种用于高效存储和处理大规模数据的压缩数据结构。在StarRocks中，Bitmap 通常用于解决多维度数据的过滤和聚合问题。通过使用针对位图的位运算，从而提供了高性能的筛选和聚合操作。Bitmap可以理解为一个由位组成的二进制向量，其中每个位对应于一条数据记录的某个属性。使用Bitmap进行数据过滤和聚合操作时，可以通过位运算（如并、交、异或）高效的对数据进行筛选和组合。位图压缩技术还可以减少存储空间的使用，提高查询性能。
在Starrocks中，Bitmap常用于处理大规模数据的快速过滤、数据预聚合和多维度分析等场景，可以大大提高数据处理的效率和性能。

2.2 Bitmap在用户人群的优势

  用户人群普遍推荐使用 Bitmap（位图）的原因是因为 Bitmap 能够有效地解决某些数据处理问题，具有以下优点：

（1）节省存储空间：Bitmap 使用位的方式表示数据集中的存在与否，比如在大规模数据集中，标记一个用户是否满足某个条件，而不需要存储实际的数据内容，从而节省了存储空间。

（2）快速过滤：Bitmap 可以在常量时间内（O(1)）进行数据过滤操作，即可以快速确定某个用户是否满足某个条件，例如判断某个用户是否属于某个特定年龄段或者某个地理区域。

（3）快速计算交集和并集：Bitmap 可以高效地进行交集和并集操作，即可将两个或多个 Bitmap 进行逻辑运算，从而得到包含满足整体条件的用户集合。这对于倒排索引、数据集合的合并等场景非常有用。

（4）简单高效：Bitmap 算法实现简单，具有高效的计算性能和查询速度。

** 缺陷：Bitmap 适用于处理稀疏数据，如果数据比较密集或者范围较大，可能会导致 Bitmap 的存储和计算开销过大**。因此，在应用 Bitmap 时需要根据具体情况进行评估和选择合适的算法和数据结构。
总结来说，用户人群推荐使用 Bitmap 是因为它可以在存储和计算效率上提供优势，并且适用于处理稀疏数据的情况。

2.3 设计方案

2.4 数据流

  目前版本主要还是以离线的方式为业务提供数据，在离线数仓完成用户画像标签与用户行为日志，然后将数据同步到Starrocks完成Bitmap的转化。

2.4.1 Hive的用户画像表（user_profile）

CREATE EXTERNAL TABLE IF NOT EXISTS  user_profile
(uid string  COMMENT '用户id' ,
appId bigint  COMMENT 'app id' ,
tag1 string  COMMENT '标签1' ,
tag2 bigint  COMMENT '标签2' ,
tag3 decimal(38,4)  COMMENT '标签3' ,
......
tag198 string  COMMENT '标签198' ,
tag199 bigint  COMMENT '标签199' ,
tag200 decimal(38,4)  COMMENT '标签200'
) 
COMMENT '商业版c端用户画像应用表'
PARTITIONED BY ( 
 `dt` string  COMMENT '按天分区'  
) 

2.4.2 Hive的用户行为标签表（user_action_tags）

CREATE EXTERNAL TABLE IF NOT EXISTS  user_profile
(uid string  COMMENT '用户id' ,
appId bigint  COMMENT 'app id' ,
eventCode string  COMMENT '用户行为事件' ,
tagType string  COMMENT '标签类型' ,
tagValue string  COMMENT '标签值' 
) 
COMMENT '商业版c端用户画像应用表'
PARTITIONED BY ( 
`dt` string  COMMENT '按天分区'  
) 

2.4.3 Starrocks的用户画像标签unnest类表

CREATE TABLE `user_profile_unnest_{dataType}` (
  `u_id` bigint(20) not NULL COMMENT '用户自增id主键',
  `tag_type` varchar(50) not NULL DEFAULT '' COMMENT '标签名',
  `tag_value` BIGINT not NULL DEFAULT '0' COMMENT '标签值-字段类型与dataType 保持一致',
) ENGINE=OLAP 

2.4.4 Starrocks的用户画像标签bitmap类表

CREATE TABLE `bitmap_user_profile_{dataType}` (
  `dt` int(11) not NULL COMMENT '日期分区',
  `tag_type` varchar(50) not NULL DEFAULT '' COMMENT '标签名',
  `tag_value` BIGINT not NULL DEFAULT '0' COMMENT '标签值-字段类型与dataType 保持一致',
  `uid_bitmap` bitmap NOT NULL COMMENT 'uid bitmap'
) ENGINE=OLAP 

2.4.5 Starrocks的用户行为标签unnest表

CREATE TABLE `user_action_unnest` (
  `dt` int(11) not NULL COMMENT '日期分区',
  `u_id` bigint(20) not NULL COMMENT '用户自增id主键',
  `app_id` bigint(20) not NULL COMMENT 'appid',
  `event_code` bigint(20) not NULL COMMENT '行为事件编码',
  `tag_key` varchar(50) not NULL COMMENT '',
  `tag_value` string NULL COMMENT ''
) ENGINE=OLAP 

2.4.6 Starrocks的用户行为标签bitmap表

CREATE TABLE `bitmap_user_action` (
  `dt` int(11) not NULL COMMENT '日期分区',
  `app_id` bigint(20) not NULL COMMENT 'appid',
  `event_code` bigint(20) not NULL COMMENT '行为事件编码',
  `tag_type` varchar(50) not NULL DEFAULT '' COMMENT '标签名',
  `tag_value` BIGINT not NULL DEFAULT '0' COMMENT '标签值',
  `uid_bitmap` bitmap NOT NULL COMMENT 'uid bitmap'
) ENGINE=OLAP 

 用户画像标签在做Bitmap转化的过程中会根据标签值的数据类型进行拆分，当下仅使用字符串（String）、整型（Bigint）、精度类型（Decimal）。行为标签是根据日志埋点平台定义的参数，日志以Json格式存储，当前仅使用字符串类型。因业务平台支持导入第三方用户进行营销，所以基于uid的自增id的过程放在了Starrocks端，行为日志仅支持内部APP用户，离线数仓处理完Unnest表后，直接同步到Starrocks端，关联uid_mapping获取u_id。

2.5 Bitmap 常用函数介绍

 更多函数见官网：函数列表 | StarRocks

函数功能bitmap_agg将一列中的多行非 NULL 数值合并成一行 BITMAP 值，即多行转一行。bitmap_and计算两个 bitmap 的交集，返回新的 bitmap。bitmap_andnot计算两个输入的 bitmap 的差集。bitmap_count统计 bitmap 中不重复值的个数。bitmap_intersect求一组 bitmap 值的交集。bitmap_or计算两个 bitmap 的并集，返回新的 bitmap。bitmap_union求一组 bitmap 值的并集。bitmap_union_count计算一组 bitmap 值的并集，并返回并集的基数。to_bitmap将输入值转换为 bitmap。

2.6 宽表 VS Bitmap

参考文章：

直播实录 | 37 手游如何用 StarRocks 实现用户画像分析 - 墨天轮

Starrocks的Bitmap在用户人群中的应用_starrocks bitmap-CSDN博客

使用 Bitmap 实现精确去重 | StarRocks