Is it possible to use bitmap index with more than two possible values?

Question

It clear how bitmap indexes works with two possible values (gender: male and female). But how is it possible to use with 3 or more values? Can anyone explain how it works in postgresql?

Answer 1

PostgreSQL does not have a bitmap index, it can do bitmap index scans over regular B-tree indexes.

For that it is not important how many values the indexed column (or columns) can have.

This is how it works:

• The index is scanned for the search condition.

• Rather than visiting the table for each row found, PostgreSQL builds a bitmap. This bitmap normally has one bit per table row, and the rows are sorted in physical address (ctid) order. The value of the bit indicates if that row matches the search condition or not (which has nothing to do with the value range of the indexed columns).

  If work_mem is too small to contain a bitmap with one bit per row, PostgreSQL degrades to storing one bit per 8KB page. This shows up as “lossy” entries in the EXPLAIN (ANALYZE) output and will lead to false positive hits in the next step which affects performance.

• During a second step, the bitmap heap scan, PostgreSQL visits the table and fetches (and re-checks, if necessary) all rows that show a hit in the bitmap.

The advantages of a bitmap index scan are:

• Even if many rows are selected, PostgreSQL has to visit each table block only once, and the rows are visited in physical order.

• Several bitmap index scans on the same table can be combined with a “bitmap AND” or a “bitmap OR” before the table is scanned. This can handle ORs efficiently and combine several conditions with AND if each of the conditions alone is not selective enough to warrant an index scan.