Index scan vs full table scan

A full table scan (a sequential scan) reads every page of a table in physical order. An index scan descends a B-tree and then fetches each matching row from whichever page it lives on. The planner prices both and picks the cheaper, and because a random page read is priced at four sequential ones, a plain index scan stops paying off surprisingly early, often below 1% of the rows. When the planner ignores your index, it is usually right.

Picture it first: the dark-store picker

A quick-commerce dark store has 40 aisles. A picker gets an order and a handheld that tells her the aisle and shelf of every product. That handheld is an index.

For a four-item order, she walks straight to four shelves. Nothing beats that.

Now the order is “pull every item that expires this week”: 1,500 products scattered across all 40 aisles. Following the handheld item by item sends her criss-crossing the store 1,500 times. Walking every aisle once, end to end, glancing at each shelf, is faster, even though most shelves have nothing to pull. Each glance is cheap because she never has to cross the store.

Two refinements complete the picture. If the store shelved products by expiry date, this week’s items would sit together in two aisles, and the handheld would win again. And a smart picker could first sort her 1,500-item list by aisle and shelf, then do one walk, visiting only the shelves on the list.

Map it back: shelves are pages; walking the aisles end to end is a sequential scan; each trip to one shelf is a random page read; the handheld is the index; shelving by expiry is correlation; and sorting the list before walking is a bitmap heap scan.

Two ways to read a table

Tables live in fixed-size pages, 8 KB in PostgreSQL, and the database reads whole pages. Every example here uses an IRCTC-style bookings table in PostgreSQL 18:

CREATE TABLE bookings (
  id           bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  pnr          char(10)    NOT NULL UNIQUE,
  user_id      bigint      NOT NULL,
  train_no     integer     NOT NULL,
  journey_date date        NOT NULL,
  status       text        NOT NULL,   -- CONFIRMED, RAC, WAITLIST, CANCELLED
  booked_at    timestamptz NOT NULL DEFAULT now(),
  fare_paise   integer     NOT NULL
);
-- 10,000,000 rows of about 80 bytes: ~100 rows per 8 KB page,
-- so 100,000 heap pages (about 800 MB).
-- Single-column indexes on user_id, train_no, journey_date, status, booked_at.

A sequential scan reads pages 1, 2, 3 … 100,000 and tests every row. The pattern is perfectly predictable, so the operating system and the storage device read ahead, and each page costs little.

An index scan descends the B-tree to the first matching key and walks the leaf entries in key order. Each entry points to a row, and the database fetches that row’s page. Rows matching user_id = 8812 were inserted months apart, so they sit on unrelated pages: each fetch is a random read, and the next one can’t be predicted. (The B-tree itself is covered in database indexes.)

In InnoDB the details differ but the shape is the same: a full scan walks the clustered (primary-key) index’s leaf pages in order, and each row found through a secondary index costs a second descent into the clustered index. More on that below.

How the planner prices each path

PostgreSQL’s planner can’t run every candidate plan to see which is fastest, so it estimates a cost for each, in arbitrary units, and keeps the cheapest. The units are anchored to one sequential page read. The defaults:

Why 4.0? The documentation is candid: a random read from durable storage is normally much more than four times as expensive as a sequential one, but the default assumes most random reads, such as index lookups, are served from cache.

The sequential scan cost is pages × seq_page_cost plus rows × (cpu_tuple_cost + cpu_operator_cost for the filter). For bookings:

100,000 × 1.0 + 10,000,000 × (0.01 + 0.0025) = 100,000 + 125,000 = 225,000, whatever the filter matches.

The index scan cost is the index pages it reads, plus the heap pages it fetches at random_page_cost each, plus a little CPU per entry and per row. Three queries against bookings show the planner choosing each family (parallel workers disabled to keep the numbers comparable):

-- PostgreSQL 18, SET max_parallel_workers_per_gather = 0

-- 1 row: WHERE pnr = '4521837960'
Index Scan using bookings_pnr_key on bookings  (cost=0.43..8.45 rows=1 width=72) (actual time=0.031..0.032 rows=1.00 loops=1)
  Index Cond: (pnr = '4521837960'::bpchar)
  Index Searches: 1
  Buffers: shared hit=4

