Database field guide · 02
Indexes and Access Paths
From data structure to execution plan
How B-trees, covering indexes, scan methods, and optimizer costs turn a predicate into physical work.
Franck Pachot7 chaptersB-trees · access paths · execution plans
Build the mental model before choosing the mechanism.
This minibook was AI-generated from Franck Pachot's archived blog posts. Links to the original articles are included for source context and verification.
01
The index is a physical promise
An index promises ordered access to a subset of table facts. It is not inherently faster than a table scan: its value depends on how much data can be rejected before visiting the table and how those visits are distributed across storage.
- A B-tree branch narrows the search; leaf entries identify rows or row locations.
- Selectivity determines how soon an index stops being cheaper than scanning.
- The table remains the source of truth unless the index covers every required fact.
02
Read the tree from root to leaf
Height, fan-out, key width, and block density determine the work needed to reach a leaf. A wide covering index can save table visits while increasing branch size, cache pressure, and write cost. Index design is therefore a workload trade, not a checklist item.
- Prefix columns define which predicates can navigate the tree.
- Included or trailing columns can cover output without improving navigation.
- Block splits preserve order; they are normal maintenance, not automatic evidence of damage.
03
One predicate, several access paths
A sequential scan, index scan, index-only scan, and bitmap scan answer the same logical request with different physical work. The optimizer compares estimated pages, tuples, CPU operations, ordering benefits, and parallelism rather than following a rule such as ‘an index exists, therefore use it.’
- Sequential scans amortize I/O when much of the table is needed.
- Index scans excel when few row locations are visited predictably.
- Bitmap scans collect many locations before visiting table pages, trading latency for locality.
04
Covering is product-specific
Oracle can often return indexed columns directly because row visibility is resolved through undo and block metadata. PostgreSQL index-only scans also consult the visibility map: an index containing every projected column may still visit the heap when pages are not known to be all-visible.
- Coverage is a query property, not an index label.
- Visibility and recent updates influence PostgreSQL heap fetches.
- Measure logical reads and heap fetches, not only the plan node name.
05
Ordering is work you may avoid
A B-tree already stores keys in order. Matching equality prefixes and an ordered suffix can eliminate sorting, accelerate min/max queries, and stop early for top-N retrieval. Direction, null ordering, and mixed ascending/descending requirements decide whether the stored order is reusable.
- Filtering and ordering should be designed together.
- A reverse scan can satisfy a fully reversed order.
- Pagination needs a deterministic tie-breaker in the index and query.
06
Design from evidence
Start with the query shape and expected cardinality, then verify estimates against actual rows and buffers. An index that rescues one statement can slow every write and duplicate another index. Keep the smallest set that supports real invariants and access paths.
- Use EXPLAIN with runtime statistics where production safety permits.
- Compare estimates, actual rows, buffers, and elapsed time.
- Re-test after data distribution and workload shape change.
07
Field manual
Concrete mechanics, diagnostic evidence, and executable patterns to carry into a real system.
01
Read an access path by counting visits
An index lookup has two distinct costs: walking branch blocks to a leaf, then visiting heap or table blocks for matching entries. A three-level B-tree does not mean three I/O operations per row because upper blocks are usually cached. The variable cost is commonly the table visit pattern. PostgreSQL exposes it as heap fetches and buffer hits; Oracle exposes consistent gets and physical reads. A poor clustering factor turns adjacent index entries into scattered table visits.
EXPLAIN (ANALYZE, BUFFERS, WAL)
SELECT customer_id, created_at
FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 20;
Build one index for filtering and stopping
Equality columns normally lead, followed by range and ordering columns. The key below lets the executor seek to one customer, scan in requested order, and stop after twenty entries. INCLUDE columns are payload: they can make the query covering but cannot navigate the tree. On PostgreSQL, an index-only plan still needs all-visible heap pages; inspect Heap Fetches rather than trusting the node name alone.
CREATE INDEX orders_customer_recent_ix
ON orders (customer_id, created_at DESC, order_id DESC)
INCLUDE (status, total);
Know when a bitmap wins
A PostgreSQL bitmap index scan gathers tuple identifiers from one or more indexes, combines them with bitmap AND/OR, sorts visits by heap block, then reads each needed block. It is useful between a selective point lookup and a broad sequential scan. A lossy bitmap stores page-level rather than tuple-level membership when work_mem is tight, so the Bitmap Heap Scan must recheck predicates.
SET LOCAL work_mem = '64MB';
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM event
WHERE tenant_id = 7
AND severity IN ('ERROR', 'FATAL');
Measure maintenance, not folklore
Every extra index adds WAL or redo, cache churn, uniqueness checks where applicable, and page split work. PostgreSQL's pg_stat_user_indexes reveals read usage but cannot prove an index is redundant; constraints, rare reporting jobs, and standby workloads matter. Compare definitions and left prefixes before removal, then observe a complete business cycle.
SELECT relname, indexrelname, idx_scan,
pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
ORDER BY idx_scan, pg_relation_size(indexrelid) DESC;
08
Source articles
Optional deep dives with the complete experiments and product-version context behind this guide.
