Index bloat in Postgres: why VACUUM never shrinks an index

TL;DR. Postgres tables and indexes bloat by different mechanisms, and the index mechanism is structural. A heap page's free space can hold any new row; an index entry must live where its key sorts, so free space in the wrong key range helps nobody. VACUUM deletes dead index entries but returns a page to the tree only when the page is completely empty, and B-tree pages split as they fill without ever merging back. Postgres 13 and 14 slowed the update-driven path down considerably. The delete-driven path, the one queue-shaped and time-ordered workloads hit, still has exactly one fix: rebuild the index.

In a pgbench test Cybertec ran against PostgreSQL 13, an update-heavy workload on a 10,000-row table left an index at 4 MB with its leaf pages 5.33 percent full, and the interesting detail is which index: one on a column no UPDATE in the test ever changed. The table's logical content ended where it started. The index grew about nineteen times past what its live entries needed and stayed there, because nothing in ordinary Postgres operation ever gives that space back. Understanding why that happens, which workloads trigger it, and what the last few major versions did about it is the difference between reindexing on evidence and reindexing on folklore.

Free space in the wrong key range is dead space

Table bloat and index bloat are usually explained together, dead tuples accumulating under MVCC, and the shared explanation hides the part that matters. When VACUUM clears dead tuples from a heap page, the reclaimed space is generally useful: a heap row can be inserted wherever there is room. An index does not have that freedom. A B-tree entry must be placed where its key sorts, so space freed on a leaf page covering the key range 2024-03-01 to 2024-03-04 is usable only by new entries that happen to fall in that range. If your keys are timestamps or sequential ids, no new entry will ever fall there again.

That asymmetry is compounded by two rules of the B-tree's on-disk life. First, pages split but never merge: when a leaf page fills, it becomes two, and no later deletion pattern will fold two half-empty ones back into one. Second, the reclaim rule is all-or-nothing: B-tree pages that become completely empty are reclaimed for reuse elsewhere in the index, and a page holding even one live entry stays allocated. The documentation states the resulting failure mode plainly: a usage pattern in which most, but not all, keys in each range are eventually deleted will see poor use of space. Even the reclaimed pages only go back into the index's own free list. Short of a rebuild, the file on disk never gets smaller.

A new index starts dense on purpose: leaf pages are packed to the default fillfactor of 90 percent at build time and when the index extends at the right end. Everything after that build is a slow walk downward, and how fast you walk depends on the workload's shape.

Two workload shapes produce most of it

The moving key range. Job queues, event logs, session tables, anything indexed on a timestamp or a serial id where old rows are deleted as new ones arrive. Inserts land at the right edge of the tree, in fresh, dense pages. Deletes hollow out the left. Every failed job that is kept, every event flagged for review, every session with a legal hold pins its leaf page at one or two live entries out of a few hundred. This is the documented worst case above, and it is invisible from table size: the table can hold a steady 100,000 rows for months while its indexes triple.

The empty-page rule at work. Old pages keep a straggler each and stay allocated; only the one page that emptied completely leaves the tree.

Update churn on non-HOT tables. An UPDATE in Postgres writes a new row version, and unless the heap-only-tuple optimization applies, that new version needs a new entry in every index on the table, including indexes on columns whose values the update did not touch. HOT is off the table the moment any indexed column changes, so one volatile indexed column, a status flag or an updated_at timestamp, taxes every other index beside it. This is exactly the workload in the Cybertec test: the index that bloated worst was on a column the updates never modified. It filled with identical-key entries pointing at successive row versions, page after page of version history that no query would ever want.

Which shape you have determines what, if anything, recent Postgres versions already did for you.

Postgres 13 and 14 fixed half of the problem

Two B-tree changes landed a few versions back, both aimed squarely at the second shape.

Deduplication, in Postgres 13, merges groups of equal-key entries into a single posting list: the key stored once, followed by a sorted array of row pointers. The pass runs lazily, only when an incoming entry would otherwise split the page, which makes splits rarer and buys time for cleanup to catch up. It has exclusions worth knowing: numeric and therefore jsonb columns cannot deduplicate, neither can float4, float8, container types, text under nondeterministic collations, or any index with INCLUDE columns.

Bottom-up index deletion, in Postgres 14, attacks version churn directly. When a page is about to suffer a split driven by accumulating row versions, the index first checks which of its entries point to versions no transaction can see anymore and deletes them, often avoiding the split entirely. The feature specifically targets indexes that updates do not logically modify, the innocent-bystander case above. In the same Cybertec test on Postgres 14, that unchanged-column index landed at 532 kB and 39 percent leaf density instead of 4 MB and 5 percent: about seven and a half times smaller, from a minor-version upgrade's worth of effort.

