Partial Index Scan Degradation

When a query uses a B-tree index on a low-selectivity column (one where the filter matches most rows), the index scan reads all or most index pages plus all the corresponding heap pages, performing more total I/O than a sequential scan would. The query planner may choose the index scan based on stale statistics that underestimate the selectivity, causing a query that should take 50ms on a sequential scan to take 5 seconds on an index scan because it reads the heap via thousands of random I/O operations instead of one sequential pass.

Index scans are efficient when they retrieve a small fraction of table rows (high selectivity). A query fetching 1% of rows via an index reads 1% of heap pages (random I/O) plus the relevant index pages: far less total I/O than a full sequential scan. But when a query retrieves 40% or more of rows, an index scan can be more expensive than a sequential scan: it reads 40% of heap pages as random I/O (each page access requiring a separate disk seek on HDDs, or a separate I/O request on SSDs), plus the full index leaf level. A sequential scan reads 40% of the table as contiguous sequential I/O, which modern storage executes at 4–20x the throughput of random I/O.

The PostgreSQL query planner estimates the cost of each plan using column statistics collected by ANALYZE (stored in pg_statistic). If statistics are stale (collected when the data distribution was different) or the planner's default selectivity assumptions are inaccurate (e.g., for complex predicates involving type casts, LIKE patterns, or correlated columns), the planner may estimate 1% selectivity when the actual selectivity is 40%. It chooses the index scan expecting cheap I/O but executes expensive random I/O across 40% of the table.

The most common production trigger is a data distribution shift. A table is initially 90% inactive (archived) and 10% active. The index on status = 'active' returns 10% of rows (high selectivity), so the planner correctly chooses the index scan. Over time, more records become active (business growth, migration failure). Now 85% of records are active. The same query on status = 'active' returns 85% of rows (low selectivity). If ANALYZE has not run since the distribution shifted, the planner still estimates 10% selectivity, uses the index scan, and performs 8.5x more random heap I/O than it estimated.

The planning error is confirmed by EXPLAIN ANALYZE: the "Rows Removed by Filter" count is near zero (the filter is not removing many rows after the index lookup), and the actual rows/estimated rows ratio shows a large discrepancy. The fix is to run ANALYZE on the affected table to update statistics, but this is often not obvious to engineers who assume autovacuum/autoanalyze is keeping statistics current (it may not be, if the table is large and autoanalyze thresholds are not calibrated for the data distribution shift rate).