Existence bitmap
An existence bitmap marks which positions in a row-identifier mapping correspond to existing rows, bounding set operations to that domain.
Domain: Allocated row slots can contain holes. O'Neil and Quass bound bitmap complement by the existence bitmap, so inversion does not manufacture nonexistent rows. Their read-mostly warehouse setting is distinct from modern concurrent snapshot visibility. [1]
Truth: Existence does not establish predicate truth. For exact masks E of visible rows, T of TRUE results and N of UNKNOWN results at one snapshot, WHERE NOT p selects E & ~(T | N); p IS NOT TRUE selects E & ~T. N is the predicate's unknown set, not always a column's NULL mask. [2]
Approximation: If a positive candidate set contains all true matches plus false positives, its complement omits those false-positive rows from the negative answer. Rechecking surviving rows cannot restore omitted rows. Refine the positive set first, or retain a complete negative candidate bound. The worked proof and native controls are application-side examples, not a database defect. [4]
Identity: Combine masks only with a compatible row mapping, domain and snapshot. An existence bitmap is neither a PostgreSQL visibility map nor a certificate that a candidate satisfies its predicate. The published WAL control deliberately mixes exported masks; SQLite itself retains the reader's original snapshot. [3] [4]
Relations
Citations
- O'Neil and Quass (SIGMOD 1997): Improved Query Performance with Variant Indexes, sections 2.1.2 and 2.3
- PostgreSQL 18: comparison predicates, including IS NOT TRUE
- SQLite: isolation and held WAL reader snapshots
- Hesela: bitmap negation, synthetic set models and native SQLite controls
Sources & caveats
- Source synthesis and elementary set derivation. The native illustration uses SQLite 3.45.1 on tiny constructed integer/NULL data; it is not a PostgreSQL experiment, performance benchmark or fleet measurement.
- Machine-readable results and runnable code: https://hesela.dev/research/bitmap-negation/README.md