Bitmap index
A bitmap index represents indexed predicates as sets of row identifiers encoded by bitmaps, allowing queries to combine those sets.
Encoding: In an equality-encoded index, each distinct attribute value has a bitmap whose set bits identify matching rows. Range encoding instead represents cumulative predicates. Encoding determines the meaning of a bit; compression determines how those bits are stored. [1]
Queries: For compatible row-identifier mappings, AND intersects candidate sets and OR combines them. Bitmap operations can evaluate several predicates before fetching table rows. A bitmap index is therefore more than a dense bit vector, and its bitmaps need not all use the same physical representation. [2]
Design: Attribute cardinality, row ordering, encoding, compression and the query mix jointly affect space and work. Low cardinality alone does not establish the best design. Maintaining several index encodings adds storage and update work. [1]
Storage: Roaring partitions integer identifiers into containers and chooses among sorted arrays, bitsets and runs. This is one exact set representation, not an approximate membership test with false positives. [3]
Negation: Complement needs a bounded row universe and the predicate's unknown set. A positive candidate superset cannot simply be inverted into a complete negative result: its false positives become missing negative rows. See the source-backed existence-bitmap contract and runnable example. [4]
Relations
Citations
- Chan and Ioannidis (1998), Bitmap Index Design and Evaluation, SIGMOD, pp. 355-366; DOI 10.1145/276304.276336
- Lemire et al., Roaring Bitmaps: Implementation of an Optimized Software Library, arXiv:1709.07821v6, section 1
- Lemire, Ssi-Yan-Kai and Kaser, Consistently faster and smaller compressed bitmaps with Roaring, arXiv:1603.06549v4
- Hesela: bitmap complement, predicate truth and snapshot identity
Sources & caveats
- Source synthesis of bitmap-index design, not a query-engine benchmark. The SIGMOD 1998 study focuses on selection queries in read-mostly environments. [1]
- Combining sets presupposes compatible row identities and a suitable database visibility policy; bitmap encoding alone does not supply transaction isolation.