Opensource internals

PostgreSQL Deduplicates B-Tree Entries

46 min read Jay Hubbert

A B-tree over a column with many duplicates does not store one index entry per row: it stores a posting list of TIDs, and when the list gets too long it is split in place, in the same atomic action as the insert.

Every index is a lie about multiplicity. A CREATE INDEX on a boolean column produces a structure in which, logically, there are only two distinct keys — but the index has to be able to answer “give me every row where is_active is true”, and there may be nine million of them. The naive answer is one index entry per row: nine million entries, nine million TIDs, nine million line pointers, and a B-tree whose leaves are almost entirely made of redundant copies of the same key.

PostgreSQL refuses to pay that. Instead of storing one entry per row, a B-tree leaf can store one entry with a list of TIDs — a posting list. The key appears once; the TIDs appear in a compact array. When that array gets too long, it is not promoted to some other structure and it does not cause the page to split; it is split in place, and the split is folded into the atomic action that inserted the offending row, so that concurrent inserter never sees a half-split list.

This is a walk through how it works, based on reading the PostgreSQL source (version 20devel, commit e75fcc9867f).

The logical index versus the physical index

The logical contents of a B-tree index never change. What changes is the physical representation of a leaf page. The nbtree README says it plainly:

Deduplication alters the physical representation of tuples without changing the logical contents of the index, and without adding overhead to read queries.

So there are two representations of “the key true occurs in rows 1, 2, 3, and 7”:

RepresentationPhysical form
Plain (non-posting) tupleone index tuple per row, each with its own TID in t_tid
Posting list tupleone index tuple, with the key followed by an array of TIDs

Both represent the same set of (key, TID) pairs. The scan code has to know which one it is looking at, which is why the format has an explicit “is this a posting list?” bit.

The tuple format

An index tuple starts with the standard IndexTupleData header. From src/include/access/itup.h:

c 
typedef struct IndexTupleData
{
	ItemPointerData t_tid;		/* item pointer to heap tuple */
	unsigned short t_info;		/* flag bits, first 11 bits are size of tuple */
	/* On machines where it might be too large, t_ctid is stored in two
	 * pieces, though it's always 6 bytes.  t_info is 16 bits, so the
	 * offset number can only be 14 bits.  We use the upper 2 bits of the
	 * offset number for the "has nulls" and "has varwidth" flags.
	 */
	/* Bits 0-10 are size in bytes of the variable-size part of the tuple,
	 * including any null bitmap.  Bits 11-15 are the flag bits.
	 */
} IndexTupleData;

The key data follows. But a posting list tuple needs to store two things after the key: how many TIDs there are, and where the TID array starts. There is no room in t_info (its upper bits are already spoken for) and there is no room in the 6-byte t_tid either — unless you stop using t_tid for a TID at all.

And that is exactly what a posting list tuple does. It repurposes t_tid. From src/include/access/nbtree.h:

c 
// src/include/access/nbtree.h
/*
 * Posting tuple format (alternative non-pivot tuple representation):
 *
 *  t_tid | t_info | key values | posting list (TID array)
 *
 * Posting list tuples are recognized as such by having the
 * INDEX_ALT_TID_MASK status bit set in t_info and the BT_IS_POSTING status
 * bit set in t_tid's offset number.  These flags redefine the content of
 * the posting tuple's t_tid to store the location of the posting list
 * (instead of a block number), as well as the total number of heap TIDs
 * present in the tuple (instead of a real offset number).
 *
 * The 12 least significant bits from t_tid's offset number are used to
 * represent the number of heap TIDs present in the tuple, leaving 4 status
 * bits (the BT_STATUS_OFFSET_MASK bits).  Like any non-pivot tuple, the
 * number of columns stored is always implicitly the total number in the
 * index (in practice there can never be non-key columns stored, since
 * deduplication is not supported with INCLUDE indexes).
 */

So the layout of a posting list tuple’s t_tid is:

BitsMeaning
Block numberByte offset of the TID array within the tuple
Offset number, low 12 bitsNumber of TIDs in the posting list
Offset number, bit 12BT_PIVOT_HEAP_TID_ATTR (unused here)
Offset number, bit 13BT_IS_POSTING — this is a posting list tuple
Offset number, bits 14-15unused

The masks:

c 
// src/include/access/nbtree.h
/* Item pointer offset bit masks */
#define BT_OFFSET_MASK				0x0FFF
#define BT_STATUS_OFFSET_MASK		0xF000
/* BT_STATUS_OFFSET_MASK status bits */
#define BT_PIVOT_HEAP_TID_ATTR		0x1000
#define BT_IS_POSTING				0x2000

And the accessors, which are just bit-fiddling on t_tid:

c 
// src/include/access/nbtree.h
static inline void
BTreeTupleSetPosting(IndexTuple itup, uint16 nhtids, int postingoffset)
{
	Assert(nhtids > 1);
	Assert((nhtids & BT_STATUS_OFFSET_MASK) == 0);
	Assert((size_t) postingoffset == MAXALIGN(postingoffset));
	Assert(postingoffset < INDEX_SIZE_MASK);
	Assert(!BTreeTupleIsPivot(itup));

	itup->t_info |= INDEX_ALT_TID_MASK;
	ItemPointerSetOffsetNumber(&itup->t_tid, (nhtids | BT_IS_POSTING));
	ItemPointerSetBlockNumber(&itup->t_tid, postingoffset);
}

static inline uint16
BTreeTupleGetNPosting(IndexTuple posting)
{
	OffsetNumber existing;

	Assert(BTreeTupleIsPosting(posting));

	existing = ItemPointerGetOffsetNumberNoCheck(&posting->t_tid);
	return (existing & BT_OFFSET_MASK);
}

static inline uint32
BTreeTupleGetPostingOffset(IndexTuple posting)
{
	Assert(BTreeTupleIsPosting(posting));

	return ItemPointerGetBlockNumberNoCheck(&posting->t_tid);
}

static inline ItemPointer
BTreeTupleGetPosting(IndexTuple posting)
{
	return (ItemPointer) ((char *) posting +
						  BTreeTupleGetPostingOffset(posting));
}

Two consequences fall out of this immediately:

  • The number of TIDs in a posting list is capped at 4095 (BT_OFFSET_MASK is 12 bits), even though the storage could hold far more.
  • The TID array is a plain array of ItemPointerData — six bytes each, no compression, no encoding. This is the single biggest difference from GIN, which compresses the same kind of array.

The posting list lives inside the tuple, immediately after the key columns, at a MAXALIGN’d offset. BTreeTupleGetHeapTID() returns the first TID of a posting list, and BTreeTupleGetMaxHeapTID() the last:

c 
// src/include/access/nbtree.h
static inline ItemPointer
BTreeTupleGetHeapTID(IndexTuple itup)
{
	if (BTreeTupleIsPivot(itup))
	{
		/* Pivot tuple heap TID representation? */
		if ((ItemPointerGetOffsetNumberNoCheck(&itup->t_tid) &
			 BT_PIVOT_HEAP_TID_ATTR) != 0)
			return (ItemPointer) ((char *) itup + IndexTupleSize(itup) -
								  sizeof(ItemPointerData));

		/* Heap TID attribute was truncated */
		return NULL;
	}
	else if (BTreeTupleIsPosting(itup))
		return BTreeTupleGetPosting(itup);

	return &itup->t_tid;
}

/*
 * Get maximum heap TID attribute, which could be the only TID in the case of
 * a non-pivot tuple that does not have a posting list.
 *
 * Works with non-pivot tuples only.
 */
static inline ItemPointer
BTreeTupleGetMaxHeapTID(IndexTuple itup)
{
	Assert(!BTreeTupleIsPivot(itup));

	if (BTreeTupleIsPosting(itup))
	{
		uint16		nposting = BTreeTupleGetNPosting(itup);

		return BTreeTupleGetPostingN(itup, nposting - 1);
	}

	return &itup->t_tid;
}

Building a posting list tuple

The function that builds one is _bt_form_posting(), in src/backend/access/nbtree/nbtdedup.c — a file that exists only in modern PostgreSQL, because the nbtree implementation was split up into fourteen files during the v20 development cycle.

