PostgreSQL v12 reworked B-tree index storage, and v13 added deduplication of index entries. v14 continues the line with "bottom-up" index entry deletion (commit d168b666823b6e0bcf60ed19ce24fb5fb91b8ccf), aimed at reducing unnecessary page splits, index bloat and fragmentation in heavily updated indexes.
Where index bloat comes from
A B-tree holds one index entry per row version ("tuple") that is still visible to somebody. When VACUUM removes dead tuples, it must delete the matching index entries too, leaving empty space in the index page — space that is reusable, but stays empty if nothing is inserted there.
Some bloat is normal. Beyond a certain point, though, it costs:
- range scans touch more pages;
- cached index pages consume RAM for bloat;
- fewer entries per page mean less fan out, so the index may carry more levels than needed.
Frequent updates to the same row make this worse: until VACUUM catches up, table and index hold many versions of one row. When an index page fills, PostgreSQL splits it in two — an expensive operation that leaves behind two bloated pages once VACUUM has cleaned up.
Existing defenses
HOT tuples
Heap-only tuple updates are PostgreSQL's strongest defense against index churn. An UPDATE produces tuples referenced only by the previous version of the table row rather than by an index, so no new index entry is written at all and index bloat is avoided entirely.
Killing index tuples
When an index scan meets an entry pointing at a dead table tuple, it marks that entry as "killed"; later scans skip it before VACUUM gets to remove it. If the index page is full, PostgreSQL can delete such entries to avoid a page split.
Bottom-up deletion in v14
Bottom-up index tuple deletion goes further. Immediately before a page split, it removes index entries that point to dead tuples. Fewer entries can mean the split is avoided altogether, along with the bloat it would have caused later when VACUUM ran. In effect, part of VACUUM's work is done earlier, at the moment where it prevents bloat.
Measuring the effect with pgbench
A custom pgbench run compared v13 and v14. The test table:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
CREATE TABLE testtab ( id bigint CONSTRAINT testtab_pkey PRIMARY KEY, unchanged integer, changed integer ); INSERT INTO testtab SELECT i, i, 0 FROM generate_series(1, 10000) AS i; CREATE INDEX testtab_unchanged_idx ON testtab (unchanged); CREATE INDEX testtab_changed_idx ON testtab (changed); |
The pgbench script, bench.sql:
|
1 2 3 4 5 6 7 8 9 10 11 |
set id random_gaussian(1, 10000, 10) UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; |
A normal distribution was chosen because real workloads tend to update some (recent) rows more than others. Each row is updated ten times, to make a page split more likely. The script runs 60000 times — 10000 iterations across 6 clients:
|
1 |
pgbench -n -c 6 -f bench.sql -t 10000 test |
Index statistics come from the pgstattuple extension via psql:
|
1 2 3 4 5 6 |
SELECT i.indexrelid::regclass AS index, s.index_size, s.avg_leaf_density FROM pg_index AS i CROSS JOIN LATERAL pgstatindex(i.indexrelid) AS s WHERE indrelid = 'testtab'::regclass; |
Those are the v13 results:
|
1 2 3 4 5 6 |
index │ index_size │ avg_leaf_density ═══════════════════════╪════════════╪══════════════════ testtab_pkey │ 319488 │ 66.6 testtab_unchanged_idx │ 4022272 │ 5.33 testtab_changed_idx │ 4505600 │ 13.57 (3 rows) |
And for v14:
|
1 2 3 4 5 6 |
index │ index_size │ avg_leaf_density ═══════════════════════╪════════════╪══════════════════ testtab_pkey │ 245760 │ 87.91 testtab_unchanged_idx │ 532480 │ 39.23 testtab_changed_idx │ 4038656 │ 14.23 (3 rows) |
The largest gain is in testtab_unchanged_idx: in v13 the index is severely bloated, while in v14 it shows only 60% bloat, which is acceptable for an index. That is where the new feature matters most — the UPDATE never scans this index, so no killed index tuples exist, yet bottom-up deletion still removed enough entries to avoid a page split in most cases.
testtab_pkey improves measurably as well. Because the UPDATE does scan that index, dead entries get killed, and the feature removes them before a split. The gap to v13 is smaller here, since v13 already handles this index well.
testtab_changed_idx cannot benefit: the feature only addresses the case where the UPDATE leaves the indexed value alone. Its lower leaf density compared with testtab_unchanged_idx on v13 comes from index deduplication, which can apply because the index entry is not modified.
Upgrades
The index storage format did not change, so the feature works automatically after pg_upgrade for indexes created on PostgreSQL v12 or later. An index created on an earlier version needs a REINDEX to benefit, since pg_upgrade only copies index files and does not update the internal index version.
