Contents

• pgbitmap - Bitmap Extension for Postgres
• Status
• Change History
• Doxygen Docs
• Why not use the Postgres Bitstring Type?
• What is this useful for?
• API Summary
• API Details and Examples
  • Conversion to and from text
  • Creating bitmaps
  • Bit Manipulation and Testing
  • Bitmap Range Functions
  • Bitmap Comparison Functions and Operators
  • Set Operations on Bitmaps
  • Extracting all Elements of a Bitmap
  • Bitmap Aggregates
  • Installing pgbitmap using pgxn
  • Building pgbitmap Manually

pgbitmap - Bitmap Extension for Postgres

This extension creates a space-optimised, non-sparse, bitmap type for postgres.

A bitmap is an array of bits, indexed by an integer. Bitmaps provide an efficient means to implement sets and pgbitmap provides operations for:

• creating new bitmaps;
• adding an element to a bitmap;
• removing an element from a bitmap;
• testing for inclusion of an element in a bitmap;
• finding the minimum and maximum bits in the bitmap;
• unioning bitmaps together (set union/logical or);
• intersecting bitmaps (set intersection/logical and);
• subtracting one bitmap from another;
• converting bitmaps to and from textual representations;
• converting bitmaps to and from arrays;
• aggregating bits, and bitmaps, into bitmaps.

Status

This is a beta release. The plan is to give it real-life usage before releasing a production version if all looks well.

There are no known bugs or deficiencies. If you find any problems or want enhancements, contact me and I will do what I can to respond quickly.

Change History

0.2 (alpha) Initial release

0.3 (alpha) Fix for bitmap corruption when adding bit to empty bitmap.

0.5 (alpha) Change name of extension to pgbitmap from bitmap.

0.6 (alpha) Minor fixes to Makefiles find_pg_config and docs

0.9 (beta) Minor updates to documentation and to allow distribution through pgxn. Updated to Beta status as it all seems stable enough.

0.9.1 (beta) Updated to convince pgxn to fully index the extension.

0.9.2 (beta) Fix for bitmap union bug on unions of empty bitmaps.

0.9.3 (beta) No-change update for release to PGXN

0.9.4 (beta) Utility functions made available to other extensions.

0.9.5 (beta) Fix to (unused by pgbitmap) definition of DatumGetBitmap

Doxygen Docs

pgbitmap is documented internally using Doxygen, with this page acting as the start page. The current docs can be found here.

Why not use the Postgres Bitstring Type?

The standard Postgres bit type is limited in a number of ways. In particular, each bit string starts at bit zero so a bitstring for bit 1,000,000 would contain the overhead of 1,000,000 zero bits. It also, currently, does not have all of the functionality that this bitmap type provides.

What is this useful for?

Pgbitmap was developed as a means of implementing sets of integers. It is particularly suited for managing sets of privileges for Virtual Private Database implementations.

API Summary

Functions: ```.c bitmap_in(text) -> bitmap

bitmap_out(bitmap) -> text

bitmap() -> bitmap                          implemented by bitmap_new_empty()

bitmap(integer) -> bitmap                   implemented by bitmap_new()

bitmap_setbit(bitmap, integer) -> bitmap

bitmap_testbit(bitmap, integer) -> boolean

bitmap_clearbit(bitmap, integer) -> bitmap

is_empty(bitmap) -> boolean                 implemented by bitmap_is_empty()

bitmin(bitmap) -> integer                   implemented by bitmap_bitmin()

bitmax(bitmap) -> integer                   implemented by bitmap_bitmax()

bitmap_setmin(bitmap, integer) -> bitmap

bitmap_setmax(bitmap, integer) -> bitmap

bitmap_equal(bitmap, bitmap) -> boolean

bitmap_nequal(bitmap, bitmap) -> boolean

bitmap_lt(bitmap, bitmap) -> boolean

bitmap_le(bitmap, bitmap) -> boolean

bitmap_gt(bitmap, bitmap) -> boolean

bitmap_ge(bitmap, bitmap) -> boolean

bitmap_cmp(bitmap, bitmap) -> integer

bitmap_union(bitmap, bitmap) -> bitmap

bitmap_intersection(bitmap, bitmap) -> bitmap

bitmap_minus(bitmap, bitmap) -> bitmap

to_array(bitmap) -> array of integer        

to_bitmap(array of integer) -> bitmap       implemented using aggregate bitmap_of()

```