-- 0.5% of rows: WHERE status = 'RAC'
Bitmap Heap Scan on bookings  (cost=561.43..85731.20 rows=49650 width=72) (actual time=6.912..142.538 rows=50214.00 loops=1)
  Recheck Cond: (status = 'RAC'::text)
  Heap Blocks: exact=39477
  Buffers: shared hit=1822 read=37698
  ->  Bitmap Index Scan on bookings_status_idx  (cost=0.00..549.02 rows=49650 width=0) (actual time=5.874..5.875 rows=50214.00 loops=1)
        Index Cond: (status = 'RAC'::text)
        Index Searches: 1
        Buffers: shared hit=43

-- 78% of rows: WHERE status = 'CONFIRMED'
Seq Scan on bookings  (cost=0.00..225000.00 rows=7801140 width=72) (actual time=0.019..1210.744 rows=7798305.00 loops=1)
  Filter: (status = 'CONFIRMED'::text)
  Rows Removed by Filter: 2201695
  Buffers: shared hit=2048 read=97952

The Seq Scan’s total cost, 225,000.00, is exactly the arithmetic above. The middle plan is the subject of a later section; first, where exactly does the plain index scan stop winning? (Query execution plans explains how to read every field in these plans.)

Where the crossover falls

Take a column with no relationship to physical order, such as user_id, and ask for 1% of the table: 100,000 rows.

Worst case. Every matching row is on a different page: 100,000 random reads × 4.0 = 400,000, against 225,000 for the sequential scan. The index loses by almost 2×.

What the planner actually estimates. Some rows will share pages. PostgreSQL uses an approximation from Mackert and Lohman’s 1989 paper on index scans through an LRU buffer: for a table that fits in effective_cache_size, fetching n rows from T pages touches about 2Tn ÷ (2T + n) distinct pages. With T = 100,000 and n = 100,000, that is 2 × 100,000 × 100,000 ÷ 300,000 ≈ 66,700 pages. Then:

• heap pages: 66,700 × 4.0 ≈ 266,700
• per-row and per-entry CPU: 100,000 × (0.01 + 0.005 + 0.0025) = 1,750
• index pages: about 270 leaf pages × 4.0 ≈ 1,100

Total ≈ 269,500: still about 20% dearer than the sequential scan. Solving for the point where the two costs meet gives about 0.8% of the rows, roughly 77,000 of 10 million. Fetching one row in 125 is already too many for a plain index scan.

The intuition is worth keeping. The sequential scan’s 225,000 buys every page and a check of every row. At 4.0 per random page, the index scan can afford about 225,000 ÷ 4 ≈ 56,000 page fetches, and because scattered rows cost about one page each, that budget is gone by the time about 77,000 rows match.

Tuning random_page_cost

The 4.0 default already assumes most random reads hit the cache. The documentation suggests lowering random_page_cost when your data is likely to be fully cached, and notes that setting it equal to seq_page_cost makes sense if the database is entirely in RAM, since there is then no penalty for reading pages out of order. Fast SSDs shrink the gap too, which is why many teams run with a lower value. Redo the 1% case with 1.1: 66,700 × 1.1 + the CPU and index terms ≈ 75,400, a third of the sequential scan. In this model the uncorrelated crossover jumps from 0.8% to about 56%.

Correlation: when physical order matches the index

The calculation above assumed the worst: matching rows scattered at random. Often they aren’t. Bookings are appended in time order, so rows with nearby booked_at values sit on the same or adjacent pages. A range on booked_at that matches 1% of rows reads about 1% of the pages, one after another: 1,000 pages, mostly sequential, not 66,700 random ones.

PostgreSQL measures this as correlation in pg_stats: the statistical correlation between the physical row order and the column’s sorted order, from −1 to +1. Values near ±1 make index scans cheaper; values near 0 don’t.

SELECT attname, correlation
FROM pg_stats
WHERE tablename = 'bookings'
  AND attname IN ('booked_at', 'journey_date', 'train_no', 'user_id');
--  booked_at     |  0.9999   appended in time order
--  journey_date  |  0.91     bookings open weeks before travel
--  train_no      |  0.0038
--  user_id       | -0.0012

The planner computes two heap-I/O costs: the uncorrelated estimate above, and a perfectly correlated one (one random read, then sequential reads of just the pages that hold matches). It then blends them using the square of the correlation. Running the same arithmetic for bookings:

Squaring makes moderate correlation nearly worthless: 0.5 buys only a quarter of the benefit. Only columns that track insertion order closely (timestamps, sequential IDs, dates on append-only tables) get the big win. You can reorder a table once with CLUSTER, but PostgreSQL doesn’t maintain that order as rows change. InnoDB gets it for free on the primary key, because the table is the primary-key index: a primary-key range is always a perfectly correlated read.

Bitmap scans: the middle ground

