A table scan says "I'll read everything and sort it out." An index scan says "I know exactly where the answers live, and I'll only read those." The planner makes that call with cost estimates; the executor then executes a very precise form of archaeology: descend, walk, fetch, verify.
Step 1 — the planner's decision
The planner compares costs: full scan = pages × seq_page_cost (default 1.0); index scan = descent pages (≈ tree height) + matching leaf pages + one heap fetch per matching row × random_page_cost (default 4.0). With random_page_cost = 4, an index scan only wins below ~20% selectivity on typical hardware — and the real number on modern SSDs (where random ≈ sequential) is much lower, which is why people set it to 1.1 and watch plans change.
Index Scan using users_pkey on users (cost=0.42..8.44 rows=1 width=...)
Index Cond: (id = 42)Step 2 — descent
The executor starts at the root and descends: binary search per level, following child pointers, 3-5 page fetches for a typical tree (see the b-tree insert trace for the shape). Each page is a buffer-pool fetch: ~1µs warm, ~100µs-1ms cold. Result: the leftmost leaf page where the key range starts. Index Cond is applied during the walk — every internal-page comparison is a decision point, not just at the leaf.
Step 3 — walking the leaf chain
Within a leaf page, a binary search finds the first entry ≥ the lower bound. Then the scan walks within the page and, when the page ends, follows the next-sibling pointer to the next leaf — leaf pages are linked in key order. For id BETWEEN 100 AND 200: typically 1-2 leaf pages, ~150-300 entries each, cost ~1-5µs per page. The entries produced are (key, TID) pairs.
Step 4 — the heap fetch
Each TID points at a heap page: block N, offset M. The executor fetches that heap page from the buffer pool and reads the row. Here's the catch: TIDs are emitted in key order, not disk order. A WHERE id IN (5, 50000, 7) can produce three separate random-ish page fetches — each is a random_page_cost at plan time, and each is a real random read at runtime. On an HDD this is brutal; on NVMe it's nearly free (the random_page_cost tuning story).
Step 5 — visibility
Every row returned must pass the MVCC visibility check: is this row version visible to this transaction's snapshot? The tuple header's xmin/xmax (and in Postgres, the t_infomask bits) decide: visible, deleted, or in-progress. This is per-row work — a few hundred ns each. Two subtleties:
- HOT updates: updated rows keep the same index entries when the update touches no indexed columns — the chain walk skips dead versions without extra index work.
- Killed tuples: if a previous scan proved a row dead, the TID is marked; the new scan skips the fetch.
Step 6 — bitmap scan: fixing the order
When the planner estimates many matches (selectivity too high for TID-by-TID random reads), it picks a bitmap scan: the index is scanned to build a bitmap of candidate heap pages (no fetches), then the heap is read in page order, every matching page once. Sequential I/O, no repeated page visits — the classic middle ground between pure index scan and full table scan.
Step 7 — index-only scan: skipping the heap
If every needed column is in the index (a covering index, or Postgres INCLUDE columns), the heap becomes optional. But MVCC still lives in the heap tuple — so the index-only scan consults the visibility map first: pages marked all-visible skip the heap entirely; others do a visibility-check fetch. A cold index-only scan can read 10x less data than the equivalent heap-referencing scan.
What it costs
- Descent (any point lookup): 3-5 page fetches: ~5-20µs warm.
- Leaf traversal: ~1-5µs per page; range scans pay per page covered.
- Heap fetch: ~1µs warm, 50µs-5ms cold; bitmap scans convert N random reads into sequential ones.
- Visibility checks: ~100-500ns per row, invisible in EXPLAIN but visible in
pg_stat_user_tables(idx_tup_fetch).
EXPLAIN (ANALYZE) SELECT * FROM orders WHERE created_at >= '2026-01-01'
AND created_at < '2026-02-01';
Index Scan using orders_created_at_idx on orders (cost=0.43..4212.18 rows=90212 width=...)
(actual time=0.018..31.4 rows=90211 loops=1)
Planning Time: 0.112 ms
Execution Time: 31.4 ms90k rows, 31ms — ~350ns per row, almost all of it heap fetches and visibility checks. That's the whole trade in miniature: the index found the rows in microseconds; the heap gave them to you one random fetch at a time. Every "why is my index scan slow" investigation is really "how many heap pages did you actually touch?"