c 
// src/backend/access/nbtree/nbtdedup.c
/*
 * Build a posting list tuple based on caller's "base" index tuple and list of
 * heap TIDs.  When nhtids == 1, builds a standard non-pivot tuple without a
 * posting list. (Posting list tuples can never have a single heap TID, partly
 * because that ensures that deduplication always reduces final MAXALIGN()'d
 * size of entire tuple.)
 *
 * Convention is that posting list starts at a MAXALIGN()'d offset (rather
 * than a SHORTALIGN()'d offset), in line with the approach taken when
 * appending a heap TID to new pivot tuple/high key during suffix truncation.
 * This sometimes wastes a little space that was only needed as alignment
 * padding in the original tuple.  Following this convention simplifies the
 * space accounting used when deduplicating a page (the same convention
 * simplifies the accounting for choosing a point to split a page at).
 *
 * Note: Caller's "htids" array must be unique and already in ascending TID
 * order.  Any existing heap TIDs from "base" won't automatically appear in
 * returned posting list tuple (they must be included in htids array.)
 */
IndexTuple
_bt_form_posting(IndexTuple base, const ItemPointerData *htids, int nhtids)
{
	uint32		keysize,
				newsize;
	IndexTuple	itup;

	if (BTreeTupleIsPosting(base))
		keysize = BTreeTupleGetPostingOffset(base);
	else
		keysize = IndexTupleSize(base);

	Assert(!BTreeTupleIsPivot(base));
	Assert(nhtids > 0 && nhtids <= PG_UINT16_MAX);
	Assert(keysize == MAXALIGN(keysize));

	/* Determine final size of new tuple */
	if (nhtids > 1)
		newsize = MAXALIGN(keysize +
						   nhtids * sizeof(ItemPointerData));
	else
		newsize = keysize;

	Assert(newsize <= INDEX_SIZE_MASK);
	Assert(newsize == MAXALIGN(newsize));

	/* Allocate memory using palloc0() (matches index_form_tuple()) */
	itup = palloc0(newsize);
	memcpy(itup, base, keysize);
	itup->t_info &= ~INDEX_SIZE_MASK;
	itup->t_info |= newsize;
	if (nhtids > 1)
	{
		/* Form posting list tuple */
		BTreeTupleSetPosting(itup, nhtids, keysize);
		memcpy(BTreeTupleGetPosting(itup), htids,
			   sizeof(ItemPointerData) * nhtids);
		Assert(_bt_posting_valid(itup));
	}
	else
	{
		/* Form standard non-pivot tuple */
		itup->t_info &= ~INDEX_ALT_TID_MASK;
		ItemPointerCopy(htids, &itup->t_tid);
		Assert(ItemPointerIsValid(&itup->t_tid));
	}

	return itup;
}

The size formula is the whole of the space accounting:

text 
posting tuple size = MAXALIGN(key bytes + nhtids * 6)

For a boolean column, the key is 8 bytes of IndexTupleData plus one byte of datum, so MAXALIGN’d to 16. A posting list of 200 TIDs is therefore 16 + 1200 = 1216 bytes, versus 200 separate tuples at (16 + 4 bytes of line pointer) each = 4000 bytes. Three times smaller, and — more importantly — 200 line pointers become one.

The nhtids == 1 case deliberately degrades to a plain tuple rather than a one-element posting list. The comment explains why: a posting list tuple can never hold a single TID, “partly because that ensures that deduplication always reduces final MAXALIGN()’d size of entire tuple.” If you merged two 16-byte tuples into a posting list of two TIDs, you would get 16 + 12 = 28 bytes plus a line pointer — bigger than the two separate tuples (32 + 8 = 40 bytes, so actually smaller), but the point stands: there must never be a case where merging makes the page bigger.

When does deduplication happen?

Not eagerly. Deduplication is lazy, and it happens at exactly one moment: when an insert finds that the target leaf page has no room and a page split is about to happen.

The nbtree README:

Deduplication is always applied lazily, at the point where it would otherwise be necessary to perform a page split. It occurs only when LP_DEAD items have been removed, as our last line of defense against splitting a leaf page (bottom-up index deletion may be attempted first, as our second last line of defense).

The chain of decisions lives in _bt_delete_or_dedup_one_page() in src/backend/access/nbtree/nbtinsert.c:

c 
// src/backend/access/nbtree/nbtinsert.c
	/*
	 * Perform bottom-up index deletion pass when executor hint indicated that
	 * incoming item is logically unchanged, or for a unique index that is
	 * known to have physical duplicates for some other reason.  ...
	 *
	 * Note: Bottom-up index deletion uses the same equality/equivalence
	 * routines as deduplication internally.  However, it does not merge
	 * together index tuples, so the same correctness considerations do not
	 * apply.  We deliberately omit an index-is-allequalimage test here.
	 */
	if ((indexUnchanged || uniquedup) &&
		_bt_bottomupdel_pass(rel, buffer, heapRel, insertstate->itemsz))
		return;

	/* Perform deduplication pass (when enabled and index-is-allequalimage) */
	if (BTGetDeduplicateItems(rel) && itup_key->allequalimage)
		_bt_dedup_pass(rel, buffer, insertstate->itup, insertstate->itemsz,
					   (indexUnchanged || uniquedup));

Two gates there, and they are the two conditions under which deduplication is possible at all:

  1. deduplicate_items — the storage parameter, on by default:

    c 
    // src/include/access/nbtree.h
#define BTGetDeduplicateItems(relation) \
	(AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
				 relation->rd_rel->relam == BTREE_AM_OID), \
	((relation)->rd_options ? \
	 ((BTOptions *) (relation)->rd_options)->deduplicate_items : true))

  2. allequalimage — whether the index’s operator class guarantees that “equal” implies “bytewise identical”. This is the interesting one, and it is discussed below.

The deduplication pass itself

_bt_dedup_pass() in nbtdedup.c rewrites the whole page. It copies the page to a temporary buffer, walks the tuples, groups the equal ones, forms posting list tuples for the groups, and then swaps the new page in. The critical part is the size limit:

c 
// src/backend/access/nbtree/nbtdedup.c
	/*
	 * Initialize deduplication state.
	 *
	 * It would be possible for maxpostingsize (limit on posting list tuple
	 * size) to be set to one third of the page.  However, it seems like a
	 * good idea to limit the size of posting lists to one sixth of a page.
	 * That ought to leave us with a good split point when pages full of
	 * duplicates can be split several times.
	 */
	state = palloc_object(BTDedupStateData);
	state->deduplicate = true;
	state->nmaxitems = 0;
	state->maxpostingsize = Min(BTMaxItemSize / 2, INDEX_SIZE_MASK);

BTMaxItemSize is the maximum size of a single btree index entry:

c 
// src/include/access/nbtree.h
/*
 * Maximum size of a btree index entry, including its tuple header.
 *
 * We actually need to be able to fit three items on every page,
 * so restrict any one item to 1/3 the per-page available space.
 * ...
 */
#define BTMaxItemSize \
	(MAXALIGN_DOWN((BLCKSZ - \
					MAXALIGN(SizeOfPageHeaderData + 3*sizeof(ItemIdData)) - \
					MAXALIGN(sizeof(BTPageOpaqueData))) / 3) - \
					MAXALIGN(sizeof(ItemPointerData)))

On an 8 kB page that works out to 2696 bytes, so maxpostingsize is 1348 bytes — a bit under a sixth of the page, as the comment says. And 1348 bytes of 6-byte TIDs is at most 224 TIDs per posting list, less the space taken by the key.

This is the constant that bounds a posting list. There are actually two bounds, and they are different things:

BoundValueWhere it comes from
maxpostingsize1348 bytes (~1/6 page)Min(BTMaxItemSize / 2, INDEX_SIZE_MASK)
TID count per list≤ 4095BT_OFFSET_MASK, 12 bits of the offset number
Derived TID count≤ 224, less the key1348 bytes / 6 bytes per TID

The 4095 limit is the hard ceiling; the 1348-byte limit is what actually binds in practice, and it is deliberately conservative so that a page full of posting lists can still be split sensibly.

The merge condition

Now the heart of it. While walking the page, the pass keeps a “pending posting list”: a base tuple plus a growing array of TIDs. Each subsequent tuple is either merged into the pending list, or terminates it:

c 
// src/backend/access/nbtree/nbtdedup.c
		else if (state->deduplicate &&
				 _bt_keep_natts_fast(rel, state->base, itup) > nkeyatts &&
				 _bt_dedup_save_htid(state, itup))
		{
			/*
			 * Tuple is equal to base tuple of pending posting list.  Heap
			 * TID(s) for itup have been saved in state.
			 */
		}

