对大数据开发人员，海量数据的判重和基数统计是常用需求，RoaringBitmap 类型以及相关函数是目前很高效的一个解决方案。很多大数据库产品很早就支持 RoaringBitmap 类型，OceanBase 4.3.3 作为主打 OLAP 场景的正式版本（GA）也包含一功能。本文主要分享 RoaringBitmap 原理、场景和 OceanBase RoaringBitmap 的使用示例。

RoaringBitmap 诞生背景简介

海量数据的判重和基数统计需求，难度是数据量大且性能要尽可能好。技术方案的关键就是数据结构及其算法，数据结构也决定了其算法能力空间。

基础的数据结构就是常用的数据类型，如数值、字符串、时间等。假设要业务数据数值化存储，使用整型存储（无符号），其表达的值域是 [0, 2 32-1]，一共 4294967296 个数。如果记录不重复且记录数满配，单就这一列会占用存储空间16GB。这个判重方法有遍历、排序加二分查找、BloomFilter 等。

所以后来有些场景会用Bitmap（位图）存储这个数据，每个位（bit）对应一行记录的状态（0表示不存在，1表示存在）。如果记录不重复且记录数满配，这个位图结构最大存储空间是512MB。针对位图的判重效率就非常高。

Bitmap 结构下在海量数据（40亿+）的前提下，即使有大量数据重复也不会增加存储空间和降低判重效率。位图支持与运算（求交集）、或运算（求并集）。但是如果记录数不多且重复值很高的情况下（学术界称之为稀疏矩阵），Bitmap 存储就有点浪费内存空间（固定 512MB）。于是学术界有提出稀疏位图（或叫压缩位图）概念，Roaring Bitmap 就是稀疏位图的实现方案中目前认为最好的方案，并且已经被多个数据库产品支持。比如说 PostgreSQL 、AnalyticDB、PolarDB、Doris、ClickHouse、OceanBase （列举的不一定全）。

Roaring Bitmap 原理简介

32 位地址空间容量下的数据值如果全用 Bitmap 存储，碰到稀疏矩阵数据，为 0 的位会很多，很浪费存储空间。RoaringBitmap 对这个 32 位使用做了一些改进，分为高 16 位和低 16 位。高 16 位做为记录的索引 KEY，低 16 位作为记录的值 VALUE。所以高 16 位有多少不同的记录，就有多少个KEY，最多记录数 2 16个。有的文章也把每个记录称之位一个 HASH Bucket（桶），每个 Bucket 的大小就是低 16 位存储的记录数。

低 16 位的数据结构分为三类。如果记录数少于 4096 个，就使用 16 位的 Short Int 稀疏数组。名为数组，实际上是链表结构，以节省空间。如果记录数超过 4096 个，就开始使用 16 位的 Bitmap 存储。如果碰到连续的数据，则使用 Run Length Coding（简称 RLE）存储一个开始和结束的整型值。

1730177610

Roaring Bitmap （后简称 rb）也支持两个 rb 集合求并集、交集、差集、计算基数、排序等。这些操作是 SQL 运算逻辑的基础。

OB RoaringBitmap 类型和函数

OB 4.3.2 开始支持数据类型 roaringbitmap，以及相关函数。函数列表如下：

函数类型	函数名称	函数作用
位图构造函数	rb_build_empty	构建一个空的位图数据。值为 `0x0100`。
	rb_build_varbinary	Varbinary 为 OceanBase 私有格式，是由 version 信息、type 信息、data 等部分组成的二进制格式。
	rb_from_string	通过特定格式的字符串来构建位图数据。字符串格式为需要构建的位图数据的每一个元素，并通过逗号隔开，如 1,2,3,4。
位图基数计算函数	rb_cardinality	返回输入位图数据的基数。
	rb_and_cardinality rb_or_cardinality rb_andnot_cardinality	返回两个位图数据做与计算后，得到的新位图数据的基数。
	rb_and_null2empty_cardinality rb_or_null2empty_cardinality rb_andnot_null2empty_cardinality	返回两个位图数据做与计算后，得到的新位图数据的基数。
	rb_xor_cardinality	返回两个位图数据做与计算后，得到的新位图数据的基数。
位图运算函数	rb_and rb_and_null2empty	计算两个位图数据的交集。
	rb_or rb_or_null2empty	计算两个位图数据的并集。
	rb_xor	提供两个位图数据的异或运算。
	rb_andnot rb_andnot_null2empty	提供两个位图数据的与非运算。
位图判断函数	rb_is_empty	判断输入的位图数据是否为空。
位图输出函数	rb_to_varbinary	用于以 varbinary 的形式输出位图数据。
	rb_to_string	以字符串的形式依次输出位图数据的每一个元素，并以逗号隔开。其中元素的输出格式为 UINT64，输出的最大元素个数为 1000000。
