RoaringBitmap函数

背景信息

RoaringBitmap是一种高效的Bitmap压缩算法，目前已被广泛应用在各种语言和各种大数据平台。适合计算超高基维的，常用于去重、标签筛选、时间序列等计算中。

RoaringBitmap算法是将32位的INT类型数据划分为2¹⁶个数据块（Chunk），每一个数据块对应整数的高16位，并使用一个容器（Container）来存放一个数值的低16位。RoaringBitmap将这些容器保存在一个动态数组中，作为一级索引。容器使用两种不同的结构：数组容器（Array Container）和位图容器（Bitmap Container）。数组容器存放稀疏的数据，位图容器存放稠密的数据。如果一个容器里面的整数数量小于4096，就用数组容器来存储值。若大于4096，就用位图容器来存储值。

采用这种存储结构，RoaringBitmap可以快速检索一个特定的值。在做位图计算（AND、OR、XOR）时，RoaringBitmap提供了相应的算法来高效地实现在两种容器之间的运算。使得RoaringBitmap无论在存储和计算性能上都表现优秀。

使用限制

操作符列表

以下操作符支持处理RoaringBitmap和RoaringBitmap64类型的数据。

Bitmap函数列表

• 支持处理RoaringBitmap和RoaringBitmap64类型的函数

  函数名	输入类型	输出类型	描述	示例
  rb_build_agg	INTEGER|BIGINT	入参的数据类型为： INTEGER时，返回RoaringBitmap类型。 BIGINT时，返回RoaringBitmap64类型。	将Offset聚合成RoaringBitmap。 说明 仅Hologres V3.1及以上版本支持BIGINT入参类型，并返回RoaringBitmap64类型。	rb_build_agg(1)
  rb_cardinality	RoaringBitmap | RoaringBitmap64	INTEGER	统计基数。	rb_cardinality(rb_build('{1,2,3,4,5}'))
  rb_and_cardinality	RoaringBitmap | RoaringBitmap64，RoaringBitmap | RoaringBitmap64	INTEGER	And计算并返回基数。	rb_and_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))
  rb_or_cardinality	RoaringBitmap | RoaringBitmap64，RoaringBitmap | RoaringBitmap64	INTEGER	Or计算并返回基数。	rb_or_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))
  rb_range	RoaringBitmap | RoaringBitmap64，BIGINT，BIGINT	RoaringBitmap | RoaringBitmap64	返回从起始位置（包含）到结束位置（不包含）范围的新集合，位置从1开始计数。 说明 Hologres V1.3.16及以上版本支持。	rb_range(rb_build('{1,2,3}'), 2, 3)
  rb_minimum	RoaringBitmap | RoaringBitmap64	INTEGER	返回Bitmap中最小的Offset，如果Bitmap为空则返回-1。	rb_minimum(rb_build('{1,2,3}'))
  rb_maximum	RoaringBitmap | RoaringBitmap64	INTEGER	返回Bitmap中最大的Offset，如果Bitmap为空则返回0。	rb_maximum(rb_build('{1,2,3}'))
  rb_to_array	RoaringBitmap | RoaringBitmap64	INTEGER[]	返回Bitmap对应整型数组。	rb_to_array(rb_build('{1,2,3}'))
  rb_to_array_string	RoaringBitmap | RoaringBitmap64, TEXT	TEXT	返回Bitmap对应整型数组拼接的字符串。	rb_to_array_string(rb_build('{1,2,3}'),',')

• 仅支持处理RoaringBitmap64类型的函数

  函数名	输入类型	输出类型	描述	示例
  rb64_build	BIGINT[]	RoaringBitmap64	通过数组创建一个64位的RoaringBitmap。 说明 Hologres V3.1及以上版本支持。	--准备数据 CREATE TABLE public.tn ( id INT, num BIGINT[] ); INSERT INTO public.tn ("id", "num") VALUES (01, '{1,2}'); SELECT rb64_build (num) rb_num,num FROM public.tn; 返回结果如下。 rb_num num \x030100000000000000000000003a30000001000000000001001000000001000200 {1,2}