Read that condition as three separate tests:

  • state->deduplicate — the pass has not given up (the “single value” strategy can turn it off; see below).
  • _bt_keep_natts_fast(rel, state->base, itup) > nkeyatts — the keys are equal. _bt_keep_natts_fast() returns the number of leading attributes that must be kept to distinguish two tuples; if it exceeds the number of key attributes, the two tuples have identical keys.
  • _bt_dedup_save_htid(state, itup) — the merged list still fits. This returns false if appending the TIDs would push the posting list over maxpostingsize.

That third test is the “posting list is not too long” condition, and it is worth reading closely because it is where the size limit is enforced:

c 
// src/backend/access/nbtree/nbtdedup.c
bool
_bt_dedup_save_htid(BTDedupState state, IndexTuple itup)
{
	int			nhtids;
	ItemPointer htids;
	Size		mergedtupsz;

	Assert(!BTreeTupleIsPivot(itup));

	if (!BTreeTupleIsPosting(itup))
	{
		nhtids = 1;
		htids = &itup->t_tid;
	}
	else
	{
		nhtids = BTreeTupleGetNPosting(itup);
		htids = BTreeTupleGetPosting(itup);
	}

	/*
	 * Don't append (have caller finish pending posting list as-is) if
	 * appending heap TID(s) from itup would put us over maxpostingsize limit.
	 *
	 * This calculation needs to match the code used within _bt_form_posting()
	 * for new posting list tuples.
	 */
	mergedtupsz = MAXALIGN(state->basetupsize +
						   (state->nhtids + nhtids) * sizeof(ItemPointerData));

	if (mergedtupsz > state->maxpostingsize)
	{
		/*
		 * Count this as an oversized item for single value strategy, though
		 * only when there are 50 TIDs in the final posting list tuple.  This
		 * limit (which is fairly arbitrary) avoids confusion about how many
		 * 1/6 of a page tuples have been encountered/created by the current
		 * deduplication pass.
		 * ...
		 */
		if (state->nhtids > 50)
			state->nmaxitems++;

		return false;
	}

	/*
	 * Save heap TIDs to pending posting list tuple -- itup can be merged into
	 * pending posting list
	 */
	state->nitems++;
	memcpy(state->htids + state->nhtids, htids,
		   sizeof(ItemPointerData) * nhtids);
	state->nhtids += nhtids;
	state->phystupsize += MAXALIGN(IndexTupleSize(itup)) + sizeof(ItemIdData);

	return true;
}

When the limit is hit, the pending list is finalized as-is and a new pending list starts with the tuple that did not fit. That is exactly what produces a page with several posting lists of the same key rather than one enormous one.

Finishing a pending list

When a group ends, _bt_dedup_finish_pending() either writes the base tuple unchanged (if the group had only one member) or forms a posting list tuple:

c 
// src/backend/access/nbtree/nbtdedup.c
Size
_bt_dedup_finish_pending(Page newpage, BTDedupState state)
{
	OffsetNumber tupoff;
	Size		tuplesz;
	Size		spacesaving;

	Assert(state->nitems > 0);
	Assert(state->nitems <= state->nhtids);
	Assert(state->intervals[state->nintervals].baseoff == state->baseoff);

	tupoff = OffsetNumberNext(PageGetMaxOffsetNumber(newpage));
	if (state->nitems == 1)
	{
		/* Use original, unchanged base tuple */
		tuplesz = IndexTupleSize(state->base);
		...
		spacesaving = 0;
	}
	else
	{
		IndexTuple	final;

		/* Form a tuple with a posting list */
		final = _bt_form_posting(state->base, state->htids, state->nhtids);
		tuplesz = IndexTupleSize(final);
		Assert(tuplesz <= state->maxpostingsize);

		/* Save final number of items for posting list */
		state->intervals[state->nintervals].nitems = state->nitems;

		...
		spacesaving = state->phystupsize - (tuplesz + sizeof(ItemIdData));
		/* Increment nintervals, since we wrote a new posting list tuple */
		state->nintervals++;
		Assert(spacesaving > 0 && spacesaving < BLCKSZ);
	}

	/* Reset state for next pending posting list */
	state->nhtids = 0;
	state->nitems = 0;
	state->phystupsize = 0;

	return spacesaving;
}

Note spacesaving > 0: the code asserts that merging always made the page smaller. If it ever did not, merging would be a pessimization and the assert would fire.

The “single value” strategy

A page full of one repeated key is a special case. The dedup pass has a special strategy for it, described in _bt_do_singleval():

The general goal of this strategy is to ensure that nbtsplitloc.c (which uses its own single value strategy) will find a useful split point as further duplicates are inserted, and successive rightmost page splits occur among pages that store the same duplicate value. When the page finally splits, it should end up BTREE_SINGLEVAL_FILLFACTOR% full, just like it would if deduplication were disabled.

The strategy limits the page to at most six maxpostingsize-sized posting lists, and then stops deduplicating entirely. It is triggered when the page’s first and last data items both compare equal to the tuple being inserted — that is, the whole page holds one value:

c 
// src/backend/access/nbtree/nbtdedup.c
	itemid = PageGetItemId(page, minoff);
	itup = (IndexTuple) PageGetItem(page, itemid);

	if (_bt_keep_natts_fast(rel, newitem, itup) > nkeyatts)
	{
		itemid = PageGetItemId(page, PageGetMaxOffsetNumber(page));
		itup = (IndexTuple) PageGetItem(page, itemid);

		if (_bt_keep_natts_fast(rel, newitem, itup) > nkeyatts)
			return true;
	}

	return false;
c 
// src/backend/access/nbtree/nbtdedup.c
			if (singlevalstrat)
			{
				/*
				 * Single value strategy's extra steps.
				 *
				 * Lower maxpostingsize for sixth and final large posting list
				 * tuple at the point where 5 maxpostingsize-capped tuples
				 * have either been formed or observed.
				 *
				 * When a sixth maxpostingsize-capped item is formed/observed,
				 * stop merging together tuples altogether. ...
				 */
				if (state->nmaxitems == 5)
					_bt_singleval_fillfactor(page, state, newitemsz);
				else if (state->nmaxitems == 6)
				{
					state->deduplicate = false;
					singlevalstrat = false; /* won't be back here */
				}
			}

This is a strange-looking piece of code that exists for a very practical reason: a page full of duplicates must eventually be split, and the split must land in a sensible place. The split-point logic (_bt_findsplitloc(), in nbtsplitloc.c) has its own “single value strategy” that leaves the left page 96% full, and the dedup pass has to cooperate with it.

Splitting a posting list

Now the interesting case: what happens when you insert a row whose TID falls inside the range of TIDs already covered by an existing posting list?

Physically, the posting list is a sorted array of TIDs, and the new row’s TID belongs somewhere in the middle of it. You cannot simply append it — the array must stay sorted, because everything downstream (binary searches, range checks, VACUUM) assumes it is.

PostgreSQL’s answer is _bt_swap_posting().

Finding the insertion point

The binary search over the page finds the tuple; if that tuple is a posting list, a second binary search over the posting list finds the offset at which the new TID belongs. From src/backend/access/nbtree/nbtsearch.c:

c 
// src/backend/access/nbtree/nbtsearch.c
		/*
		 * If tuple at offset located by binary search is a posting list whose
		 * TID range overlaps with caller's scantid, perform posting list
		 * binary search to set postingoff for caller.  Caller must split the
		 * posting list when postingoff is set.  This should happen
		 * infrequently.
		 */
		if (unlikely(result == 0 && key->scantid != NULL))
		{
			/*
			 * postingoff should never be set more than once per leaf page
			 * binary search.  That would mean that there are duplicate table
			 * TIDs in the index, which is never okay.  Check for that here.
			 */
			if (insertstate->postingoff != 0)
				ereport(ERROR,
						(errcode(ERRCODE_INDEX_CORRUPTED),
						 errmsg_internal("table tid from new index tuple (%u,%u) cannot find insert offset between offsets %u and %u of block %u in index \"%s\"",
										 ItemPointerGetBlockNumber(key->scantid),
										 ItemPointerGetOffsetNumber(key->scantid),
										 low, stricthigh,
										 BufferGetBlockNumber(insertstate->buf),
										 RelationGetRelationName(rel))));

			insertstate->postingoff = _bt_binsrch_posting(key, page, mid);
		}

