RoaringBitmap 诞生背景简介

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

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

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

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

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

OB RoaringBitmap 类型和函数

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

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);

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

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

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

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;

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)

更多阅读

• https://blog.bcmeng.com/post/doris-bitmap.html

• https://arxiv.org/pdf/1402.6407

• OB 4.3.2 JSON 列类型和索引使用体验

• OB 4.3.2 外部表使用体验

• OB 4.3 列存表使用体验