Neither mechanism touches the first shape. A deleted queue entry is not a row version waiting to be cleaned; it is gone, and the sparse pages it leaves behind hold distinct keys that no posting list can compress. If your bloat comes from the moving key range, you are on Postgres 18 exactly where you were on Postgres 11.

Measure density, not estimates

Most bloat dashboards run some descendant of the check_postgres estimation query that circulates on the Postgres wiki. Those queries infer expected index size from column statistics, which makes them cheap and approximately right at best; they exist because the exact method used to be expensive. The exact method is pgstatindex, from the pgstattuple extension in contrib:

CREATE EXTENSION IF NOT EXISTS pgstattuple;

SELECT avg_leaf_density, leaf_fragmentation
FROM pgstatindex('orders_created_at_idx');

avg_leaf_density is the number to watch, read against the build-time baseline of about 90: the gap between that and what you measure is the rebuild's payoff. The honesty has a price: pgstatindex walks the whole index, page by page, under a read lock. On a multi-gigabyte index that is real I/O, so run it on a replica or off-peak, and sample the handful of indexes pg_stat_user_indexes says are both large and hot rather than sweeping the catalog nightly.

The measurement matters beyond disk. A 40-percent-dense index does over twice the I/O per range scan that a dense one does, and it occupies over twice the shared_buffers space to keep the same entries cached. On managed platforms that price storage and I/O separately, bloat is one of the quiet line items autoscaling cannot optimize away: capacity follows the waste instead of questioning it.

The fix is a rebuild, and it is one reviewable statement

Since Postgres 12, REINDEX INDEX CONCURRENTLY builds a replacement index alongside the old one and swaps it in, holding only a SHARE UPDATE EXCLUSIVE lock, so reads and writes flow throughout. Plain REINDEX is faster and simpler but takes an ACCESS EXCLUSIVE lock on the index, blocking writes to the table and any reads that would use that index, the same lock discipline that governs all online DDL. The concurrent path's costs are bounded and worth stating: two table scans, a wait for every transaction that might use the index to finish (one long-running analytics query stalls the swap), and peak disk holding both the old and new index at once.

It can also fail, and the failure mode is polite but littering: an interrupted or errored run leaves behind an invalid index suffixed _ccnew, which continues to receive writes while serving no queries. After any failed run, check pg_index for indisvalid = false, drop the leftover, and rerun. The REINDEX reference page documents the cleanup, and skipping it means paying the bloat tax twice on the same index.

One property of this fix deserves more attention than it gets. REINDEX INDEX CONCURRENTLY orders_created_at_idx is a single statement naming a single object, with a measurable before and after: density 41 going in, density 90 coming out. That makes it reviewable in a way most database maintenance never was, the same property that Postgres 19's REPACK brings to table bloat. Whether the operator is a person on a Tuesday night or an agent proposing maintenance, "this index is at 41 percent density and here is the one statement that fixes it" is an approvable claim. "The database feels slow, I will clean some things up" is not.

A rebuild is not a cure, and treating it as one is the most common way teams end up reindexing quarterly forever. If the workload is a moving key range, the index starts re-bloating the moment the rebuild commits, on the same schedule as before. For queue and log tables the durable fix is usually structural: partition by time and drop or truncate old partitions, which discards index entries wholesale instead of hollowing out pages one delete at a time. Reindex to reclaim the past; change the shape to protect the future.

Datapace is building the context layer between your databases and your AI: resolved meaning validated by the people who own the data, the workload evidence beside it (cost, performance, usage and freshness, lineage), and a policy gate over what an agent may do and access, served over MCP. Bloat is a good example of the evidence half: whether an index is worth rebuilding is answerable from measurements, and the measurements belong next to the schema they describe. If storage and I/O waste is the thread you are pulling, start with the cost optimization use case.

Sources

1. PostgreSQL documentation, Routine Reindexing (empty-page reclaim rule, the most-but-not-all-keys-deleted pattern, access speed of fresh indexes).
2. PostgreSQL documentation, B-Tree Indexes: Implementation (deduplication and posting lists, bottom-up index deletion, deduplication exclusions).
3. PostgreSQL documentation, REINDEX (locks, concurrent rebuild costs, invalid _ccnew indexes and recovery).
4. PostgreSQL documentation, CREATE INDEX (B-tree default fillfactor of 90).
5. PostgreSQL documentation, pgstattuple (pgstatindex output, page-by-page accumulation, locking).
6. Cybertec, Index bloat reduced in PostgreSQL v14 (measured index sizes and leaf densities on the same workload under v13 and v14).
7. PostgreSQL wiki, Index Maintenance (estimation queries and their provenance).