B-Tree Deduplication and Index Size #

An index on orders(status) is 2.1 GB on one server and 640 MB on another holding the same data. Scans through the larger one read three times as many pages, and the planner prices it accordingly. Both run PostgreSQL 16. The difference: the smaller index was built after upgrading, the larger one came across with pg_upgrade from PostgreSQL 12 and still uses the old on-disk format without deduplication.

B-tree structure and access patterns are covered in B-tree index optimization. Deduplication changes how duplicate keys are stored, which changes size, scan cost and bloat behaviour.

The Index Condition #

Before PostgreSQL 13, a B-tree stored one leaf entry per heap tuple: the key plus a tuple identifier. An index on a column with five distinct values over 100 million rows held 100 million entries, each repeating one of five keys.

From PostgreSQL 13, B-tree deduplication stores runs of equal keys as a single posting list entry: the key once, followed by a compact array of tuple identifiers. Deduplication happens lazily, when a leaf page would otherwise split, so an index converges to its compact form as it fills. The effect depends on repetition:

Deduplication is not available for some indexes:

It is on by default and can be disabled per index with WITH (deduplicate_items = off).

Smaller indexes help plans directly: fewer leaf pages to read for range scans and bitmap scans, fewer levels in large trees, and a lower cost in the planner’s index scan estimate, which can move the crossover toward index access as described in sequential vs index scans.

One entry per row versus posting lists Left, without deduplication: a leaf page holds repeated entries such as shipped with one tuple identifier each, so a page holds a few hundred entries. Right, with deduplication: a leaf page holds shipped once followed by a posting list of many tuple identifiers, so the same page covers thousands of rows. before PostgreSQL 13 / old format (shipped, tid 1) (shipped, tid 2) (shipped, tid 3) … one entry per row ≈ 400 row pointers per leaf page deduplicated posting list shipped → [tid 1, tid 2, tid 3, …] key stored once per run compact tid array thousands of row pointers per leaf page the saving grows with how often each key repeats

Annotated EXPLAIN Evidence #

SELECT indexrelid::regclass, pg_size_pretty(pg_relation_size(indexrelid))
FROM pg_index WHERE indrelid = 'orders'::regclass;
         indexrelid          | pg_size_pretty
-----------------------------+----------------
 orders_pkey                 | 2014 MB
 orders_status_idx           | 2104 MB     -- 5 distinct values, yet as large as the primary key
 orders_customer_id_idx      | 1980 MB

Check the on-disk version with pageinspect:

CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT version, allequalimage FROM bt_metap('orders_status_idx');
 version | allequalimage
---------+---------------
       3 | f             -- version 3: pre-13 format, deduplication impossible

A bitmap scan for one status before rebuilding:

Bitmap Heap Scan on orders  (actual time=412.8..3204.1 rows=4020110 loops=1)
  ->  Bitmap Index Scan on orders_status_idx  (actual time=402.6..402.6 rows=4020110 loops=1)
        Index Cond: (status = 'returned'::text)
        Buffers: shared hit=2210 read=19204        -- ~21k index pages read

After REINDEX INDEX CONCURRENTLY orders_status_idx:

  ->  Bitmap Index Scan on orders_status_idx  (actual time=98.4..98.4 rows=4020110 loops=1)
        Index Cond: (status = 'returned'::text)
        Buffers: shared hit=4104                  -- ~4k index pages; version 4, deduplicated
-- index size: 2104 MB → 612 MB
Checking deduplication status Three items are annotated. An index on five values as large as the primary key suggests no deduplication. bt_metap version 3 shows the pre-PostgreSQL-13 format. Index buffers per scan falling from 21 thousand to 4 thousand after REINDEX shows the effect on plans. orders_status_idx 2104 MB (5 values) as big as the unique primary key bt_metap … version = 3 old format, deduplication off Buffers: read=19204 → hit=4104 5× fewer index pages per scan version 4 is required; pg_upgrade keeps old indexes at version 3

Step-by-Step Resolution #

  1. Find large indexes on repetitive keys. Compare index size with distinct counts:

    SELECT i.indexrelid::regclass AS index, pg_size_pretty(pg_relation_size(i.indexrelid)) AS size,
       s.n_distinct
