Sequential scan versus index scan

A sequential scan reads every page of a table in file order and discards the rows that do not match. An index scan walks the index to find matching entries and fetches the heap pages they point at, in index order. The planner costs both and takes the cheaper. The index path is charged for fetching pages one at a time in an order the storage did not choose, so its cost depends on how many distinct pages the matching rows are spread across.

The five percent rule is not a rule

The folklore says PostgreSQL stops using an index somewhere around a few percent of the table. There is no such threshold in the planner, and the number that does the work is physical correlation: how closely the order of a column’s values matches the order the rows are stored in. A column whose values ascend with the file can return half the table through an index, because the heap fetches walk forward through consecutive pages. A column whose values are scattered pays a separate page fetch for nearly every row.

This is why the same query shape, against two columns holding exactly the same values, gets two different plans. It is also why an index that performed well on a freshly loaded table degrades after months of updates move rows around, with no change to the query, the data volume or the statistics, and why clustering a table on an index changes plans without changing any setting.

The same selectivity, two plans

Both columns below hold every integer from one to five hundred thousand. One ascends with the file and one does not, and each predicate matches half the table.

CREATE TABLE reading AS
SELECT g AS seq_key, ((g::bigint * 7919) % 500000)::int AS scattered_key, repeat('.', 60) AS pad
FROM generate_series(1, 500000) g;
CREATE INDEX reading_seq_idx ON reading (seq_key);
CREATE INDEX reading_scattered_idx ON reading (scattered_key);
ANALYZE reading;
SET max_parallel_workers_per_gather = 0;
EXPLAIN (COSTS OFF) SELECT count(pad) FROM reading WHERE seq_key <= 250000;
EXPLAIN (COSTS OFF) SELECT count(pad) FROM reading WHERE scattered_key <= 250000;
SELECT attname, round(correlation::numeric, 2) AS correlation
FROM pg_stats WHERE tablename = 'reading' AND attname LIKE '%key';

SELECT 500000
CREATE INDEX
CREATE INDEX
ANALYZE
SET
                    QUERY PLAN                     
---------------------------------------------------
 Aggregate
   ->  Index Scan using reading_seq_idx on reading
         Index Cond: (seq_key <= 250000)
(3 rows)

                QUERY PLAN                 
-------------------------------------------
 Aggregate
   ->  Seq Scan on reading
         Filter: (scattered_key <= 250000)
(3 rows)

    attname    | correlation 
---------------+-------------
 seq_key       |        1.00
 scattered_key |        0.00
(2 rows)

Half the table through an index, half the table by reading everything and throwing half away, from identical values and identically shaped indexes. The correlation statistic in the last query is the input that separates them: one column sits at exactly one, the other rounds to zero.

What to do with a scan you did not want

Before adding an index, check whether one already exists and is being passed over for this reason, because a second index on the same column will be passed over too. The catalog view that shows which indexes are used, which are redundant and which scans wanted an index that is missing is the subject of unused and missing indexes. Where the plan lands on neither extreme, the middle node is a bitmap heap scan.