The pg_roaringbitmap extension is an efficient bitmap storage and computing extension.

Implementation principle

The RoaringBitmap algorithm mainly addresses the fixed space consumption issue of traditional Bitmap. It reduces Bitmap space usage while providing high-performance bitmap computing. In the most extreme scenarios, traditional bitmap may occupy a large space even when storing only two numbers. For example, storing the numbers 0 and 1,000,000 requires traditional bitmap to pre-allocate 1,000,001 bits, about 125 KB of space; but Roaringbitmap only requires 8 bytes in this case.

Classic RoaringBitmap algorithm

The classic RoaringBitmap algorithm divides each 32-bit signed integer in the set [-2147483648, 2147483647] into two parts: high 16 bits + low 16 bits. The high 16 bits serve as the first-level index for storage and retrieval, while the low 16 bits are the secondary data stored in Containers. Containers have two Types: Array Container and Bitmap Container, as shown below:

In the above Roaring bitmap, the 4-byte integer values stored have high 16Bits of 0x0000, 0x0001, 0x0002 respectively:

High 16 bits 0x0000: stored using an ordered Array Container, containing the first 1000 multiples of 62.

High 16 bits 0x0001: stored using an ordered Array Container, containing 100 integers in the range [216, 216+100).

High 16 bits 0x0002: stored using a Bitmap Container, containing 215 even numbers in the range [216, 3×216).

The choice between Array Container and Bitmap Container depends on the number of 16Bit integers stored in the corresponding Container. The details are as follows:

When the number of 16Bit integers stored in the Container is less than or equal to 4096, the maximum space occupied by a single Container is 4096 * 16Bit = 8KB, and an array container is used for storage;

When the number of 16Bit integers stored in the Container is greater than 4096, a Bitmap container is used for storage. The space occupied by a single Bitmap container is fixed at: 216Bit = 8KB.

RoaringBitmap used by the extension

The RoaringBitmap used by the Extension adopts an algorithm that adds run container optimization to the classic RoaringBitmap algorithm, optimizing bitmaps with step properties. The details are as follows:

In the above Roaring bitmap, the 4-byte integer values stored have high 16Bits of 0x0000, 0x0001, 0x0002 respectively:

High 16Bit 0x0000: stored in an array container ordered array, storing the first 1000 integers that are multiples of 62

High 16Bit 0x0001: stored in a run container in compressed form, storing three intervals [216, 216 + 100), [216 + 101, 216 + 201), [216 + 300, 216 + 400) totaling 300 integers, with the container occupying only 6Bit.

High 16Bit 0x0002: stored in a bitmap container, storing 215 even numbers in the range [2×216, 3×216).

Install extension

Use the following command to install the extension.

Data type

Type name

roaringbitmap

Usage example

GUC

Parameter name	roaringbitmap.output_format
Parameter description	character type, used to control the output format of roaringbitmap type, value range: array and bytea, default value is bytea array: Return roaringbitmap values as an array format during queries bytea: Return roaringbitmap values as bytea format during queries
Usage	set roaringbitmap.output_format = 'array'; select '{-1,2,555555,-4}'::roaringbitmap; set roaringbitmap.output_format = 'bytea'; select '{-1,2,555555,-4}'::roaringbitmap; set roaringbitmap.output_format = 'array'; select '\x3a300000030000000000000008000000ffff01002000000022000000240000000200237afcffffff'::roaringbitmap; sysbench=> set roaringbitmap.output_format = "array"; SET sysbench=> select '{-1,2,5555555,-4}':: roaringbitmap; roaringbitmap ------------------ {2,555555,-4,-1} (1 row) sysbench=> sysbench=> set roaringbitmap.output_format = 'bytea'; SET sysbench=> select '{-1,2,55555,-4}'::roaringbitmap; roaringbitmap ---------------------------------------------------------------------------------- \x3a300000030000000000000008000000ffff01002000000022000000240000000200237afcffffff sysbench=> sysbench=> select '\x3a300000030000000000000008000000ffff01002000000022000000240000000200237afcffffff'::roaringbitmap; roaringbitmap ----------------------------------------------------------------------------------- \x3a300000030000000000000080000000ffff01002000000022000000240000000200237afcfffffff (1 row) sysbench=> set roaringbitmap.output_format = 'array' SET sysbench=> select '\x3a300000030000000000000008000000ffff01002000000022000000240000000200237afcffffff'::roaringbitmap; roaringbitmap ---------------- {2,555555,-4,-1} (1 row) sysbench=>