FROM pg_index i
JOIN pg_attribute a ON a.attrelid = i.indrelid AND a.attnum = i.indkey[0]
JOIN pg_stats s ON s.tablename = i.indrelid::regclass::text AND s.attname = a.attname
WHERE i.indrelid = 'orders'::regclass;

  2. Check the B-tree version with bt_metap(). Version 3 or lower means the index predates PostgreSQL 13 and must be rebuilt.

  3. Check eligibility. INCLUDE columns, numeric, float, jsonb, array and nondeterministic-collation keys prevent deduplication. Consider whether a column type change (for example numeric codes to integer) or dropping INCLUDE columns is worthwhile.

  4. Rebuild without blocking writes:

    REINDEX INDEX CONCURRENTLY orders_status_idx;

    After a major-version upgrade with pg_upgrade, schedule concurrent rebuilds for all large B-tree indexes — the procedure in REINDEX CONCURRENTLY without downtime.

  5. Measure leaf density after the rebuild with pgstattuple:

    CREATE EXTENSION IF NOT EXISTS pgstattuple;
SELECT leaf_pages, avg_leaf_density FROM pgstatindex('orders_status_idx');

  6. Re-check plans that use the index; lower index scan costs can change access paths.

What rebuilding saved per index The status index fell from 2,104 to 612 megabytes. The customer_id index fell from 1,980 to 1,140 megabytes. The primary key stayed at 2,014 megabytes because its keys are unique. An index with INCLUDE columns stayed at 2,610 megabytes because it cannot deduplicate. status (5 values) 2,104 → 612 MB customer_id 1,980 → 1,140 MB primary key (unique) 2,014 → 2,014 MB (status) INCLUDE (total) 2,610 → 2,610 MB bars show size after REINDEX; repetitive keys shrink, unique and INCLUDE do not

Before and After #

-- BEFORE: orders_status_idx, B-tree version 3 (pg_upgrade from 12)
Bitmap Index Scan on orders_status_idx  Buffers: shared hit=2210 read=19204   index size 2104 MB

-- AFTER: REINDEX INDEX CONCURRENTLY
Bitmap Index Scan on orders_status_idx  Buffers: shared hit=4104              index size 612 MB

Deduplication and update bloat #

On unique indexes, deduplication matters for a different reason. An update that is not HOT inserts a new index entry for the new row version while the old entry remains until vacuum. On a hot row updated many times between vacuums, the unique index accumulates several entries for the same key. PostgreSQL 13+ can deduplicate those versions and, from PostgreSQL 14, also performs bottom-up index deletion, removing entries for dead versions when a page would otherwise split. Together they keep unique indexes on update-heavy tables far smaller than they were on older releases, which reduces the index bloat discussed in measuring index bloat with pgstattuple. Neither mechanism works on indexes still in the version 3 format.

Deduplication has a small write cost: when a page fills, the server spends CPU merging entries before deciding whether to split. On indexes with unique keys and heavy insert load, that work finds nothing to merge. PostgreSQL skips it for unique indexes unless it detects duplicates from versions, so there is rarely a reason to disable it; deduplicate_items = off is worth testing only on insert-heavy, non-unique indexes with near-unique keys.

Common Pitfalls #

Assuming pg_upgrade modernises indexes. It keeps their on-disk format. Diagnostic signal: bt_metap version 3. Fix: REINDEX CONCURRENTLY after upgrading.

Adding INCLUDE columns to a repetitive index. It disables deduplication. Diagnostic signal: covering index several times larger than the key-only version. Fix: weigh index-only scan benefits against the size, as in INCLUDE columns vs composite keys.

Low-cardinality indexes that are never selective. Deduplication makes them small, not useful. Diagnostic signal: the planner never uses an index on a 50/50 boolean. Fix: a partial index on the rare value instead.

Numeric codes. numeric keys cannot deduplicate. Diagnostic signal: a code column index much larger than an equivalent integer index. Fix: store codes as integer types where values are integral.

Frequently Asked Questions #

What is B-tree deduplication in PostgreSQL? #

Introduced in PostgreSQL 13, it stores runs of identical keys in a B-tree leaf as one entry with a list of row pointers instead of repeating the key per row. Indexes on repetitive values become much smaller and cheaper to scan.

Why did my index not get smaller after upgrading to PostgreSQL 13 or later? #

Indexes carried over by pg_upgrade keep their old on-disk format, which cannot deduplicate. Rebuild them with REINDEX or REINDEX CONCURRENTLY to convert them to the new format.

Which indexes cannot use deduplication? #

Indexes with INCLUDE columns, indexes on numeric, float, jsonb or container types, text columns with nondeterministic collations, and indexes still in the pre-13 format.

Up: B-Tree Index Optimization