The biggest index in our orders database was on a column with five distinct values. The table held about 400 million rows, and the plain btree on status weighed 13.6 GB — roughly a fifth of the table itself — because every row paid for its own index tuple, and eighty million of those tuples stored the exact same key bytes for 'shipped'. The embarrassing part is the timeline: we had pg_upgraded that cluster from PostgreSQL 12 to 14 almost two years earlier, and deduplication — the headline btree feature that shipped in PostgreSQL 13 — had done nothing for us the entire time. Not because it was off, but because nothing had ever rewritten the index.
One Sunday morning I ran REINDEX INDEX CONCURRENTLY on it. Forty-one minutes later the index came back at 2.4 GB, same column, same queries, same plans, same latency on the fulfillment queue's status = 'pending' lookup. Nearly six times smaller, from a storage-format change that was sitting in the binary the whole time, waiting for someone to rebuild. The mechanics of posting lists themselves are covered in the posting lists field notes; this note is about the operational gap — why upgraded clusters keep their fat indexes, how to find the ones worth rebuilding, and how to prove the shrink was real.
What does btree deduplication actually store instead of duplicate keys?
It stores posting lists: one index tuple per distinct key value that carries a sorted array of heap tuple identifiers, instead of one index tuple per table row. Before PostgreSQL 13, eighty million rows with status = 'shipped' meant eighty million index tuples, each repeating the key, each paying tuple-header and alignment overhead. After 13, those collapse into chains of compact tuples that are mostly just TID arrays — roughly six bytes per row instead of sixteen-plus. That per-row difference is the entire 5.7x from my incident, and it is why the win is so boring to explain and so large to measure.
Two design properties matter operationally. First, deduplication is lazy: nbtree runs a dedup pass when a page fills and would otherwise split, merging what it can before resorting to the split. It is a split-avoidance strategy, not a background compaction job — you cannot schedule it and you cannot force it short of a rebuild. Second, it is purely physical. The planner, the opclass, the scan semantics see no difference; TIDs inside a posting list stay in heap order, so bitmap heap scans still get physically sorted input for free. And one posting list is bounded by the maximum index tuple size — about 2704 bytes on standard 8 KB pages — so a key with millions of duplicates becomes many posting lists rather than one magical tuple. The win stays enormous; it just is not infinite.
Why does deduplication only pay off on low-cardinality indexes?
Because the savings are per duplicate row, so the ratio of old size to new size is basically the ratio of rows to distinct keys. The arithmetic is crude but predictive. With N rows and K distinct keys, a pre-13 index carries N full tuples; a deduplicated one carries K keys plus roughly N six-byte TID entries. Our orders index had N = 400 million and K = 5, which is as lopsided as real schemas get, and the measured 13.6 GB to 2.4 GB lands close to what the napkin says. A btree on an email column with 300 million distinct values has almost no duplicates to merge — the old format already stores one tuple per key — and rebuilding it buys you nothing but a fresher fillfactor. Status flags, type enums, boolean-ish markers, tenant columns where one tenant owns ninety percent of the rows: those are the candidates. The quick screen is n_distinct from pg_stats against the index's size in bytes — when a multi-gigabyte index sits on a column with single-digit distinct values, you are looking at repeated key bytes wearing an index costume.
One honest exception, because it keeps people from overcorrecting: write-heavy unique indexes do benefit, through MVCC garbage rather than through true duplicates. An UPDATE leaves the old row version's index entry in place until vacuum removes it, so between vacuum cycles a hot row's key value appears in the unique index many times — duplicates in the only sense the storage layer cares about — and posting lists merge those. That is a real effect on churn-heavy tables, and it is the version of the story where unique indexes gain. It does not change the rule for the audit below: it changes what you expect from it, which I get to in the verification section.
Why doesn't the upgrade deduplicate your existing indexes by itself?
Because deduplication is a physical storage decision made when index pages are written, and pg_upgrade copies relation files byte for byte without rewriting them. An index built on PostgreSQL 12 arrives on PostgreSQL 14 in exactly the layout 12 wrote, and since dedup only runs when a page fills and faces a split, the only pages that ever get the new treatment are the ones later churn forces open. A mostly-static index on a status column — rows enter as 'pending', leave as 'archived', and the giant 'shipped' mass just sits there — can run for years on a dedup-capable version while keeping its entire pre-13 body. That was our cluster: the capability had been live since the upgrade reboot, and the benefit was zero until something rebuilt the index from scratch. New indexes created on 13+ deduplicate from birth; inherited ones do not.
The deterministic fix is a full rebuild, and the audit query is a two-minute job. Find big indexes, check the cardinality of their columns, rebuild the lopsided ones:
SELECT schemaname, relname AS table_name, indexrelname,
pg_size_pretty(pg_relation_size(indexrelid)) AS index_size,
idx_scan
FROM pg_stat_user_indexes
WHERE pg_relation_size(indexrelid) > 1073741824
ORDER BY pg_relation_size(indexrelid) DESC;
SELECT attname, n_distinct, null_frac
FROM pg_stats
WHERE tablename = 'orders';
SELECT pg_size_pretty(pg_relation_size('orders_status_idx')) AS before_size;
REINDEX INDEX CONCURRENTLY orders_status_idx;
SELECT pg_size_pretty(pg_relation_size('orders_status_idx')) AS after_size;REINDEX CONCURRENTLY is the right tool on a live system — the plain form blocks writes to the table for the whole build — but respect its cost sheet. It cannot run inside a transaction block. It builds a full second copy and swaps, so you need the index's own size again in free disk, and the build's I/O competes with your workload for those forty-one minutes. It takes brief exclusive locks at the start and end; ours waited ninety seconds behind a long report query before the final swap landed. And if it fails or is interrupted, it leaves an invalid index with a _ccnew suffix that serves no queries — drop it before retrying, or the next attempt builds a third copy. The full workflow is in the REINDEX guide.
How does deduplication interact with bloat and bottom-up deletion?
Deduplication shrinks live duplicates; PostgreSQL 14's bottom-up index deletion prunes dead ones in place, and the two compose into most of the reason a rebuilt low-cardinality index stays small. Before 14, a page full of mostly-dead posting-list entries still had to split when a new tuple needed room, and splits are how ordinary churn hardens into permanent bloat — the page count ratchets up and vacuum rarely gets to hand whole pages back. Bottom-up deletion instead prunes individual dead TIDs out of posting lists in place when a split looms, confirming against the heap before removing them, and postpones or avoids the split entirely. On our orders index, the rebuilt 2.4 GB has been stable for months of steady churn, which is the two features doing their jobs together: dedup keeps the live set compact, bottom-up deletion keeps the garbage from cracking pages open.
Know what neither one fixes, because this is where the expectation goes wrong. Updates that modify the indexed column mint brand-new index entries — those are non-HOT updates, and no storage trick reclaims them cheaply; that is the fillfactor and HOT-update conversation, and the bloat patterns it produces are the ones the btree index bloat notes walk through. And a low-cardinality index has a bloat shape of its own: a single key's posting lists sprawl across thousands of pages, so deleting all rows of one status leaves a sparse middle that vacuum cannot return to the operating system — only the tail comes back. REINDEX remains the compaction tool of last resort there; deduplication just means you need it far less often than a PG12-era baseline would suggest.
How do you verify the shrink — and when should you not expect one?
Measure three numbers and write them down before you touch anything: pg_relation_size of the index, idx_scan from pg_stat_user_indexes as the usage baseline, and n_distinct from pg_stats as the dedup forecast. After the rebuild, size is the payoff, and idx_scan ticking upward at its old rate is the proof that the planner still uses the index exactly as before — deduplication changes storage, not scan behavior, so a query regression after REINDEX has another cause, usually freshly reset statistics or a changed fillfactor rather than posting lists. If you want the physical confirmation, pgstattuple's pgstatindex reports avg_leaf_density; ours went from the low forties percent before the rebuild to about 91 percent after, which is the difference between an index that is mostly empty space and one that is mostly useful bytes.
The not-worth-rebuilding list is just as valuable as the candidate list, because a pointless REINDEX CONCURRENTLY still costs you a full copy's worth of disk and I/O. Skip unique and primary-key indexes on append-mostly tables with vacuum keeping pace — there are no physical duplicates to merge, and the rebuild only repacks free space you could reclaim with a fraction of the effort. Skip high-cardinality columns for the same reason. Skip any index with INCLUDE columns, which never deduplicate — the payload columns are not part of the key, so there is no whole-tuple equality to merge on. Skip indexes built on nondeterministic collations, which opt out because dedup requires equal keys to be truly interchangeable. And check reloptions for deduplicate_items = off before blaming the format — we found one index where a migration had carried that setting through a dump and restore years earlier, quietly exempting it from the feature the whole time. When two of your top-ten indexes by size come back from a rebuild within a few percent of where they started, that is not a failed reindex; it is a correct forecast you skipped.
Watching index sizes catch up with reality, with MonPG
Everything in this note is counter-shaped, which is why the audit stops being folklore once you graph it. Per-index size over time makes the 13.6-to-2.4 GB step a visible event instead of a rumor, and the regrowth slope afterward tells you whether bottom-up deletion is keeping pace with your churn or whether the table's update pattern is rebuilding bloat underneath you. idx_scan alongside size answers the second question every audit raises — is this thing even used — before you spend I/O rebuilding it, and the bloat-detection side of the loop pairs naturally with the reindex workflow. MonPG graphs exactly these series — index and table sizes over time, index scan counts, dead tuples and vacuum runs on the parent table — as part of its PostgreSQL monitoring, retained long enough to compare this quarter's index body against the one pg_upgrade handed you. The step-down after a dedup-aware rebuild should be the last surprise your status column ever gives you.