Set Returning Functions: .c bits(bitmap) -> set of integer implemented by bitmap_bits()

Operators: ```.c bitmap + integer -> bitmap implemented by bitmap_setbit()

bitmap ? integer -> boolean                 implemented by bitmap_testbit()

bitmap - integer -> bitmap                  implemented by bitmap_clearbit()

bitmap = bitmap -> boolean                  implemented by bitmap_equal()

bitmap <> bitmap -> boolean                 implemented using bitmap_equal()

bitmap < bitmap -> boolean                  implemented by bitmap_lt()

bitmap <= bitmap -> boolean                 implemented by bitmap_le()

bitmap > bitmap -> boolean                  implemented by bitmap_gt()

bitmap >= bitmap -> boolean                 implemented by bitmap_ge()

bitmap + bitmap -> bitmap                   implemented by bitmap_union()

bitmap * bitmap -> bitmap                   implemented by bitmap_intersection()

bitmap - bitmap -> bitmap                   implemented by bitmap_minus()

```

Aggregates: ```.c bitmap_of(integer) -> bitmap implemented by bitmap_setbit()

union_of(bitmap) -> bitmap                  implemented by bitmap_union()

intersect_of(bitmap) -> bitmap              implemented by bitmap_intersection()

```

API Details and Examples

Conversion to and from text

``` bitmap_in(text) -> bitmap

bitmap_out(bitmap) -> text

```

The bitmap type has a compact textual representation that is not intended to be human-readable. This textual representation enables bitmaps to be used in hstore, and in text-based backups.

In addition to the functions described above, casts, ::text, ::bitmap, can also be used.

Creating bitmaps

``` bitmap() -> bitmap

bitmap(integer) -> bitmap

to_bitmap(array of integer) -> bitmap

bitmap_of(aggregate of integer) -> bitmap

```

An empty bitmap can be created using bitmap(). A bitmap with a single element included (ie a single bit set to 1) can also be created using bitmap(n). Bitmaps are more usually created from arrays or queries. The following queries return identical bitmaps:

``` select bitmap() + 1 + 2 + 3;

select bitmap(1) + 2 + 3;

select bitmap_setbit(bitmap_setbit(bitmap(1), 2), 3);

select to_bitmap('{1, 2, 3}');

select array[1, 2, 3]::bitmap;

select bitmap_of(x)
  from generate_series(1, 3) x;

```

Bit Manipulation and Testing

``` bitmap_setbit(bitmap, integer) -> bitmap

bitmap + integer -> bitmap

bitmap_clearbit(bitmap, integer) -> bitmap

bitmap - integer -> bitmap

bitmap_testbit(bitmap, integer) -> boolean

bitmap ? integer -> boolean

`` Elements can be added to a bitmap using thebitmap_setbit()function or the+operator. They can be removed usingbitmap_clearbit()or the-operator, and can be tested using thebitmap_testbit() function or the?` operator. The setbit and clearbit functions are rarely directly used in SQL, as array or aggregation operations are usually faster.

This is how you might test for a privilege, in a round-about sort of way: select bitmap_of(privilege_id) ? 42 from my_privileges;

Bitmap Range Functions

``` is_empty(bitmap) -> boolean

bitmin(bitmap) -> integer

bitmin(bitmap) -> integer

bitmap_setmin(bitmap, integer) -> bitmap

bitmap_setmax(bitmap, integer) -> bitmap

``` Bitmaps are stored as ranges of bits. There are a number of functions for checking and manipulating bitmap ranges.

is_empty() returns true if the bitmap contains no elements.

bitmin() returns the lowest value element in the bitmap (ie the lowest bit that is set). If the bitmap is empty, it returns null.

