PostgreSQL Sorts Rows Fast

Every ORDER BY is three problems wearing a trench coat.

The first is a memory problem: a million rows of text will not fit in work_mem, and when they don’t fit, you are in the disk-sort business, and disk sorts are slow in a way that has nothing to do with disks. The second is a comparison problem: sorting is O(n log n) comparisons, and if each comparison is a strcoll() on two locale-aware strings, you are doing millions of calls into a library that walks character tables. The third is a cache problem: even if every comparison is a single integer compare, the array of tuples you are comparing is bigger than your L2 cache, and every comparison is a potential cache miss, which on a modern CPU costs more than the comparison itself.

PostgreSQL has a separate, dedicated answer to each of those three, and they compose. The answers are:

Problem	Answer	Where
Comparisons are expensive	abbreviated keys	`varlena.c`, `sortsupport.h`
Comparisons are cache misses	radix sort, presorted detection	`tuplesort.c` (new in 20devel)
Memory is finite	bounded heap, external merge	`tuplesort.c`

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

The sort is a state machine

Everything in the sorter hangs off one struct, Tuplesortstate (src/backend/utils/sort/tuplesort.c):

c
/*
 * Possible states of a Tuplesort object.  These denote the states that
 * persist between calls of Tuplesort routines.
 */
typedef enum
{
	TSS_INITIAL,				/* Loading tuples; still within memory limit */
	TSS_BOUNDED,				/* Loading tuples into bounded-size heap */
	TSS_BUILDRUNS,				/* Loading tuples; writing to tape */
	TSS_SORTEDINMEM,			/* Sort completed entirely in memory */
	TSS_SORTEDONTAPE,			/* Sort completed, final run is on tape */
	TSS_FINALMERGE,				/* Performing final merge on-the-fly */
} TupSortStatus;

The transitions are worth internalizing, because almost every interesting decision in the sorter is conditioned on the current state:

State	Meaning	Exit to
`TSS_INITIAL`	tuples accumulating in an unsorted array	`TSS_BOUNDED`, `TSS_BUILDRUNS`, `TSS_SORTEDINMEM`
`TSS_BOUNDED`	tuples accumulating in a top-N heap	`TSS_SORTEDINMEM`
`TSS_BUILDRUNS`	runs being written to tape	`TSS_SORTEDONTAPE`, `TSS_FINALMERGE`
`TSS_SORTEDINMEM`	fully sorted, in memory	—
`TSS_SORTEDONTAPE`	fully sorted, materialized on one tape	—
`TSS_FINALMERGE`	final merge being performed on the fly	—

TSS_INITIAL is the “everything is fine” state. TSS_BUILDRUNS means we’ve run out of memory and are writing sorted runs to tape. TSS_FINALMERGE is the clever one: instead of writing the final merged run to disk and reading it back, the sorter keeps the merge heap live and serves tuples straight out of it as the caller asks for them. One whole pass of disk I/O disappears.

What is actually being sorted

The unit of sorting is the SortTuple, defined in src/include/utils/tuplesort.h:

c
typedef struct
{
	void	   *tuple;			/* the tuple itself */
	Datum		datum1;			/* value of first key column */
	bool		isnull1;		/* is first key column NULL? */
	uint8		curbyte;		/* chunk of datum1 for current radix sort pass */
	int			srctape;		/* source tape number */
} SortTuple;

Five fields, and the comment above the struct explains why there are only one and a half key columns in there:

Storing the first key column lets us save heap_getattr or index_getattr calls during tuple comparisons. We could extract and save all the key columns not just the first, but this would increase code complexity and overhead, and wouldn’t actually save any comparison cycles in the common case where the first key determines the comparison result.

That is the correct answer, and it is the reason the whole abbreviated-key machinery has to be so careful: only the leading key is cached. If the first key ties, the tiebreak path goes back to the tuple and does heap_getattr() again for the second key, the third key, and so on.

The comment continues:

There is one special case: when the sort support infrastructure provides an “abbreviated key” representation, where the key is (typically) a pass by value proxy for a pass by reference type. In this case, the abbreviated key is stored in datum1 in place of the actual first key column.

So datum1 is a slot with two possible meanings: the actual first key value, or a stand-in for it. The sorter must therefore be able to undo the stand-in, which is what removeabbrev is for (see below).

curbyte is new in 20devel — it is scratch space for the radix sort, which stashes the current pass’s byte in the tuple itself so the permutation step does not have to recompute it.

srctape records which input tape a tuple came from, during a merge.

Memory accounting

work_mem (in kilobytes) becomes allowedMem (in bytes) at the start:

c
	state->allowedMem = Max(workMem, 64) * (int64) 1024;

and availMem is the running remainder. The two macros that do all the bookkeeping are startlingly small:

c
#define LACKMEM(state)		((state)->availMem < 0 && !(state)->slabAllocatorUsed)
#define USEMEM(state,amt)	((state)->availMem -= (amt))
#define FREEMEM(state,amt)	((state)->availMem += (amt))

Three facts fall out of that.

First, the accounting is deliberately approximate. The file’s own comment says so:

We count space allocated for tuples against the workMem limit, plus the space used by the variable-size memtuples array. Fixed-size space is not counted; it’s small enough to not be interesting.

and:

Note that we count actual space used (as shown by GetMemoryChunkSpace) rather than the originally-requested size. This is important since palloc can add substantial overhead.

Second, LACKMEM is not “out of memory”. It is “the budget is overspent”, and it is the trigger for the transition to tape-based operation. Overshooting is allowed — the tuple that tips you over the line is still admitted — but the next dumptuples() call will flush.

Third, LACKMEM is disabled once the slab allocator is in use, because during a merge the sorter manages tuple memory itself and there is no budget left to speak of. That is why the macro has the !(state)->slabAllocatorUsed clause at all.

The memtuples array itself grows on a doubling schedule until it gets close to the limit, then switches to a proportional estimate. From grow_memtuples():

Normally, at each increment we double the size of the array. When doing that would exceed a limit, we attempt one last, smaller increase (and then clear the growmemtuples flag so we don’t try any more). That allows us to use memory as fully as permitted; sticking to the pure doubling rule could result in almost half going unused.

The comparison problem: abbreviated keys

Now the interesting part.

The contract

src/include/utils/sortsupport.h defines the framework. The struct is big, but only a few fields matter:

c
	int			(*comparator) (Datum x, Datum y, SortSupport ssup);
	...
	bool		abbreviate;
	...
	Datum		(*abbrev_converter) (Datum original, SortSupport ssup);
	...
	bool		(*abbrev_abort) (int memtupcount, SortSupport ssup);
	...
	int			(*abbrev_full_comparator) (Datum x, Datum y, SortSupport ssup);
} SortSupportData;

The idea: an opclass may supply a converter that turns a pass-by-reference value (a text, say) into a pass-by-value proxy (a Datum holding eight bytes of something). The sort then compares proxies, which is one integer compare. If the proxies are equal, you fall back to the real comparator to break the tie.

The header comment states the rules, and they are strict:

This representation is a simple approximation of the original Datum. It must be possible to compare datums of this representation with each other using the supplied alternative comparator, and have any non-zero return value be a reliable proxy for what a proper comparison would indicate. Returning zero from the alternative comparator does not indicate equality, as with a conventional support routine 1, though – it indicates that it wasn’t possible to determine how the two abbreviated values compared. A proper comparison, using “abbrev_full_comparator”/ApplySortAbbrevFullComparator() is therefore required.

So the abbreviated comparator may return “I don’t know” (zero), but it may never lie.

