Bitmap Index Scans and the Order of Heap Fetches

A plan that uses one index and fetches rows in index order is optimal when the index’s order matches the table’s physical order and pessimal when it does not. A plan that combines two indexes has no single order to inherit, because the two indexes disagree about which rows come first. The bitmap scan exists to resolve both problems at once, by separating the question of which rows match from the question of in what order to visit them.

Collecting row identifiers before fetching anything

A bitmap scan executes in two phases. The first phase runs one or more index scans, each producing a stream of row identifiers, and builds a bitmap in which bit $i$ is set if row $i$ matches. The second phase walks the bitmap in physical order and fetches the matching rows from the heap.

The separation is the whole point. In the first phase, the index is scanned in index order, which is sequential within the index and which is the only order the index can offer. In the second phase, the rows are visited in heap order, which is sequential within the heap. Each structure is traversed in the order it prefers, and the random access that a plain index scan would incur at every row is replaced by a single ordered pass over the heap.

The ordering key for the second phase is the row’s physical location, which in a heap table is a page number plus a slot. Sorting the matching identifiers by that pair groups all rows on the same page together, so each heap page is read once and all its matching rows are extracted before moving on. For a scan matching $r$ rows spread over $p$ pages, the fetch cost drops from $r$ page reads to $p$ page reads, and $p$ is at most the table’s page count.

Combining predicates inside the bitmap

The second index scan has an advantage the first does not: it can be combined bitwise rather than row-by-row. An AND of two predicates is a bitwise AND of their bitmaps, an OR is a bitwise OR, and a NOT is a complement over the bitmap’s universe. Each combination is linear in the bitmap’s size and does not require probing the other index per row, which is what a nested-loop join of two index scans would cost.

This makes bitmap scans the natural plan for a conjunction of predicates on separately indexed columns, a shape that a plain index scan handles badly: with two single-column indexes, the engine can use one and filter on the other, which means fetching every row the first index matches and discarding most of them. With bitmaps, it intersects the identifier sets first and fetches only the rows that satisfy both.

The combination also has a cost that is easy to overlook: the bitmap must cover the whole range of row identifiers, not just the matching ones, because a bitmap is indexed by identifier. A table whose identifiers are dense integers compresses well; a table with sparse or widely separated identifiers wastes bitmap space on the gaps. The usual encoding is a compressed bitmap over the identifier space, where a long run of zeros costs a few bytes rather than one bit per identifier, and the choice of encoding determines whether a bitmap on a sparse table is compact or pathological.

The bitmaps are built in memory and are subject to a memory budget. When the budget is exceeded, the engine either degrades the plan to a plain index scan, or converts the bitmap into an ordered list of identifiers and spills it, losing the constant-time combination in favour of a merge. The threshold is a planner decision and it is why the same query can take a bitmap plan on one execution and an index scan on another: the plan depends on an estimate of how many rows match, and the estimate can be wrong.

Compression: run-length and roaring

A bitmap over a billion row identifiers is 125 MB if stored one bit per identifier, which is too large to build per query. Two encodings dominate.

The run-length encoding stores alternating run lengths, so a dense region of matching rows costs a small integer per run rather than a bit per row. It is excellent for clustered matches and terrible for alternating matches, where every run has length one and the encoding is larger than the raw bitmap.

Roaring bitmaps partition the identifier space into blocks of 65536 identifiers, and store each block either as a sorted array of set positions, as a bitmap, or as run-length encoded runs, choosing per block by size. A dense block is a bitmap of 8 KiB; a sparse block is an array of 2-byte positions. Combination is per block, so the cost is proportional to the number of non-empty blocks rather than to the identifier space, which is what makes a bitmap over a billion identifiers tractable when only a few million match.

The practical consequence for an index design is that bitmap combination is cheap when the matches are either very dense or very sparse, and expensive in the middle, where every block is partially full and neither encoding is compact. That middle is also where the plan is most likely to be chosen, since a predicate matching a few percent of rows is exactly the case a bitmap scan is for.

What the reordering costs

Losing index order has a price that is not obvious from the fetch count. If the query has an ORDER BY on the indexed column, the bitmap scan destroys the ordering and the engine must sort, which is a full sort of the result and can be more expensive than the fetch it saved. If the query has a LIMIT, the plain index scan can stop after the first $k$ rows, whereas the bitmap scan must build the whole bitmap before it knows which rows come first physically, so the limit is applied after the entire matching set is known. A query for the ten most recent rows by an indexed timestamp is the canonical case where the bitmap scan is the wrong plan, and a planner that costs a bitmap scan without accounting for the limit will produce a slow plan for exactly that query.

The second cost is that the bitmap must be complete before the fetch begins, so the scan’s latency to first row is the time to scan the entire index range, not the time to find one row. For an interactive query returning a small result from a large range, that is a real difference in perceived latency even when total work is lower.

The third cost is that a bitmap scan cannot easily serve as the inner side of a nested-loop join, because the inner side is executed once per outer row and building a bitmap per outer row is wasteful. The plan shape that suits a bitmap is a single pass over a large range, and a join that would probe it many times should use a different access path.

Visibility and the fetch

The second phase fetches heap pages, and in a system with multi-version concurrency control the fetched row version may not be the one visible to the transaction. The bitmap records identifiers, not versions, so the heap fetch must check visibility, and rows that fail the check are discarded. A bitmap built from an index that stores visibility information can avoid the check for some pages, but for pages with recent modifications the check requires reading the heap page anyway, which is the fetch the bitmap was trying to make efficient.

The same interaction appears in the index-only scan discussion: the fetch is avoided only when visibility is certain without it. A bitmap scan always fetches, because its purpose is to order the fetch, not to avoid it. That is why a covering index with a bitmap scan is a combination that gains nothing: the bitmap’s benefit is page ordering, and the covering index’s benefit is not reading pages at all.

A bitmap scan on a clustered table has a further wrinkle. The row identifier in a secondary index of a clustered table is the primary key, not a physical location, so a bitmap over secondary index entries is a set of primary keys, and the physical ordering must be recovered by looking up each primary key in the clustered index. That is a random descent per row, which defeats the purpose. Engines that support bitmap scans on clustered tables therefore either maintain a mapping from primary key to physical location for the scan, or restrict the technique to heap-organized tables. The ordering benefit of a bitmap is fundamentally a property of having a stable physical address per row, which is the thing a clustered table deliberately gives up.

When the plan is chosen and when it is wrong

The planner chooses a bitmap scan when the estimated number of matching rows is large enough that fetching in index order would touch many pages, and small enough that a sequential scan of the whole table would read more pages than the matching set requires. The lower bound is where the bitmap’s fixed cost — building and sorting — dominates; the upper bound is where the table scan’s sequential advantage dominates.

Both bounds depend on the clustering of the index relative to the table, and the statistic that captures it is the same clustering factor described in clustered and secondary access paths. A well-clustered index makes the plain index scan nearly as good as the bitmap, because the rows it fetches are already in page order, and the bitmap’s reordering buys little. A badly clustered index makes the bitmap much better, because the plain scan would touch a different page per row. The planner’s estimate of this factor is therefore as important as its estimate of the row count, and a stale statistic produces a plan that is not merely suboptimal but wrong by an order of magnitude.