and the helper itself:

c 
// src/backend/access/nbtree/nbtsearch.c
static int
_bt_binsrch_posting(BTScanInsert key, Page page, OffsetNumber offnum)
{
	IndexTuple	itup;
	ItemId		itemid;
	int			low,
				high,
				mid,
				res;

	/*
	 * If this isn't a posting tuple, then the index must be corrupt (if it is
	 * an ordinary non-pivot tuple then there must be an existing tuple with a
	 * heap TID that equals inserter's new heap TID/scantid).  Defensively
	 * check that tuple is a posting list tuple whose posting list range
	 * includes caller's scantid.
	 * ...
	 */
	itemid = PageGetItemId(page, offnum);
	itup = (IndexTuple) PageGetItem(page, itemid);
	if (!BTreeTupleIsPosting(itup))
		return 0;

	Assert(key->heapkeyspace && key->allequalimage);

	/*
	 * In the event that posting list tuple has LP_DEAD bit set, indicate this
	 * to _bt_binsrch_insert() caller by returning -1, a sentinel value.  A
	 * second call to _bt_binsrch_insert() can take place when its caller has
	 * removed the dead item.
	 */
	if (ItemIdIsDead(itemid))
		return -1;

	/* "high" is past end of posting list for loop invariant */
	low = 0;
	high = BTreeTupleGetNPosting(itup);
	Assert(high >= 2);

	while (high > low)
	{
		mid = low + ((high - low) / 2);
		res = ItemPointerCompare(key->scantid,
								 BTreeTupleGetPostingN(itup, mid));

		if (res > 0)
			low = mid + 1;
		else if (res < 0)
			high = mid;
		else
			return mid;
	}

	/* Exact match not found */
	return low;
}

The returned postingoff is the offset within the posting list where the new TID belongs.

The swap

Here is the whole of _bt_swap_posting():

c 
// src/backend/access/nbtree/nbtdedup.c
/*
 * Prepare for a posting list split by swapping heap TID in newitem with heap
 * TID from original posting list (the 'oposting' heap TID located at offset
 * 'postingoff').  Modifies newitem, so caller should pass their own private
 * copy that can safely be modified.
 *
 * Returns new posting list tuple, which is palloc()'d in caller's context.
 * This is guaranteed to be the same size as 'oposting'.  Modified newitem is
 * what caller actually inserts. (This happens inside the same critical
 * section that performs an in-place update of old posting list using new
 * posting list returned here.)
 * ...
 * See nbtree/README for details on the design of posting list splits.
 */
IndexTuple
_bt_swap_posting(IndexTuple newitem, IndexTuple oposting, int postingoff)
{
	int			nhtids;
	char	   *replacepos;
	char	   *replaceposright;
	Size		nmovebytes;
	IndexTuple	nposting;

	nhtids = BTreeTupleGetNPosting(oposting);
	Assert(_bt_posting_valid(oposting));

	/*
	 * The postingoff argument originated as a _bt_binsrch_posting() return
	 * value.  It will be 0 in the event of corruption that makes a leaf page
	 * contain a non-pivot tuple that's somehow identical to newitem (no two
	 * non-pivot tuples should ever have the same TID).  This has been known
	 * to happen in the field from time to time.
	 *
	 * Perform a basic sanity check to catch this case now.
	 */
	if (!(postingoff > 0 && postingoff < nhtids))
		elog(ERROR, "posting list tuple with %d items cannot be split at offset %d",
			 nhtids, postingoff);

	/*
	 * Move item pointers in posting list to make a gap for the new item's
	 * heap TID.  We shift TIDs one place to the right, losing original
	 * rightmost TID. (nmovebytes must not include TIDs to the left of
	 * postingoff, nor the existing rightmost/max TID that gets overwritten.)
	 */
	nposting = CopyIndexTuple(oposting);
	replacepos = (char *) BTreeTupleGetPostingN(nposting, postingoff);
	replaceposright = (char *) BTreeTupleGetPostingN(nposting, postingoff + 1);
	nmovebytes = (nhtids - postingoff - 1) * sizeof(ItemPointerData);
	memmove(replaceposright, replacepos, nmovebytes);

	/* Fill the gap at postingoff with TID of new item (original new TID) */
	Assert(!BTreeTupleIsPivot(newitem) && !BTreeTupleIsPosting(newitem));
	ItemPointerCopy(&newitem->t_tid, (ItemPointer) replacepos);

	/* Now copy oposting's rightmost/max TID into new item (final new TID) */
	ItemPointerCopy(BTreeTupleGetMaxHeapTID(oposting), &newitem->t_tid);

	Assert(ItemPointerCompare(BTreeTupleGetMaxHeapTID(nposting),
							  BTreeTupleGetHeapTID(newitem)) < 0);
	Assert(_bt_posting_valid(nposting));

	return nposting;
}

Three steps, and they are worth tracing with concrete numbers. Suppose the posting list is [10, 20, 30, 40] and the new row’s TID is 25.

The binary search returns the offset at which 25 belongs, which is index 2 (between 20 and 30): _bt_binsrch_posting() walks low=0, high=4, probes index 2 (30), sees 25 < 30 and narrows to low=0, high=2, probes index 1 (20), sees 25 > 20 and sets low=2. The loop ends with high == low == 2, and 2 is returned.

Now the three steps, with nhtids = 4 and postingoff = 2:

  1. Shift. nmovebytes = (4 - 2 - 1) * 6 = 6 bytes, so memmove() copies the TID at slot 2 (30) into slot 3. The array is now [10, 20, 30, 30] — slot 2 still holds its old value because it was the source of the copy, and it is about to be overwritten. The old maximum 40 has been pushed out of the array entirely (“losing original rightmost TID”).
  2. Fill the hole. The new item’s original TID (25) is written into slot 2: [10, 20, 25, 30]. Still sorted, because the binary search guaranteed that 25 belongs exactly there.
  3. Take over the maximum. The old maximum (40) is copied into the new item’s t_tid. The new index tuple on the page is now a plain tuple pointing at row 40, and the posting list tuple covers rows 10, 20, 25 and 30.

The union of covered rows is exactly right: {10, 20, 25, 30} from the posting list plus {40} from the new tuple. Nothing is lost, nothing is duplicated, and the posting list stays sorted.

So the general rule is: the posting list keeps its first postingoff TIDs, gains the new TID at position postingoff, and keeps its original TIDs from postingoff onward shifted right by one — with the old maximum pushed out into the newly inserted tuple. The posting list tuple is exactly the same size as it was before; the new tuple is an ordinary, small index tuple that happens to carry the old maximum’s TID. That is the sense in which the README says “the size of the posting list won’t change”.

The assertions in the function are the machine-checked statement of this invariant:

c 
	Assert(ItemPointerCompare(BTreeTupleGetMaxHeapTID(nposting),
							  BTreeTupleGetHeapTID(newitem)) < 0);
	Assert(_bt_posting_valid(nposting));

The first says the modified list’s maximum (the old second-to-last TID) is strictly less than the new tuple’s TID (the old maximum), and the second says the modified list is still strictly increasing.

There is no posting tree

This is worth stating explicitly, because the phrase “posting tree” shows up in GIN, in mailing-list discussion of btree, and in older blog posts about index deduplication — but there is no such thing in btree.

A “posting tree”, in the GIN sense, is a separate tree of pages whose leaves hold the list of rows matching one key. GIN needs it because a single GIN key can match millions of rows and therefore cannot be stored in one tuple on one page. btree never needed it, because in btree a posting list is bounded by the page: it lives inside a tuple on a leaf page, and the bound (1348 bytes, ~224 TIDs) is small enough that a page full of posting lists can still be split sensibly.

Upstream btree has only ever had posting lists — deduplication arrived in a single commit, 0d861bbb702 (“Add deduplication to nbtree”, February 2020), and it arrived in exactly the form it still has: a posting list tuple on a leaf page, with in-place posting list splits. You can verify the absence of the older design in the current source: grep -r BTP_POSTING over src/ returns nothing, and there is no posting-tree page type, no posting-tree split, and no posting-tree WAL record anywhere in nbtree.

The README explains the design rationale:

