RDS for PostgreSQL
RDS for PostgreSQL
Document
- Documentation
RDS for PostgreSQL User guideExtensionsBitmap computing (pg_roaringbitmap)
Copy page
Download PDFExtensions
Bitmap computing (pg_roaringbitmap)
Copy pageDownload PDFBitmap computing (pg_roaringbitmap)
The pg_roaringbitmap extension is an efficient bitmap storage and computing extension.
Implementation principle
The RoaringBitmap algorithm mainly addresses the fixed space consumption issue of traditional Bitmap. It reduces Bitmap space usage while providing high-performance bitmap computing. In the most extreme scenarios, traditional bitmap may occupy a large space even when storing only two numbers. For example, storing the numbers 0 and 1,000,000 requires traditional bitmap to pre-allocate 1,000,001 bits, about 125 KB of space; but Roaringbitmap only requires 8 bytes in this case.
Classic RoaringBitmap algorithm
The classic RoaringBitmap algorithm divides each 32-bit signed integer in the set [-2147483648, 2147483647] into two parts: high 16 bits + low 16 bits. The high 16 bits serve as the first-level index for storage and retrieval, while the low 16 bits are the secondary data stored in Containers. Containers have two Types: Array Container and Bitmap Container, as shown below:
In the above Roaring bitmap, the 4-byte integer values stored have high 16Bits of 0x0000, 0x0001, 0x0002 respectively:
- High 16 bits 0x0000: stored using an ordered Array Container, containing the first 1000 multiples of 62.
- High 16 bits 0x0001: stored using an ordered Array Container, containing 100 integers in the range [216, 216+100).
- High 16 bits 0x0002: stored using a Bitmap Container, containing 215 even numbers in the range [216, 3×216).
The choice between Array Container and Bitmap Container depends on the number of 16Bit integers stored in the corresponding Container. The details are as follows:
- When the number of 16Bit integers stored in the Container is less than or equal to 4096, the maximum space occupied by a single Container is 4096 * 16Bit = 8KB, and an array container is used for storage;
- When the number of 16Bit integers stored in the Container is greater than 4096, a Bitmap container is used for storage. The space occupied by a single Bitmap container is fixed at: 216Bit = 8KB.
RoaringBitmap used by the extension
The RoaringBitmap used by the Extension adopts an algorithm that adds run container optimization to the classic RoaringBitmap algorithm, optimizing bitmaps with step properties. The details are as follows:
In the above Roaring bitmap, the 4-byte integer values stored have high 16Bits of 0x0000, 0x0001, 0x0002 respectively:
- High 16Bit 0x0000: stored in an array container ordered array, storing the first 1000 integers that are multiples of 62
- High 16Bit 0x0001: stored in a run container in compressed form, storing three intervals [216, 216 + 100), [216 + 101, 216 + 201), [216 + 300, 216 + 400) totaling 300 integers, with the container occupying only 6Bit.
- High 16Bit 0x0002: stored in a bitmap container, storing 215 even numbers in the range [2×216, 3×216).
Install extension
Use the following command to install the extension.
tip
A super account is required to create the extension.
create extension roaringbitmap;
tip
A super account is required to create the extension. Instructions
Data type
Type name | roaringbitmap |
Usage example | select '{}'::roaringbitmap; select ' { } '::roaringbitmap; select '{ 1 }'::roaringbitmap; select '{-1,2,555555,-4}'::roaringbitmap; select '{ -1 , 2 , 555555 , -4 }'::roaringbitmap; select '{ 1 , -2 , 555555 , -4 }'::roaringbitmap; select '{ 1 , -2 , 555555 , -4 ,2147483647,-2147483648}'::roaringbitmap; select roaringbitmap('{ 1 , -2 , 555555 , -4 }'); select '{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400}'::roaringbitmap; |
GUC
Parameter name | roaringbitmap.output_format |
Parameter description | character type, used to control the output format of roaringbitmap type, value range: array and bytea, default value is bytea
|
Usage | set roaringbitmap.output_format = 'array'; select '{-1,2,555555,-4}'::roaringbitmap; set roaringbitmap.output_format = 'bytea'; select '{-1,2,555555,-4}'::roaringbitmap; set roaringbitmap.output_format = 'array'; select '\x3a300000030000000000000008000000ffff01002000000022000000240000000200237afcffffff'::roaringbitmap; sysbench=> set roaringbitmap.output_format = "array"; SET sysbench=> select '{-1,2,5555555,-4}':: roaringbitmap; roaringbitmap ------------------ {2,555555,-4,-1} (1 row) sysbench=> sysbench=> set roaringbitmap.output_format = 'bytea'; SET sysbench=> select '{-1,2,55555,-4}'::roaringbitmap; roaringbitmap ---------------------------------------------------------------------------------- \x3a300000030000000000000008000000ffff01002000000022000000240000000200237afcffffff sysbench=> sysbench=> select '\x3a300000030000000000000008000000ffff01002000000022000000240000000200237afcffffff'::roaringbitmap; roaringbitmap ----------------------------------------------------------------------------------- \x3a300000030000000000000080000000ffff01002000000022000000240000000200237afcfffffff (1 row) sysbench=> set roaringbitmap.output_format = 'array' SET sysbench=> select '\x3a300000030000000000000008000000ffff01002000000022000000240000000200237afcffffff'::roaringbitmap; roaringbitmap ---------------- {2,555555,-4,-1} (1 row) sysbench=> |
Functions and operators
helper functions
used to generate integer arrays of specified dimensions.
create or replace function gen_array(dim int4)
returns int4[]
as $$
select array_agg((random()* 1000000)::int4) from generate_series(1, dim)
$$
language sql
volatile
cost 1;
Functions and operators
Functions
Aggregate functions
drop table tbl_rb_agg;
create table tbl_rb_agg(id serial, rb roaringbitmap);
insert into tbl_rb_agg(rb) select rb_build('{1,2,3,4,5}');
insert into tbl_rb_agg(rb) select rb_build('{3,4,5,6,7}');
insert into tbl_rb_agg(rb) select rb_build('{4,5,6,7,8,9}');
select * from tbl_rb_agg;
sysbench=> drop table tbl_rb_agg;
DROP TABLE
sysbench=> create table tbl_rb_agg(id serial, rb roaaringbitmap);
CREATE TABLE
sysbench=>
sysbench=> insert into tbl_rb_agg(rb) select rb_build('{1,2,3,4,5}');
INSERT 0 1
sysbench=> insert into tbl_rb_agg(rb) select rb_build('{3,4,5,6,7}');
INSERT 0 1
sysbench=> insert into tbl_rb_agg(rb) select rb_build('{4,5,6,7,8,9}');
INSERT 0 1
sysbench=> select * from tbl_rb_agg;
id | rb
---+-------------————
1 | {1,2,3,4,5}
2 | {3,4,5,6,7}
3 | {4,5,6,7,8,9}
(3 rows)
Last updated: 2026.01.13 18:44:18
All rights reserved © Beijing Volcano Engine Technology Co., Ltd2024