位图聚合函数	rb_build_agg	将数值列聚合为位图数据。
	rb_or_agg	将位图列的多行数据进行或运算，并聚合为位图数据。
	rb_and_agg	将位图列的多行数据进行与运算，并聚合为位图数据。

OB Roaring Bitmap 示例

下面以用户行为分析在 OB 的例子来演示这一功能。

首先构造基础数据用户标签表。

-- 用户属性表：共有100万个用户，每个用户有64个属性 --create table t_user_tag (  uid int8,   tag int,        mod_time timestamp,    primary key (tag,uid)  ); DELIMITER //CREATE PROCEDURE insert_user_tag(IN min_uid BIGINT, IN max_uid BIGINT)BEGIN
    DECLARE uid BIGINT UNSIGNED;
    SET uid = min_uid;
    WHILE uid <= max_uid DO
        -- Loop to generate 64 random tags for each user
        INSERT IGNORE INTO t_user_tag        SELECT uid, mod( rand(unix_timestamp())*1000000,1999), current_timestamp() from table(generator(64));  
        SET uid = uid + 1; -- Move to the next UID
    END WHILE;END //DELIMITER ;call insert_user_tag(1,250000);call insert_user_tag(250001,500000);call insert_user_tag(500001,750000);call insert_user_tag(750001,1000000);

然后生成标签和用户对应索引表，使用 roaringbitmap 类型。

create table t_tag_userbit (  
  tag int primary key,            
  userbit roaringbitmap,
  mod_time timestamp);  insert /*+ enable_parallel_dml parallel(3) */ into t_tag_userbit 
select tag,rb_build_agg(uid),current_timestamp() from t_user_tag group by tag order by tag;

抽查几笔数据看看 roaringbitmap 类型的数据特征。

select * from t_tag_userbit where tag in (1,11,111,1111);

1730177638

这里看到的是 dbeaver 工具格式化后的结果，实际 rb 列是二进制数据。

1730177648

如果是在命令行 mysql或 obclient下，默认这个数据展示可能是乱码，可以在命令行下加一个参数 --binary-as-hex ，使用十六进制展示 binary 类型数据。

obclient -h127.1 -P2881  -uroot@obmysql -p test --binary-as-hex

下面是一些 roaringbitmap 类型相关的函数演示。

比如格式化显示和查看基数。

select tag, rb_to_string(userbit),rb_cardinality(userbit), mod_time 
from t_tag_userbit where tag in (1382, 1406,10257);

1730177665

计算同时满足两个 tag标签场景的的用户数。

select rb_cardinality(rb_and_agg(userbit)) from t_tag_userbit  where tag in (1990,1998) ;

更新标签用户索引表。

update t_tag_userbit set userbit = rb_or(userbit, rb_from_string('61,71,73,74,85')) where tag = 1998;

看一下 SQL 执行计划。

obclient [test]> explain select rb_cardinality(rb_and_agg(userbit)) from t_tag_userbit  where tag in (1002,1990,1998) ;+-----------------------------------------------------------------------------------------------------+| Query Plan                                                                                          |+-----------------------------------------------------------------------------------------------------+| ========================================================                                            || |ID|OPERATOR       |NAME         |EST.ROWS|EST.TIME(us)|                                            || --------------------------------------------------------                                            || |0 |SCALAR GROUP BY|             |1       |14          |                                            || |1 |└─TABLE GET    |t_tag_userbit|3       |14          |                                            || ========================================================                                            || Outputs & filters:                                                                                  || -------------------------------------                                                               ||   0 - output([rb_cardinality(T_FUN_SYS_RB_AND_AGG(t_tag_userbit.userbit))]), filter(nil), rowset=16 ||       group(nil), agg_func([T_FUN_SYS_RB_AND_AGG(t_tag_userbit.userbit)])                           ||   1 - output([t_tag_userbit.userbit]), filter(nil), rowset=16                                       ||       access([t_tag_userbit.userbit]), partitions(p0)                                               ||       is_index_back=false, is_global_index=false,                                                   ||       range_key([t_tag_userbit.tag]), range[1002 ; 1002], [1990 ; 1990], [1998 ; 1998],             ||       range_cond([t_tag_userbit.tag IN (1002, 1990, 1998)])                                         |+-----------------------------------------------------------------------------------------------------+15 rows in set (0.041 sec)

从执行计划看 SQL 引擎有跟 RB 有关的算子： T_FUN_SYS_RB_AND_AGG 。

ITPub博客

OB 4.3.3 AP 新功能体验：RoaringBitmaps 类型

RoaringBitmap 诞生背景简介

Roaring Bitmap 原理简介

OB RoaringBitmap 类型和函数

OB Roaring Bitmap 示例

最新文章