And then the reason for the whole thing, which is not “fewer instructions”:

In many cases this results in most or all comparisons only using the cheap alternative comparison func, which is typically implemented as code that compiles to just a few CPU instructions. CPU cache miss penalties are expensive; to get good overall performance, sort infrastructure must heavily weigh cache performance.

That is the thesis of this entire subsystem. The abbreviated key is not mainly about doing less arithmetic; it is about making the comparison itself touch one cache line instead of two long strings.

Only the leading key may be abbreviated

Abbreviation is only ever applied to the first sort key. In tuplesortvariants.c, every variant sets up its sort keys with the same one-liner:

c
		/* Convey if abbreviation optimization is applicable in principle */
		sortKey->abbreviate = (i == 0 && base->haveDatum1);

i == 0 is the leading key. base->haveDatum1 means “this variant actually maintains datum1”. The CLUSTER variant, for instance, sets it to false when the leading index attribute is an expression rather than a plain column:

c
	/*
	 * If we don't have a simple leading attribute, we don't currently
	 * initialize datum1, so disable optimizations that require it.
	 */
	if (arg->indexInfo->ii_IndexAttrNumbers[0] == 0)
		base->haveDatum1 = false;
	else
		base->haveDatum1 = true;

Why only the leading key? Two reasons. First, SortTuple only has room for one. Second, and more deeply: the value of abbreviation comes from avoiding touching the tuple at all. If you cache eight bytes for the first key and eight bytes for the second, you’ve doubled the memory traffic of the sort array for a benefit that only materializes when the first key ties — and when the first key ties often, the abbreviated-key strategy was a bad idea anyway (see the cost model below).

The datum-sort variant has a different restriction, and the comment is worth quoting in full:

c
	/*
	 * Abbreviation is possible here only for by-reference types.  In theory,
	 * a pass-by-value datatype could have an abbreviated form that is cheaper
	 * to compare.  In a tuple sort, we could support that, because we can
	 * always extract the original datum from the tuple as needed.  Here, we
	 * can't, because a datum sort only stores a single copy of the datum; the
	 * "tuple" field of each SortTuple is NULL.
	 */
	base->sortKeys->abbreviate = !typbyval;

The conversion

The conversion happens in tuplesort_puttuple_common():

c
	if (!useAbbrev)
	{
		/*
		 * Leave ordinary Datum representation, or NULL value.  If there is a
		 * converter it won't expect NULL values, and cost model is not
		 * required to account for NULL, so in that case we avoid calling
		 * converter and just set datum1 to zeroed representation (to be
		 * consistent, and to support cheap inequality tests for NULL
		 * abbreviated keys).
		 */
	}
	else if (!consider_abort_common(state))
	{
		/* Store abbreviated key representation */
		tuple->datum1 = state->base.sortKeys->abbrev_converter(tuple->datum1,
															   state->base.sortKeys);
	}
	else
	{
		/*
		 * Set state to be consistent with never trying abbreviation.
		 *
		 * Alter datum1 representation in already-copied tuples, so as to
		 * ensure a consistent representation (current tuple was just
		 * handled).  It does not matter if some dumped tuples are already
		 * sorted on tape, since serialized tuples lack abbreviated keys
		 * (TSS_BUILDRUNS state prevents control reaching here in any case).
		 */
		REMOVEABBREV(state, state->memtuples, state->memtupcount);
	}

Note the NULL case: NULL values are never abbreviated. useAbbrev is false for them, so datum1 stays the zeroed representation. That keeps the NULL check on the abbreviated key trivial and, importantly, keeps the cost model from having to reason about NULLs.

The REMOVEABBREV path is the interesting one. If the cost model decides to give up on abbreviation mid-sort, every tuple already sitting in memtuples[] has an abbreviated datum1 and needs to be converted back to the real key value. removeabbrev_heap() does exactly that:

c
removeabbrev_heap(Tuplesortstate *state, SortTuple *stups, int count)
{
	int			i;
	TuplesortPublic *base = TuplesortstateGetPublic(state);

	for (i = 0; i < count; i++)
	{
		HeapTupleData htup;

		htup.t_len = ((MinimalTuple) stups[i].tuple)->t_len +
			MINIMAL_TUPLE_OFFSET;
		htup.t_data = (HeapTupleHeader) ((char *) stups[i].tuple -
										 MINIMAL_TUPLE_OFFSET);
		stups[i].datum1 = heap_getattr(&htup,
									   base->sortKeys[0].ssup_attno,
									   (TupleDesc) base->arg,
									   &stups[i].isnull1);
	}
}

It goes back into the tuple and re-extracts the real value. Which means the aborted abbreviation strategy has cost something: you paid the conversion on every tuple, and now you pay a re-extraction on every tuple. This is why the abort decision is made early.

The cost model

The abort check is consider_abort_common():

c
static bool
consider_abort_common(Tuplesortstate *state)
{
	Assert(state->base.sortKeys[0].abbrev_converter != NULL);
	Assert(state->base.sortKeys[0].abbrev_abort != NULL);
	Assert(state->base.sortKeys[0].abbrev_full_comparator != NULL);

	/*
	 * Check effectiveness of abbreviation optimization.  Consider aborting
	 * when still within memory limit.
	 */
	if (state->status == TSS_INITIAL &&
		state->memtupcount >= state->abbrevNext)
	{
		state->abbrevNext *= 2;

		/*
		 * Check opclass-supplied abbreviation abort routine.  It may indicate
		 * that abbreviation should not proceed.
		 */
		if (!state->base.sortKeys->abbrev_abort(state->memtupcount,
												state->base.sortKeys))
			return false;

		/*
		 * Finally, restore authoritative comparator, and indicate that
		 * abbreviation is not in play by setting abbrev_converter to NULL
		 */
		state->base.sortKeys[0].comparator = state->base.sortKeys[0].abbrev_full_comparator;
		state->base.sortKeys[0].abbrev_converter = NULL;
		/* Not strictly necessary, but be tidy */
		state->base.sortKeys[0].abbrev_abort = NULL;
		state->base.sortKeys[0].abbrev_full_comparator = NULL;

		/* Give up - expect original pass-by-value representation */
		return true;
	}

	return false;
}

Two design points:

The sampling is exponentially spaced. state->abbrevNext starts at 10 (set in tuplesort_begin_common(): state->abbrevNext = 10;) and doubles every time. So the cost model is consulted at 10, 20, 40, 80, 160, …, 10,000, … tuples. Early on, a bad strategy is caught cheaply.
The check only runs in TSS_INITIAL. Once the sort has started spilling to tape, the decision is locked in. At that point the tuples are already written in abbreviated form (well — see the external merge section; they are not stored abbreviated), and switching strategies would be worse than finishing the job.

The opclass’s own abbrev_abort callback then gets to apply a type-specific heuristic. For text that’s varstr_abbrev_abort().

How text abbreviates: eight bytes of strxfrm

src/backend/utils/adt/varlena.c is where the text strategy lives. The header comment on the converter states the whole encoding:

c
/*
 * Conversion routine for sortsupport.  Converts original to abbreviated key
 * representation.  Our encoding strategy is simple -- pack the first 8 bytes
 * of a strxfrm() blob into a Datum (on little-endian machines, the 8 bytes are
 * stored in reverse order), and treat it as an unsigned integer.  When the "C"
 * locale is used just memcpy() from original instead.
 */

Eight bytes, one Datum, unsigned integer comparison. The work:

c
	pres = (char *) &res;
	/* memset(), so any non-overwritten bytes are NUL */
	memset(pres, 0, max_prefix_bytes);
	len = VARSIZE_ANY_EXHDR(authoritative);

	/* Get number of bytes, ignoring trailing spaces */
	if (sss->typid == BPCHAROID)
		len = bpchartruelen(authoritative_data, len);

	/*
	 * If we're using the C collation, use memcpy(), rather than strxfrm(), to
	 * abbreviate keys.  The full comparator for the C locale is also
	 * memcmp().  This should be faster than strxfrm().
	 */
	if (sss->collate_c)
		memcpy(pres, authoritative_data, Min(len, max_prefix_bytes));
	else
	{
		...
	}

So in the C locale, the “abbreviated key” is literally the first eight bytes of the string, and the comparator is a memcmp-flavored unsigned integer compare. In a non-C locale, it is the first eight bytes of the strxfrm()-transformed string — the transform being what makes strcmp() on transformed blobs equivalent to strcoll() on the originals.

And then the byteswap:

c
	/*
	 * Byteswap on little-endian machines.
	 *
	 * This is needed so that ssup_datum_uint64_cmp() (an unsigned integer
	 * 3-way comparator) works correctly on all platforms.  If we didn't do
	 * this, the comparator would have to call memcmp() with a pair of
	 * pointers to the first byte of each abbreviated key, which is slower.
	 */
	res = DatumBigEndianToNative(res);

This is a lovely piece of engineering. The abbreviated key is bytes, not an integer, so a naive memcmp() on two eight-byte values would compare them in the wrong order on a little-endian machine (the first byte in memory is the least significant byte of the big-endian integer you want to compare). The alternative would be to make the comparator call memcmp() on two pointers, which costs an extra function call and touches two cache lines instead of one. So instead the bytes are reversed at conversion time, once per tuple, and the comparison stays a single integer compare.

That is the whole “cache performance” thesis in action: pay once per tuple at conversion, save on every comparison.

How the cost model estimates cardinality: HyperLogLog

The abort callback needs to know how many distinct abbreviated keys it has seen, and how many distinct original keys it has seen, and compare the two. Counting exactly would be expensive; counting approximately is cheap. So:

c
		/*
		 * Maintain approximate cardinality of both abbreviated keys and original,
		 * authoritative keys using HyperLogLog.  Used as cheap insurance against
		 * the worst case, where we do many string transformations for no saving
		 * in full strcoll()-based comparisons.  These statistics are used by
		 * varstr_abbrev_abort().
		 *
		 * First, Hash key proper, or a significant fraction of it.  Mix in length
		 * in order to compensate for cases where differences are past
		 * PG_CACHE_LINE_SIZE bytes, so as to limit the overhead of hashing.
		 */
		hash = hash_bytes((unsigned char *) authoritative_data,
					  Min(len, PG_CACHE_LINE_SIZE));

	if (len > PG_CACHE_LINE_SIZE)
		hash ^= murmurhash32((uint32) len);

	addHyperLogLog(&sss->full_card, hash);

	/* Hash abbreviated key */
	hash = (uint32) murmurhash64(DatumGetUInt64(res));

	addHyperLogLog(&sss->abbr_card, hash);

Two HyperLogLog registers, one for each population. Only the first cache line (64 bytes) of the string is hashed — beyond that, differences are unlikely to matter for the ordering and hashing the whole string would be too expensive. Length is mixed in to catch differences that live past the 64-byte mark.

The abort decision:

c
	/* Have a little patience */
	if (memtupcount < 100)
		return false;

	abbrev_distinct = estimateHyperLogLog(&sss->abbr_card);
	key_distinct = estimateHyperLogLog(&sss->full_card);

and then the test that matters:

c
	/*
	 * If the number of distinct abbreviated keys approximately matches the
	 * number of distinct authoritative original keys, that's reason enough to
	 * proceed.  We can win even with a very low cardinality set if most
	 * tie-breakers only memcmp().  This is by far the most important
	 * consideration.
	 *
	 * While comparisons that are resolved at the abbreviated key level are
	 * considerably cheaper than tie-breakers resolved with memcmp(), both of
	 * those two outcomes are so much cheaper than a full strcoll() once
	 * sorting is underway that it doesn't seem worth it to weigh abbreviated
	 * cardinality against the overall size of the set in order to more
	 * accurately model costs.  Assume that an abbreviated comparison, and an
	 * abbreviated comparison with a cheap memcmp()-based authoritative
	 * resolution are equivalent.
	 */
	if (abbrev_distinct > key_distinct * sss->prop_card)

prop_card starts at 0.20 — the abbreviation is considered worth it as long as it retains at least a fifth of the original’s distinctness. And past 10,000 tuples it decays:

c
		if (memtupcount > 10000)
			sss->prop_card *= 0.65;

because the comparison count grows faster than the linear cost of transformation.

And the punchline, which is the actual justification for the whole mechanism:

c
	/*
	 * Abort abbreviation strategy.
	 *
	 * The worst case, where all abbreviated keys are identical while all
	 * original strings differ will typically only see a regression of about
	 * 10% in execution time for small to medium sized lists of strings.
	 * Whereas on modern CPUs where cache stalls are the dominant cost, we can
	 * often expect very large improvements, particularly with sets of strings
	 * of moderately high to high abbreviated cardinality.  There is little to
	 * lose but much to gain, which our strategy reflects.
	 */

Worst case: 10% slower. Best case: much faster. That’s the bet the abbreviated-key machinery makes, and the cost model is what keeps the bet honest.

Non-C collations need strxfrm, and strxfrm is often not safe

The strxfrm() requirement is not a stylistic preference; it is a correctness one, because strxfrm() is what makes byte-order comparison equivalent to collation order. The setup code says:

c
	else
	{
		/*
		 * We use varlenafastcmp_locale except for type NAME.
		 */
		if (typid == NAMEOID)
		{
			ssup->comparator = namefastcmp_locale;
			/* Not supporting abbreviation with type NAME, for now */
			abbreviate = false;
		}
		else
			ssup->comparator = varlenafastcmp_locale;

		/*
		 * Unfortunately, it seems that abbreviation for non-C collations is
		 * broken on many common platforms; see pg_strxfrm_enabled().
		 *
		 * Even apart from the risk of broken locales, it's possible that
		 * there are platforms where the use of abbreviated keys should be
		 * disabled at compile time.  For example, macOS's strxfrm()
		 * implementation is known to not effectively concentrate a
		 * significant amount of entropy from the original string in earlier
		 * transformed blobs. ...
		 */
		if (!pg_strxfrm_enabled(locale))
			abbreviate = false;
	}

pg_strxfrm_enabled() (in src/backend/utils/adt/pg_locale.c) simply consults the collation provider:

c
pg_strxfrm_enabled(pg_locale_t locale)
{
	if (locale->collate == NULL)
		return true;

	/*
	 * locale->collate->strnxfrm is still a required method, even if it may
	 * have the wrong behavior, because the planner uses it for estimates in
	 * some cases.
	 */
	return locale->collate->strxfrm_is_safe;
}

locale->collate == NULL means the C locale, where the “transform” is the identity. So: in the C locale you get abbreviation; in most other locales you do not. That is a large, under-appreciated performance difference between LC_COLLATE=C and everything else.

The other half of the string story: caching strcoll

Even without abbreviation, the locale comparator does something clever. varstrfastcmp_locale() keeps the previous two operands in buffers:

c
	/*
	 * We're likely to be asked to compare the same strings repeatedly, and
	 * memcmp() is so much cheaper than strcoll() that it pays to try to cache
	 * comparisons, even though in general there is no reason to think that
	 * that will work out (every string datum may be unique).  Caching does
	 * not slow things down measurably when it doesn't work out, and can speed
	 * things up by rather a lot when it does.  In part, this is because the
	 * memcmp() compares data from cachelines that are needed in L1 cache even
	 * when the last comparison's result cannot be reused.
	 */
	arg1_match = true;
	if (len1 != sss->last_len1 || memcmp(sss->buf1, a1p, len1) != 0)
	{
		arg1_match = false;
		memcpy(sss->buf1, a1p, len1);
		sss->buf1[len1] = '\0';
		sss->last_len1 = len1;
	}

	/*
	 * If we're comparing the same two strings as last time, we can return the
	 * same answer without calling strcoll() again.  This is more likely than
	 * it seems (at least with moderate to low cardinality sets), because
	 * quicksort compares the same pivot against many values.
	 */
	if (len2 != sss->last_len2 || memcmp(sss->buf2, a2p, len2) != 0)
	{
		memcpy(sss->buf2, a2p, len2);
		sss->buf2[len2] = '\0';
		sss->last_len2 = len2;
	}
	else if (arg1_match && !sss->cache_blob)
	{
		/* Use result cached following last actual strcoll() call */
		return sss->last_returned;
	}

	result = pg_strcoll(sss->buf1, sss->buf2, sss->locale);

The last comment in that block is the one that matters: quicksort compares the same pivot against many values. The pivot is the same string over and over, so caching it and the previous value turns most comparisons into a memcmp plus, sometimes, a cached answer.

Note also the cache is not free of correctness concerns, and the code is careful about it. cache_blob distinguishes “buf2 holds a strxfrm() blob” from “buf2 holds the original string”, because comparing a blob to an original would be nonsense. The comment explains:

To avoid somehow confusing a strxfrm() blob and an original string, constantly keep track of the variety of data that buf1 and buf2 currently contain.

The templated qsort

When abbreviation doesn’t apply, PostgreSQL uses a quicksort — but not libc’s. src/include/lib/sort_template.h is a template that generates specialized sort functions at compile time, based on the Bentley & McIlroy algorithm:

c
/*
 * Qsort routine based on J. L. Bentley and M. D. McIlroy,
 * "Engineering a sort function",
 * Software--Practice and Experience 23 (1993) 1249-1265.
 *
 * We have modified their original by adding a check for already-sorted
 * input, which seems to be a win per discussions on pgsql-hackers around
 * 2006-03-21.
 *
 * Also, we recurse on the smaller partition and iterate on the larger one,
 * which ensures we cannot recurse more than log(N) levels (since the
 * partition recursed to is surely no more than half of the input).  Bentley
 * and McIlroy explicitly rejected doing this on the grounds that it's "not
 * worth the effort", but we have seen crashes in the field due to stack
 * overrun, so that judgment seems wrong.
 */

The template is instantiated twice in tuplesort.c:

c
/*
 * Special versions of qsort just for SortTuple objects.  qsort_tuple() sorts
 * any variant of SortTuples, using the appropriate comparetup function.
 * qsort_ssup() is specialized for the case where the comparetup function
 * reduces to ApplySortComparator(), that is single-key MinimalTuple sorts
 * and Datum sorts.
 */

#define ST_SORT qsort_tuple
#define ST_ELEMENT_TYPE SortTuple
#define ST_COMPARE_RUNTIME_POINTER
#define ST_COMPARE_ARG_TYPE Tuplesortstate
#define ST_CHECK_FOR_INTERRUPTS
#define ST_SCOPE static
#define ST_DECLARE
#define ST_DEFINE
#include "lib/sort_template.h"

#define ST_SORT qsort_ssup
#define ST_ELEMENT_TYPE SortTuple
#define ST_COMPARE(a, b, ssup) \
	ApplySortComparator((a)->datum1, (a)->isnull1, \
						(b)->datum1, (b)->isnull1, (ssup))
#define ST_COMPARE_ARG_TYPE SortSupportData
#define ST_CHECK_FOR_INTERRUPTS
#define ST_SCOPE static
#define ST_DEFINE
#include "lib/sort_template.h"

Two instantiations, and the difference matters. qsort_tuple takes a function pointer, so every comparison is an indirect call. qsort_ssup inlines ApplySortComparator directly into the sort loop, so a single-key sort on a Datum compiles down to a compare of two integers plus a couple of branches. The template’s own header notes the caveat:

NB: If the comparator function is inlined, some compilers may produce worse code with the optimized comparison routines in common/int.h than with code with the following form:
    if (a < b)
        return -1;
    if (a > b)
        return 1;
    return 0;

Three things in the generated sort are worth pulling out.

The already-sorted fast path:

c
	presorted = 1;
	for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
		 pm += ST_POINTER_STEP)
	{
		DO_CHECK_FOR_INTERRUPTS();
		if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
		{
			presorted = 0;
			break;
		}
	}
	if (presorted)
		return;

One linear pass, n-1 comparisons, and if the input is already ordered you are done. n log n becomes n. This pays off constantly: the sorter produces sorted runs, index scans produce sorted output, and ORDER BY on a already-sorted column is a single scan.

The median-of-three pivot, done properly for large inputs:

c
	pm = a + (n / 2) * ST_POINTER_STEP;
	if (n > 7)
	{
		pl = a;
		pn = a + (n - 1) * ST_POINTER_STEP;
		if (n > 40)
		{
			size_t		d = (n / 8) * ST_POINTER_STEP;

			pl = DO_MED3(pl, pl + d, pl + 2 * d);
			pm = DO_MED3(pm - d, pm, pm + d);
			pn = DO_MED3(pn - 2 * d, pn - d, pn);
		}
		pm = DO_MED3(pl, pm, pn);
	}
	DO_SWAP(a, pm);

For n > 40 it takes a ninther (median of three medians) at the first, middle and last eighths of the array, and then the median of those three. This is the classic defence against adversarially ordered input — the “median-of-3 killer” sequence that turns quicksort into O(n^2) — and it costs nothing in the common case.

Interrupt checks. ST_CHECK_FOR_INTERRUPTS puts a CHECK_FOR_INTERRUPTS() into the partition loop, so a Ctrl-C during a multi-second sort is responsive rather than being deferred to the end of the sort. Both instantiations define it.

The radix sort (new in 20devel)

Commit ef3c3cf6d02 (“Perform radix sort on SortTuples with pass-by-value Datums”, John Naylor, February 2026) added something the sorter has never had before: a non-comparison sort.

The motivation, from the commit message:

Radix sort can be much faster than quicksort, but for our purposes it is limited to sequences of unsigned bytes. To make tuples with other types amenable to this technique, several features of tuple comparison must be accounted for, i.e. the sort key must be “normalized”:
Signedness – It’s possible to modify a signed integer such that it can be compared as unsigned. …
Direction – SQL allows specification of ASC or DESC. The descending case is easily handled by taking the complement of the unsigned representation.
NULL values – NULLS FIRST and NULLS LAST must work correctly.

Normalization

normalize_datum() does the signedness and direction work:

c
static inline Datum
normalize_datum(Datum orig, SortSupport ssup)
{
	Datum		norm_datum1;

	if (ssup->comparator == ssup_datum_int64_cmp)
		norm_datum1 = orig + (Int64GetDatum(PG_INT64_MAX)) + 1;
	else if (ssup->comparator == ssup_datum_uint64_cmp)
		norm_datum1 = orig;
	else
	{
		/*
		 * Truncate to uint32. For the int32 case, we don't need to do this,
		 * but it forces the upper half of the datum to be zero regardless of
		 * sign.
		 */
		uint32		u32 = DatumGetUInt32(orig);

		if (ssup->comparator == ssup_datum_int32_cmp)
			norm_datum1 = UInt32GetDatum(u32 + ((uint32) PG_INT32_MAX) + 1);
		else
		{
			norm_datum1 = UInt32GetDatum(u32);
			Assert(ssup->comparator == ssup_datum_uint32_cmp);
		}
	}

	if (ssup->ssup_reverse)
		norm_datum1 = ~norm_datum1;

	return norm_datum1;
}

For int64: add INT64_MAX + 1, which maps [-2^63, 2^63-1] onto [0, 2^64-1] while preserving order. For int32: the same trick in 32 bits. For DESC: complement every bit, which reverses unsigned order.

This is the “signedness” bullet from the commit message, done exactly as described.

The permutation

The core of the radix sort is radix_sort_recursive(). It counts byte occurrences, computes partition offsets, then permutes the array in place:

c
	/*
	 * Swap tuples to correct partition.
	 *
	 * In traditional American flag sort, a swap sends the current element to
	 * the correct partition, but the array pointer only advances if the
	 * partner of the swap happens to be an element that belongs in the
	 * current partition. That only requires one pass through the array, but
	 * the disadvantage is we don't know if the pointer can advance until the
	 * swap completes. Here lies the most interesting innovation from the
	 * upstream ska_byte_sort: After initiating the swap, we immediately
	 * proceed to the next element. This makes better use of CPU pipelining,
	 * but also means that we will often need multiple iterations of this
	 * loop. ska_byte_sort() maintains a separate list of which partitions
	 * haven't finished, which is updated every loop iteration. Here we simply
	 * check each partition during every iteration.
	 *
	 * If we started with a single partition, there is nothing to do. If a
	 * previous loop iteration results in only one partition that hasn't been
	 * counted as sorted, we know it's actually sorted and can exit the loop.
	 */
	num_remaining = num_partitions;
	while (num_remaining > 1)
	{
		/* start the count over */
		num_remaining = num_partitions;

		for (int i = 0; i < num_partitions; i++)
		{
			uint8		idx = remaining_partitions[i];

			for (SortTuple *st = begin + partitions[idx].offset;
				 st < begin + partitions[idx].next_offset;
				 st++)
			{
				size_t		offset = partitions[st->curbyte].offset++;
				SortTuple	tmp;

				/* swap current tuple with destination position */
				Assert(offset < n_elems);
				tmp = *st;
				*st = begin[offset];
				begin[offset] = tmp;

				CHECK_FOR_INTERRUPTS();
			};

			/* Is this partition sorted? */
			if (partitions[idx].offset == partitions[idx].next_offset)
				num_remaining--;
		}
	}

Note that the byte for the current pass is stashed in st->curbyte during the counting pass, so the permutation doesn’t have to recompute it. And note the structure of the loop: it doesn’t advance a single pointer through the array; it instead walks each partition’s target range and swaps elements into place, re-checking which partitions are complete on each sweep.

Skipping common prefix bytes

If all values share the same byte at the current level, there is no point sorting on it. The code detects this and jumps ahead:

c
	if (num_partitions == 1)
	{
		/*
		 * There is only one distinct byte at the current level. It can happen
		 * that some subsequent bytes are also the same for all input values,
		 * such as the upper bytes of small integers. To skip unproductive
		 * passes for that case, we compute the level where the input has more
		 * than one distinct byte, so that the next recursion can start there.
		 */
		if (common_upper_bits == 0)
			next_level = sizeof(Datum);
		else
		{
			int			diffpos;

			/*
			 * The upper bits of common_upper_bits are zero where all datums
			 * have the same bits.
			 */
			diffpos = pg_leftmost_one_pos64(DatumGetUInt64(common_upper_bits));
			next_level = sizeof(Datum) - 1 - (diffpos / BITS_PER_BYTE);
		}
	}

common_upper_bits is accumulated during the counting pass as the OR of ref_datum ^ this_datum over all elements — the set of bit positions where values differ. If it’s zero, every value is identical and the sort is finished. Otherwise the highest differing byte tells you where to resume.

This matters enormously in practice: sorting a million int4 values, the top four bytes are zero for all of them, and you skip straight to the interesting bytes.

NULL partitioning

NULLs are handled before the radix sort, by partitioning the array by nullness. The partition uses a branchless cyclic permutation:

c
	/*
	 * If we have more than one tuple left after the quick check, partition
	 * the remainder using branchless cyclic permutation, based on
	 * https://orlp.net/blog/branchless-lomuto-partitioning/
	 */
	Assert(n > 0);
	if (d1 < n - 1)
	{
		size_t		i = d1,
					j = d1;
		SortTuple	tmp = data[d1]; /* create gap at front */

		while (j < n - 1)
		{
			/* gap is at j, move i's element to gap */
			data[j] = data[i];
			/* advance j to the first unknown element */
			j += 1;
			/* move the first unknown element back to i */
			data[i] = data[j];
			/* advance i if this element belongs in the left partition */
			i += (data[i].isnull1 == nulls_first);

			CHECK_FOR_INTERRUPTS();
		}

		/* place gap between left and right partitions */
		data[j] = data[i];
		/* restore the saved element */
		data[i] = tmp;
		/* assign it to the correct partition */
		i += (data[i].isnull1 == nulls_first);

		/* d1 is now the number of elements in the left partition */
		d1 = i;
	}

The i += (data[i].isnull1 == nulls_first) is the branchless part: the increment is a conditional move, not a branch. Nulls are the minority case in almost every real query, and a predictable branch would be cheaper… but a mispredicted branch is catastrophic, and this is a case where the branch outcome is genuinely unpredictable.

Before the branchless part there’s a linear scan for the common case:

c
	/*
	 * Find the first NOT NULL if NULLS FIRST, or first NULL if NULLS LAST.
	 * This also serves as a quick check for the common case where all tuples
	 * are NOT NULL in the first sort key with the default order ASC NULLS
	 * LAST.
	 */
	while (d1 < n && data[d1].isnull1 == nulls_first)
	{
		d1++;
		CHECK_FOR_INTERRUPTS();
	}

With the default ASC NULLS LAST, nulls_first is false, so this loop advances past all the non-null tuples at the front — which is all of them, in the overwhelmingly common case. The whole partition is then a no-op.

When does the radix sort get used?

The gate is in tuplesort_sort_memtuples():

c
	if (state->memtupcount > 1)
	{
		/*
		 * Do we have the leading column's value or abbreviation in datum1?
		 */
		if (state->base.haveDatum1 && state->base.sortKeys)
		{
			SortSupport ssup = &state->base.sortKeys[0];

			/* Does it compare as an integer? */
			if (state->memtupcount >= QSORT_THRESHOLD &&
				(ssup->comparator == ssup_datum_uint64_cmp ||
				 ssup->comparator == ssup_datum_int64_cmp ||
				 ssup->comparator == ssup_datum_uint32_cmp ||
				 ssup->comparator == ssup_datum_int32_cmp))
			{
				radix_sort_tuple(state->memtuples,
								 state->memtupcount,
								 state);
				verify_memtuples_sorted(state);
				return;
			}
		}

		/* Can we use the single-key sort function? */
		if (state->base.onlyKey != NULL)
		{
			qsort_ssup(state->memtuples, state->memtupcount,
					   state->base.onlyKey);
		}
		else
		{
			qsort_tuple(state->memtuples,
						state->memtupcount,
						state->base.comparetup,
						state);
		}
	}