• 仅支持处理RoaringBitmap类型的函数

  函数名	输入类型	输出类型	描述	示例
  rb_build	INTEGER[]	RoaringBitmap	通过数组创建一个32位RoaringBitmap。	--返回结果：\x3a3000000100000000000000100000000100 SELECT rb_build_agg(1);
  roaringbitmap_in	TEXT	RoaringBitmap	将TEXT类型转换成RoaringBitmap类型。 说明 Hologres V2.1.33及以上版本支持。	--新建示例表。 CREATE TABLE rb_text ( id int, a text ); --插入示例数据。 INSERT INTO rb_text VALUES (1, '\x3a300000010000000000090010000000010002000300040005000600070008000900c800'); --将字段a转换成roaringbitmap类型，并进行and聚合运算。 SELECT rb_and_cardinality_agg (roaringbitmap_in (a::cstring)) FROM rb_text; --返回结果 rb_and_cardinality_agg| ----------------------- 10|
  rb_index	RoaringBitmap, INTEGER	BIGINT	返回此roaringbitmap中元素从0开始的索引，如果不存在则返回-1。 说明 Hologres V1.3.16及以上版本支持。	rb_index(rb_build('{1,2,3}'),3)
  rb_and_null2empty	RoaringBitmap，RoaringBitmap	RoaringBitmap	And计算。当输入参数为Null时，按empty处理。 说明 Hologres V1.1.42及以上版本支持。	rb_and_null2empty(rb_build(null),rb_build('{3,4,5}'))
  rb_or_null2empty	RoaringBitmap，RoaringBitmap	RoaringBitmap	Or计算。当输入为Null时，按empty处理。 说明 Hologres V1.1.42及以上版本支持。	rb_or_null2empty(rb_build(null),rb_build('{3,4,5}'))
  rb_andnot_null2empty	RoaringBitmap，RoaringBitmap	RoaringBitmap	AndNot计算。当输入为Null时，按empty处理。 说明 Hologres V1.1.42及以上版本支持。	rb_andnot_null2empty(rb_build(null),rb_build('{3,4,5}'))
  rb_and_null2empty_cardinality	RoaringBitmap，RoaringBitmap	INTEGER	And计算并返回基数。当输入为Null时，按empty处理。 说明 Hologres V1.1.42及以上版本支持。	rb_and_null2empty_cardinality(rb_build(null),rb_build('{3,4,5}'))
  rb_or_null2empty_cardinality	RoaringBitmap，RoaringBitmap	INTEGER	Or计算并返回基数。当输入为Null时，按empty处理。 说明 Hologres V1.1.42及以上版本支持。	rb_or_null2empty_cardinality(rb_build(null),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_andnot_null2empty_cardinality	RoaringBitmap，RoaringBitmap	INTEGER	AndNot计算并返回基数。当输入为Null时，按empty处理。 说明 Hologres V1.1.42及以上版本支持。	rb_andnot_null2empty_cardinality(rb_build(null),rb_build('{3,4,5}'))
  rb_is_empty	RoaringBitmap	BOOLEAN	判断是否为空的Bitmap。	rb_is_empty(rb_build('{1,2,3,4,5}'))
  rb_fill	RoaringBitmap，BIGINT，BIGINT	RoaringBitmap	填写指定范围（不包括range_end）。 说明 Hologres V1.3.16及以上版本支持。	rb_fill(rb_build('{1,2,3}'), 5, 7)
  rb_clear	RoaringBitmap，BIGINT，BIGINT	RoaringBitmap	清除指定范围（不包括 range_end）。 说明 Hologres V1.3.16及以上版本支持。	rb_clear(rb_build('{1,2,3}'), 2, 3)
  rb_contains_bitmap	RoaringBitmap，RoaringBitmap	BOOLEAN	判断第一个Bitmap是否包含第二个Bitmap。	rb_contains(rb_build('{1,2,3}'),rb_build('{3}'))
  rb_flip	RoaringBitmap,INTEGER,INTEGER	RoaringBitmap	翻转Bitmap中特定的Offset段。	rb_flip(rb_build('{1,2,3}'),2,3)
  rb_range_cardinality	RoaringBitmap, BIGINT, BIGINT	BIGINT	返回从起始位置（包含）到结束位置（不包含）范围的基数，位置从1开始计数。 说明 Hologres V1.3.16及以上版本支持。	rb_range_cardinality(rb_build('{1,2,3}'), 2, 3)
  rb_rank	RoaringBitmap,INTEGER	INTEGER	返回Bitmap中小于等于指定Offset的基数。	rb_rank(rb_build('{1,2,3}'),3)
  rb_jaccard_dist	RoaringBitmap，RoaringBitmap	DOUBLE PRECISION	返回两个Bitmap的Jaccard距离（或Jaccard相似系数）。 说明 Hologres V1.3.16及以上版本支持。	rb_jaccard_dist(rb_build('{1,2,3}'), rb_build('{3,4}'))
  rb_select	RoaringBitmap, bitset_limit bigint, bitset_offset bigint=0, reverse boolean=false, range_start bigint=-2147483648, range_end bigint=2147483647	RoaringBitmap	返回范围 [range_start,range_end) 之间Bitmap的子集 [bitset_offset,bitset_offset+bitset_limit)。	rb_select(rb_build('{1,2,3,4,5,6,7,8,9}'), 5, 2)
  rb_iterate	RoaringBitmap	Set of Integer	返回Offset List。	rb_iterate(rb_build('{1,2,3}'))

Bitmap聚合函数列表

• 支持处理RoaringBitmap和RoaringBitmap64类型的函数

  函数名	输入类型	输出类型	描述	示例
  rb_or_agg	RoaringBitmap | RoaringBitmap64	与入参类型一致。	Or聚合计算。	rb_or_agg(rb_build('{1,2,3}'))
  rb_and_agg	RoaringBitmap | RoaringBitmap64	与入参类型一致。	And聚合计算。	rb_and_agg(rb_build('{1,2,3}'))
  rb_or_cardinality_agg	RoaringBitmap | RoaringBitmap64	INTEGER	Or聚合计算并返回其基数。	rb_or_cardinality_agg(rb_build('{1,2,3}'))
  rb_and_cardinality_agg	RoaringBitmap | RoaringBitmap64	INTEGER	And聚合计算并返回其基数。	rb_and_cardinality_agg(rb_build('{1,2,3}'))

• 仅支持处理RoaringBitmap类型的函数

  函数名	输入类型	输出类型	描述	示例
  rb_xor_agg	RoaringBitmap	RoaringBitmap	Xor聚合计算。	rb_xor_agg(rb_build('{1,2,3}'))
  rb_xor_cardinality_agg	RoaringBitmap	INTEGER	Xor聚合计算并返回其基数。	rb_xor_cardinality_agg(rb_build('{1,2,3}'))

其他Bitmap函数

以下函数仅支持处理RoaringBitmap类型的数据。

使用示例

如下内容将为您介绍RoaringBitmap函数完整的使用示例。

1. 加载RoaringBitmap函数插件。

   CREATE EXTENSION roaringbitmap;

2. 创建带有RoaringBitmap数据类型的表。

   --创建名称为t1的表
   CREATE TABLE public.t1 (id integer, bitmap roaringbitmap);

3. 使用rb_build函数插入RoaringBitmap的数据。

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

4. 进行Bitmap计算（OR、AND、XOR、ANDNOT）。

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

5. 进行Bitmap聚合计算（OR、AND、XOR、BUILD），并生成新的RoaringBitmap类型。

   SELECT RB_OR_AGG(bitmap) FROM public.t1;
   SELECT RB_AND_AGG(bitmap) FROM public.t1;
   SELECT RB_XOR_AGG(bitmap) FROM public.t1;
   SELECT RB_BUILD_AGG(id) FROM public.t1;

6. 统计基数（Cardinality），即统计RoaringBitmap中包含多少个位置为1的BIT位。

   SELECT RB_CARDINALITY(bitmap) FROM public.t1;

7. 从RoaringBitmap中返回位置为1的BIT下标（即位置值）。

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

8. 将RoaringBitmap转换为数组结构。

   SELECT RB_TO_ARRAY(bitmap) FROM public.t1 WHERE id = 1;