位图计算（pg_roaringbitmap）
最近更新时间：2024.02.23 15:45:09
首次发布时间：2023.08.08 23:52:58
pg_roaringbitmap 插件是一款高效的位图存储和运算的插件。
实现原理
RoaringBitmap 算法主要解决传统 Bitmap 的空间占用固化的问题，其在降低 Bitmap 空间的同时，还提供高性能的 bitmap 运算。在最极端的场景下，传统的 bitmap 即使存储两个数字，也有可能占据大量的空间。例如，存储数字 0 和 数字 1000000，传统的 bitmap 需要提前申请 1000001 个 bit 位，大约 125KB 的空间；而 Roaringbitmap 在此种场景下，仅仅只需 8 Byte 即可。
经典 RoaringBitamp 算法
最经典的 RoaringBitamp 算法，将 32bit 的有符号 Integer 整数集 [-2147483648, 2147483647] 中的每个整数划分两部分：高 16Bit + 低 16Bit，高 16Bit 作为 一级索引进行存储检索，低16 Bit 作为二级数据存储于 Container 中，Container 有 两种类型：Array Container 和 Bitmap Container，如下图所示：
上图 Roaring bitmap 中，存储高 16Bit 分别为 0x0000、0x0001、0x0002 的部分 4 字节整数值：
高 16Bit 为 0x0000：使用 Array Container 有序数组存储，存储前 1000 个 62 的整数倍对应的数字。
高 16Bit 为 0x0001：使用 Array Container 有序数组存储，存储 [216, 216+100) 区间内的 100 个整数。
高 16Bit 为 0x0002：使用 Bitmap Container 位图存储，存储 [216, 3×216) 区间内 215 个偶数。
Array Container 和 Bitmap Container 的选择，取决于对应 Container 中存储的 16Bit 整数的个数，具体如下：
当 Container 中存储的 16Bit 整数个数小于等于 4096 时，单个 Container 所占据的空间最大值为 4096 * 16Bit = 8KB，此时采用 array container 存储；
当 Container 中存储的 16Bit 整数个数大于 4096 时，采用 Bitmap container 存储，单个 Bitmap container 所占据的空间固定为：216Bit = 8KB。
插件采用的 RoaringBitmap
相较于经典 RoaringBitmap 算法，pg_roaringbitmap 插件采用的算法增加了 run container，对某些具有步长属性的位图进行了适当的优化。如下图所示：
上图 Roaring bitmap 中，存储高 16Bit 分别为 0x0000、0x0001、0x0002 的部分 4 字节整数值：
高 16Bit 为 0x0000：使用 Array Container 有序数组存储，存储前 1000 个 62 的整数倍对应的数字
高 16Bit 为 0x0001：使用 Run Container 压缩存储，存储 [216, 216+ 100), [216+101, 216+ 201), [216+300, 216+ 400) 三个区间总计 300 个整数，Container 占用空间仅 6Bit。
高 16Bit 为 0x0002：使用 Bitmap Container 位图存储，存储 [2×216, 3×216) 区间内 215 个偶数。
安装插件
使用以下命令即可安装插件。
create extension roaringbitmap;
使用说明
数据类型
| 类型名称 | roaringbitmap |
|---|---|
使用案例 |
|
GUC
| 参数名称 | roaringbitmap.output_format |
|---|---|
参数说明 | 字符类型，用于控制 roaringbitmap 类型的输出格式，取值范围为：array 和 bytea，默认值为 bytea。
|
用法 |
|
函数和操作符
辅助函数
用于生成指定维度的整型数组。
create or replace function gen_array(dim int4) returns int4[] as $$ select array_agg((random()* 1000000)::int4) from generate_series(1, dim) $$ language sql volatile cost 1;
函数及操作符
| 函数名称 | 操作符名称 | 输入 | 输出 | 说明 | 示例 |
|---|---|---|---|---|---|
rb_and | & | roaringbitmap, roaringbitmap | roaringbitmap | 与 |
|
rb_or | | | roaringbitmap, roaringbitmap | roaringbitmap | 或 |
|
rb_xor | # | roaringbitmap, roaringbitmap | roaringbitmap | 异或 |
|
rb_andnot | - | roaringbitmap, roaringbitmap | roaringbitmap | 与非 |
|
rb_add | | | roaringbitmap, integer | roaringbitmap | 向位图中增加 |
|
| | integer, roaringbitmap | roaringbitmap | 向位图中增加 |
| |
rb_remove | - | roaringbitmap, integer | roaringbitmap | 从位图中移除整数 |
|
rb_contains | @> | roaringbitmap, roaringbitmap | bool | 是否包含 |
|
@> | roaringbitmap, integer | bool | 是否包含 |
| |
rb_containedby | <@ | roaringbitmap, roaringbitmap | bool | 是否存在于 |
|
<@ | integer, roaringbitmap | bool | 是否存在于 |
| |
rb_intersect | && | roaringbitmap, roaringbitmap | bool | 是否相交 |
|
rb_equals | = | roaringbitmap, roaringbitmap | bool | 是否相等 |
|
rb_not_equals | <> | roaringbitmap, roaringbitmap | bool | 是否不等 |
|
函数
| 函数名称 | 输入 | 输出 | 说明 | 示例 |
|---|---|---|---|---|
rb_build | integer[] | roaringbitmap | 通过整数数组创建位图 |
|
rb_index | roaringbitmap, integer | bigint | 返回整数在位图中从 0 开始的下标，不存在返回 -1 |
|
rb_cardinality | roaringbitmap | bigint | 返回基数 |
|
rb_and_cardinality | roaringbitmap, roaringbitmap | bigint | 位图与后返回基数 |
|
rb_or_cardinality | roaringbitmap, roaringbitmap | bigint | 位图或后返回基数 |
|
rb_xor_cardinality | roaringbitmap, roaringbitmap | bigint | 位图异或后返回基数 |
|
rb_andnot_cardinality | roaringbitmap, roaringbitmap | bigint | 位图与非后返回基数 |
|
rb_is_empty | roaringbitmap | bool | 位图是否为空 |
|
rb_fill | roaringbitmap, range_start bigint, range_end bigint | roaringbitmap | 填充位图指定范围，不包含 range_end |
|
rb_clear | roaringbitmap, range_start bigint, range_end bigint | roaringbitmap | 清空位图指定范围整数，不包含 range_end |
|
rb_flip | roaringbitmap, range_start bigint, range_end bigint | roaringbitmap | 将指定范围反正，存在置为不存，不存在置为存在，不包含 range_end |
|
rb_range | roaringbitmap, range_start bigint, range_end bigint | roaringbitmap | 返回指定范围的子位图，不包含 range_end |
|
rb_range_cardinality | roaringbitmap, range_start bigint, range_end bigint | bigint | 返回指定范围子位图的基数，不包含 range_end |
|
rb_min | roaringbitmap | integer | 返回 Bitmap 中最小的 Offset，如果 Bitmap 为空则返回 NULL。 |
|
rb_max | roaringbitmap | integer | 返回 Bitmap 中最大的 Offset，如果 Bitmap 为空则返回 NULL。 |
|
rb_rank | roaringbitmap, integer | bigint | 返回位图中小于等于指定 Offset 的基数。 |
|
rb_jaccard_dist | roaringbitmap, roaringbitmap | float8 | 返回两个位图的 Jaccar 系数，该数值越大，表示位图的相似度越高 |
|
rb_select | roaringbitmap, bitset_limit bigint,bitset_offset bigint=0,reverse boolean=false,range_start bigint=0,range_end bigint=4294967296 | roaringbitmap | 返回区间 [range_start,range_end) 的子集 [bitset_offset,bitset_offset+bitset_limit) |
|
rb_to_array | roaringbitmap | integer[] | 将整数数组转换成位图 |
|
rb_iterate | roaringbitmap | SETOF integer | 将位图中的整数以记录的形式返回，和 rb_build_agg 效果相反 |
|
聚合函数
drop table tbl_rb_agg; create table tbl_rb_agg(id serial, rb roaringbitmap); insert into tbl_rb_agg(rb) select rb_build('{1,2,3,4,5}'); insert into tbl_rb_agg(rb) select rb_build('{3,4,5,6,7}'); insert into tbl_rb_agg(rb) select rb_build('{4,5,6,7,8,9}'); select * from tbl_rb_agg;
sysbench=> drop table tbl_rb_agg; DROP TABLE sysbench=> create table tbl_rb_agg(id serial, rb roaaringbitmap); CREATE TABLE sysbench=> sysbench=> insert into tbl_rb_agg(rb) select rb_build('{1,2,3,4,5}'); INSERT 0 1 sysbench=> insert into tbl_rb_agg(rb) select rb_build('{3,4,5,6,7}'); INSERT 0 1 sysbench=> insert into tbl_rb_agg(rb) select rb_build('{4,5,6,7,8,9}'); INSERT 0 1 sysbench=> select * from tbl_rb_agg; id | rb ---+-------------———— 1 | {1,2,3,4,5} 2 | {3,4,5,6,7} 3 | {4,5,6,7,8,9} (3 rows)
| 函数名称 | 输入 | 输出 | 说明 | 示例 |
|---|---|---|---|---|
rb_or_agg | roaringbitmap | roaringbitmap | 或聚合 |
|
rb_or_cardinality_agg | roaringbitmap | bigint | 或聚合并返回其基数 |
|
rb_and_agg | roaringbitmap | roaringbitmap | 与聚合 |
|
rb_and_cardinality_agg | roaringbitmap | bigint | 与聚合并返回其基数 |
|
rb_xor_agg | roaringbitmap | roaringbitmap | 异或聚合 |
|
rb_xor_cardinality_agg | roaringbitmap | bigint | 异或聚合并返回其基数 |
|
rb_build_agg | integer | roaringbitmap | 通过整数集合构造位图，和 rb_iterate 效果相反 |
|