Three conditions:

The variant maintains datum1 (haveDatum1).
There are at least QSORT_THRESHOLD tuples:

c
/*
 * Threshold below which qsort_tuple() is generally faster than a radix sort.
 */
#define QSORT_THRESHOLD 40

The leading key’s comparator is one of four specific functions: ssup_datum_uint64_cmp, ssup_datum_int64_cmp, ssup_datum_uint32_cmp, ssup_datum_int32_cmp. Not “any comparator that happens to be an integer compare” — literally one of these four function pointers, because normalize_datum() has to know which normalization to apply.

That third condition is the interesting restriction. It means the radix sort applies to:

int2, int4, date — whose opclasses install ssup_datum_int32_cmp;
int8, timestamp — ssup_datum_int64_cmp;
oid — ssup_datum_uint32_cmp;
uuid, macaddr, inet, bytea — whose opclasses abbreviate, and so install ssup_datum_uint64_cmp as the abbreviated comparator;
and, importantly, abbreviated text keys, because the abbreviation machinery sets the comparator to ssup_datum_uint64_cmp:

c
		if (abbreviate)
		{
			sss->prop_card = 0.20;
			initHyperLogLog(&sss->abbr_card, 10);
			initHyperLogLog(&sss->full_card, 10);
			ssup->abbrev_full_comparator = ssup->comparator;
			ssup->comparator = ssup_datum_uint64_cmp;
			ssup->abbrev_converter = varstr_abbrev_convert;
			ssup->abbrev_abort = varstr_abbrev_abort;
		}

So the two technologies compose: abbreviated text keys become eight-byte unsigned integers, and those integers are exactly the kind of thing a radix sort wants.

Note also that the radix sort only sorts by the first key. When all bytes of the first key are exhausted, the code falls back to the tiebreak comparator:

c
			else if (state->base.onlyKey == NULL)
			{
				/*
				 * We've finished radix sort on all bytes of the pass-by-value
				 * datum (possibly abbreviated), now sort using the tiebreak
				 * comparator.
				 */
				qsort_tuple(partition_begin,
							num_elements,
							state->base.comparetup_tiebreak,
							state);
			}

And a partition smaller than the threshold is sorted with plain qsort instead of recursing.

The presorted fast path, again

The radix sort has its own presorted check, applied to the not-null partition:

c
	else
	{
		bool		presorted = true;

		for (SortTuple *st = not_null_start + 1;
			 st < not_null_start + not_null_count;
			 st++)
		{
			if (COMPARETUP(state, st - 1, st) > 0)
			{
				presorted = false;
				break;
			}

			CHECK_FOR_INTERRUPTS();
		}

		if (presorted)
			return;
		else
		{
			radix_sort_recursive(not_null_start,
								 not_null_count,
								 0,
								 state);
		}
	}

Interesting: this check uses the full comparator, not the normalized one, so it correctly handles DESC and NULL ordering. If the input is already sorted, it returns without doing anything.

Note this is a linear scan over the whole array. If the data is not presorted, you pay one extra pass of comparisons before the radix sort — but since the radix sort is not comparison-based, that pass is the only comparison-based work in the entire sort, and it’s n-1 comparisons of one integer each.

The bounded heap: ORDER BY … LIMIT is a different algorithm

A LIMIT query does not need a sort. It needs the k smallest elements. PostgreSQL knows this, and tuplesort_set_bound() takes a hint:

c
/*
 * tuplesort_set_bound
 *
 *	Advise tuplesort that at most the first N result tuples are required.
 *
 * Must be called before inserting any tuples. ...
 *
 * This is a hint only. The tuplesort may still return more tuples than
 * requested.  Parallel leader tuplesorts will always ignore the hint.
 */
void
tuplesort_set_bound(Tuplesortstate *state, int64 bound)

And it disables abbreviation, because for a bounded sort it doesn’t pay:

c
	/*
	 * Bounded sorts are not an effective target for abbreviated key
	 * optimization.  Disable by setting state to be consistent with no
	 * abbreviation support.
	 */
	state->base.sortKeys->abbrev_converter = NULL;
	if (state->base.sortKeys->abbrev_full_comparator)
		state->base.sortKeys->comparator = state->base.sortKeys->abbrev_full_comparator;

The mechanism is a max-heap of size bound, kept in the sort array itself. The transition happens in tuplesort_puttuple_common():

c
			/*
			 * Check if it's time to switch over to a bounded heapsort. We do
			 * so if the input tuple count exceeds twice the desired tuple
			 * count (this is a heuristic for where heapsort becomes cheaper
			 * than a quicksort), or if we've just filled workMem and have
			 * enough tuples to meet the bound.
			 *
			 * Note that once we enter TSS_BOUNDED state we will always try to
			 * complete the sort that way.  In the worst case, if later input
			 * tuples are larger than earlier ones, this might cause us to
			 * exceed workMem significantly.
			 */
			if (state->bounded &&
				(state->memtupcount > state->bound * 2 ||
				 (state->memtupcount > state->bound && LACKMEM(state))))
			{
				if (trace_sort)
					elog(LOG, "switching to bounded heapsort at %d tuples: %s",
						 state->memtupcount,
						 pg_rusage_show(&state->ru_start));
				make_bounded_heap(state);
				MemoryContextSwitchTo(oldcontext);
				return;
			}

Once in TSS_BOUNDED, each new tuple is compared against the root of the heap — which holds the current worst of the best bound tuples — and discarded if it’s not better:

c
		case TSS_BOUNDED:

			/*
			 * We don't want to grow the array here, so check whether the new
			 * tuple can be discarded before putting it in.  This should be a
			 * good speed optimization, too, since when there are many more
			 * input tuples than the bound, most input tuples can be discarded
			 * with just this one comparison.  Note that because we currently
			 * have the sort direction reversed, we must check for <= not >=.
			 */
			if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
			{
				/* new tuple <= top of the heap, so we can discard it */
				free_sort_tuple(state, tuple);
				CHECK_FOR_INTERRUPTS();
			}
			else
			{
				/* discard top of heap, replacing it with the new tuple */
				free_sort_tuple(state, &state->memtuples[0]);
				tuplesort_heap_replace_top(state, tuple);
			}
			break;

One comparison per input tuple. That is the whole point. ORDER BY x LIMIT 10 over a million rows does a million comparisons, not twenty million (n log n), and the memory footprint is bound tuples, not n.

The direction is reversed so that the largest of the retained tuples sits at the root, which is the one you can throw away. make_bounded_heap() does the flip:

c
/*
 * Convert the existing unordered array of SortTuples to a bounded heap,
 * discarding all but the smallest "state->bound" tuples.
 *
 * When working with a bounded heap, we want to keep the largest entry
 * at the root (array entry zero), instead of the smallest as in the normal
 * sort case.  This allows us to discard the largest entry cheaply.
 * Therefore, we temporarily reverse the sort direction.
 */
static void
make_bounded_heap(Tuplesortstate *state)

and reversedirection() flips both the sort order and the NULL order:

c
static void
reversedirection(Tuplesortstate *state)
{
	SortSupport sortKey = state->base.sortKeys;
	int			nkey;

	for (nkey = 0; nkey < state->base.nKeys; nkey++, sortKey++)
	{
		sortKey->ssup_reverse = !sortKey->ssup_reverse;
		sortKey->ssup_nulls_first = !sortKey->ssup_nulls_first;
	}
}

