Bitmap access: combine candidate sets, then recheck what was lost

A persistent bitmap index is a stored representation whose design may associate bit vectors with values or ranges, often with compression. A PostgreSQL Bitmap Index Scan instead builds a temporary in-memory candidate-location structure from an ordinary supported index access path. Several such results can be combined by BitmapAnd or BitmapOr, then consumed by a Bitmap Heap Scan. Calling that plan a persistent bitmap index conflates the search structure with the execution strategy. Their write behavior and storage requirements can be very different.

For an exact row-location model, an AND keeps only locations reported by every contributing predicate; an OR keeps locations reported by at least one. Duplicate locations in an OR are visited once in the set representation. Candidate row identities must refer to compatible table storage and snapshot processing, not arbitrary identifiers from unrelated tables. A combined candidate still needs the normal visibility and any required predicate checks. Set algebra organizes where to look; it does not create transaction semantics or make an approximate access method exact.

Under memory pressure, a transient bitmap can represent a whole heap page rather than every matching tuple offset on that page. This lossy entry means that relevant candidates may be somewhere on the page, not that every row satisfies the original condition. The executor must inspect the page's tuples and recheck the necessary predicates. Access methods can also return lossy candidates for other reasons. Do not infer that a visible Recheck Cond means every page was lossy; examine exact and lossy page statistics and the access method's contract.

MVCC visibility is a separate check from predicate truth. A row location can pass the indexed condition but reference a version the current query cannot see. An exact tuple bitmap does not remove visibility processing, and a lossy bitmap does not authorize returning false matches. Conversely, lossy representation must preserve a superset of required candidates so matching rows are not omitted. When evaluating memory settings, compare added recheck work and page visits against memory consumption rather than treating a smaller bitmap as automatically faster.

Visiting heap pages in physical order can improve locality, but it discards the original B-tree result order. A query requiring ORDER BY may therefore need a separate sort, and a small LIMIT may favor an ordered index scan that stops early. Combining two selective indexes also requires performing both searches and building the bitmap. A planner can rationally choose one index plus filtering, a composite index, or a sequential scan instead. The useful choice depends on candidate density, page distribution, cache state, and sorting costs.

The cache lab isolates page reuse rather than building a bitmap. Reset, set C=4 and s=4, predict twelve hits in the initial sixteen requests, then Play or Step. Separately Reset, set C=4 and s=1, predict zero hits because the sixteen-address cycle exceeds capacity, then Play or Step. The model cannot reorder a real candidate list, expose lossy tuple bits, or perform rechecks. Use it to explain why the mapping from rows to physical pages matters, while doing the actual candidate intersections on paper.