Posting list splits conceptually “rewrite” an insert that overlaps with an existing posting list into an insert that adds its final new item just to the right of the posting list instead. The size of the posting list won’t change, and so page space accounting code does not need to care about posting list splits at all.

The “size of the posting list won’t change” phrasing is about the tuple’s size: the posting list tuple keeps exactly the same number of TIDs (it gains one and loses one to the new tuple), so it occupies exactly the same number of bytes on the page. That is what makes the page-split accounting simple.

WAL: the special case

The write-ahead log for a posting list split is unusual, and it is unusual in an instructive way. Normally a WAL record describes a delta — “insert this tuple at this offset”. For a posting list split, the delta would be “insert a TID into the middle of an array inside a tuple that is already on the page”, which is exactly the kind of fiddly, error-prone delta that WAL is supposed to avoid.

PostgreSQL’s solution: log the inputs, not the result. The WAL record contains the postingoff value and the original new tuple; the REDO routine replays the very same _bt_swap_posting() call that the primary performed. The record does not have to describe the whole posting list; it describes the operation on it, and the operation is deterministic.

From src/backend/access/nbtree/nbtinsert.c:

c 
// src/backend/access/nbtree/nbtinsert.c
			else if (postingoff != 0)
			{
				/*
				 * Leaf insert with posting list split.  Must include
				 * postingoff field before newitem/orignewitem.
				 */
				Assert(isleaf);
				xlinfo = XLOG_BTREE_INSERT_POST;
			}
			...
			XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
			if (postingoff == 0)
			{
				/* Just log itup from caller */
				XLogRegisterBufData(0, itup, IndexTupleSize(itup));
			}
			else
			{
				/*
				 * Insert with posting list split (XLOG_BTREE_INSERT_POST
				 * record) case.
				 *
				 * Log postingoff.  Also log origitup, not itup.  REDO routine
				 * must reconstruct final itup (as well as nposting) using
				 * _bt_swap_posting().
				 */
				upostingoff = postingoff;

				XLogRegisterBufData(0, &upostingoff, sizeof(uint16));
				XLogRegisterBufData(0, origitup,
									IndexTupleSize(origitup));
			}

And the REDO routine, in src/backend/access/nbtree/nbtxlog.c:

c 
// src/backend/access/nbtree/nbtxlog.c
		else
		{
			ItemId		itemid;
			IndexTuple	oposting,
						newitem,
						nposting;
			uint16		postingoff;

			/*
			 * A posting list split occurred during leaf page insertion.  WAL
			 * record data will start with an offset number representing the
			 * point in an existing posting list that a split occurs at.
			 *
			 * Use _bt_swap_posting() to repeat posting list split steps from
			 * primary.  Note that newitem from WAL record is 'orignewitem',
			 * not the final version of newitem that is actually inserted on
			 * page.
			 */
			postingoff = *((uint16 *) datapos);
			datapos += sizeof(uint16);
			datalen -= sizeof(uint16);

			itemid = PageGetItemId(page, OffsetNumberPrev(xlrec->offnum));
			oposting = (IndexTuple) PageGetItem(page, itemid);

			/* Use mutable, aligned newitem copy in _bt_swap_posting() */
			Assert(isleaf && postingoff > 0);
			newitem = CopyIndexTuple((IndexTuple) datapos);
			nposting = _bt_swap_posting(newitem, oposting, postingoff);

			/* Replace existing posting list with post-split version */
			memcpy(oposting, nposting, MAXALIGN(IndexTupleSize(nposting)));

			/* Insert "final" new item (not orignewitem from WAL stream) */
			Assert(IndexTupleSize(newitem) == datalen);
			if (PageAddItem(page, newitem, datalen, xlrec->offnum, false, false) == InvalidOffsetNumber)
				elog(PANIC, "failed to add posting split new item");
		}

Note what is not in the WAL record: the modified posting list tuple. The REDO routine recomputes it from the original posting list (which is on the page, unmodified in the WAL stream — the page is replayed from the last full-page image or incremental change) and the postingoff. This is why the record is small: two bytes of offset plus the new tuple.

The same trick is used for page splits that coincide with a posting list split. The split record carries the offset:

c 
// src/include/access/nbtxlog.h
typedef struct xl_btree_split
{
	uint32		level;			/* tree level of page being split */
	OffsetNumber firstrightoff; /* first origpage item on rightpage */
	OffsetNumber newitemoff;	/* new item's offset */
	uint16		postingoff;		/* offset inside orig posting tuple */
} xl_btree_split;

#define SizeOfBtreeSplit	(offsetof(xl_btree_split, postingoff) + sizeof(uint16))

and the header comment above it explains the subtlety:

_R variant leaf page split records that must deal with a posting list split will include an explicit newitem, though it is never used on the right page – it is actually an orignewitem needed to update existing posting list.

Deduplication itself has its own record type, which is even more compact — it logs the intervals of the page that were deduplicated, not the resulting tuples:

c 
// src/include/access/nbtxlog.h
/*
 * When page is deduplicated, consecutive groups of tuples with equal keys are
 * merged together into posting list tuples.
 *
 * The WAL record represents a deduplication pass for a leaf page.  An array
 * of BTDedupInterval structs follows.
 */
typedef struct xl_btree_dedup
{
	uint16		nintervals;

	/* DEDUPLICATION INTERVALS FOLLOW */
} xl_btree_dedup;

#define SizeOfBtreeDedup 	(offsetof(xl_btree_dedup, nintervals) + sizeof(uint16))

and the corresponding logging code:

c 
// src/backend/access/nbtree/nbtdedup.c
	/* XLOG stuff */
	if (RelationNeedsWAL(rel))
	{
		xl_btree_dedup xlrec_dedup;

		xlrec_dedup.nintervals = state->nintervals;

		XLogBeginInsert();
		XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
		XLogRegisterData(&xlrec_dedup, SizeOfBtreeDedup);

		/*
		 * The intervals array is not in the buffer, but pretend that it is.
		 * When XLogInsert stores the whole buffer, the array need not be
		 * stored too.
		 */
		XLogRegisterBufData(0, state->intervals,
							state->nintervals * sizeof(BTDedupInterval));

		recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_DEDUP);
	}

An interval says “offsets baseoff..baseoff+nitems-1 were merged into a posting list tuple”, and the REDO routine rebuilds it. Again: the WAL records the fact of the transformation, not the transformed bytes.

VACUUM and dead TIDs

A posting list can contain dead TIDs, and VACUUM has to remove them. But it cannot simply delete a TID from the middle of the array without breaking the sort order or the tuple’s self-description (the number of TIDs is stored in the tuple header).

The approach: rebuild the tuple without the dead TIDs, and overwrite the old tuple in place.

First, the scan. In src/backend/access/nbtree/nbtree.c, the vacuum scan distinguishes plain tuples from posting list tuples:

c 
// src/backend/access/nbtree/nbtree.c
				Assert(!BTreeTupleIsPivot(itup));
				if (!BTreeTupleIsPosting(itup))
				{
					/* Regular tuple, standard table TID representation */
					if (callback(&itup->t_tid, callback_state))
					{
						deletable[ndeletable++] = offnum;
						nhtidsdead++;
					}
					else
						nhtidslive++;
				}
				else
				{
					BTVacuumPosting vacposting;
					int			nremaining;

					/* Posting list tuple */
					vacposting = btreevacuumposting(vstate, itup, offnum,
													&nremaining);
					if (vacposting == NULL)
					{
						/*
						 * All table TIDs from the posting tuple remain, so no
						 * delete or update required
						 */
						Assert(nremaining == BTreeTupleGetNPosting(itup));
					}
					else if (nremaining > 0)
					{
						/*
						 * Store metadata about posting list tuple in
						 * updatable array for entire page.  Existing tuple
						 * will be updated during the later call to
						 * _bt_delitems_vacuum().
						 */
						Assert(nremaining < BTreeTupleGetNPosting(itup));
						updatable[nupdatable++] = vacposting;
						nhtidsdead += BTreeTupleGetNPosting(itup) - nremaining;
					}
					else
					{
						/*
						 * All table TIDs from the posting list must be
						 * deleted.  We'll delete the index tuple completely
						 * (no update required).
						 */
						Assert(nremaining == 0);
						deletable[ndeletable++] = offnum;
						nhtidsdead += BTreeTupleGetNPosting(itup);
						pfree(vacposting);
					}

					nhtidslive += nremaining;
				}