Finally, sort_bounded_heap() unheapifies in place:

c
	/*
	 * We can unheapify in place because each delete-top call will remove the
	 * largest entry, which we can promptly store in the newly freed slot at
	 * the end.  Once we're down to a single-entry heap, we're done.
	 */
	while (state->memtupcount > 1)
	{
		SortTuple	stup = state->memtuples[0];

		/* this sifts-up the next-largest entry and decreases memtupcount */
		tuplesort_heap_delete_top(state);
		state->memtuples[state->memtupcount] = stup;
	}

The heap pops in descending order, and each popped tuple is written into the slot just vacated, so the final array is sorted ascending with no extra memory.

Where it’s used. nodeSort.c passes the bound when the planner has decided the sort is bounded:

c
		if (node->bounded)
			tuplesortopts |= TUPLESORT_ALLOWBOUNDED;
		...
		if (node->bounded)
			tuplesort_set_bound(tuplesortstate, node->bound);

and nodeIncrementalSort.c uses it for the prefix-key groups:

c
	/*
	 * If the current node has a bound, then it's reasonably likely that a
	 * large prefix key group will benefit from bounded sort, so configure the
	 * tuplesort to allow for that optimization.
	 */
	if (node->bounded)
	{
		tuplesort_set_bound(node->prefixsort_state,
							node->bound - node->bound_Done);
	}

Note that TUPLESORT_ALLOWBOUNDED is not the default — the flag has to be set explicitly, because bounded sorts use a different memory context strategy (see below).

The external merge path

When the tuple array outgrows work_mem, the sort becomes an external sort. The file header comment explains the shape of it:

We use a balanced k-way merge. Before PostgreSQL 15, we used the polyphase merge algorithm (Knuth’s Algorithm 5.4.2D), but with modern hardware, a straightforward balanced merge is better. Knuth is assuming that tape drives are expensive beasts, and in particular that there will always be many more runs than tape drives. The polyphase merge algorithm was good at keeping all the tape drives busy, but in our implementation a “tape drive” doesn’t cost much more than a few Kb of memory buffers, so we can afford to have lots of them.

Spilling to tape

inittapes() decides how many tapes to use:

c
	if (mergeruns)
	{
		/* Compute number of input tapes to use when merging */
		state->maxTapes = tuplesort_merge_order(state->allowedMem);
	}
	else
	{
		/* Workers can sometimes produce single run, output without merge */
		Assert(WORKER(state));
		state->maxTapes = MINORDER;
	}

and tuplesort_merge_order() is where the memory-versus-tape-count tradeoff gets made:

c
	mOrder = allowedMem /
		(2 * TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE);

	/*
	 * Even in minimum memory, use at least a MINORDER merge.  On the other
	 * hand, even when we have lots of memory, do not use more than a MAXORDER
	 * merge.  Tapes are pretty cheap, but they're not entirely free.  Each
	 * additional tape reduces the amount of memory available to build runs,
	 * which in turn can cause the same sort to need more runs, which makes
	 * merging slower even if it can still be done in a single pass.  Also,
	 * high order merges are quite slow due to CPU cache effects; it can be
	 * faster to pay the I/O cost of a multi-pass merge than to perform a
	 * single merge pass across many hundreds of tapes.
	 */
	mOrder = Max(mOrder, MINORDER);
	mOrder = Min(mOrder, MAXORDER);

with

c
#define MINORDER		6		/* minimum merge order */
#define MAXORDER		500		/* maximum merge order */
#define TAPE_BUFFER_OVERHEAD		BLCKSZ
#define MERGE_BUFFER_SIZE			(BLCKSZ * 32)

That comment is a gem: “high order merges are quite slow due to CPU cache effects; it can be faster to pay the I/O cost of a multi-pass merge than to perform a single merge pass across many hundreds of tapes.” The third problem (cache) reappears at the merge stage. A 500-way merge means a 500-element heap that is touched randomly on every output tuple — 500 distinct cache lines, and the heap order changes constantly. The code caps the merge order at 500 and prefers more passes over a huge fan-in.

Building the runs

dumptuples() sorts the in-memory batch and writes it to a tape:

c
	/*
	 * Sort all tuples accumulated within the allowed amount of memory for
	 * this run.
	 */
	tuplesort_sort_memtuples(state);
	...
	memtupwrite = state->memtupcount;
	for (i = 0; i < memtupwrite; i++)
	{
		SortTuple  *stup = &state->memtuples[i];

		WRITETUP(state, state->destTape, stup);
	}

	state->memtupcount = 0;

	/*
	 * Reset tuple memory.  We've freed all the tuples that we previously
	 * allocated.  It's important to avoid fragmentation when there is a stark
	 * change in the sizes of incoming tuples.  In bounded sorts,
	 * fragmentation due to AllocSetFree's bucketing by size class might be
	 * particularly bad if this step wasn't taken.
	 */
	MemoryContextReset(state->base.tuplecontext);

Each run is terminated by a zero length word (markrunend()), and the memory used by the tuples is returned to the budget:

c
	/*
	 * Now update the memory accounting to subtract the memory used by the
	 * tuple.
	 */
	FREEMEM(state, state->tupleMem);
	state->tupleMem = 0;

The merge

mergeruns() is the balanced k-way merge. The first thing it does is throw away abbreviation:

