文档

Roaring Bitmap

更新时间:

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}')