Three outcomes for a posting list tuple:

Live TIDsAction
AllNothing
SomeRewrite the tuple without the dead TIDs
NoneDelete the whole tuple

The helper that works out which is which:

c 
// src/backend/access/nbtree/nbtree.c
static BTVacuumPosting
btreevacuumposting(BTVacState *vstate, IndexTuple posting,
				   OffsetNumber updatedoffset, int *nremaining)
{
	int			live = 0;
	int			nitem = BTreeTupleGetNPosting(posting);
	ItemPointer items = BTreeTupleGetPosting(posting);
	BTVacuumPosting vacposting = NULL;

	for (int i = 0; i < nitem; i++)
	{
		if (!vstate->callback(items + i, vstate->callback_state))
		{
			/* Live table TID */
			live++;
		}
		else if (vacposting == NULL)
		{
			/*
			 * First dead table TID encountered.
			 *
			 * It's now clear that we need to delete one or more dead table
			 * TIDs, so start maintaining metadata describing how to update
			 * existing posting list tuple.
			 */
			vacposting = palloc(offsetof(BTVacuumPostingData, deletetids) +
								nitem * sizeof(uint16));

			vacposting->itup = posting;
			vacposting->updatedoffset = updatedoffset;
			vacposting->ndeletedtids = 0;
			vacposting->deletetids[vacposting->ndeletedtids++] = i;
		}
		else
		{
			/* Second or subsequent dead table TID */
			vacposting->deletetids[vacposting->ndeletedtids++] = i;
		}
	}

	*nremaining = live;
	return vacposting;
}

Note the optimization: nothing is allocated at all unless there is actually a dead TID to remove.

Then _bt_update_posting() in nbtdedup.c builds the new tuple:

c 
// src/backend/access/nbtree/nbtdedup.c
void
_bt_update_posting(BTVacuumPosting vacposting)
{
	IndexTuple	origtuple = vacposting->itup;
	uint32		keysize,
				newsize;
	IndexTuple	itup;
	int			nhtids;
	int			ui,
				d;
	ItemPointer htids;

	nhtids = BTreeTupleGetNPosting(origtuple) - vacposting->ndeletedtids;

	Assert(_bt_posting_valid(origtuple));
	Assert(nhtids > 0 && nhtids < BTreeTupleGetNPosting(origtuple));

	/*
	 * Determine final size of new tuple.
	 *
	 * This calculation needs to match the code used within _bt_form_posting()
	 * for new posting list tuples.  We avoid calling _bt_form_posting() here
	 * to save ourselves a second memory allocation for a htids workspace.
	 */
	keysize = BTreeTupleGetPostingOffset(origtuple);
	if (nhtids > 1)
		newsize = MAXALIGN(keysize +
						   nhtids * sizeof(ItemPointerData));
	else
		newsize = keysize;
	...
	ui = 0;
	d = 0;
	for (int i = 0; i < BTreeTupleGetNPosting(origtuple); i++)
	{
		if (d < vacposting->ndeletedtids && vacposting->deletetids[d] == i)
		{
			d++;
			continue;
		}
		htids[ui++] = *BTreeTupleGetPostingN(origtuple, i);
	}
	Assert(ui == nhtids);
	Assert(d == vacposting->ndeletedtids);
	Assert(nhtids == 1 || _bt_posting_valid(itup));
	Assert(nhtids == 1 || ItemPointerIsValid(&itup->t_tid));

	/* vacposting arg's itup will now point to updated version */
	vacposting->itup = itup;
}

The nhtids == 1 case degrades back to a plain tuple, exactly as in _bt_form_posting() — and note the assertion at the end, which says that a single-TID result must have a valid TID in t_tid rather than in a posting list.

The physical write happens in _bt_delitems_vacuum() (src/backend/access/nbtree/nbtpage.c), which overwrites the tuple in place with PageIndexTupleOverwrite():

c 
// src/backend/access/nbtree/nbtpage.c
	/*
	 * Handle posting tuple updates.
	 *
	 * Deliberately do this before handling simple deletes.  If we did it the
	 * other way around (i.e. WAL record order -- simple deletes before
	 * updates) then we'd have to make compensating changes to the 'updatable'
	 * array of offset numbers.
	 *
	 * PageIndexTupleOverwrite() won't unset each item's LP_DEAD bit when it
	 * happens to already be set.  It's important that we not interfere with
	 * any future simple index tuple deletion operations.
	 */
	for (int i = 0; i < nupdatable; i++)
	{
		OffsetNumber updatedoffset = updatedoffsets[i];
		IndexTuple	itup;
		Size		itemsz;

		itup = updatable[i]->itup;
		itemsz = MAXALIGN(IndexTupleSize(itup));
		if (!PageIndexTupleOverwrite(page, updatedoffset, itup, itemsz))
			elog(PANIC, "failed to update partially dead item in block %u of index \"%s\"",
				 BufferGetBlockNumber(buf), RelationGetRelationName(rel));
	}

One more subtlety, from the nbtree README:

We can set the LP_DEAD bit with posting list tuples, though only when all TIDs are known dead.

That is, a posting list tuple is either fully live-ish (some TIDs may be dead but the tuple is not marked dead) or fully dead (LP_DEAD set). A posting list is never partially marked dead, because the LP_DEAD bit is per-line-pointer and there is no way to say “this one is dead but that one isn’t” without rewriting the tuple.

Bottom-up deletion

The other way dead index entries get cleaned up is bottom-up index deletion, which is the preferred mechanism in modern PostgreSQL and predates (and complements) deduplication. The pass is _bt_bottomupdel_pass() in nbtdedup.c, and it uses exactly the same equality machinery as deduplication:

c 
// src/backend/access/nbtree/nbtdedup.c
		else if (_bt_keep_natts_fast(rel, state->base, itup) > nkeyatts &&
				 _bt_dedup_save_htid(state, itup))
		{
			/* Tuple is equal; just added its TIDs to pending interval */
		}

The difference is that it does not merge tuples; it asks the table AM which of the logical rows behind the duplicates are safe to delete, and the table AM deletes the heap tuples, which makes the index entries dead by themselves.

For posting list tuples the heuristics are more conservative, and the comment explains why:

Our approach to marking entries whose TIDs come from posting lists is more complicated. Posting lists can only be formed by a deduplication pass (or during an index build), so recent version churn affecting the pointed-to logical rows is not particularly likely.

c 
// src/backend/access/nbtree/nbtdedup.c
			/*
			 * Complicated case: A posting list tuple.
			 *
			 * We make the conservative assumption that there can only be at
			 * most one affected logical row per posting list tuple. ...
			 */
			int			nitem = BTreeTupleGetNPosting(itup);
			bool		firstpromising = false;
			bool		lastpromising = false;
			...
			if (dupinterval)
			{
				/*
				 * Complicated rule: either the first or last TID in the
				 * posting list gets marked promising (if any at all)
				 */
				...
				/* Only entry with predominant table block can be promising */
				firstpromising = (minblocklist == midblocklist);
				lastpromising = (!firstpromising &&
								 midblocklist == maxblocklist);
			}

At most one TID per posting list tuple is offered to the table AM as a “promising” candidate, and only if the tuple’s TIDs mostly point at the same heap block.

The counterpoint: how GIN does it

GIN has had posting lists far longer than btree, and it does everything differently. The comparison is instructive because it shows what btree gave up.

GIN compresses the TID array

GIN stores a posting list as a varbyte-encoded delta stream. From src/backend/access/gin/ginpostinglist.c:

c 
// src/backend/access/gin/ginpostinglist.c
/*
 * For encoding purposes, item pointers are represented as 64-bit unsigned
 * integers. The lowest 11 bits represent the offset number, and the next
 * lowest 32 bits are the block number. That leaves 21 bits unused, i.e.
 * only 43 low bits are used.
 *
 * 11 bits is enough for the offset number, because MaxHeapTuplesPerPage <
 * 2^11 on all supported block sizes. We are frugal with the bits, because
 * smaller integers use fewer bytes in the varbyte encoding, saving disk
 * space. ...
 *
 * These 43-bit integers are encoded using varbyte encoding. In each byte,
 * the 7 low bits contain data, while the highest bit is a continuation bit.
 * When the continuation bit is set, the next byte is part of the same
 * integer, otherwise this is the last byte of this integer. 43 bits need
 * at most 7 bytes in this encoding:
 *
 * 0XXXXXXX
 * 1XXXXXXX 0XXXXYYY
 * ...
 *
 * X = bits used for offset number
 * Y = bits used for block number
 * u = unused bit
 *
 * The bytes are in stored in little-endian order.
 *
 * An important property of this encoding is that removing an item from list
 * never increases the size of the resulting compressed posting list. Proof:
 *
 * Removing number is actually replacement of two numbers with their sum. We
 * have to prove that varbyte encoding of a sum can't be longer than varbyte
 * encoding of its summands. Sum of two numbers is at most one bit wider than
 * the larger of the summands. Widening a number by one bit enlarges its length
 * in varbyte encoding by at most one byte. Therefore, varbyte encoding of sum
 * is at most one byte longer than varbyte encoding of larger summand. Lesser
 * summand is at least one byte, so the sum cannot take more space than the
 * summands, Q.E.D.
 *
 * This property greatly simplifies VACUUM, which can assume that posting
 * lists always fit on the same page after vacuuming. Note that even though
 * that holds for removing items from a posting list, you must also be
 * careful to not cause expansion e.g. when merging uncompressed items on the
 * page into the compressed lists, when vacuuming.
 */

That “removing an item never increases the size” property is a lovely piece of engineering, and btree simply cannot have it: btree’s posting list is a flat array of fixed-size TIDs, and it must be rebuilt to remove an entry.

The encoder itself:

c 
// src/backend/access/gin/ginpostinglist.c
static void
encode_varbyte(uint64 val, unsigned char **ptr)
{
	unsigned char *p = *ptr;

	while (val > 0x7F)
	{
		*(p++) = 0x80 | (val & 0x7F);
		val >>= 7;
	}
	*(p++) = (unsigned char) val;

	*ptr = p;
}

and the compressed list structure:

c 
// src/include/access/ginblock.h
typedef struct
{
	ItemPointerData first;		/* first item in this posting list (unpacked) */
	uint16		nbytes;			/* number of bytes that follow */
	unsigned char bytes[FLEXIBLE_ARRAY_MEMBER]; /* varbyte encoded items */
} GinPostingList;

#define SizeOfGinPostingList(plist) (offsetof(GinPostingList, bytes) + SHORTALIGN((plist)->nbytes) )
#define GinNextPostingListSegment(cur) ((GinPostingList *) (((char *) (cur)) + SizeOfGinPostingList((cur))))

The first TID is stored unpacked (so that the decoder knows where the list starts without decoding from the beginning); everything after it is a delta stream.

For a btree-style comparison: btree’s 6-byte-per-TID array versus GIN’s typically 1–2 bytes per TID for dense lists. GIN wins on space by a factor of three or more, and btree does not even try, because — as the README says:

Posting list compression would break the assumptions made by posting list splits about page space accounting … Besides, posting list compression does not offer a compelling trade-off for nbtree, since in general nbtree is optimized for consistent performance with many concurrent readers and writers. Compression would also make the deletion of a subset of TIDs from a posting list slow and complicated, which would be a big problem for workloads that depend heavily on bottom-up index deletion.

GIN has a posting tree; btree does not

The other half of the contrast: GIN does have a posting tree. A GIN index entry for a key points at a tree of pages that hold the list of rows containing that key, because a single key can match millions of rows and cannot fit on one page. The GIN data pages store GinPostingList structures, and the tree has internal pages with PostingItem pairs.

btree never needed that, because in btree the posting list is bounded by the page: it lives inside a tuple on a leaf page, and the bound (1348 bytes, ~224 TIDs) is chosen so that a page full of posting lists can still be split sensibly.

GIN’s key extraction

One more piece of GIN machinery worth comparing, because it is the mirror image of btree’s problem. GIN has to extract multiple keys from one column value (intarray, tsvector, arrays), sort them, and remove duplicates before it can build a posting list. That happens in ginExtractEntries() in src/backend/access/gin/ginutil.c.

The comparator is a hand-written one that also detects duplicates as a side effect, which is a neat trick:

c 
// src/backend/access/gin/ginutil.c
typedef struct
{
	FmgrInfo   *cmpDatumFunc;
	Oid			collation;
	bool		haveDups;
} cmpEntriesArg;

static int
cmpEntries(const void *a, const void *b, void *arg)
{
	const Datum *aa = (const Datum *) a;
	const Datum *bb = (const Datum *) b;
	cmpEntriesArg *data = (cmpEntriesArg *) arg;
	int			res;

	res = DatumGetInt32(FunctionCall2Coll(data->cmpDatumFunc,
										  data->collation,
										  *aa, *bb));

	/*
	 * Detect if we have any duplicates.  If there are equal keys, qsort must
	 * compare them at some point, else it wouldn't know whether one should go
	 * before or after the other.
	 */
	if (res == 0)
		data->haveDups = true;

	return res;
}

#define ST_SORT qsort_arg_entries
#define ST_ELEMENT_TYPE Datum
#define ST_COMPARE_ARG_TYPE cmpEntriesArg
#define ST_COMPARE(a, b, arg) cmpEntries(a, b, arg)
#define ST_SCOPE static
#define ST_DEFINE
#define ST_DECLARE
#include "lib/sort_template.h"

The sort_template.h trick generates a specialised sort with a context argument, so GIN does not pay for a qsort callback per comparison. The haveDups flag is the payoff: the sort has to compare equal elements at least once, so it learns for free whether there are duplicates, and only then pays for a uniquifying pass:

c 
// src/backend/access/gin/ginutil.c
	if (nentries > 1)
	{
		cmpEntriesArg arg;

		arg.cmpDatumFunc = &ginstate->compareFn[attnum - 1];
		arg.collation = ginstate->supportCollation[attnum - 1];
		arg.haveDups = false;

		qsort_arg_entries(entries, nentries, &arg);

		if (arg.haveDups)
			nentries = qunique_arg(entries, nentries, sizeof(Datum), cmpEntries, &arg);
	}

And NULLs are removed before the sort, because NULLs are all equal to each other and the sort would otherwise have to special-case them:

c 
// src/backend/access/gin/ginutil.c
	/*
	 * Scan the items for any NULLs.  All NULLs are considered equal, so we
	 * just need to check and remember if there are any.  We remove them from
	 * the array here, and after deduplication, put back one NULL entry to
	 * represent them all.
	 */
	hasNull = false;
	if (nullFlags)
	{
		int32		numNonNulls = 0;

		for (int32 i = 0; i < nentries; i++)
		{
			if (nullFlags[i])
				hasNull = true;
			else
			{
				entries[numNonNulls] = entries[i];
				numNonNulls++;
			}
		}
		nentries = numNonNulls;
	}

The comment “put back one NULL entry to represent them all” is the same idea as btree’s “NULL is just another value from the domain of indexed values” — deduplication works on NULLs just as well as on any other value.

The rules for when deduplication applies

Three independent conditions, all of which must hold.

1. The index must be deduplication-safe (“allequalimage”)

The operator class must guarantee that two equal datums have the same image — the same bytes. This is not the same as “equal”. A bpchar value 'a' and 'a ' compare equal but have different images, and if they were merged into one posting list, an index-only scan would have to return one image for both rows.

The check lives in _bt_allequalimage() in src/backend/access/nbtree/nbtutils.c:

c 
// src/backend/access/nbtree/nbtutils.c
/*
 * Are all attributes in rel "equality is image equality" attributes?
 *
 * We use each attribute's BTEQUALIMAGE_PROC opclass procedure.  If any
 * opclass either lacks a BTEQUALIMAGE_PROC procedure or returns false, we
 * return false; otherwise we return true.
 *
 * Returned boolean value is stored in index metapage during index builds.
 * Deduplication can only be used when we return true.
 */
