Use efficient roaring bitmaps to implement large-scale tag-based filtering - AnalyticDB

A roaring bitmap is an efficient data structure. Compared with bitmaps, roaring bitmaps provide higher processing performance and use fewer memory resources. Roaring bitmaps are suitable for computing scenarios such as intersection, union, and difference set operations and deduplication. In most cases, roaring bitmaps are used for user profiling, personalized recommendation, and precision marketing.

Background information

A bitmap is a common data structure that consists of the values 0 and 1. A separate bitmap is created to house all possible values for each column. Each bit indicates whether a data row has a value in the corresponding column. Conventional bitmaps use large amounts of memory resources. We recommend that you use compressed bitmaps. Roaring bitmaps are efficient compressed bitmaps that are used in almost all popular programming languages on a variety of big data platforms.

Introduction

In a roaring bitmap, each 32-bit integer contains 16 most significant bits and 16 least significant bits. The 16 most significant bits are stored in multiple chunks, and the 16 least significant bits are stored in a container. Each chunk can store up to 2^16 integers. A roaring bitmap stores containers in a dynamically expanding array and sorts the containers based on the 16 most significant bits. You can use the 16 most significant bits and the binary search method to quickly search for the containers. The following types of containers are used to store data based on data characteristics:

Array container: stores scattered and non-consecutive data. An array container can store fewer than 4,096 integers.
Bitmap container: stores a large number of consecutive integers. A bitmap container can store 4,096 or more integers.
Run container: stores a large number of consecutive increasing values. You can use a run container only if the size of the container is smaller than the size of an array container and the size of a bitmap container.

Roaring bitmaps use the preceding storage structure to significantly improve the data compression ratio and rapidly retrieve specific values. Roaring bitmaps support bitmap operations such as AND, OR, and XOR between the three types of containers. Roaring bitmaps can deliver excellent storage and computing performance.

For more information about roaring bitmaps, visit GitHub.

Usage notes

Only AnalyticDB for PostgreSQL instances of V6.3.8.9 or later support roaring bitmaps. For information about how to view the minor version of an AnalyticDB for PostgreSQL instance, see View the minor engine version.

Use roaring bitmaps

Install the extension

Before you use roaring bitmaps in an AnalyticDB for PostgreSQL instance, install the roaringbitmap extension on the Extensions page of the instance. For more information, see Install, update, and uninstall extensions.

Create a table

Create a table that is used to store roaring bitmap data.

CREATE TABLE t1 (id integer, bitmap roaringbitmap);

Insert data

Use the rb_build function to insert roaring bitmap data.

-- Set the bit values at specific positions in an array to 1. 
INSERT INTO t1 SELECT 1,RB_BUILD(ARRAY[1,2,3,4,5,6,7,8,9,200]);
-- Set the bit values of multiple elements to 1 and aggregate the bit values into a roaring bitmap.  
INSERT INTO t1 SELECT 2,RB_BUILD_AGG(e) FROM GENERATE_SERIES(1,100) e;

Query data

Obtain the subscripts of the bits that are set to 1.

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

Sample bitmap operations:

Perform bitmap operations such as OR, AND, XOR, and 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;

Perform bitmap aggregate operations such as OR, AND, XOR, and BUILD to generate new roaring bitmaps.

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;

Calculate the cardinality of the roaring bitmap. The cardinality is the number of bits that are set to 1 in the roaring bitmap.
```
SELECT RB_CARDINALITY(bitmap) FROM t1;
```

Bitmap calculation functions