bitmax() returns the highest element in the bitmap, or null if the bitmap is empty.

bitmap_setmin() and bitmap_setmax() can be used to efficiently clear large sections of a bitmap. The result of:

select bitmap_setmin(bitmap_of(x), 200) from generate_series(1, 205) x;

would be a bitmap with elements 200 to 205.

Bitmap Comparison Functions and Operators

``` bitmap_equal(bitmap, bitmap) -> boolean

bitmap_nequal(bitmap, bitmap) -> boolean

bitmap_lt(bitmap, bitmap) -> boolean

bitmap_le(bitmap, bitmap) -> boolean

bitmap_gt(bitmap, bitmap) -> boolean

bitmap_ge(bitmap, bitmap) -> boolean

bitmap_cmp(bitmap, bitmap) -> integer

bitmap = bitmap -> boolean

bitmap <> bitmap -> boolean

bitmap < bitmap -> boolean

bitmap <= bitmap -> boolean

bitmap > bitmap -> boolean

bitmap >= bitmap -> boolean

``` Bitmaps may be compared. This is primarily for the purpose of sorting and indexing. Testing for equality or inequality is probably the only useful comparison from an API perspective.

Set Operations on Bitmaps

``` bitmap_union(bitmap, bitmap) -> bitmap

bitmap_intersection(bitmap, bitmap) -> bitmap

bitmap_minus(bitmap, bitmap) -> bitmap

bitmap + bitmap -> bitmap

bitmap * bitmap -> bitmap

bitmap - bitmap -> bitmap

``` These functions and operators act on a pair of bitmaps to yield a result.

bitmap_union(), the + operator, returns a bitmap containing all elements from both arguments. The following queries return identical results:

``` select bitmap_union(to_bitmap({'1 2 3'}), to_bitmap({'1 3 5'}));

select to_bitmap({'1 2 3 5}');

```

bitmap_intersect(), the * operator, yields the set of common elements from its arguments. The following queries return identical results: ``` select to_bitmap({'1 2 3}') * to_bitmap('{3, 4, 5}');

select bitmap(3);

```

bitmap_minus(), the - operator, yields a bitmap containing all elements from the first argument that do not appear in the second. These queries return identical results: ``` select to_bitmap({'1 2 3}') - to_bitmap('{3, 4, 5}');

select to_bitmap('{1, 2}');

```

Extracting all Elements of a Bitmap

``` to_array(bitmap) -> array of integer

bits(bitmap) -> set of integer

```

These functions return the elements of a bitmap, either as an array, or as a set. Use the set returning function like this: select bits as privilege_id from bits(privileges); The to_array() function can also be invoked as a cast, eg: select privileges::int4[];

Bitmap Aggregates

``` union_of(bitmap) -> bitmap

intersect_of(bitmap) -> bitmap

```

These functions aggregate a collection of bitmaps using the union or intersect operations. Eg to identify all privileges of all members of a group of offices, we could use something like this: select union_of(privs) as office_privs, office_name from user_privs where office_name like '%admin%' group by office_name;

Installing pgbitmap using pgxn

If you're using the pgxn client all you need to do is this: $ pgxn install pgbitmap $ pgxn load -d mydb pgbitmap

Building pgbitmap Manually

Pgbitmap can be built using the standard Postgres PGXS build mechanism as described here [https://www.postgresql.org/docs/12/extend-pgxs.html].

The build will need to be able to find the pg_config executable that matches your Postgres version. It will attempt to find this using find_pg_config (in the top-level pgbitmap directory). If it cannot find pg_config the build will fail.

You can manually define the location in the PG_CONFIG file: $ echo <path to pg_config> >PG_CONFIG

From the pgbitmap directory (the root directory of the extension), use the following commands: $ make To build the extension, followed by:

$ sudo make install To install it. You may then need to stop and restart your database service to have postgres recognise the extension.

To test the installation use:

$ make test

To create html documentation (in docs/html/index.html) use:

$ make docs

You will need to have doxygen and dot installed.