基于高效压缩位图Roaring Bitmap实现大规模标签筛选 - 云原生数据仓库AnalyticDB

Roaring Bitmap是一种高效的数据结构，与Bitmap相比，具备更高的处理性能且占用更少的内存空间。适合集合操作（交集、并集和差集）、去重等计算场景，常用于用户画像、个性化推荐、精准营销等业务场景。

背景信息

位图（BitMap）是一种常用的数据结构，位图为每个列所有可能的值创建一个单独的0和1的系列，每个位（bit）对应一个数据行是否存在对应的值。传统的位图会占用大量内存，一般需要对位图进行压缩处理。Roaring Bitmap是一种高效优秀的位图压缩算法，目前已被广泛应用在各语言和各大数据平台上。

Roaring Bitmap压缩算法简介

Roaring Bitmap数据结构是将32位整型（INT）数划分为高16位和低16位。其中，高16位被划分为多个数据块（Chunk），低16位使用一个容器（Container）来存放，因此每个数据块最多能够存储2^16个整数。Roaring Bitmap将这些容器保存在一个动态数组中，按照高16位进行排序，可以通过高16位二分查找快速定位对应的容器。根据数据特征，使用三种不同的容器进行存储：

数组容器（Array Container）：存储稀疏的数据，整数较为分散且不连续的情况。若容器里的最大数据小于4096，则使用数组容器来存储值。
位图容器（Bitmap Container）：存储稠密的数据，有很多连续的整数存在的情况。若容器里的最大数据大于等于4096，则使用位图容器来存储值。
运行容器（Run Container）：存储连续值较多的数据。Run Container只有在其存储空间大小同时小于Array Container和Bitmap Container时才会被使用。

采用这种存储结构，Roaring Bitmap极大地提高了数据的压缩率，并且可以快速检索一个特定的值。在做位图计算（AND，OR，XOR）时，Roaring Bitmap提供了相应的算法来高效地实现在三种容器之间的运算。使得Roaring Bitmap无论在存储和计算性能上都变得优秀。

更多关于Roaring Bitmap的介绍信息，请参见Roaring Bitmap官方网站。

注意事项

仅V6.3.8.9及以上版本支持使用Roaring Bitmap。如何查看实例内核版本，请参见查看内核小版本。

使用Roaring Bitmap位图计算

安装插件

使用Roaring Bitmap位图计算功能之前，您需要在云原生数据仓库 AnalyticDB PostgreSQL 版实例中插件管理中安装Roaring Bitmap插件。具体操作，请参见安装、升级与卸载插件。

创建表

创建带有Roaring Bitmap数据类型的表。

CREATE TABLE t1 (id integer, bitmap roaringbitmap);

插入数据

使用rb_build函数插入Roaring Bitmap的数据。

--数组位置对应的bit值为1。
INSERT INTO t1 SELECT 1,RB_BUILD(ARRAY[1,2,3,4,5,6,7,8,9,200]);
--将输入的多条记录的值对应位置的bit值设置为1，最后聚合为一个Roaring Bitmap。 
INSERT INTO t1 SELECT 2,RB_BUILD_AGG(e) FROM GENERATE_SERIES(1,100) e;

查询数据

从Roaring Bitmap中返回位置为1的bit下标（位置值）。

SELECT RB_ITERATE(bitmap) FROM t1 WHERE id = 1;

更多位图计算示例如下。

Bitmap计算（OR、AND、XOR、ANDNOT）。

SELECT RB_OR(a.bitmap,b.bitmap) FROM (SELECT bitmap FROM t1 WHERE id = 1) AS a,(SELECT bitmap FROM t1 WHERE id = 2) AS b;

Bitmap聚合计算（OR、AND、XOR、BUILD），并生成新的Roaring Bitmap类型。

SELECT RB_OR_AGG(bitmap) FROM t1;
SELECT RB_AND_AGG(bitmap) FROM t1;
SELECT RB_XOR_AGG(bitmap) FROM t1;
SELECT RB_BUILD_AGG(e) FROM GENERATE_SERIES(1,100) e;