c
	if (state->base.sortKeys != NULL && state->base.sortKeys->abbrev_converter != NULL)
	{
		/*
		 * If there are multiple runs to be merged, when we go to read back
		 * tuples from disk, abbreviated keys will not have been stored, and
		 * we don't care to regenerate them.  Disable abbreviation from this
		 * point on.
		 */
		state->base.sortKeys->abbrev_converter = NULL;
		state->base.sortKeys->comparator = state->base.sortKeys->abbrev_full_comparator;

This is important. Abbreviated keys are not written to disk. The on-tape representation is the tuple itself; datum1 is recomputed on read. So a merge pass compares full keys, not abbreviated ones — the abbreviation benefit is confined to the in-memory run-building phase.

Then the merge itself, with the on-the-fly final merge:

c
			/*
			 * If there's just one run left on each input tape, then only one
			 * merge pass remains.  If we don't have to produce a materialized
			 * sorted tape, we can stop at this point and do the final merge
			 * on-the-fly.
			 */
			if ((state->base.sortopt & TUPLESORT_RANDOMACCESS) == 0
				&& state->nInputRuns <= state->nInputTapes
				&& !WORKER(state))
			{
				/* Tell logtape.c we won't be writing anymore */
				LogicalTapeSetForgetFreeSpace(state->tapeset);
				/* Initialize for the final merge pass */
				beginmerge(state);
				state->status = TSS_FINALMERGE;
				return;
			}

TSS_FINALMERGE is the state where the merge heap stays live and tuples are pulled out of it one at a time as the caller requests them. The caller path is in tuplesort_gettuple_common():

c
		case TSS_FINALMERGE:
			Assert(forward);
			/* We are managing memory ourselves, with the slab allocator. */
			Assert(state->slabAllocatorUsed);
			...
			if (state->memtupcount > 0)
			{
				int			srcTapeIndex = state->memtuples[0].srctape;
				LogicalTape *srcTape = state->inputTapes[srcTapeIndex];
				SortTuple	newtup;

				*stup = state->memtuples[0];
				...
				if (!mergereadnext(state, srcTape, &newtup))
				{
					/*
					 * If no more data, we've reached end of run on this tape.
					 * Remove the top node from the heap.
					 */
					tuplesort_heap_delete_top(state);
					state->nInputRuns--;
					...
					return true;
				}
				newtup.srctape = srcTapeIndex;
				tuplesort_heap_replace_top(state, &newtup);
				return true;
			}
			return false;

One tuple out of the heap, one tuple read from the tape, one heap replacement. The caller never sees the disk at all.

The slab allocator

During the merge, tuple memory is managed by hand rather than by palloc. The reason:

c
/*
 * During merge, we use a pre-allocated set of fixed-size slots to hold
 * tuples.  To avoid palloc/pfree overhead.
 *
 * Merge doesn't require a lot of memory, so we can afford to waste some,
 * by using gratuitously-sized slots.  If a tuple is larger than 1 kB, the
 * palloc() overhead is not significant anymore.
 *
 * 'nextfree' is valid when this chunk is in the free list.  When in use, the
 * slot holds a tuple.
 */
#define SLAB_SLOT_SIZE 1024

typedef union SlabSlot
{
	union SlabSlot *nextfree;
	char		buffer[SLAB_SLOT_SIZE];
} SlabSlot;

One kilobyte per slot, even though the median tuple might be fifty bytes. The waste is deliberate and bounded: a merge only keeps nTapes + 1 tuples live at a time, so the waste is at most 500 KB. In exchange, there is no palloc/pfree churn at all during the hottest loop in the sort.

The allocation is one big block with a free list threaded through it:

c
static void
init_slab_allocator(Tuplesortstate *state, int numSlots)
{
	if (numSlots > 0)
	{
		char	   *p;
		int			i;

		state->slabMemoryBegin = palloc(numSlots * SLAB_SLOT_SIZE);
		state->slabMemoryEnd = state->slabMemoryBegin +
			numSlots * SLAB_SLOT_SIZE;
		state->slabFreeHead = (SlabSlot *) state->slabMemoryBegin;
		USEMEM(state, numSlots * SLAB_SLOT_SIZE);

		p = state->slabMemoryBegin;
		for (i = 0; i < numSlots - 1; i++)
		{
			((SlabSlot *) p)->nextfree = (SlabSlot *) (p + SLAB_SLOT_SIZE);
			p += SLAB_SLOT_SIZE;
		}
		((SlabSlot *) p)->nextfree = NULL;
	}
	...
}

and tuples larger than a slot fall back to palloc:

c
	if (tuplen > SLAB_SLOT_SIZE || !state->slabFreeHead)
		return MemoryContextAlloc(state->base.sortcontext, tuplen);

The IS_SLAB_SLOT pointer-range check distinguishes the two cases at free time, which is why the arena bounds are kept in the state struct.

Caveats

Several things are worth knowing before you draw conclusions from this.

Abbreviation is mostly a C-locale feature. As established above, non-C collations disable abbreviation unless the collation provider declares strxfrm() safe. On a system with LC_COLLATE=en_US.UTF-8, text sorts do not get abbreviated keys, and therefore do not get the radix sort either (since the radix sort requires the uint64 comparator that abbreviation installs). The C locale is dramatically faster for ORDER BY on text.

The radix sort requires one of four exact comparator functions. Not “compares like an integer” — one of ssup_datum_uint64_cmp, ssup_datum_int64_cmp, ssup_datum_uint32_cmp, ssup_datum_int32_cmp, by pointer identity. A type with an “integer-like” comparator that isn’t one of those four gets no radix sort.

The radix sort sorts by the first key only. Ties fall back to qsort with the tiebreak comparator, so a sort with many duplicate leading keys degrades toward a comparison sort.

Abbreviation is disabled for bounded sorts and disabled during merges. Both are deliberate; neither is a bug.

work_mem is per sort operation, per parallel worker. A parallel sort with four workers gets four separate budgets. And work_mem doesn’t bound the total: the initial array plus all the tuples plus the merge buffers add up. The merge buffer allocation is separate:

c
	state->tape_buffer_mem = state->availMem;
	USEMEM(state, state->tape_buffer_mem);

The bounded heap is a hint, not a guarantee. tuplesort_set_bound() says “at most the first N result tuples are required”, and the sort “may still return more tuples than requested”. The planner sets it, and the executor honours it, but the API is deliberately loose — and the parallel leader ignores it entirely.

Bounded sorts change the memory context strategy. The tuple context is a regular AllocSet for bounded sorts and a bump allocator otherwise:

c
	/*
	 * ... For bounded sorts, tuples may be pfreed in any
	 * order, so we use a regular aset.c context so that it can make use of
	 * free'd memory.  When the sort is not bounded, we make use of a bump.c
	 * context as this keeps allocations more compact with less wastage.
	 * Allocations are also slightly more CPU efficient.
	 */
	if (TupleSortUseBumpTupleCxt(state->base.sortopt))
		state->base.tuplecontext = BumpContextCreate(state->base.sortcontext,
													 "Caller tuples",
													 ALLOCSET_DEFAULT_SIZES);
	else
		state->base.tuplecontext = AllocSetContextCreate(state->base.sortcontext,
														 "Caller tuples",
														 ALLOCSET_DEFAULT_SIZES);

The abbreviation cost model can be wrong. It samples at exponentially spaced intervals and uses a heuristic threshold. A pathological dataset — thousands of distinct strings sharing a long prefix, so that all abbreviated keys are identical — will be caught, but only after the sampling interval where the threshold trips. The code’s own comment puts the worst case at about a 10% regression.

What it all means in practice

ORDER BY on text is dramatically faster under LC_COLLATE=C. This is the single biggest practical takeaway. The C locale gets memcmp() comparisons, abbreviated keys, and (via the abbreviation) the radix sort. Most other locales get strcoll() comparisons and a caching layer that helps but is not the same thing. If your workload sorts text and you have the option, the C locale is worth a benchmark.

ORDER BY ... LIMIT is a completely different algorithm. A million-row ORDER BY x LIMIT 10 does a million comparisons, not twenty million, and keeps ten tuples in memory. The planner only sets the bound when it’s confident; a LIMIT over a query with a WHERE clause that the planner can’t push down may not get it.

A radix sort is not a general-purpose sort. It applies to integers and to abbreviated text keys, and only above 40 elements. Everything else — numeric, date with a nonstandard comparator, collated text, tuples with an expression in the leading position — falls back to the Bentley & McIlroy quicksort.

work_mem is the knob, but it’s a blunt one. Increasing it turns an external sort into an in-memory sort, which is the single biggest win available in sorting. But it multiplies: each parallel worker gets its own budget, and each concurrent sort gets its own budget. A session running several sorts concurrently can use work_mem × workers × sorts.

The presorted fast path means already-ordered data is cheap. If the input to the sort is already in order — an index scan on the sort column, a naturally-ordered table — the sort costs n comparisons, not n log n. This is why ORDER BY on an indexed column with a matching collation is fast even without the index providing the order (it doesn’t, but the sort is cheap anyway).

The cache is the real currency. Every design decision in this subsystem that looks like a pessimization — the 1 KB slab slots, the byteswap at conversion time, the uint64 comparator restriction, the MAXORDER cap on merge fan-in — trades instructions for cache behavior. The header comment on sortsupport.h says it outright: “CPU cache miss penalties are expensive; to get good overall performance, sort infrastructure must heavily weigh cache performance.”

Abbreviation is a bet with a bounded downside. Worst case about 10% slower on small-to-medium string lists; best case substantially faster. The HyperLogLog cost model is what keeps the bet from being unbounded.