Between “a few rows” and “most of the table” sits a third plan, the one the planner chose for status = 'RAC' above. It runs in two steps:

1. Bitmap Index Scan. Read the index and, instead of fetching rows, collect every matching row location into an in-memory bitmap organised by page number.
2. Bitmap Heap Scan. Walk the bitmap in page order and read each marked page once, in physical order, checking the condition again for the rows on it.

This is the picker sorting her list by aisle before walking. Each page is read at most once, and in ascending order, so reads are as close to sequential as the matches allow. The planner reflects that: for bitmap heap scans the cost per page slides from random_page_cost towards seq_page_cost as the fraction of the table being fetched grows (by the square root of that fraction). For status = 'RAC' (0.5%, about 50,000 rows on about 40,000 pages), the price per page is 4 − 3 × √0.4 ≈ 2.1, so the heap part costs about 84,000. A plain index scan would cost about 161,000 and the sequential scan 225,000, so the bitmap wins comfortably, as the plan showed.

Bitmaps also let the planner combine indexes. With separate indexes on train_no and journey_date, WHERE train_no = 4417 AND journey_date = '2026-11-14' can build two bitmaps, AND them (BitmapAnd), and visit only pages that appear in both. OR conditions use BitmapOr.

Two costs come with it. Order is lost: rows come out in page order, so an ORDER BY needs a sort, and a LIMIT can’t stop the scan early. And memory is bounded by work_mem. When the bitmap would exceed it, PostgreSQL switches some pages to lossy storage, remembering only that the page holds a match, not which rows. Those pages must have every row rechecked: EXPLAIN ANALYZE shows Heap Blocks: exact=… lossy=… and a Rows Removed by Index Recheck line. If a hot query shows lossy blocks, a little more work_mem for that session usually fixes it.

Index-only scans and the visibility map

The cheapest way to avoid random heap reads is not to read the heap at all. If every column a query needs is in the index, PostgreSQL can run an index-only scan, answering from index entries alone. (Designing indexes for this is covered in composite index design.)

There is a catch rooted in MVCC. Index entries don’t say which transactions can see them; only heap rows do. So for each entry the scan checks the table’s visibility map, a bit per heap page meaning “every row here is visible to every transaction”. Bit set: return the entry, no heap visit. Bit clear: visit the heap page anyway. The map is tiny (the documentation puts it at four orders of magnitude smaller than the heap), so it usually stays in memory.

The bits have a life cycle, and that is what makes index-only scans unreliable on busy tables. Only VACUUM sets them; any insert, update or delete on a page clears that page’s bit. Since PostgreSQL 13, inserts trigger autovacuum too, partly so that append-only tables get their bits set. The planner knows this: it discounts heap fetches using the fraction of the table’s pages currently marked all-visible, so a freshly churned table may get no index-only scan at all.

Read Heap Fetches in EXPLAIN ANALYZE. If it is close to the row count, the index-only scan is behaving like a plain index scan, and the fix is VACUUM (or more aggressive autovacuum settings on that table), not another index. Tables with heavy updates bring their own cost in dead rows; see vacuum and bloat.

LIMIT, ORDER BY and the optimistic planner

LIMIT changes the arithmetic. An index scan in ORDER BY order can stop after n rows, so the planner charges only the fraction of its cost it expects to need. ORDER BY booked_at DESC LIMIT 20 on an index over booked_at reads about 20 entries, whatever the table size; the same property makes keyset pagination fast. A sequential scan with a sort has to read everything first.

The trap is in the word expects. Take “the latest 20 bookings on train 4417”, with indexes on booked_at and on train_no but not on both:

SELECT * FROM bookings
WHERE train_no = 4417
ORDER BY booked_at DESC
LIMIT 20;

Statistics say train 4417 has about 5,000 bookings, 0.05% of the table. Assuming those rows are spread evenly through time, walking booked_at backwards should find 20 within 20 ÷ 0.0005 = 40,000 entries: cheap, and no sort. But 4417 is a summer special. All its bookings are from April, seven months back:

Limit  (cost=0.43..1612.88 rows=20 width=72) (actual time=8734.551..8734.902 rows=20.00 loops=1)
  ->  Index Scan Backward using bookings_booked_at_idx on bookings  (cost=0.43..403112.18 rows=5000 width=72) (actual time=8734.549..8734.897 rows=20.00 loops=1)
        Filter: (train_no = 4417)
        Rows Removed by Filter: 6912408
        Index Searches: 1