统计基数（Cardinality），即统计Roaring Bitmap中包含多少个位置为1的bit位。
```
SELECT RB_CARDINALITY(bitmap) FROM t1;
```

Bitmap函数列表

函数名	输入	输出	描述	示例
rb_build	integer[]	roaringbitmap	通过数组创建一个Bitmap。	`rb_build('{1,2,3,4,5}')`
rb_and	roaringbitmap,roaringbitmap	roaringbitmap	And计算。	`rb_and(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_or	roaringbitmap,roaringbitmap	roaringbitmap	Or计算。	`rb_or(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_xor	roaringbitmap,roaringbitmap	roaringbitmap	Xor计算。	`rb_xor(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_andnot	roaringbitmap,roaringbitmap	roaringbitmap	AndNot计算。	`rb_andnot(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_cardinality	roaringbitmap	integer	统计基数。	`rb_cardinality(rb_build('{1,2,3,4,5}'))`
rb_and_cardinality	roaringbitmap,roaringbitmap	integer	And计算并返回基数。	`rb_and_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_or_cardinality	roaringbitmap,roaringbitmap	integer	Or计算并返回基数。	`rb_or_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_xor_cardinality	roaringbitmap,roaringbitmap	integer	Xor计算并返回基数。	`rb_xor_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_andnot_cardinality	roaringbitmap,roaringbitmap	integer	AndNot计算并返回基数。	`rb_andnot_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_is_empty	roaringbitmap	boolean	判断是否为空的Bitmap。	`rb_is_empty(rb_build('{1,2,3,4,5}'))`
rb_equals	roaringbitmap,roaringbitmap	boolean	判断两个Bitmap是否相等。	`rb_equals(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_intersect	roaringbitmap,roaringbitmap	boolean	判断两个Bitmap是否相交。	`rb_intersect(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_remove	roaringbitmap,integer	roaringbitmap	从Bitmap移除特定的Offset。	`rb_remove(rb_build('{1,2,3}'),3)`
rb_flip	roaringbitmap,integer	roraingbitmap	翻转Bitmap中特定的Offset。	`rb_flip(rb_build('{1,2,3}'),3)`
rb_flip	roaringbitmap,integer,integer	roaringbitmap	翻转Bitmap中特定的Offset段。	`rb_flip(rb_build('{1,2,3}'),2,3)`
rb_minimum	roaringbitmap	integer	返回Bitmap中最小的Offset，如果Bitmap为空则返回-1。	`rb_minimum(rb_build('{1,2,3}'))`
rb_maximum	roaringbitmap	integer	返回Bitmap中最大的Offset，如果Bitmap为空则返回0。	`rb_maximum(rb_build('{1,2,3}'))`
rb_rank	roaringbitmap,integer	integer	返回Bitmap中小于等于指定Offset的基数。	`rb_rank(rb_build('{1,2,3}'),3)`
rb_iterate	roaringbitmap	setof integer	返回Offset List。	`rb_iterate(rb_build('{1,2,3}'))`
rb_contains	roaringbitmap, integer	bool	判断Bitmap是否包含特定的Offset。	`rb_contains(rb_build('{1,2,3}'),1)`
rb_contains	roaringbitmap,integer,integer	bool	判断Bitmap是否包含特定的Offset段（某个范围）。	`rb_contains(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_contains	roaringbitmap, roaringbitmap	bool	判断Bitmap是否包含另外一个bitmap。	`rb_contains(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_becontained	integer, roaringbitmap	bool	判断特定的Offset是否被Bitmap包含。	`rb_becontained(1, rb_build('{1,2,3}'))`
rb_becontained	roaringbitmap,roaringbitmap	bool	判断Bitmap是否被另外一个包含。	`rb_becontained(rb_build('{1}'), rb_build('{1,2,3}'))`
rb_add	roaringbitmap, integer	roaringbitmap	添加特定的Offset到Bitmap。	`rb_add(rb_build('{1,2,3,4}'), 5)`
rb_add_2	integer, roaringbitmap	roaringbitmap	Add a specific offset to roaringbitmap.	`rb_add_2(5, rb_build('{1,2,3,4}'))`
rb_add	roaringbitmap,integer, integer	roaringbitmap	添加特定的Offset段到Bitmap。	`rb_add(rb_build('{1,2,3,4}'), 6,8)`
rb_remove	roaringbitmap,integer, integer	roaringbitmap	从Bitmap移除特定的Offset。	`rb_remove(rb_build('{1,2,3,4,6,7,8}'), 6,8)`
rb_jaccard_index	roaringbitmap,roaringbitmap	float8	计算两个Bitmap之间的jaccard相似系数。	`rb_jaccard_index(rb_build('{1,2,3,4}'), rb_build('{1,2}'))`
rb_to_array	roaringbitmap	integer[]	Bitmap转数组。	`rb_to_array(rb_build('{1,2,3,4}'))`
rb_iterate_decrement	roaringbitmap	integer[]	返回Offset List（从大到小）。	`rb_iterate_decrement(rb_build('{1,2,3,4}'))`

Bitmap聚合函数列表

聚合函数名	输入	输出	描述	示例
rb_build_agg	integer	roaringbitmap	将Offset聚合成Bitmap。	`rb_build_agg(1)`
rb_or_agg	roaringbitmap	roaringbitmap	Or聚合计算。	`rb_or_agg(rb_build('{1,2,3}'))`
rb_and_agg	roaringbitmap	roaringbitmap	And聚合计算。	`rb_and_agg(rb_build('{1,2,3}'))`
rb_xor_agg	roaringbitmap	roaringbitmap	Xor聚合计算。	`rb_xor_agg(rb_build('{1,2,3}'))`
rb_or_cardinality_agg	roaringbitmap	integer	Or聚合计算并返回其基数。	`rb_or_cardinality_agg(rb_build('{1,2,3}'))`
rb_and_cardinality_agg	roaringbitmap	integer	And聚合计算并返回其基数。	`rb_and_cardinality_agg(rb_build('{1,2,3}'))`
rb_xor_cardinality_agg	roaringbitmap	integer	Xor聚合计算并返回其基数。	`rb_xor_cardinality_agg(rb_build('{1,2,3}'))`

操作符

操作符	left	right	output	描述	示例
&	roaringbitmap	roaringbitmap	roaringbitmap	两个Bitmap And操作。	`rb_build('{1,2,3}') & rb_build('{1,2,4}')`
\|	roaringbitmap	roaringbitmap	roaringbitmap	两个Bitmap Or操作。	`rb_build('{1,2}') \| rb_build('{1,3}')`
#	roaringbitmap	roaringbitmap	roaringbitmap	两个Bitmap Xor操作。	`rb_build('{1,2}') # rb_build('{1,3}')`
~	roaringbitmap	roaringbitmap	roaringbitmap	两个Bitmap Andnot操作。	`rb_build('{2,3}') ~ rb_build('{2,4}')`
+	roraingbitmap	integer	roaringbitmap	向Bitmap中添加特定的Offset。	`rb_build('{2,3}') + 1`
-	roraingbitmap	integer	roaringbitmap	从Bitmap移除特定的Offset。	`rb_build('{1,2,3}') - 1`
=	roaringbitmap	roaringbitmap	boolean	判断两个Bitmap是否相等。	`rb_build('{2,3}') = rb_build('{2,3}')`
<>	roaringbitmap	roaringbitmap	boolean	判断两个Bitmap是否不相等。	`rb_build('{2,3}') <> rb_build('{1,2,3}')`
&&	roaringbitmap	roaringbitmap	boolean	判断两个Bitmap是否相交。	`rb_build('{2,3}') && rb_build('{3,4}')`
@>	roaringbitmap	roaringbitmap	boolean	判断Bitmap是否包含另外一个。	`rb_build('{2,3}') @> rb_build('{2}')`
@>	roaringbitmap	integer	boolean	判断Bitmap是否包含特定的Offset。	`rb_build('{2,3}') @> 2`
<@	roaringbitmap	roaringbitmap	boolean	判断Bitmap是否被另外一个包含。	`rb_build('{2,3}') <@ rb_build('{1,2,3}')`
<@	integer	roaringbitmap	boolean	判断特定的Offset是否被Bitmap包含。	`rb_build('{2,3}') <@ rb_build('{3}')`