bool
_bt_allequalimage(Relation rel, bool debugmessage)
{
	bool		allequalimage = true;

	/* INCLUDE indexes can never support deduplication */
	if (IndexRelationGetNumberOfAttributes(rel) !=
		IndexRelationGetNumberOfKeyAttributes(rel))
		return false;

	for (int i = 0; i < IndexRelationGetNumberOfKeyAttributes(rel); i++)
	{
		Oid			opfamily = rel->rd_opfamily[i];
		Oid			opcintype = rel->rd_opcintype[i];
		Oid			collation = rel->rd_indcollation[i];
		Oid			equalimageproc;

		equalimageproc = get_opfamily_proc(opfamily, opcintype, opcintype,
										   BTEQUALIMAGE_PROC);

		/*
		 * If there is no BTEQUALIMAGE_PROC then deduplication is assumed to
		 * be unsafe.  Otherwise, actually call proc and see what it says.
		 */
		if (!OidIsValid(equalimageproc) ||
			!DatumGetBool(OidFunctionCall1Coll(equalimageproc, collation,
											   ObjectIdGetDatum(opcintype))))
		{
			allequalimage = false;
			break;
		}
	}

	if (debugmessage)
	{
		if (allequalimage)
			elog(DEBUG1, "index \"%s\" can safely use deduplication",
				 RelationGetRelationName(rel));
		else
			elog(DEBUG1, "index \"%s\" cannot use deduplication",
				 RelationGetRelationName(rel));
	}

	return allequalimage;
}

The result is recorded in the index metapage at build time, so the decision is made once, by CREATE INDEX or REINDEX, and is then consulted on every insert.

The types that fail this test are listed in the documentation (doc/src/sgml/btree.sgml):

TypeWhy
text, varchar with a nondeterministic collationCase and accent differences must be preserved
character(n) / char / bpcharTrailing spaces are disregarded when comparing, but must be preserved
numericNumeric display scale must be preserved
jsonbUses numeric internally
float4, float8-0 and 0 are equal but have distinct representations
Container types (arrays, ranges, composites)Not supported yet

The bpchar case is not theoretical. In October 2026, PostgreSQL rescinded deduplication support for bpchar_ops, bpchar_pattern_ops and oidvector_ops (commit a32b8dc9865, “Rescind unsafe deduplication support”):

bpchar equality ignores trailing spaces, so equal values in a column with no length specifier can have different images. Similarly, oidvector equality intentionally pays no attention to the array lower bound field. We nevertheless allowed nbtree deduplication to be used with indexes built with bpchar_ops, bpchar_pattern_ops, or oidvector_ops. A posting list split could therefore place a TID in an index tuple whose key was equal to, but not bytewise identical to, the corresponding table value. This allowed index-only scans to return subtly wrong results.

That is the whole failure mode in one sentence: a posting list split moves a TID from one index tuple to another, and if the two tuples' keys are merely equal rather than identical, the row now claims to have a key value it never had.

2. INCLUDE columns make deduplication impossible

The same function returns false for any index with non-key columns:

c 
	/* INCLUDE indexes can never support deduplication */
	if (IndexRelationGetNumberOfAttributes(rel) !=
		IndexRelationGetNumberOfKeyAttributes(rel))
		return false;

The reason is obvious in hindsight: an INCLUDE column’s value is per-row, not per-key. Two rows with the same key but different INCLUDE values cannot share one index tuple, because an index-only scan has to return the row’s own INCLUDE value.

The nbtree header comment says the same thing about the format:

Like any non-pivot tuple, the number of columns stored is always implicitly the total number in the index (in practice there can never be non-key columns stored, since deduplication is not supported with INCLUDE indexes).

3. The index must not be unique… except when it is

Unique indexes can use deduplication, contrary to what many people assume. The rationale is in the README:

Unique index leaf pages only get a deduplication pass when an insertion (that might have to split the page) observed an existing duplicate on the page in passing. … Our ultimate goal is to delay leaf page splits indefinitely (i.e. to prevent them altogether).

A unique index with version churn (an UPDATE that changes the key) can temporarily hold two entries with the same key. Deduplication lets the page absorb that without splitting, buying time for bottom-up deletion to clean up.

What it all means in practice

A B-tree index over a low-cardinality column can be dramatically smaller than you think. A boolean column with a 50/50 split over ten million rows produces roughly 5000 posting list tuples, not ten million index entries. If you REINDEX such an index and it shrinks by an order of magnitude, that is deduplication doing its job.

Deduplication is lazy, so a freshly created index may not look deduplicated. CREATE INDEX does deduplicate eagerly, using a different strategy — each group of duplicates in the sorted input is merged before being added to the pending page. But an index that grew by incremental inserts will only be deduplicated when a page split was about to happen. If you want the compact form, REINDEX.

deduplicate_items = off is a real option, and rarely a good one. The cost of a deduplication pass on a page with no duplicates is a scan of the page’s tuples comparing keys — not free, but not catastrophic. The documentation’s advice is:

Write-heavy workloads that don’t benefit from deduplication due to having few or no duplicate values in indexes will incur a small, fixed performance penalty (unless deduplication is explicitly disabled).

If you have a high-cardinality index on a write-heavy table and you are chasing insert throughput, turning it off is a legitimate experiment.

A posting list is not a compression scheme. Six bytes per TID, no deltas, no varbyte encoding. If you want compressed posting lists, you want GIN. btree’s posting lists are a deduplication mechanism: they remove the repeated keys, not the repeated structure within the TID array.

Posting list splits are cheap in WAL terms, and that was a deliberate design goal. The WAL record carries two bytes of offset and the new tuple; the modified posting list is recomputed at replay time. A posting list split is not a “rewrite the whole posting list” WAL record.

Dead TIDs in a posting list are cleaned up by rewriting the tuple, not by marking it. The LP_DEAD bit is only set on a posting list tuple when every TID in it is dead. If a posting list has 200 TIDs and 3 are dead, VACUUM rebuilds the tuple with 197 TIDs. On a high-churn table that is a lot of tuple rewriting — which is one reason bottom-up index deletion, which deletes the heap rows and lets the index entries die naturally, is the preferred cleanup path.

Deduplication requires equality to imply identity. If your column compares equal in more ways than it compares identically — trailing spaces, numeric display scale, -0 versus 0, a nondeterministic collation — then PostgreSQL will refuse to deduplicate it, and if it was ever allowed to, that was a bug (as a32b8dc9865 fixed).

The number of TIDs per posting list is bounded twice, and the smaller bound is the interesting one. 4095 is the hard limit from the 12-bit offset number; ~224 is the practical limit from the one-sixth-of-a-page size cap. A key that is 300 bytes long leaves room for only ~174 TIDs per posting list, so a wide key means short lists.

Look at it yourself

pageinspect can show you the raw posting list tuples:

sql 
CREATE EXTENSION pageinspect;

-- the leaf page's tuples, with the raw t_tid
SELECT itemoffset, ctid, itemlen, data
FROM bt_page_items('myindex', 0);

For a posting list tuple, the ctid column is the repurposed t_tid: the block number is the byte offset of the TID array within the tuple, and the offset number’s low 12 bits are the number of TIDs. itemlen is the whole tuple’s length, key plus TID array. The data column deliberately excludes the posting list, so it shows you just the key columns:

c 
// contrib/pageinspect/btreefuncs.c
	/*
	 * Make sure that "data" column does not include posting list or pivot
	 * tuple representation of heap TID(s).
	 * ...
	 */
	if (BTreeTupleIsPosting(itup))
		dlen -= IndexTupleSize(itup) - BTreeTupleGetPostingOffset(itup);

Which means that to see the raw TID array you have to go at the raw page yourself.

The amcheck extension’s bt_index_check() and bt_index_parent_check() will verify posting list invariants, and bt_index_check() has specific handling for posting list tuples.

Further reading

  • src/backend/access/nbtree/README — the design document. The sections “Notes about deduplication”, “Deduplication in unique indexes” and “Posting list splits” are the authoritative description of everything above.
  • src/backend/access/nbtree/nbtdedup.c — the deduplication pass itself (_bt_dedup_pass), the posting list builder (_bt_form_posting), the posting list splitter (_bt_swap_posting), and the VACUUM-time posting list rebuilder (_bt_update_posting).
  • src/include/access/nbtree.h — the tuple format documentation and the BTreeTuple* accessors.
  • src/backend/access/nbtree/nbtxlog.c — the WAL redo routines for posting list splits, and src/include/access/nbtxlog.h for the record formats.
  • src/backend/access/gin/ginpostinglist.c — GIN’s varbyte encoding of posting lists, and the proof that removing an entry never grows the list.
  • doc/src/sgml/btree.sgml, section “Deduplication” — the user-facing description of when deduplication is used and when it is not.

PostgresPerformanceBtreeIndexInternals