This topic describes how to use Roaring bitmaps in AnalyticDB for PostgreSQL. A bitmap is a common data structure that consists of 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 that column. A bitmap helps you check whether a value exists. It also enables you to expedite bitmap-related computing by using bitwise operations such as AND, OR, and ANDNOT. In the big data discipline, bitmaps are suitable for data queries and correlated computing workloads such as removing duplicate data, filtering data based on tags, and generating time series.
A conventional bitmap occupies a large amount of memory resources. Therefore, we recommend that you use compressed bitmaps. Roaring bitmaps are efficient compressed bitmaps that are used in almost all popular programming languages on various big data platforms.
Overview
In a Roaring bitmap, a 32-bit integer within the range of [0, n] is divided into two parts: the most significant 16 bits comprise a 2^16 chunk and the least significant 16 bits are stored in a container. The containers of a Roaring bitmap are stored in a dynamic array as the primary index. AnalyticDB for PostgreSQL supports two types of containers: array containers and bitmap containers. An array container is used to store sparse data while a bitmap container is used to store dense data. An array container can store up to 4,096 integers. A bitmap container can store more than 4,096 integers.
Based on the preceding storage structure, AnalyticDB for PostgreSQL can rapidly retrieve a specific value from a Roaring bitmap. Roaring bitmaps provide algorithms suitable for bitwise operations such as AND, OR, and XOR between the two types of containers. This enables Roaring bitmaps to deliver excellent storage and computing performance.
For more information, visit Roaring Bitmaps.
Procedure
Create the RoaringBitmap extension.
CREATE EXTENSION roaringbitmap;
Create a table with the roaringbitmap data type.
CREATE TABLE t1 (id integer, bitmap roaringbitmap);
Call the rb_build function to insert data of the roaringbitmap type.
-- Set the bit value of a data record in the 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;
Perform bitwise 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 bitwise operations such as OR, AND, XOR, and BUILD to aggregate data and generate a new 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;
Calculate the cardinality of the Roaring bitmap. The cardinality indicates how many bit values are 1 in the Roaring bitmap.
SELECT RB_CARDINALITY(bitmap) FROM t1;
Obtain the subscripts of the bits whose values are 1.
SELECT RB_ITERATE(bitmap) FROM t1 WHERE id = 1;
Bitmap calculation functions
Function name | Input data | Message | Description | Examples |
---|---|---|---|---|
rb_build | integer[] | roaringbitmap | Creates a Roaring bitmap from an integer array. |
|
rb_and | roaringbitmap,roaringbitmap | roaringbitmap | Performs an AND operation. |
|
rb_or | roaringbitmap,roaringbitmap | roaringbitmap | Performs an OR operation. |
|
rb_xor | roaringbitmap,roaringbitmap | roaringbitmap | Performs an XOR operation. |
|
rb_andnot | roaringbitmap,roaringbitmap | roaringbitmap | Performs an ANDNOT operation. |
|
rb_cardinality | roaringbitmap | integer | Calculates the cardinality of a Roaring bitmap. |
|
rb_and_cardinality | roaringbitmap,roaringbitmap | Integer | Calculates the cardinality from an AND operation on two Roaring bitmaps. |
|
rb_or_cardinality | roaringbitmap,roaringbitmap | Integer | Calculates the cardinality from an OR operation on two Roaring bitmaps. |
|
rb_xor_cardinality | roaringbitmap,roaringbitmap | Integer | Calculates the cardinality from an XOR operation on two Roaring bitmaps. |
|
rb_andnot_cardinality | roaringbitmap,roaringbitmap | Integer | Calculates the cardinality from an ANDNOT operation on two Roaring bitmaps. |
|
rb_is_empty | roaringbitmap | boolean | Checks whether a Roaring bitmap is empty. |
|
rb_equals | roaringbitmap,roaringbitmap | boolean | Checks whether two Roaring bitmaps are the same. |
|
rb_intersect | roaringbitmap,roaringbitmap | boolean | Checks whether two Roaring bitmaps intersect. |
|
rb_remove | roaringbitmap,integer | roaringbitmap | Removes an offset from a Roaring bitmap. |
|
rb_flip | roaringbitmap,integer,integer | roaringbitmap | Flips specific offsets in a Roaring bitmap. |
|
rb_minimum | roaringbitmap | integer | Returns the smallest offset in a Roaring bitmap. If the Roaring bitmap is empty, the value -1 is returned. |
|
rb_maximum | roaringbitmap | integer | Returns the largest offset in a Roaring bitmap. If the Roaring bitmap is empty, the value 0 is returned. |
|
rb_rank | roaringbitmap,integer | Integer | Returns the number of elements that are smaller than or equal to a specified offset in a Roaring bitmap. |
|
rb_iterate | roaringbitmap | setof integer | Returns a list of offsets from a Roaring bitmap. |
|
Bitmap aggregate functions
Function | Input data | Message | Description | Examples |
---|---|---|---|---|
rb_build_agg | Integer | roaringbitmap | Creates a Roaring bitmap from a group of offsets. |
|
rb_or_agg | roaringbitmap | roaringbitmap | Performs an OR aggregate operation. |
|
rb_and_agg | roaringbitmap | roaringbitmap | Performs an AND aggregate operation. |
|
rb_xor_agg | roaringbitmap | roaringbitmap | Performs an XOR aggregate operation. |
|
rb_or_cardinality_agg | roaringbitmap | integer | Calculates the cardinality from an OR aggregate operation on two Roaring bitmaps. |
|
rb_and_cardinality_agg | roaringbitmap | integer | Calculates the cardinality from an AND aggregate operation on two Roaring bitmaps. |
|
rb_xor_cardinality_agg | roaringbitmap | integer | Calculates the cardinality from an XOR aggregate operation on two Roaring bitmaps. |
|