Bitmap indexes: making selectivity multiplicative in the index

How do bitmaps make combining predicates independent of selectivity, and where do they break?

The constraint is that the crossover formula judges each predicate alone. Five predicates that each keep 20% of the rows are all individually useless: each is far past s/r. Their conjunction (all five at once), if the columns are independent, keeps 0.2⁵ = 0.00032 = 0.032% of the rows, which is very much worth an index. The gap between those two facts is where bitmap indexes live.

Represent "the rows that match value v" as a string of N bits (bit i is 1 if row i matches). Then AND, OR and NOT work on whole machine words, 64 rows per instruction. Combining predicates costs about N/64 word operations, independent of selectivity. For N = 10⁸ that is 1.56 million word operations, under a millisecond. You evaluate the whole conjunction inside the index, reach a selectivity that clears the crossover, and only then touch data.

rows matching A: 1 0 1 1 0 1 ...
rows matching B: 1 1 0 1 0 0 ...
A AND B        : 1 0 0 1 0 0 ...     (one instruction per 64 rows)

Space is the obvious problem and the reason for a whole body of research. A naive bitmap index on a column with cardinality c costs N × c bits. That is fine at c = 10 and catastrophic at c = 10⁶. Hence compression, and the scheme the industry converged on, Roaring, picks a representation per chunk of row ids (a sorted array when sparse, a raw bitmap when dense, runs when clustered) and keeps random access while it compresses.

The boundary condition is updates. Flipping one row's value means rewriting chunks, and chunk representations can change type under you. Oracle's bitmap indexes lock at segment granularity on data changes, which is why its documentation says bitmap indexes are for data warehouses. That is not a style preference. It is a concurrency consequence. Bitmap indexes belong to read-mostly systems.

The twist worth carrying away: bitmaps appear as a temporary structure even in systems that have no bitmap index. PostgreSQL's bitmap heap scan builds a throw-away bitmap from one or more B-tree scans, for two reasons: to combine several indexes with AND/OR, and to sort the resulting page references so the table is visited in physical order. The second reason is the one to notice: the bitmap is used to reconstruct clustering at query time. It converts k random fetches into a single ordered pass. It is the clustering problem solved by a bitmap, built on the fly for each query.