Why table order matters for index scans

In a PostgreSQL heap table, rows have no inherent order. B-tree indexes give you fast point lookups, but range scans can suffer badly: each row you fetch may live in a different 8 kB block, turning what should be a sequential read into a scatter of random I/O operations. If the table happens to be physically sorted in the same order as the index, however, a range scan touches far fewer blocks and becomes substantially cheaper.

The CLUSTER command rewrites a table in the order of a chosen index. The trade-off is that only one physical ordering can exist, so you can only fully optimize range scans on one index per table. Indexes that share leading columns with the clustering index will still benefit to some degree.

PostgreSQL's planner quantifies this effect via the correlation statistics that ANALYZE collects for each column: a value of 1 means ascending physical order, -1 means descending, and near 0 means no relationship between logical and physical order. The optimizer uses this number when estimating the cost of index range scans.

CLUSTER's pain points

Because CLUSTER shares its implementation with VACUUM (FULL), it inherits two serious drawbacks:

  • It takes an ACCESS EXCLUSIVE lock, blocking even reads while it runs.
  • It needs roughly twice the table's disk space temporarily.

There is also a third problem that persists after the operation finishes: the ordering does not survive normal workload. New INSERTs append rows at the end, and UPDATEs create new row versions elsewhere in the heap. Over time, correlation decays and you have to repeat the expensive CLUSTER procedure.

HOT updates keep rows in place

While there is no way to keep INSERTs from degrading physical order, HOT (Heap-Only Tuple) updates offer a way to preserve it under UPDATE load. A HOT update leaves the new version of a row in the same 8 kB block as the old version, and does not modify any indexed column. That means it barely disturbs the correlation of indexed columns at all, so index range scans stay efficient after updates.

There are limitations. HOT cannot help with INSERTs, and to make updates HOT you must set a fillfactor below 100, which leaves empty space in each block. That artificial bloat slows down sequential scans and reduces cache efficiency.

Testing HOT's effect on correlation

To measure how well HOT preserves the order set by CLUSTER, a test table was loaded with 10 million rows in random key order, then clustered on key. An unlogged table was used since WAL is irrelevant to the observed effect, and shared_buffers was sized to avoid disk I/O. Autovacuum was tuned aggressively so it could keep up with the update workload.

With the table prepared, a custom pgbench script ran 60 million UPDATEs against the key column with six concurrent clients on PostgreSQL 15.2. The benchmark then measured three things:

  • How well key correlation survived the workload.
  • What fraction of updates were HOT, and whether autovacuum was triggered.
  • How much the table and its indexes bloated, relative to the freshly clustered sizes (the table occupied 422 MB, the two indexes together 428 MB).

Various fillfactor settings were tested. Once all updates were HOT, lowering the fillfactor further produced no additional benefit.

Results

The benchmark results confirmed the expected behavior: with a sufficiently low fillfactor, all or nearly all updates became HOT, and correlation remained essentially intact. Table and index bloat stayed limited to the space reserved by the fillfactor, since HOT updates never move rows to other pages. With a higher fillfactor, fewer updates were HOT, correlation degraded, and the table required re-clustering to restore performance.

Implications

For tables that receive no INSERTs, setting fillfactor so that most updates are HOT can keep the physical ordering established by CLUSTER intact indefinitely. That means fast index range scans without the need to schedule periodic re-clustering runs. The new row version stays in the same page as the old one, so the correlation that CLUSTER established is preserved, and you avoid the access-exclusive lock and double disk space cost of repeated clustering.