Q11 — Why does a full table scan sometimes beat an index?

Isn't an index always faster?

After understanding B-trees, it's tempting to conclude that indexes are universally superior. An index lets you find rows in O(log n) — surely that beats a full table scan every time?

No. There are real, common situations where a database will deliberately ignore an available index and scan the entire table instead. Understanding why requires thinking about what an index lookup actually costs, step by step.

What does an index lookup actually cost?

When you use an index to find rows, the process has two phases:

First, traverse the B+ tree to find the matching leaf nodes. This gives you a list of row pointers — row IDs or primary key values that tell you where the actual rows live on disk.

Second, for each row pointer, fetch the actual row from the table. This is the critical step. Each pointer points to a specific physical location on disk. Fetching the row means going to that location.

Now here is the problem: rows that match your query may be scattered across many different disk pages. If you're looking for all users aged 30, age=30 rows might exist in page 1, page 47, page 203, page 891, page 1402... You must fetch each of these pages individually, in random order.

Each of these fetches is a random I/O — the disk (or SSD) must seek to a different location for each one. Random I/O is expensive. On a spinning hard disk, each seek takes 5–10 milliseconds. On an SSD, random reads are faster but still significantly slower than sequential reads, and they generate more read amplification.

What does a full table scan cost?

A full table scan reads every page of the table from beginning to end, sequentially. No jumping around. The disk reads pages 1, 2, 3, 4, 5... in order.

Sequential I/O is much faster than random I/O. On an HDD, sequential throughput might be 100–200 MB/s, while random I/O might achieve only 1–2 MB/s equivalent (due to seek time). On SSDs, the gap is smaller but still real — sequential reads fill the cache prefetcher efficiently, while random reads don't.

Additionally, modern operating systems and databases use read-ahead: when they see sequential access, they prefetch the next pages before they're requested, hiding disk latency. This optimization doesn't apply to random access.

So when does the index lose?

The trade-off comes down to selectivity — the fraction of rows your query matches.

If your query matches 0.1% of rows (100 rows out of 100,000), the index wins decisively. You read ~3-4 B-tree nodes to find the pointers, then fetch 100 rows from specific locations. 100 random reads. Far cheaper than reading all 100,000 rows.

If your query matches 50% of rows (50,000 rows out of 100,000), the index becomes counterproductive. The B-tree navigation is wasted — you're going to touch almost every page anyway. Instead of a clean sequential scan through all 100,000 rows, you're now doing 50,000 random reads scattered across the table. You've replaced a fast sequential scan with a slow random crawl that visits nearly the same pages.

The database's query planner calculates this trade-off using statistics it maintains about the data distribution. It estimates how many rows will match your query, estimates the cost of index-based random I/O vs sequential scan I/O, and picks whichever is cheaper.

What queries tend to be low-selectivity?

Any query where a large fraction of rows match:

WHERE status = 'active' when 80% of users are active
WHERE country = 'US' on a US-centric app where 70% of users are American
WHERE created_at > '2020-01-01' when most data was created after 2020
WHERE is_deleted = false when almost nothing is deleted

In all of these, the index column has low cardinality (few distinct values) or you're querying the majority of the range. An index on is_deleted with only two possible values (true/false) is almost never useful for the WHERE is_deleted = false case — you'd always be fetching the bulk of the table.

What does "the query planner ignores the index" look like?

You can see this with EXPLAIN or EXPLAIN ANALYZE in PostgreSQL:

sql

EXPLAIN SELECT * FROM users WHERE country = 'US';
-- Seq Scan on users  (cost=0.00..4521.00 rows=87000 width=184)
--   Filter: (country = 'US'::text)

The planner sees that 87,000 out of 100,000 rows match. It estimates a sequential scan is cheaper than 87,000 random index-driven fetches. Even if you have an index on country, it's ignored.

Compare with a high-selectivity query:

sql

EXPLAIN SELECT * FROM users WHERE email = 'alice@example.com';
-- Index Scan using users_email_idx on users  (cost=0.42..8.44 rows=1 width=184)
--   Index Cond: (email = 'alice@example.com'::text)

One row expected. Index wins easily.

Why does this matter for index design?

This is why adding indexes blindly is wrong. An index on is_deleted, status, or country might help some queries but be useless or actively harmful for others (the extra B-tree write on every insert/update is always paid, regardless of whether the index is ever used).

Good index design requires thinking about query selectivity: how many rows does this query typically return as a fraction of the table? Indexes shine when selectivity is high (the query matches very few rows). They're wasted when selectivity is low.

Composite indexes (indexing multiple columns together) are one way to recover selectivity: (country, city, age) as a compound index makes WHERE country = 'US' AND city = 'San Francisco' AND age = 30 highly selective even though each column alone would not be.

The mental model

code

Index lookup cost:
  ├── B-tree traversal: ~4 disk reads (cheap, fixed)
  └── Row fetches: N random disk reads (scales with matching rows)

Full scan cost:
  └── Sequential read of entire table (fast I/O, prefetchable)

Break-even point: roughly 5–20% of rows matching (depends on table size, hardware)
  → Below: index wins
  → Above: full scan wins

Query planner uses statistics to estimate row count, chooses cheaper option.

Index design principle:
  High-selectivity column (email, user_id) → great index candidate
  Low-selectivity column (status, boolean) → index often useless or harmful

The full table scan exists not as a fallback for missing indexes, but as a legitimate execution strategy that beats indexes whenever your query touches a large fraction of the data.