位图计算(roaringbitmap)

RDS PostgreSQL提供roaringbitmap插件,可以使用位图计算功能,提高查询性能。

您可以加入RDS PostgreSQL插件交流钉钉群(103525002795),进行咨询、交流和反馈,获取更多关于插件的信息。

前提条件

实例为RDS PostgreSQL 12或以上版本。

背景信息

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

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

注意事项

为确保插件的稳定性,建议升级到最新内核小版本。

说明

如需升级内核小版本,请参见升级内核小版本

操作步骤

  1. 创建插件。示例如下:

    CREATE EXTENSION roaringbitmap;
  2. 创建带有RoaringBitmap数据类型的表。示例如下:

    CREATE TABLE t1 (id integer, bitmap roaringbitmap);
  3. 使用rb_build函数插入roaringbitmap的数据。示例如下:

    --数组位置对应的BIT值为1
    INSERT INTO t1 SELECT 1,RB_BUILD(ARRAY[1,2,3,4,5,6,7,8,9,200]);
    --将输入的多条记录的值对应位置的BIT值设置为1,最后聚合为一个roaringbitmap  
    INSERT INTO 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 t1 WHERE id = 1) AS a,(SELECT bitmap FROM t1 WHERE id = 2) AS b;
  5. 进行Bitmap聚合计算(OR、AND、XOR、BUILD),并生成新的roaringbitmap类型。示例如下:

    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;
  6. 统计基数(Cardinality),即统计roaringbitmap中包含多少个位置为1的BIT位。示例如下:

    SELECT RB_CARDINALITY(bitmap) FROM t1;
  7. 从roaringbitmap中返回位置为1的BIT下标(即位置值)。示例如下:

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

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

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