existence-bitmap · shipping · also EBM

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

related
Bitmap index, Bitmap heap scan (PostgreSQL)

Citations

  1. O'Neil and Quass (SIGMOD 1997): Improved Query Performance with Variant Indexes, sections 2.1.2 and 2.3 (accessed 2026-11-19)
  2. PostgreSQL 18: comparison predicates, including IS NOT TRUE (accessed 2026-11-19)
  3. SQLite: isolation and held WAL reader snapshots (accessed 2026-11-19)
  4. Hesela: bitmap negation, synthetic set models and native SQLite controls (accessed 2026-11-19)
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

JSON: /data/terms/existence-bitmap.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Existence bitmap. Hesela. 2026-11-19. https://hesela.dev/terms/existence-bitmap/