Index Correlation and Physical Row Order #

Two range queries return the same 200,000 rows from the same 80-million-row table through B-tree indexes of the same size. One reads 1,900 heap pages and finishes in 90 ms. The other reads 186,000 heap pages and takes 11 seconds, and the planner refuses to use its index unless forced. The difference is not the index; it is where the matching rows sit on disk.

The general crossover between access paths is covered in sequential vs index scans. This page covers the statistic that moves that crossover more than any other for range scans: correlation.

The Cost-Model Condition #

An index scan reads index entries in key order and fetches each matching row from the heap. If rows with neighbouring key values live on neighbouring pages, consecutive fetches hit the same page or the next one — nearly sequential I/O. If they are scattered, nearly every fetch is a new random page.

ANALYZE measures this as pg_stats.correlation: the correlation between the column’s sort order and the physical row order, from −1 to 1. The planner’s index scan cost interpolates between two extremes using the square of the correlation:

Because the correlation is squared, 0.7 counts as barely half of perfect ordering, and 0.3 is almost indistinguishable from random. Typical values:

Bitmap heap scans sidestep correlation by sorting page fetches physically, which is why the planner often prefers them for low-correlation columns — see bitmap heap scan vs index scan thresholds.

Same index order, different heap layouts Two panels. Left: with correlation near 1, consecutive index entries point to consecutive heap pages, drawn as parallel short arrows into a contiguous run of pages. Right: with correlation near 0, consecutive index entries point to pages spread across the whole table, drawn as crossing arrows into scattered pages. correlation ≈ 0.99 index entries k1 … k6 in key order 2 contiguous page runs correlation ≈ 0.02 index entries k1 … k6 in key order 6 random page fetches heap pages below each index

Annotated EXPLAIN Evidence #

SELECT attname, correlation FROM pg_stats
WHERE tablename = 'payments' AND attname IN ('created_at', 'merchant_id');
   attname   | correlation
-------------+-------------
 created_at  |    0.998812
 merchant_id |    0.004120

High correlation:

Index Scan using payments_created_at_idx on payments
    (cost=0.57..9204.10 rows=201400 width=64) (actual time=0.03..88.4 rows=204110 loops=1)
  Index Cond: (created_at >= '2026-09-10' AND created_at < '2026-09-11')
  Buffers: shared hit=2440 read=1904
  -- ~4,300 buffers for 204k rows → ~50 rows per page touched

Low correlation, index scan forced for comparison:

Index Scan using payments_merchant_id_idx on payments
    (cost=0.57..648210.30 rows=198200 width=64) (actual time=0.05..11204.6 rows=199840 loops=1)
  Index Cond: (merchant_id = ANY ('{…}'::bigint[]))
  Buffers: shared hit=14002 read=186220
  -- ~200k buffers for 200k rows → one page per row: fully random heap access
  -- cost is 70× the created_at scan for the same row count

The metric to read: heap buffers per row returned. Near 1 / rows-per-page means ordered access; near 1.0 means random.

Buffers per row returned Left: created_at with correlation 0.999 reads about 4,300 buffers for 204 thousand rows, about 0.02 buffers per row. Right: merchant_id with correlation 0.004 reads about 200 thousand buffers for 200 thousand rows, one buffer per row. merchant_id · correlation 0.004 Buffers: hit=14002 read=186220 rows=199840 ≈ 1.0 buffer per row → random created_at · correlation 0.999 Buffers: hit=2440 read=1904 rows=204110 ≈ 0.02 buffers per row → ordered divide buffers by rows: the ratio exposes physical order

Step-by-Step Resolution #

  1. Read correlation for the column driving the range or ORDER BY scan.

  2. Measure buffers per row with EXPLAIN (ANALYZE, BUFFERS) on the real query. Methods for attributing buffers to nodes are in using BUFFERS to find I/O hotspots.

  3. Choose the remedy by access pattern.

    • Many rows by a scattered key, no ordering needed: let the planner use a bitmap heap scan; do not force an index scan.
    • The query also needs heap columns and rows per key are many: a covering index removes heap fetches entirely — see covering index design.
    • The table is read mostly by one key and rarely written: CLUSTER reorders it once.
    • The column is naturally ordered by insertion and range-scanned: a BRIN index is far smaller than a B-tree.

  4. Apply it.

    -- one-off physical reorder (takes ACCESS EXCLUSIVE lock for the rewrite)