Function	Input	Output	Description	Example
rb_build	integer[]	roaringbitmap	Creates a roaring bitmap from an integer array.	`rb_build('{1,2,3,4,5}')`
rb_and	roaringbitmap,roaringbitmap	roaringbitmap	Performs an AND operation.	`rb_and(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_or	roaringbitmap,roaringbitmap	roaringbitmap	Performs an OR operation.	`rb_or(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_xor	roaringbitmap,roaringbitmap	roaringbitmap	Performs an XOR operation.	`rb_xor(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_andnot	roaringbitmap,roaringbitmap	roaringbitmap	Performs an ANDNOT operation.	`rb_andnot(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_cardinality	roaringbitmap	integer	Calculates the cardinality.	`rb_cardinality(rb_build('{1,2,3,4,5}'))`
rb_and_cardinality	roaringbitmap,roaringbitmap	integer	Calculates the cardinality by performing an AND operation on two roaring bitmaps.	`rb_and_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_or_cardinality	roaringbitmap,roaringbitmap	integer	Calculates the cardinality by performing an OR operation on two roaring bitmaps.	`rb_or_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_xor_cardinality	roaringbitmap,roaringbitmap	integer	Calculates the cardinality by performing an XOR operation on two roaring bitmaps.	`rb_xor_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_andnot_cardinality	roaringbitmap,roaringbitmap	integer	Calculates the cardinality by performing an ANDNOT operation on two roaring bitmaps.	`rb_andnot_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_is_empty	roaringbitmap	boolean	Checks whether a roaring bitmap is empty.	`rb_is_empty(rb_build('{1,2,3,4,5}'))`
rb_equals	roaringbitmap,roaringbitmap	boolean	Checks whether two roaring bitmaps are the same.	`rb_equals(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_intersect	roaringbitmap,roaringbitmap	boolean	Checks whether two roaring bitmaps intersect.	`rb_intersect(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_remove	roaringbitmap,integer	roaringbitmap	Removes a specific offset from a roaring bitmap.	`rb_remove(rb_build('{1,2,3}'),3)`
rb_flip	roaringbitmap,integer	roraingbitmap	Flips a specific offset in a roaring bitmap.	`rb_flip(rb_build('{1,2,3}'),3)`
rb_flip	roaringbitmap,integer,integer	roaringbitmap	Flips a specific offset range in a roaring bitmap.	`rb_flip(rb_build('{1,2,3}'),2,3)`
rb_minimum	roaringbitmap	integer	Returns the smallest offset in a roaring bitmap. If the roaring bitmap is empty, -1 is returned.	`rb_minimum(rb_build('{1,2,3}'))`
rb_maximum	roaringbitmap	integer	Returns the largest offset in a roaring bitmap. If the roaring bitmap is empty, 0 is returned.	`rb_maximum(rb_build('{1,2,3}'))`
rb_rank	roaringbitmap,integer	integer	Returns the number of elements that are less than or equal to a specific offset in a roaring bitmap.	`rb_rank(rb_build('{1,2,3}'),3)`
rb_iterate	roaringbitmap	setof integer	Returns a list of offsets from a roaring bitmap.	`rb_iterate(rb_build('{1,2,3}'))`
rb_contains	roaringbitmap, integer	bool	Checks whether a roaring bitmap contains a specific offset.	`rb_contains(rb_build('{1,2,3}'),1)`
rb_contains	roaringbitmap,integer,integer	bool	Checks whether a roaring bitmap contains a specific offset range.	`rb_contains(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_contains	roaringbitmap, roaringbitmap	bool	Checks whether a roaring bitmap contains another roaring bitmap.	`rb_contains(rb_build('{1,2,3}'),rb_build('{3,4,5}'))`
rb_becontained	integer, roaringbitmap	bool	Checks whether a specific offset is contained by a roaring bitmap.	`rb_becontained(1, rb_build('{1,2,3}'))`
rb_becontained	roaringbitmap,roaringbitmap	bool	Checks whether a roaring bitmap is contained by another roaring bitmap.	`rb_becontained(rb_build('{1}'), rb_build('{1,2,3}'))`
rb_add	roaringbitmap, integer	roaringbitmap	Adds a specific offset to a roaring 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	Adds a specific offset range to a roaring bitmap.	`rb_add(rb_build('{1,2,3,4}'), 6,8)`
rb_remove	roaringbitmap,integer, integer	roaringbitmap	Removes a specific offset from a roaring bitmap.	`rb_remove(rb_build('{1,2,3,4,6,7,8}'), 6,8)`
rb_jaccard_index	roaringbitmap,roaringbitmap	float8	Calculates the Jaccard similarity coefficient between two roaring bitmaps.	`rb_jaccard_index(rb_build('{1,2,3,4}'), rb_build('{1,2}'))`
rb_to_array	roaringbitmap	integer[]	Converts a roaring bitmap into an array.	`rb_to_array(rb_build('{1,2,3,4}'))`
rb_iterate_decrement	roaringbitmap	integer[]	Returns a list of offsets from a roaring bitmap in descending order.	`rb_iterate_decrement(rb_build('{1,2,3,4}'))`

Bitmap aggregate functions

Function	Input	Output	Description	Example
rb_build_agg	integer	roaringbitmap	Creates a roaring bitmap from a group of offsets.	`rb_build_agg(1)`
rb_or_agg	roaringbitmap	roaringbitmap	Performs an OR aggregate operation.	`rb_or_agg(rb_build('{1,2,3}'))`
rb_and_agg	roaringbitmap	roaringbitmap	Performs an AND aggregate operation.	`rb_and_agg(rb_build('{1,2,3}'))`
rb_xor_agg	roaringbitmap	roaringbitmap	Performs an XOR aggregate operation.	`rb_xor_agg(rb_build('{1,2,3}'))`
rb_or_cardinality_agg	roaringbitmap	integer	Calculates the cardinality by performing an OR aggregate operation on two roaring bitmaps.	`rb_or_cardinality_agg(rb_build('{1,2,3}'))`
rb_and_cardinality_agg	roaringbitmap	integer	Calculates the cardinality by performing an AND aggregate operation on two roaring bitmaps.	`rb_and_cardinality_agg(rb_build('{1,2,3}'))`
rb_xor_cardinality_agg	roaringbitmap	integer	Calculates the cardinality by performing an XOR aggregate operation on two roaring bitmaps.	`rb_xor_cardinality_agg(rb_build('{1,2,3}'))`

Operators

Operator	Left	Right	Output	Description	Example
&	roaringbitmap	roaringbitmap	roaringbitmap	Performs an AND operation on two roaring bitmaps.	`rb_build('{1,2,3}') & rb_build('{1,2,4}')`
\|	roaringbitmap	roaringbitmap	roaringbitmap	Performs an OR operation on two roaring bitmaps.	`rb_build('{1,2}') \| rb_build('{1,3}')`
#	roaringbitmap	roaringbitmap	roaringbitmap	Performs an XOR operation on two roaring bitmaps.	`rb_build('{1,2}') # rb_build('{1,3}')`
~	roaringbitmap	roaringbitmap	roaringbitmap	Performs an ANDNOT operation on two roaring bitmaps.	`rb_build('{2,3}') ~ rb_build('{2,4}')`
+	roraingbitmap	integer	roaringbitmap	Adds a specific offset to a roaring bitmap.	`rb_build('{2,3}') + 1`
-	roraingbitmap	integer	roaringbitmap	Removes a specific offset from a roaring bitmap.	`rb_build('{1,2,3}') - 1`
=	roaringbitmap	roaringbitmap	boolean	Checks whether two roaring bitmaps are the same.	`rb_build('{2,3}') = rb_build('{2,3}')`
<>	roaringbitmap	roaringbitmap	boolean	Checks whether two roaring bitmaps are different.	`rb_build('{2,3}') <> rb_build('{1,2,3}')`
&&	roaringbitmap	roaringbitmap	boolean	Checks whether two roaring bitmaps intersect.	`rb_build('{2,3}') && rb_build('{3,4}')`
@>	roaringbitmap	roaringbitmap	boolean	Checks whether a roaring bitmap contains another roaring bitmap.	`rb_build('{2,3}') @> rb_build('{2}')`
@>	roaringbitmap	integer	boolean	Checks whether a roaring bitmap contains a specific offset.	`rb_build('{2,3}') @> 2`
<@	roaringbitmap	roaringbitmap	boolean	Checks whether a roaring bitmap is contained by another roaring bitmap.	`rb_build('{2,3}') <@ rb_build('{1,2,3}')`
<@	integer	roaringbitmap	boolean	Checks whether a specific offset is contained by a roaring bitmap.	`rb_build('{2,3}') <@ rb_build('{3}')`