Physical Operator Selection and Access Path Mechanics

Two queries over the same table can differ by three orders of magnitude in rows touched while returning identical results. The difference is the access path: the physical mechanism that produces rows from a base table. A logical plan says “scan orders with predicate status = 'open'”. The physical plan says how: read every page and test, descend a B-tree to a matching key range, consult a bitmap of candidate pages, or read only the index because it happens to contain every column needed.

Access path selection is the part of planning with the largest effect on latency and the least dependence on sophisticated cost modelling. The mechanisms have hard structural properties — ordered output, random versus sequential I/O, page revisit counts — and those properties constrain which higher operators can sit above them.

Sequential scan: the baseline and its page accounting

A sequential scan reads every page of the relation’s storage, applies the predicate to each tuple, and emits matches. Its cost is the relation’s size in pages plus the per-tuple predicate evaluation. On a table of a million rows at roughly 100 bytes each, that is on the order of ten thousand pages; reading them sequentially is the cheapest thing a storage device can do, and the predicate evaluation is a tight loop over a contiguous buffer.

The structural property that matters is that a sequential scan is the only access path with no ordering and no assumption about data distribution. It is also the path that benefits most from parallelism: the page range splits cleanly, and each worker scans a disjoint slice.

Two details are often missed. First, a scan can stop early only under a LIMIT without an ORDER BY, because then the first qualifying rows suffice; with a sort above it, the scan must complete. Second, the predicate is evaluated on the stored tuple, which may require detoasting or decoding a variable-length representation. A scan over compressed or columnar storage may therefore have a cost dominated by decompression rather than by I/O, and the row count is a poor predictor of its run time.

B-tree index scans and the visibility problem

An index scan descends the B-tree to the first matching entry, then walks the leaf level in key order, fetching each matching heap tuple. For a predicate matching a small fraction of the table, this touches far fewer pages than a sequential scan. For a predicate matching a large fraction, it is worse: each heap fetch may hit a different page, and a page already read may be revisited many times.

The crossover is a function of clustering. If the index key order correlates with physical row order, the heap fetches are nearly sequential and the scan stays cheap even at high selectivity. If it does not, the scan degenerates into random I/O and a sequential scan wins at a small fraction of matches. Systems estimate this correlation and use it in costing, which is why the same index helps one table and not another.

Index scans also have to deal with visibility. In a system with multi-version concurrency control, an index entry does not by itself say whether the row version it points at is visible to the current snapshot. The index may contain entries for deleted or uncommitted rows, and the scan must check each fetched tuple against the visibility rules. That check costs a fetch even when the tuple turns out to be invisible, which is the mechanism behind the well-known problem of a long-running transaction making an index scan touch far more pages than the number of visible rows suggests.

The output order is the index key order, ascending or descending. That property is often more valuable than the reduced I/O: an ORDER BY on the index key can be satisfied by the scan with no sort, and a merge join can consume the scan directly. The planner must know the ordering to exploit it, and a scan that produces rows in index order but then passes through an operator that destroys the order cannot feed a merge join.

Bitmap scans: collecting candidates before fetching

The bitmap heap scan separates candidate identification from tuple retrieval. The index is scanned first and the tuple identifiers of matching entries are collected into a bitmap, one bit per heap page or one entry per tuple depending on the structure. Only then are the heap pages visited, in physical order, with the bitmap used to test which tuples on each page qualify.

The gain is that each heap page is visited at most once, in ascending page order, instead of being revisited for every matching index entry. For a predicate with moderate selectivity on a non-clustered index, this converts many random fetches into one sequential pass over the candidate pages. The cost is the bitmap itself: memory proportional to the number of candidate pages, and a loss of ordering, because the heap is read in physical order rather than key order.