CLUSTER payments USING payments_merchant_id_idx;
ANALYZE payments;

-- or, for the naturally ordered column
CREATE INDEX payments_created_at_brin ON payments USING brin (created_at);

  5. Re-check correlation and buffers per row. After CLUSTER, correlation for the clustering column should be near 1, and heap reads should collapse toward sequential.

Correlation is squared in the cost model A curve of relative index scan cost against correlation from 0 to 1. Cost stays near the worst case until correlation is well above 0.5, then falls steeply toward the best case as correlation approaches 1. Markers show merchant_id at 0.004 near the worst case and created_at at 0.999 at the best case. 00.51.0 worst best merchant_id 0.004 created_at 0.999 |correlation| of the index column

Before and After #

-- BEFORE: merchant lookup, correlation 0.004
Index Scan using payments_merchant_id_idx  Buffers: shared read=186220   Execution Time: 11204.6 ms

-- AFTER: CLUSTER payments USING payments_merchant_id_idx; ANALYZE  (correlation 0.9997)
Index Scan using payments_merchant_id_idx  Buffers: shared read=3108     Execution Time: 142.9 ms

How correlation decays and how to watch it #

CLUSTER produces perfect order once. After that, every INSERT goes to whatever page has free space — often the end of the table, sometimes a hole left by a deleted row — and every UPDATE writes a new row version, which stays on the same page only when there is room there (a HOT update) and otherwise moves elsewhere. On a table where most activity is inserts of new merchants’ payments, correlation on merchant_id falls steadily as new rows accumulate outside the clustered region. On a table with frequent updates to wide rows, it falls faster still.

Leaving free space on each page with fillfactor slows the decay for updates, because more updates stay on their original page:

ALTER TABLE payments SET (fillfactor = 90);
CLUSTER payments USING payments_merchant_id_idx;   -- rewrite applies the fillfactor

Track the statistic after each automatic analyze, and schedule the next CLUSTER when it drops below the point where the plan changed — for this workload, roughly 0.9:

SELECT now(), correlation FROM pg_stats
WHERE tablename = 'payments' AND attname = 'merchant_id';

Correlation and multicolumn or expression indexes #

pg_stats.correlation is stored per column, and for a multicolumn index the planner uses the correlation of the leading column only. An index on (merchant_id, created_at) is costed as randomly ordered if merchant_id is, even when rows for each merchant happen to be stored in time order. Expression indexes use the expression’s statistics, which exist only after an ANALYZE that follows the index creation. In both cases the estimate may be more pessimistic than reality, and the evidence to trust is the measured buffers per row in EXPLAIN (ANALYZE, BUFFERS), not the cost.

Common Pitfalls #

Clustering a write-heavy table. New and updated rows land wherever there is space, so correlation decays quickly. Diagnostic signal: correlation falling back toward zero within days. Fix: prefer a covering index or bitmap scans; CLUSTER suits mostly-static tables.

Running CLUSTER on a live table. It holds an ACCESS EXCLUSIVE lock for the whole rewrite. Diagnostic signal: blocked reads and writes for the duration. Fix: schedule a maintenance window, or use an online table-rewrite tool.

Creating BRIN on an unordered column. Each block range then spans nearly the whole value range, so every range matches. Diagnostic signal: Rows Removed by Index Recheck close to the table size. Fix: use BRIN only where correlation is naturally high.

Forgetting to re-analyze. The planner keeps using the old correlation until statistics are refreshed. Diagnostic signal: no plan change after CLUSTER. Fix: ANALYZE immediately after.

Frequently Asked Questions #

What does correlation in pg_stats mean? The correlation between a column’s value order and the table’s physical row order, from −1 to 1. The planner uses it to estimate how many random page reads an index scan needs.

Does CLUSTER keep the table ordered? No. It rewrites the table once. New and updated rows go wherever space is free, so correlation decays and the command must be repeated.

When is a BRIN index a better choice than a B-tree? When the column is naturally and persistently correlated with physical order, such as an insert timestamp on an append-only table.

Up: Sequential vs Index Scans