PostgreSQL B-Tree Deduplication Internals: Slashing Index Bloat on High-Cardinality Foreign Keys and Status Columns

The Mechanics of B-Tree Index Bloat

The standard B-Tree index is the foundational workhorse of relational databases. In PostgreSQL, when an index is created on a column (e.g. CREATE INDEX idx_orders_status ON orders(status);), the engine builds a balanced search tree consisting of a meta page, internal branch pages, and leaf pages. Leaf pages store physical index tuples that map column values to Item Pointer Data (ItemPointerData or TID)—the physical block number and offset pointing to the row version on the table heap.

Historically (prior to PostgreSQL 13), B-Tree indexes stored duplicate keys in a naive, repetitive manner. If an orders table contained 10,000,000 rows with only 5 distinct status values, the B-Tree stored 10,000,000 discrete index tuples. Every single index tuple repeated the exact same column value and tuple header overhead on the leaf page:

Standard B-Tree Leaf Page Layout (Pre-PG 13):
[Key: 'SHIPPED', TID: (Block 12, Offset 1)]
[Key: 'SHIPPED', TID: (Block 12, Offset 2)]
[Key: 'SHIPPED', TID: (Block 12, Offset 3)]
... Repeated 2,000,000 times! Massive storage and memory bloat.

This duplication caused B-Tree indexes on foreign keys, status enums, and boolean flags to balloon into multiple gigabytes in size. Because indexes must remain resident in shared_buffers to maintain low-latency index scans, bloated indexes continually evicted valuable table data from RAM.

1. PostgreSQL Bottom-Up Index Deduplication

Starting with PostgreSQL 13, B-Tree index architecture was fundamentally revolutionized with Bottom-Up Index Deduplication. Instead of repeating identical key values across multiple index tuples, the engine dynamically collapses duplicate keys into a single Posting List Tuple:

Deduplicated Posting List Tuple:
[Key: 'SHIPPED' | Header | Array of TIDs: (B12, O1), (B12, O2), (B12, O3), (B14, O1)...]

The column key and its IndexTupleData header are stored exactly once. Adjacent matching tuples are merged into a packed contiguous array of 6-byte TIDs. This single architectural shift slashes physical index storage requirements by 40% to 75% on non-unique columns.

2. Deferring Leaf Page Splits and Preventing Write Amplification

Deduplication does not merely conserve disk space and RAM—it significantly improves write throughput during bulk INSERT workloads. When an 8KB B-Tree leaf page fills up, PostgreSQL is forced to perform a costly page split: allocating a new 8KB page from disk, moving 50% of the tuples to the new page, and updating the parent branch page.

With deduplication active, whenever a leaf page reaches capacity during an insert pass, PostgreSQL executes an in-memory deduplication pass. By merging existing duplicate keys into compact posting lists, the page frees up contiguous space without splitting. On write-heavy workloads, deduplication defers page splits by orders of magnitude, slashing disk write amplification and checkpoint spikes.

3. Production Benchmarks: Storage and Memory Savings

We evaluated deduplication performance on a 10,000,000-row table containing an integer foreign key (customer_id with ~100 rows per customer) on PostgreSQL 16:

4. Inspecting Posting Lists with pageinspect

PostgreSQL provides the pageinspect extension, allowing database administrators to look directly inside physical B-Tree leaf pages:

CREATE EXTENSION IF NOT EXISTS pageinspect;

-- Inspect leaf page tuples for posting lists
SELECT
    itemoffset,
    ctid,
    itemlen,
    nposting,
    data
FROM bt_page_items('idx_orders_status', 1)
LIMIT 5;

If deduplication is active, the nposting column displays the exact count of TIDs merged into that posting list tuple (e.g. nposting: 84).

5. When to Disable Deduplication (deduplicate_items = off)

While deduplicate_items = on is the default in PostgreSQL 13+, there are specific scenarios where deduplication should be disabled via WITH (deduplicate_items = off):

• Unique Indexes: By mathematical definition, unique indexes contain zero duplicate values. Deduplication checks will never find a match, wasting minor CPU cycles during index inserts.
• High-Entropy UUIDs / High-Precision Timestamps: Columns where every value is virtually distinct (such as UUIDv4 or microsecond timestamps) have an average duplicate count close to 1.0. Deduplication merge passes incur negligible but unnecessary CPU overhead.