Bitmaps also combine. Two indexes can each produce a bitmap, and the bitmaps can be intersected (rows matching both predicates) or unioned (rows matching either). This gives the planner a way to use several single-column indexes for a conjunctive predicate, which is otherwise the case where a composite index would be needed. The intersection is exact only at page granularity in the one-bit-per-page variant, so tuples on a shared page are rechecked against both predicates; that recheck is a correctness requirement, not an optimization.

A bitmap scan cannot stream. It must finish collecting candidates before it can emit the first row, which makes it unsuitable under a LIMIT that expects early rows, and it cannot preserve index order for a downstream merge join. Those two limitations are why the path is chosen for moderate selectivity without ordering requirements, and rarely otherwise.

Index-only scans and the covering condition

If every column referenced by the query appears in the index, the scan can answer from the index alone, skipping the heap entirely. This eliminates the per-tuple fetch and, in a versioned system, may still require a visibility check that consults the heap for tuples whose visibility is not recorded in the index. Implementations address that with a visibility map: pages known to contain only tuples visible to all transactions are marked, and index-only scans skip the heap check for those pages. The fraction of marked pages therefore determines how much of the gain is realized, which is why the path’s advantage decays after heavy write activity and returns after vacuuming.

The covering condition is about the query, not the schema. An index on (customer_id, created_at) covers a query selecting those two columns and a count, but not one selecting total. Adding an INCLUDE clause to the index definition stores extra non-key columns in the leaf entries, widening each entry but allowing covering scans for a broader set of queries. The trade is direct: wider leaves mean fewer entries per page, so the index is larger and its scans read more bytes per entry.

Choosing among them without a full optimizer

The mechanisms differ along four axes: how many pages are read, whether reads are sequential, whether output is ordered, and whether the first row can be produced before the last page is read. A useful decision procedure, stated informally, follows those axes rather than a single cost number.

-- predicate on a low-cardinality column, no ordering needed
SELECT id FROM orders WHERE status = 'open';
-- high selectivity: bitmap scan on an index over status, or a sequential scan
-- if the predicate matches most of the table

-- predicate on a high-cardinality column, few matches
SELECT id FROM orders WHERE customer_id = 4711;
-- index scan: few heap fetches, order by customer_id available for free

-- ordered output with a limit
SELECT id FROM orders WHERE customer_id = 4711 ORDER BY created_at LIMIT 10;
-- index scan on (customer_id, created_at) walks the range in order and stops
-- after ten rows; any other path must sort the whole match set

The LIMIT case is where access path choice and operator choice interact. An index scan that can stop early turns a linear cost into a cost proportional to the limit plus the depth of the descent. A sequential scan with a sort cannot, because the sort has to see all input. The planner expresses this by costing the path with a fraction of the expected rows, which requires knowing that the path can stop early; a bitmap scan cannot, so the same query over a bitmap path costs the full scan.

Join algorithms are selected by the same style of reasoning about mechanisms rather than numbers. A nested loop over an index on the inner side is viable when the outer input is small and the inner lookup is cheap; a hash join requires building a table from one input, which is impossible to amortize if that input is large and the other input is tiny; a merge join requires both inputs sorted on the join key, which an index scan can supply for free and which otherwise costs two sorts. The sort-based and hash-based variants each have their own memory and spilling behaviour, examined in external merge sort and sort-merge join and hash joins and hash aggregation.

Access paths that change under concurrency

An access path chosen for a read-mostly table may degrade badly under write load, and the degradation is structural rather than statistical. Index entries for deleted rows remain until vacuuming, so an index scan over a recently churned range fetches dead tuples. Page splits from concurrent inserts leave the index at lower density, so more pages are read for the same key range. A bitmap scan’s candidate set grows with the number of dead entries, and each candidate page is visited regardless of whether any live tuple remains on it.

The practical consequence is that plan choice is not stable across time even when the query and the statistics are. A path that was correct when the table was freshly loaded can become the wrong choice after a bulk delete, and the reverse. The mechanisms themselves do not change; the distribution of live tuples across pages does.