BITMAP 精准去重
本文介绍如何通过 Bitmap 类型实现精确去重。
Bitmap 是一种高效的位图索引技术，它通过 bit 位来表示对应的数据是否存在。Bitmap 特别适用于需要高效执行集合操作（如并集、交集等）的场景，并且在内存使用上非常节约。使用 Bitmap 进行精确去重相比 Count distinct 去重：
- 提高查询速度
- 减少内存/磁盘占用
Count Distinct 的实现
传统的精确去重依赖count distinct实现，表原始数据如下，假设要name列进行精确去重
| id | name |
|---|---|
| 1 | bob |
| 2 | alex |
| 3 | jack |
| 4 | tom |
| 5 | bob |
| 6 | alex |
Doris在计算时select count(distinct name) from t。会按照下图进行计算，先根据name列group by，计算一阶段去重，shuffle之后二阶段进行去重，最终计算count
Scan 1st Group By 2nd Group By Count
+---------------+ +------------+ +------------+ +------------+
| id | name | | name | | name | | count(name)|
+-----+---------+ +------------+ +------------+ +------------+
| 1 | bob | ---------------> | bob | | bob | -------> | 4 |
| 2 | alex | | alex | | alex | +------------+
| 5 | bob | +------------+ | jack |
| 6 | alex | | tom |
+---------------+ +------------+
---------------->
+---------------+ +------------+
| id | name | | name |
+-----+---------+ ---------------> +------------+
| 3 | jack | | jack |
| 4 | tom | | tom |
+-----+---------+ +------------+
由于Count Distinct需要保存计算明细数据，并且需要进行shuffle，当数据量增大时，查询也会越来越慢。用Bitmap来精确去重，可以解决count distinct 在大量数据场景下的性能问题。
使用场景
在实际的业务场景中，当数据达到一定规模之后，通过 count distinct 去重的成本也越来越高。查询也会越来越慢。而使用 Bitmap 精确去重，就是为了解决 count distinct 在大量数据场景下的性能问题。Bitmap 将对应明细数据映射为 bit 位，放弃了明细数据的灵活性下，大幅度提升计算效率。所以在如下场景可以考虑利用 Bitmap 进行精确去重：
- 查询加速：Bitmap 利用位运算进行查询计算，性能表现良好
- 压缩存储：由于将明细数据压缩为了一个 bit 位，Bitmap 类型无论在磁盘还是内存上，资源消耗都远远低于明细数据
但 Bitmap 只能对 TINYINT，SMALLINT，INT 和 BIGINT 类型的数据进行精确去重。如想要使用 Bitmap 对其他类型的数据精确去重，则需要额外构建全局字典。Doris使用了RoaringBitmap实现了Bimap的精确去重，原理和细节可以参考RoaringBitmap。
使用 BITMAP 进行精确去重
创建表
- 使用 Bitmap 去重的时候，需要在建表语句中将目标列类型设置成 Bitmap，聚合函数设置成 BITMAP_UNION
- Bitmap 类型的列不能作为 Key 列使用
创建一张聚合表 test_bitmap。其中id列表示访问用户的 ID，这里添加了uv列类型为 BITMAP，表示使用聚合函数 BITMAP_UNION 来聚合数据，
create table test_bitmap(
dt date,
id int,
name char(10),
province char(10),
os char(10),
uv bitmap bitmap_union
)
Aggregate KEY (dt,id,name,province,os)
distributed by hash(id) buckets 10;
导入数据
示例数据如下（test_bitmap.csv），可以通过 Stream Load导入。
2022-05-05,10001,测试 01,北京,windows
2022-05-05,10002,测试 01,北京,linux
2022-05-05,10003,测试 01,北京,macos
2022-05-05,10004,测试 01,河北,windows
2022-05-06,10001,测试 01,上海,windows
2022-05-06,10002,测试 01,上海,linux
2022-05-06,10003,测试 01,江苏,macos
2022-05-06,10004,测试 01,陕西,windows
Stream load 导入
curl --location-trusted -u root: -H "label:label_test_bitmap_load" \
-H "column_separator:," \
-H "columns:dt,id,name,province,os, uv=to_bitmap(id)" -T test_bitmap.csv http://fe_IP:8030/api/demo/test_bitmap/_stream_load
查询数据
Bitmap 列不允许直接查询原始值，只能通过 bitmap_union_count 的聚合函数进行查询。
求总的 UV
mysql> select bitmap_union_count(uv) from test_bitmap;
+---------------------+
| bitmap_union_count(`uv`) |
+---------------------+
| 4 |
+---------------------+
1 row in set (0.00 sec)
等价于：
mysql> SELECT COUNT(DISTINCT pv) FROM test_bitmap;
+----------------------+
| count(DISTINCT `uv`) |
+----------------------+
| 4 |
+----------------------+
1 row in set (0.01 sec)
求每一天的 UV
mysql> select bitmap_union_count(uv) from test_bitmap group by dt;
+---------------------+
| bitmap_union_count(`uv`) |
+---------------------+
| 4 |
| 4 |
+---------------------+
2 rows in set (0.01 sec)
