Hologres:roaringbitmap

How it works

A roaring bitmap divides 32-bit integers into 2^16 chunks. Integers in the same chunk share the same 16 most significant bits; the 16 least significant bits are stored in a container. Containers are held in a dynamic array as primary indexes.

Two container types balance storage and performance:

This structure enables fast value retrieval and efficient bitwise operations (AND, OR, XOR) between containers.

Limits

• Only exclusive instances of Hologres V0.10 and later support roaring bitmap functions.

  Check your instance version in the Hologres console. If the version is earlier than V0.10, upgrade the instance in the console or join the DingTalk group for technical support. See Common upgrade preparation failure errors and Obtain online support for Hologres.

• Roaring bitmap functions are loaded to the public schema by default and can only be loaded to the public schema.

• Starting from Hologres V3.1, the RoaringBitmap64 data type is supported. Some roaring bitmap functions can process data of the RoaringBitmap64 type. When processing RoaringBitmap64 data, these functions do not support constant input parameters.

• Before using roaring bitmap functions, enable the extension with the following statement. The extension is database-scoped — run this once per database. Repeat for any new database you create.

  -- Enable the extension.
  CREATE EXTENSION roaringbitmap;

  To drop the extension:

  DROP EXTENSION roaringbitmap;

  Important

  Avoid DROP EXTENSION <extension_name> CASCADE;. The CASCADE option removes the extension along with all its data and dependent objects — including PostGIS data, roaring bitmap data, Proxima data, binary log data, and BSI data, and dependent metadata, tables, views, and server objects.

• Roaring bitmap columns cannot be specified as bitmap or dictionary indexes.

• When creating a table with a roaring bitmap column, explicitly specify the column type as roaringbitmap (32-bit) or roaringbitmap64 (64-bit). Mixed calculations between the two types are not supported.

  -- Create a table with a 32-bit roaring bitmap column.
  CREATE TABLE t_rb_32 (
      bucket int,
      x roaringbitmap
  );
  
  -- Create a table with a 64-bit roaring bitmap column.
  CREATE TABLE t_rb_64 (
      bucket int,
      x roaringbitmap64
  );
  
  -- Mixed calculations return an error.
  -- ERROR: operator does not exist: roaringbitmap & roaringbitmap64
  SELECT
      a.x & b.x
  FROM
      t_rb_32 a
  JOIN t_rb_64 b ON a.bucket = b.bucket;

Operators

All operators below support both RoaringBitmap and RoaringBitmap64 types unless otherwise noted.

Roaring bitmap functions

-- Prepare data.
CREATE TABLE public.tn (
    id INT,
    num BIGINT[]
);
INSERT INTO public.tn ("id", "num") VALUES (01, '{1,2}');

SELECT rb64_build(num) rb_num, num FROM public.tn;

rb_num                                                                          | num
--------------------------------------------------------------------------------+------
\x030100000000000000000000003a30000001000000000001001000000001000200             | {1,2}

-- Create a sample table.
CREATE TABLE rb_text (
    id int,
    a text
);

-- Insert data.
INSERT INTO rb_text
    VALUES (1, '\x3a300000010000000000090010000000010002000300040005000600070008000900c800');

-- Convert to RoaringBitmap and compute AND cardinality.
SELECT
    rb_and_cardinality_agg(roaringbitmap_in(a::cstring))
FROM
    rb_text;

 rb_and_cardinality_agg
------------------------
                     10

Roaring bitmap aggregate functions

-- OR aggregate: returns the union of all input bitmaps.
SELECT rb_or_agg(bitmap)
FROM (VALUES
    (rb_build('{1,2,3}')),
    (rb_build('{2,3,4}'))
) t(bitmap);
-- Result: {1,2,3,4}

-- AND aggregate: returns the intersection of all input bitmaps.
SELECT rb_and_agg(bitmap)
FROM (VALUES
    (rb_build('{1,2,3}')),
    (rb_build('{2,3,4}'))
) t(bitmap);
-- Result: {2,3}

-- OR cardinality aggregate.
SELECT rb_or_cardinality_agg(bitmap)
FROM (VALUES
    (rb_build('{1,2,3}')),
    (rb_build('{2,3,4}'))
) t(bitmap);
-- Result: 4

-- AND cardinality aggregate.
SELECT rb_and_cardinality_agg(bitmap)
FROM (VALUES
    (rb_build('{1,2,3}')),
    (rb_build('{2,3,4}'))
) t(bitmap);
-- Result: 2

-- XOR aggregate: returns elements in exactly one of the two bitmaps.
SELECT rb_xor_agg(bitmap)
FROM (VALUES
    (rb_build('{1,2,3}')),
    (rb_build('{2,3,4}'))
) t(bitmap);
-- Result: {1,4}

-- XOR cardinality aggregate.
SELECT rb_xor_cardinality_agg(bitmap)
FROM (VALUES
    (rb_build('{1,2,3}')),
    (rb_build('{2,3,4}'))
) t(bitmap);
-- Result: 2

Other roaring bitmap functions

The following functions support only the RoaringBitmap (32-bit) type.

Examples

The following end-to-end example shows a complete workflow: enable the extension, create a table, insert data, run bitwise operations, and inspect the results.

1. Enable the extension.

   CREATE EXTENSION roaringbitmap;

2. Create a table to store roaring bitmap data.

   -- Create table t1.
   CREATE TABLE public.t1 (id integer, bitmap roaringbitmap);

3. Insert roaring bitmap data.

   -- Build a bitmap from an explicit array.
   INSERT INTO public.t1 SELECT 1, RB_BUILD(ARRAY[1,2,3,4,5,6,7,8,9,200]);
   
   -- Build a bitmap by aggregating a generated series.
   INSERT INTO public.t1 SELECT 2, RB_BUILD_AGG(e) FROM GENERATE_SERIES(1,100) e;

4. Run bitwise operations.

   -- OR the two bitmaps.
   SELECT RB_OR(a.bitmap, b.bitmap)
   FROM (SELECT bitmap FROM public.t1 WHERE id = 1) AS a,
        (SELECT bitmap FROM public.t1 WHERE id = 2) AS b;

   Expected output (the union of {1..9, 200} and {1..100}):

    rb_or
   -------
    {1,2,3,4,5,6,7,8,9,10,...,100,200}

5. Run aggregate operations to combine all bitmaps in the table.

   SELECT RB_OR_AGG(bitmap)  FROM public.t1;  -- union of all bitmaps
   SELECT RB_AND_AGG(bitmap) FROM public.t1;  -- intersection of all bitmaps
   SELECT RB_XOR_AGG(bitmap) FROM public.t1;  -- symmetric difference
   SELECT RB_BUILD_AGG(id)   FROM public.t1;  -- build a bitmap from the id column

6. Calculate cardinality (the count of set bits).

   SELECT RB_CARDINALITY(bitmap) FROM public.t1;

   Expected output:

    id | rb_cardinality
   ----+----------------
     1 |             10
     2 |            100

7. List all set offsets.

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

   Expected output:

    rb_iterate
   ------------
             1
             2
             3
             4
             5
             6
             7
             8
             9
           200

8. Convert a roaring bitmap to an array.

   SELECT RB_TO_ARRAY(bitmap) FROM public.t1 WHERE id = 1;

   Expected output:

              rb_to_array
   --------------------------------
    {1,2,3,4,5,6,7,8,9,200}