Support for Pg index lookup

[tonywong-com]

Our team is looking into more efficient and scalable query approach than the intarray extension with GIN index lookup. We are currently doing performance testing with pg_roaringbitmap, and we couldn't find any reference on GIN index support.

We are wondering if there is any Pg index support, or GIN operator support in the technical roadmap?

---

We have two main SQL use cases for looking up a page of content among 10 million records, with average bitmap cardinality of 10,000.

Use case 1: lookup records by a small array of id's, in this case 2 id's.

SELECT * FROM records WHERE bitmap && roaringbitmap('{30,38}') LIMIT 25;

Because of the lower frequency of the id 30 and 38 among the records' bitmaps. This result in an expensive SeqScan with bitmap Filter before the query planner finds 25 records. It would be great if we can do quick look-up with a bitmap GIN index alone.

Use case 2: lookup records by a large array of id's, in this case 9,900 id's, which is very close to the bitmap cardinality.

SELECT * FROM records WHERE bitmap && roaringbitmap('{1,2,....,9900}') LIMIT 25;

In this case, it is okay for not having GIN index support because the SQL is not selective to begin with, and the pg_roaringbitmap speed boost is very helpful in filtering records quickly.

---

Our concern is mainly with using pg_roaringbitmap for use case 1 above.

[ajcampa]

We have the same problem or need. We need to use an index but we recive the error "data type roaringbitmap has no default operator class for access method 'gist'" even even in PostgreSQL 15. I understand that the roaringbitmap data type defined by the pg_roaringbitmap extension does not have a specific operator class implemented for GIST or BTREE access methods...

[ChenHuajun]

Currently, roaringbitmap can be converted to integer arrays to enable indexed queries as following sample.
There are plans to support GIN indexes for roaringbitmap in the future.

create table and gin index:

CREATE EXTENSION roaringbitmap;
CREATE EXTENSION intarray;
create table tb_test_bitmaps as
  select id,rb_build_agg((random()*1000000)::int) bitmap
    from generate_series(1,100)id, generate_series(1,100000)b
    group by id;
CREATE INDEX tb_test_bitmaps_gin ON tb_test_bitmaps USING GIN (rb_to_array(bitmap) gin__int_ops);

run SQL:

db1=# explain(analyze,buffers)
SELECT id,rb_select(bitmap,5) FROM tb_test_bitmaps
 WHERE rb_to_array(bitmap) @> '{1,3,100}';
                                                   QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
 Seq Scan on tb_test_bitmaps  (cost=0.00..2.50 rows=1 width=36) (actual time=163.468..163.468 rows=0.00 loops=1)
   Filter: (rb_to_array(bitmap) @> '{1,3,100}'::integer[])
   Rows Removed by Filter: 100
   Buffers: shared hit=1801
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.101 ms
 Execution Time: 163.491 ms
(8 rows)

run SQL with gin index:

db1=# set enable_seqscan to off;
SET
db1=# explain(analyze,buffers)
SELECT id,rb_select(bitmap,5) FROM tb_test_bitmaps
 WHERE rb_to_array(bitmap) @> '{1,3,100}';
                                                           QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on tb_test_bitmaps  (cost=55.81..59.83 rows=1 width=36) (actual time=0.072..0.073 rows=0.00 loops=1)
   Recheck Cond: (rb_to_array(bitmap) @> '{1,3,100}'::integer[])
   Buffers: shared hit=10
   ->  Bitmap Index Scan on tb_test_bitmaps_gin  (cost=0.00..55.81 rows=1 width=0) (actual time=0.065..0.065 rows=0.00 loops=1)
         Index Cond: (rb_to_array(bitmap) @> '{1,3,100}'::integer[])
         Index Searches: 1
         Buffers: shared hit=10
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.111 ms
 Execution Time: 0.092 ms
(11 rows)

size of table and gin index:

db1=# select pg_table_size('tb_test_bitmaps'),pg_relation_size('tb_test_bitmaps_gin');
 pg_table_size | pg_relation_size
---------------+------------------
      13303808 |         50323456
(1 row)