Estimated cost 1,613; reality, 6.9 million rows thrown away and 8.7 seconds. The alternative the planner rejected, fetching train 4417’s 5,000 rows through its own index and sorting them, would have taken tens of milliseconds at most. No per-column statistic can describe “this train’s rows are all old”.

The fixes, in order of preference:

• A composite index that serves both the filter and the order: (train_no, booked_at). The scan seeks straight to train 4417 and reads its 20 newest entries. This is the real fix (composite index design).
• Stop the order-providing index from being considered, for example by sorting on an expression (ORDER BY booked_at + interval '0 seconds' DESC). It works, but it is a hack someone will “clean up” later; leave a comment.
• Fetch first, sort second: a CTE marked MATERIALIZED that selects the train’s rows, then ORDER BY … LIMIT outside it.

MySQL and InnoDB

InnoDB stores each table as a B+tree ordered by primary key, the clustered index, so its trade-off is shaped a little differently:

• A full table scan (type: ALL in EXPLAIN) walks the clustered index’s leaf pages from one end to the other: sequential reads.
• A primary-key range (WHERE id BETWEEN …) is the same structure read over a slice: perfectly correlated, always cheap.
• A secondary-index range (type: range or ref) reads the secondary index, then performs one primary-key lookup per row, a separate descent of the clustered index. Those are InnoDB’s random reads.
• A covering secondary index (“Using index”) skips the lookups, because every secondary entry already carries the primary key.

MySQL’s documentation lists when the optimizer prefers a full scan: the table is tiny; there is no usable condition on an indexed column; the constants cover “too large a part of the table”; or a low-cardinality key would need many lookups. For our two status queries:

mysql> EXPLAIN SELECT * FROM bookings WHERE status = 'RAC';        -- 0.5% of rows (columns trimmed)
+------+---------------------+-------+----------+-------+
| type | key                 | rows  | filtered | Extra |
+------+---------------------+-------+----------+-------+
| ref  | bookings_status_idx | 51206 |   100.00 | NULL  |
+------+---------------------+-------+----------+-------+

mysql> EXPLAIN SELECT * FROM bookings WHERE status = 'CONFIRMED';  -- 78% of rows
+------+------+---------+----------+-------------+
| type | key  | rows    | filtered | Extra       |
+------+------+---------+----------+-------------+
| ALL  | NULL | 9871203 |    78.02 | Using where |
+------+------+---------+----------+-------------+

MySQL’s counterpart to the bitmap heap scan is Multi-Range Read: collect a batch of primary keys from the secondary index, sort them, then fetch rows in key order, which turns random lookups into something closer to a sweep. EXPLAIN shows “Using MRR”. It is enabled but cost-based by default, so you often won’t see it unless the optimizer is persuaded it pays. The cost constants live in the mysql.server_cost and mysql.engine_cost tables (io_block_read_cost, memory_block_read_cost and others) and can be tuned, although the documentation’s own first remedies for a wrong full scan are ANALYZE TABLE and, as a last resort, FORCE INDEX.

When the planner gets it wrong

The cost model is usually sound. Bad plans almost always come from bad inputs: the row estimate is wrong, so the right formula is fed the wrong number. Before changing anything, compare estimated and actual rows on the scan node.

• Stale or missing statistics. After a bulk load, RAC may still look like 0.5% of rows when it is now 20%, and the planner happily runs a bitmap scan that ends up touching nearly every page, with lossy rechecks. Fix: ANALYZE bookings after big loads and deletes, and tune autovacuum’s analyse thresholds on large, fast-changing tables.
• Correlated columns. The planner multiplies selectivities as if conditions were independent. train_no = 4417 AND journey_date = '2026-11-14' looks far rarer than it is, because a train runs on particular dates. An underestimate pushes it towards index scans and nested loops. Fix: CREATE STATISTICS on the column pair.
• Generic plans. A prepared WHERE status = $1 can settle on one plan for all values, though RAC wants a bitmap scan and CONFIRMED a sequential scan. Fix: check with EXPLAIN (GENERIC_PLAN), and consider plan_cache_mode = force_custom_plan for that query.
• Functions on the column. WHERE date(booked_at) = '2026-10-26' can’t use the booked_at index, and the planner falls back to a default guess for the expression. Fix: rewrite as a range, booked_at >= '2026-10-26' AND booked_at < '2026-10-27'. (An expression index also works, but on a timestamptz it needs an immutable expression with an explicit time zone; see indexes in practice.)
• Implicit casts. If a driver binds a bigint parameter as numeric (a Java BigDecimal, say), user_id = $1 is evaluated as numeric, the column is cast, and the user_id index can’t be used. Fix: bind the matching type.
• An optimistic LIMIT, as in the previous section.

