B-tree deduplication & posting-list tuples
Simple terms
Index a column where the same value repeats over and over, a status, a tenant id, a flag, and the naive layout writes that value out again for every single row. Deduplication stores it once and hangs a list of the matching rows off it. Fewer pages, and the index splits far less often. It is on by default and it never changes a query's answer. Only the storage.
You might be asked
What is B-tree deduplication, what is a posting-list tuple, and how would you prove an index is using it, and what are the cases where it does NOT apply?
How you’d answer it
In a non-unique btree, a run of tuples that all share the same key value gets merged into one physical posting-list tuple: the key stored once, then a sorted array of heap TIDs.
It is on by default (deduplicate_items=on) and applied lazily, at index build, and again just before a leaf would split. Nothing logical changes. Same contents, same query answers. It is purely physical, and what it buys you is a smaller index and delayed page splits.
pageinspect shows it plainly: bt_page_items gives a non-NULL `tids` array on a posting tuple, and bt_page_stats reports far fewer live line pointers per leaf.
The lab numbers make the case. The same data went from 2224 kB and ~100k line pointers with it off, to 728 kB and 888 line pointers with it on, one tuple was holding 132 heap TIDs.
What the docs say
The B-tree chapter of the manual describes deduplication like this: when a leaf page holds several tuples whose indexed key values all match, a deduplication pass merges them into one "posting list" tuple, the key value stored a single time, followed by a sorted array of TIDs pointing at the matching table rows. The CREATE INDEX storage parameter deduplicate_items controls the behavior and defaults to on.
In plain words: normally two rows that share an indexed value each get their own little entry in the index. Deduplication notices the value is identical, stores it once, and keeps a single list of every row pointer that shares it. That shrinks the index and delays the point where a leaf has to split.
It runs automatically on non-unique B-trees, and lazily, at build time, and again just before a leaf would otherwise split, so it only does the work when that work buys space. Because the value and all the row pointers are still present, your query results never change; only the storage does.
The manual also notes one limit: deduplication is skipped where two datums can compare equal yet still be visibly different, for example a text column under a non-deterministic collation. Merging those would be unsafe, so those indexes keep their duplicate entries.
References
- PostgreSQL 17 manual, B-Tree Deduplication
- PostgreSQL 17 manual, CREATE INDEX (deduplicate_items storage parameter)
- Source @REL_17_10, src/backend/access/nbtree/nbtdedup.c (_bt_dedup_pass / _bt_dedup_save_htid / _bt_form_posting)
- Source @REL_17_10, src/include/access/nbtree.h (BTreeTupleIsPosting / BTreeTupleSetPosting / INDEX_ALT_TID_MASK)
- Source @REL_17_10, src/backend/access/nbtree/README (Notes about deduplication)
- pageinspect (bt_page_items / bt_page_stats)
What the code does
Navigated at tag REL_17_10. src/backend/access/nbtree/nbtdedup.c, the deduplication machinery this lab exercises: - _bt_dedup_pass() (line 58): performs a deduplication pass over a leaf page, grouping equal-key non-pivot tuples and writing posting-list tuples to a fresh copy of the page. It initializes state->maxpostingsize = Min(BTMaxItemSize(page) / 2, INDEX_SIZE_MASK) (around line 86), the comment explains this deliberately limits a posting list to about one sixth of a page so duplicate-heavy pages still split at good points. The pass runs at the last moment before an otherwise-necessary page split (and the same logic is applied during index build). - _bt_dedup_save_htid() (line 484): tries to append a tuple's heap TID(s) to the pending posting list; if the merged tuple would exceed maxpostingsize it returns false and the caller finishes the current posting list as-is. This is the per-group accumulation that produced the 132-TID groups seen on the page (one tuple stays under the size cap). - _bt_form_posting() (line 864): physically builds the posting-list tuple, it copies the key bytes once (keysize), then when nhtids > 1 calls BTreeTupleSetPosting() and memcpy()s the sorted ItemPointer array after the key. That is exactly the 'key once + TID array' layout bt_page_items showed as the `tids` column. src/include/access/nbtree.h, how a posting tuple is FLAGGED: - INDEX_ALT_TID_MASK (line 459) is the t_info bit nbtree reuses to mark 'alternative TID' tuples; BTreeTupleIsPosting() (line 492) returns true when that bit is set AND the BT_IS_POSTING status bit is set; BTreeTupleSetPosting() (line 504) sets those bits and stores the TID count + posting offset. A plain (non-posting) tuple keeps its single heap pointer in t_tid, which is why bt_page_items reported tids=NULL / a single htid for dd_off. mechanism (docs/source): the pass groups equal keys, caps posting size ~1/6 page, and emits one posting tuple per group flagged via INDEX_ALT_TID_MASK/BT_IS_POSTING. consequence (measured): dd_on shrank to 728 kB / 888 line pointers, with single tuples carrying 132 heap TIDs; line numbers read only for nbtdedup.c and nbtree.h at REL_17_10.
Proof from a real run
# Lab: pgi17 / PostgreSQL 17.10, B-tree deduplication makes posting-list tuples (LITERAL)
The SAME 100,000 rows over only 100 distinct values (val = g % 100, so 1,000 duplicate rows per
value) are indexed twice: dd_off WITH (deduplicate_items=off) and dd_on WITH (deduplicate_items=on).
pageinspect (bt_page_stats / bt_page_items) makes the on-disk difference observable.
=== env ===
PostgreSQL 17.10 (Debian 17.10-1.pgdg13+1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 14.2.0-19) 14.2.0, 64-bit
index | reloptions
--------+-------------------------
dd_off | {deduplicate_items=off}
dd_on | {deduplicate_items=on}
(2 rows)
Heap: 100000 rows, 100 distinct values (val = g % 100) => 1000 duplicate rows per value.
## STAGE 1, same data, two indexes: the deduplicated index is ~3x smaller
=== STAGE 1, same data, two indexes: the deduplicated one is far smaller ===
index | size | total_pages
--------+---------+-------------
dd_off | 2224 kB | 278
dd_on | 728 kB | 91
(2 rows)
Leaf pages and total live index tuples (line pointers) per index:
index | leaf_pages | index_line_pointers
--------+------------+---------------------
dd_off | 274 | 100273
dd_on | 89 | 888
(2 rows)
dd_off keeps ONE index tuple per heap row: 274 leaf pages, 100,273 live line pointers, 2224 kB.
dd_on merges equal-key rows into posting-list tuples: 89 leaf pages, just 888 live line pointers,
728 kB. Same logical contents, a third of the size, purely because duplicates were collapsed.
## STAGE 2, a leaf page WITHOUT dedup: one tuple per row, tids is NULL
=== STAGE 2, a leaf WITHOUT dedup: one index tuple per heap row (tids is NULL) ===
leaf | live_items | dead_items | avg_item_size
-------------------+------------+------------+---------------
dd_off leaf blk=1 | 367 | 0 | 16
(1 row)
itemoffset | itemlen | key_bytes | single_heap_tid | tids
------------+---------+-------------------------+-----------------+------
2 | 16 | 00 00 00 00 00 00 00 00 | (0,100) |
3 | 16 | 00 00 00 00 00 00 00 00 | (0,200) |
4 | 16 | 00 00 00 00 00 00 00 00 | (1,74) |
5 | 16 | 00 00 00 00 00 00 00 00 | (1,174) |
6 | 16 | 00 00 00 00 00 00 00 00 | (2,48) |
7 | 16 | 00 00 00 00 00 00 00 00 | (2,148) |
(6 rows)
The leaf holds 367 live items; the sampled items all carry the same key bytes (val=0:
00 00 00 00 ...) and each has a SINGLE heap TID in htid with tids = NULL. That is the
un-deduplicated representation: a separate 16-byte index tuple for every duplicate heap row.
## STAGE 3, the SAME data WITH dedup: one posting-list tuple holds MANY heap TIDs
=== STAGE 3, the SAME data WITH dedup: ONE posting-list tuple holds many heap TIDs ===
leaf | live_items | dead_items | avg_item_size
------------------+------------+------------+---------------
dd_on leaf blk=1 | 10 | 0 | 696
(1 row)
itemoffset | itemlen | is_posting_tuple | heap_tids_in_this_one_tuple | lowest_heap_tid
------------+---------+------------------+-----------------------------+-----------------
2 | 808 | t | 132 | (0,100)
3 | 808 | t | 132 | (58,192)
4 | 808 | t | 132 | (117,58)
5 | 808 | t | 132 | (175,150)
6 | 808 | t | 132 | (234,16)
7 | 808 | t | 132 | (292,108)
(6 rows)
Largest posting list on that leaf (heap TIDs packed into a single index tuple):
max_heap_tids_in_one_tuple | posting_tuples_on_page | heap_rows_covered_by_page
----------------------------+------------------------+---------------------------
132 | 9 | 1133
(1 row)
The leaf now holds only 10 live items (avg_item_size 696). bt_page_items shows is_posting_tuple=t,
and each ~808-byte tuple packs 132 heap TIDs (heap_tids_in_this_one_tuple=132) behind a single
copy of the key; htid is just the lowest TID of the group. On this one page, 9 posting tuples
cover 1,133 heap rows. That is the key stored once + an array of heap TIDs, the posting list.
## STAGE 4, logical contents are UNCHANGED: both indexes answer identically
=== STAGE 4, logical contents UNCHANGED: both indexes answer identically ===
rows_with_val_42
------------------
1000
(1 row)
SET
QUERY PLAN
----------------------------------------
Aggregate
-> Bitmap Heap Scan on dedup_demo
Recheck Cond: (val = 42)
-> Bitmap Index Scan on dd_on
Index Cond: (val = 42)
(5 rows)
WHERE val=42 still returns 1000, and the planner happily uses the (smaller) deduplicated index
via a Bitmap Index Scan. Deduplication changes only the physical layout, never the result.
Mechanism vs consequence:
mechanism (docs/source): at index build and at the point a leaf would otherwise split, nbtree
runs a deduplication pass that replaces runs of equal-key non-pivot tuples with one posting-list
tuple (key + heap-TID array), capped at ~1/6 of a page.
consequence (measured): dd_off 2224 kB / 100273 line pointers vs dd_on 728 kB / 888 line pointers;
tids=NULL single-TID tuples vs is_posting=t tuples carrying 132 TIDs each; identical query result.Using it under pressure
A situation where it matters
A team complains an index on a low-cardinality column (status, tenant_id, boolean-ish flag) is 'too big' and bloats fast under inserts. Deduplication is exactly the built-in mitigation: equal-key rows collapse into posting lists, so the index is smaller and splits less. Confirm it's on (deduplicate_items, default on for non-unique btrees), and remember it ALSO helps unique indexes against version churn.
If it's somehow off, a REINDEX with it on reclaims the space. The flip side: if the column type can't be safely deduplicated (e.g. numeric, or text under a nondeterministic collation), the planner/AM won't apply it and the index stays large.
The call you would make
Leave deduplicate_items on (the default) for non-unique btrees on low/medium-cardinality columns, it's a free space and split-rate win with no read cost. Don't disable it without a measured reason. Know the exclusions: it does not apply to indexes where equal datums can be visibly different (e.g. numeric like 1.0 vs 1.00, text/varchar under nondeterministic collations, some container types), nor does it help when every key is unique.
For very low-cardinality, also weigh a partial index or a different access method, but dedup usually makes the plain btree perfectly acceptable. A REINDEX is what actually rebuilds existing data into posting lists if you change the setting.
When it goes wrong
To check whether an index is deduplicated: SELECT relname, reloptions FROM pg_class WHERE relname='...'; (look for deduplicate_items, default on). Then inspect with pageinspect: SELECT * FROM bt_page_stats('idx', blk);, a leaf with many duplicates but few live_items and large avg_item_size is deduplicated. SELECT itemoffset, htid, tids FROM bt_page_items('idx', blk);, posting tuples have a non-NULL tids array (and array_length(tids,1) is the group size). If you expected dedup but tids is always NULL and the index is huge, the type/collation may be ineligible, or deduplicate_items was turned off, REINDEX with it on. Compare pg_relation_size before/after to quantify.
What people get wrong
Gotcha 1: deduplication is NOT compression of the key bytes, it removes REDUNDANT COPIES of equal keys and packs their heap TIDs into one tuple; reads are unaffected (Stage 4 returned the same count and a normal index plan). Gotcha 2: it's LAZY and bounded, a posting list is capped at ~1/6 of a page (maxpostingsize), so a value with thousands of duplicates becomes SEVERAL posting tuples, not one giant tuple (the lab's largest held 132 TIDs, not 1000).
Gotcha 3: it does not apply to every type, numeric and nondeterministic-collation text are excluded because two 'equal' datums can be visibly distinct. Gotcha 4: it also runs in UNIQUE indexes (since PG13) specifically to fight version churn, even though there's at most one live row per key.
Follow-ups they'll push on
Q. When exactly does a deduplication pass run?
Lazily, at index build, and at the moment an insert would otherwise force a leaf page split (after LP_DEAD items are removed, and after bottom-up deletion has been tried for version-churn cases). It is the 'last line of defense' against a split, which is why it does not constantly rewrite pages.
Q. Why is a posting list capped at ~1/6 of a page?
_bt_dedup_pass sets maxpostingsize = Min(BTMaxItemSize(page)/2, INDEX_SIZE_MASK); the code comment explains limiting posting lists to about a sixth of a page leaves good split points so a page full of duplicates can still be split several times cleanly.
Q. How is a posting tuple distinguished from a normal one on disk?
It sets the INDEX_ALT_TID_MASK bit in t_info plus the BT_IS_POSTING status bit (BTreeTupleIsPosting()); the key is stored once and the heap TIDs follow as a sorted array. A plain tuple keeps its single heap pointer in t_tid (tids=NULL in bt_page_items).
Q. Does deduplication change how VACUUM or index deletion work?
VACUUM/deletion operate on individual TIDs within a posting list via _bt_update_posting (rewriting the posting tuple without the dead TIDs); a posting tuple's LP_DEAD bit can only be set when ALL of its TIDs are known dead. So dedup interoperates with deletion at TID granularity rather than blocking it.
Version notes
B-tree deduplication was introduced in PostgreSQL 13 and is present and on-by-default across 14-18 (captured on 17.10). Deduplication in UNIQUE indexes (to combat version churn) also dates from 13. The posting-list on-disk format, the deduplicate_items storage parameter, and the pageinspect bt_page_items `tids` column are all available throughout 14-18; pageinspect 1.12 was used here. Type/collation eligibility rules (numeric, nondeterministic-collation text, etc. are excluded) are the same across these versions. Source line numbers were read only for REL_17_10.
How this was verified
This concept is free end to end. The manual section is grounded in the official PostgreSQL documentation, the source walk was navigated in postgres/postgres at a version-pinned tag, and the evidence is labeled as raw output or a captured run summary. Where the text distinguishes mechanism (from docs/source) from consequence (measured), that boundary is kept explicit.
Connected
Where this concept connects
How this concept links across the library, the interview questions that test it, its plain-English glossary definition, and the guided pathways it belongs to. Open the full map to explore further.
Part of these pathways
Related concepts