Functions and operators

helper functions

used to generate integer arrays of specified dimensions.

Functions and operators

function name	operators name	Input	output	Note	Example
rb_and	&	roaringbitmap, roaringbitmap	roaringbitmap	and	select rb_and(rb_build('{1,2,3,4,5}'),rb_build('{4,5,6,7}')); select rb_build('{1,2,3,4,5}') & rb_build('{4,5,6,7}'); select rb_build(gen_array(4)) & rb_build(gen_array(5)); select rb_build(gen_array(1000)) & rb_build(gen_array(1000));
rb_or	\|	roaringbitmap, roaringbitmap	roaringbitmap	or	select rb_or(rb_build('{1,2,3,4,5}'),rb_build('{4,5,6,7}')); select rb_build('{1,2,3,4,5}') select rb_build(gen_array(4)) select rb_build(gen_array(1000))
rb_xor	#	roaringbitmap, roaringbitmap	roaringbitmap	xor	select rb_xor(rb_build('{1,2,3,4,5}'),rb_build('{4,5,6,7}')); select rb_build('{1,2,3,4,5}') # rb_build('{4,5,6,7}'); select rb_build(gen_array(4)) # rb_build(gen_array(5)); select rb_build(gen_array(1000)) # rb_build(gen_array(1000));
rb_andnot	-	roaringbitmap, roaringbitmap	roaringbitmap	and Non	select rb_andnot(rb_build('{1,2,3,4,5}'),rb_build('{4,5,6,7}')); select rb_build('{1,2,3,4,5}') - rb_build('{4,5,6,7}'); select rb_build(gen_array(4)) - rb_build(gen_array(5)); select rb_build(gen_array(1000)) - rb_build(gen_array(1000));
rb_add	\|	roaringbitmap, integer	roaringbitmap	add to bitmap	select rb_add(rb_build('{1,2,3,4,5}'), 10); select rb_build('{1,2,3,4,5}') select rb_add(rb_build(gen_array(5), 10); select rb_build(rb_build(gen_array(5))
rb_add		\|	integer, roaringbitmap	roaringbitmap	add to bitmap	select rb_add(10, rb_build('{1,2,3,4,5}')); select 10 select rb_add(10, rb_build(gen_array(5)); select 10
rb_remove	-	roaringbitmap, integer	roaringbitmap	remove integer from bitmap	select rb_remove(rb_build('{1,2,3,4,5}'), 3); select rb_build('{1,2,3,4,5}') - 3;
rb_contains	@>	roaringbitmap, roaringbitmap	bool	whether it contains	select rb_contains(rb_build('{1,2,3,4,5}'),rb_build('{4,5}')); select rb_build('{1,2,3,4,5}') @> rb_build('{4,5}');
rb_contains		@>	roaringbitmap, integer	bool	whether it contains	select rb_contains(rb_build('{1,2,3,4,5}'), 3); select rb_build('{1,2,3,4,5}') @> 3;
rb_containedby	<@	roaringbitmap, roaringbitmap	bool	exists in	select rb_containedby(rb_build('{3,4,5}'),rb_build('{1,2,3,4,5,6}')); select rb_build('{3,4,5}') <@ rb_build('{1,2,3,4,5,6}');
rb_containedby		<@	integer, roaringbitmap	bool	exists in	select rb_containedby(3, rb_build('{1,2,3,4,5}')); select 3 <@ rb_build('{1,2,3,4,5}');
rb_intersect	&&	roaringbitmap, roaringbitmap	bool	whether they intersect	select rb_intersect(rb_build('{3,4,5}'),rb_build('{1,2,3,4,5,6}')); select rb_build('{3,4,5}') && rb_build('{1,2,3,4,5,6}');
rb_equals	=	roaringbitmap, roaringbitmap	bool	whether equal	select rb_equals(rb_build('{3,4,5}'),rb_build('{1,2,3,4,5,6}')); select rb_build('{3,4,5}') = rb_build('{1,2,3,4,5,6}'); select rb_equals(rb_build('{3,4,5}'),rb_build('{4,5,3}')); select rb_build('{3,4,5}') = rb_build('{4,5,3}');
rb_not_equals	<>	roaringbitmap, roaringbitmap	bool	not equal	select rb_not_equals(rb_build('{3,4,5}'),rb_build('{1,2,3,4,5,6}')); select rb_build('{3,4,5}') <> rb_build('{1,2,3,4,5,6}'); select rb_not_equals(rb_build('{3,4,5}'),rb_build('{4,5,3}')); select rb_build('{3,4,5}') <> rb_build('{4,5,3}');

Functions

function name	enter information	output	Note	Example
rb_build	integer[]	roaringbitmap	create bitmap from an integer array	set roaringbitmap.output_format = 'array'; select rb_build('{1,2,3,4,5}'); select rb_build(gen_array(10));
rb_index	roaringbitmap, integer	bigint	Return the index of the integer in the bitmap starting from 0, return -1 if not found	select rb_index(rb_build('{-1,2,-3,4,5}'), 5); select rb_index(rb_build(gen_array(10)), 10);
rb_cardinality	roaringbitmap	bigint	return cardinality	select rb_cardinality(rb_build('{-1,2,-3,4,5}')); select rb_cardinality(rb_build(gen_array(10)));
rb_and_cardinality	roaringbitmap, roaringbitmap	bigint	Return the cardinality after bitmap	select rb_and_cardinality(rb_build('{1,2,3,4,5}'),rb_build('{4,5,6,7}'));
rb_or_cardinality	roaringbitmap, roaringbitmap	bigint	bitmap or return cardinality later	select rb_or_cardinality(rb_build('{1,2,3,4,5}'),rb_build('{4,5,6,7}'));
rb_xor_cardinality	roaringbitmap, roaringbitmap	bigint	Return cardinality after bitmap xor	select rb_xor_cardinality(rb_build('{1,2,3,4,5}'),rb_build('{4,5,6,7}'));
rb_andnot_cardinality	roaringbitmap, roaringbitmap	bigint	Return the cardinality after bitmap and not	select rb_andnot_cardinality(rb_build('{1,2,3,4,5}'),rb_build('{4,5,6,7}'));
rb_is_empty	roaringbitmap	bool	whether the bitmap is empty	select rb_is_empty(rb_build('{1,2,3,4,5}')); select rb_is_empty(rb_build('{}'));
rb_fill	roaringbitmap, range_start bigint, range_end bigint	roaringbitmap	fill bitmap within specified range, excluding range_end	select rb_fill(rb_build('{1,2,3,4,5,6,7,8,9}'), 10, 15);
rb_clear	roaringbitmap, range_start bigint, range_end bigint	roaringbitmap	Clear the integers in the specified range of the bitmap, excluding range_end	select rb_clear(rb_build('{1,2,3,4,5,6,7,8,9}'), 2, 5);
rb_flip	roaringbitmap, range_start bigint, range_end bigint	roaringbitmap	Invert the specified range, existing values become non-existent, non-existing become existing, excluding range_end	select rb_flip(rb_build('{1,2,3,4,5,6,7,8,9}'), 2, 15);
rb_range	roaringbitmap, range_start bigint, range_end bigint	roaringbitmap	Return the sub-bitmap of the specified range, excluding range_end	select rb_range(rb_build('{1,2,3,4,5,6,7,8,9}'), 2, 7);
rb_range_cardinality	roaringbitmap, range_start bigint, range_end bigint	bigint	return the cardinality of the specified range sub bitmap, excluding range_end	select rb_range_cardinality(rb_build('{1,2,3,4,5,6,7,8,9}'), 2, 7);
rb_min	roaringbitmap	integer	Return the smallest offset in the bitmap, or NULL if the bitmap is empty.	select rb_min(rb_build('{67,12,23,4,35,6,7,8,9}'));
rb_max	roaringbitmap	integer	Return the largest offset in the Bitmap; return null if the Bitmap is empty.	select rb_max(rb_build('{67,12,23,4,35,6,7,8,9}'));
rb_rank	roaringbitmap, integer	bigint	return the cardinality in the bitmap less than or equal to the specified offset	select rb_rank(rb_build('{9,8,7,3,4,5,1,2,6}'), 5); select rb_rank(rb_build('{9,8,7,3,4,1,2,6}'), 5);
rb_jaccard_dist	roaringbitmap, roaringbitmap	float8	return the Jaccard coefficient of two bitmaps; the larger the value, the higher the similarity between the bitmaps	select rb_jaccard_dist(rb_build('{1,2,3,4,5}'),rb_build('{4,5,1,2,3}')); select rb_jaccard_dist(rb_build('{1,2,3,4,5}'),rb_build('{4,5,6,7}')); select rb_jaccard_dist(rb_build('{1,2,3,4,5}'),rb_build('{9,8,6,7}'));
rb_select	roaringbitmap, bitset_limit bigint,bitset_offset bigint=0,reverse boolean=false,range_start bigint=0,range_end bigint=4294967296	roaringbitmap	Return the subset [bitset_offset,bitset_offset+bitset_limit) of the range [range_start,range_end)	select rb_select(rb_build('{1,2,3,4,5,6,7,8,9}'), 5, 2); select rb_select(rb_build('{1,2,3,4,5,6,7,8,9}'), 5, 2, false, 3, 9); select rb_select(rb_build('{1,2,3,4,5,6,7,8,9}'), 5, 2, true, 3, 9);
rb_to_array	roaringbitmap	integer[]	convert an integer array to a bitmap	select rb_to_array(rb_build('{1,2,3,4,5,6,7,8,9}')); select rb_to_array(rb_build(gen_array(10)));
rb_iterate	roaringbitmap	SETOF integer	return the integers in the bitmap as records, opposite to the effect of rb_build_agg	select rb_iterate(rb_build('{1,2,3,4,5,6,7,8,9}')); select rb_iterate(rb_build(gen_array(10)));

Aggregate functions

function name	Input	output	Note	Example
rb_or_agg	roaringbitmap	roaringbitmap	or aggregate	select rb_or_agg(rb) from tbl_rb_agg;
rb_or_cardinality_agg	roaringbitmap	bigint	or aggregate and return its cardinality	select rb_or_cardinality_agg(rb) from tbl_rb_agg;
rb_and_agg	roaringbitmap	roaringbitmap	and aggregation	select rb_and_agg(rb) from tbl_rb_agg;
rb_and_cardinality_agg	roaringbitmap	bigint	and aggregate return its cardinality	select rb_and_cardinality_agg(rb) from tbl_rb_agg;
rb_xor_agg	roaringbitmap	roaringbitmap	xor aggregation	select rb_xor_agg(rb) from tbl_rb_agg;
rb_xor_cardinality_agg	roaringbitmap	bigint	xor aggregate and return its cardinality	select rb_xor_cardinality_agg(rb) from tbl_rb_agg;
rb_build_agg	integer	roaringbitmap	construct bitmap from an integer set, opposite effect of rb_iterate	select rb_build_agg(id) from tbl_rb_agg;

RDS for PostgreSQL