How statistics are gathered, extended statistics and generic plans are covered properly in query execution plans.

BEGIN;
SET LOCAL enable_seqscan = off;   -- discourages, doesn't forbid
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM bookings WHERE status = 'WAITLIST';
ROLLBACK;

Choosing an access path

Cheat sheet

How to say it in the interview

“An index scan isn’t free: each matching row costs a separate page read, and those reads are random. PostgreSQL prices a random page at four times a sequential one, so on a table with a hundred rows per page, an index on an uncorrelated column stops beating a full scan at around one percent of the rows. If the column follows insertion order, like a timestamp, it stays cheaper for a far bigger share. Between the two the planner uses a bitmap scan, which sorts the row locations by page. So if it ignores my index, I compare its row estimate to the actual count. If the estimate is right, the seq scan probably is too; if not, I fix the statistics, not the plan.”

Why would a full table scan ever be faster than using an index? Because it reads pages in order and each page once, while an index scan reads one page per matching row, out of order. Past roughly 1% of rows on an uncorrelated column, those random reads add up to more than reading everything.

What does correlation mean for an index? How closely the table’s physical row order follows the indexed column’s order. Near 1, matching rows sit together, so an index range scan reads few pages, in order. PostgreSQL blends the costs by correlation squared, so only strong correlation helps much.

When does a bitmap heap scan win? For a middle band of selectivity, or when two indexes must be combined. It fetches each page once, in physical order, but loses index order and can go lossy if work_mem is too small.

Why can an index-only scan still read the table? Visibility lives in the heap. The scan skips a heap page only if the visibility map says every row on it is visible to all; recent writes clear those bits until VACUUM sets them again.

Should you set random_page_cost to 1.1 on SSDs? Often a lower value is right: the setting models how much dearer a random page is after caching, and fast SSDs and a cached working set both shrink that gap. But test it per session on your top queries first; set too low, it makes the planner choose index scans that do millions of genuinely random reads.

Where to go next

• Database indexes: how B+trees, heaps and clustered tables are laid out.
• Composite index design: column order, covering indexes, and fixing the LIMIT trap properly.
• Query execution plans: reading plans line by line, statistics and join algorithms.
• Indexes in practice: partial and expression indexes, and finding the queries worth fixing.
• Vacuum and bloat and MVCC: why the visibility map exists and who keeps it current.
• Reads and writes: how databases store and fetch data: pages, the buffer pool and the I/O underneath every scan.
• Busy database: what happens when expensive scans pile up in production.

References and further reading

1. PostgreSQL documentation: Query Planning, Planner Cost Constantspostgresql.orgseq_page_cost 1.0, random_page_cost 4.0 and why it assumes caching, the CPU cost constants, effective_cache_size, enable_seqscan and plan_cache_mode.
2. PostgreSQL documentation: Using EXPLAINpostgresql.orgThe sequential-scan cost formula, why bitmap heap scans sort row locations into physical order, BitmapAnd plans, and the effect of LIMIT on plan choice.
3. PostgreSQL source: costsize.c (REL_18_STABLE)github.comHow index scans are costed: the Mackert–Lohman page estimate, interpolation by correlation squared, and the per-page cost curve for bitmap heap scans.
4. PostgreSQL source: tidbitmap.c (REL_18_STABLE)github.comHow a bitmap of row locations falls back to lossy, one-bit-per-page storage when it runs out of memory.
5. PostgreSQL documentation: pg_statspostgresql.orgDefinition of the correlation statistic and its effect on index-scan cost.
6. PostgreSQL documentation: Index-Only Scans and Covering Indexespostgresql.orgWhy index-only scans must check the visibility map, and why they win only when most heap pages are all-visible.
7. PostgreSQL documentation: Visibility Mappostgresql.orgAll-visible bits are set only by VACUUM and cleared by any change to the page.
8. PostgreSQL 13 release notespostgresql.orgInserts now trigger autovacuum, partly so that all-visible bits get set for index-only scans.
9. MySQL 8.0 Reference Manual: Avoiding Full Table Scansdev.mysql.comWhen MySQL chooses a full table scan (type ALL) and the documented remedies: ANALYZE TABLE, FORCE INDEX, max_seeks_for_key.
10. MySQL 8.0 Reference Manual: Multi-Range Read Optimizationdev.mysql.comSorting secondary-index keys by primary key before fetching rows, to turn random reads into a sweep.