This topic describes how to use the roaringbitmap plug-in provided by ApsaraDB RDS for PostgreSQL to improve query performance.

Prerequisites

Your RDS instance runs PostgreSQL 12.

Background information

The Roaring bitmap algorithm divides 32-bit integers into 2 16 chunks. Each chunk stores the 16 most significant digits and uses a container to store the 16 least significant digits. A Roaring bitmap stores containers in a dynamic array as primary indexes. Two types of containers are available: array containers for sparse chunks and bitmap containers for dense chunks. An array container can store up to 4,096 integers. A bitmap container can store more than 4,096 integers.

Roaring bitmaps can use this storage structure to rapidly retrieve specific values. Additionally, Roaring bitmaps provide bitwise operations such as AND, OR, and XOR between the two types of containers. Therefore, Roaring bitmaps can deliver excellent storage and computing performance.

Procedure

  1. Create a plug-in. Example:
    CREATE EXTENSION roaringbitmap;
  2. Create a table with roaringbitmap data. Example:
    CREATE TABLE t1 (id integer, bitmap roaringbitmap);
  3. Call the rb_build function to insert roaringbitmap data. Example:
    -- Set the bit value of 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;
  4. Perform bitwise operations such as OR, AND, XOR, and ANDNOT. Example:
    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. Perform bitwise aggregate operations such as OR, AND, XOR, and BUILD to generate a new Roaring bitmap. Example:
    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. Calculate the cardinality of the Roaring bitmap. The cardinality is the number of bits that are set to 1 in the Roaring bitmap. Example:
    SELECT RB_CARDINALITY(bitmap) FROM t1;
  7. Obtain the subscripts of the bits that are set to 1. Example:
    SELECT RB_ITERATE(bitmap) FROM t1 WHERE id = 1;

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 from 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 from 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 from 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 from 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 an offset from a Roaring bitmap.
rb_remove(rb_build('{1,2,3}'),3)
rb_flip roaringbitmap,integer,integer roaringbitmap Flips specific offsets 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, the value -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, the value 0 is returned.
rb_maximum(rb_build('{1,2,3}'))
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_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}'))

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 from 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 from 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 from an XOR aggregate operation on two Roaring bitmaps.
rb_xor_cardinality_agg(rb_build('{1,2,3}'))