Why Sorting Is Worth the Complexity
Most software projects trade runtime performance for development speed and code simplicity. Databases are the exception: a 10% improvement in a core operation cascades across millions of installations, making aggressive optimization worthwhile even when it complicates the code. Postgres is full of such optimizations, and one of the most impactful is SortSupport, a mechanism that accelerates sorting for common data types—often doubling performance or better. That speedup flows directly into everyday operations like ORDER BY, DISTINCT, and CREATE INDEX.
Bringing Values Closer to the Comparator
During a sort, Postgres builds small in-memory tuples representing each row. These tuples reserve space for a value the size of a native pointer (64 bits on a 64-bit machine). Simple types like booleans and integers fit entirely in that space, but larger or variable-length types do not. For those pass-by-reference types, Postgres must follow a pointer back to the heap to compare values—a fast operation, but slower than comparing data already local to the sort routine.
SortSupport solves this by storing a condensed digest of a pass-by-reference value inside the sort tuple, avoiding repeated trips to the heap. This digest, called an abbreviated key, varies by type but is designed to capture as much sort-relevant information as possible while respecting the original comparison semantics.
An abbreviated key is never allowed to produce a wrong ordering. When two keys are equal, Postgres falls back to a full comparison of the heap values to guarantee correctness—a step called an authoritative comparison.
Abbreviated Keys in Practice
Some types are easy to abbreviate. UUIDs, for example, are always 128 bits—too large for a 64-bit tuple slot—but sampling the first 64 bits produces an excellent proxy for ordering. Because V4 UUIDs are essentially random, collisions are vanishingly rare, and the initial implementation of SortSupport for UUIDs roughly doubled sorting speed.
Text-like types (text, varchar) follow a similar pattern: they pack as many leading characters as fit into the abbreviated key—complicated somewhat by locale-aware collation rules. This made operations like CREATE INDEX about three times faster. Other types are more involved. The numeric type, which supports arbitrary scale and precision, uses excess-K coding and splits its available bits into multiple sections to capture enough information to preserve ordering
Not every type required a full design effort. The macaddr type is pass-by-reference but its values are only six bytes long, so it can fit entirely into the tuple space on a 64-bit machine and partially (first four bytes) on 32-bit systems.
Inside the SortSupport Implementation
SortSupport works through an optimization called abbreviated keys. All comparisons of complex types go through a common data structure named Datum, which is pointer-sized (32 or 64 bits depending on the CPU architecture). For pass-by-value types, Datum stores the full value. For pass-by-reference types that have SortSupport enabled, it stores an abbreviated key; otherwise, it stores a pointer to the full value. The definition appears in postgres.h:
/*
* A Datum contains either a value of a pass-by-value type or a pointer
* to a value of a pass-by-reference type. Therefore, we require:
*
* sizeof(Datum) == sizeof(void *) == 4 or 8
*/
typedef uintptr_t Datum;
#define SIZEOF_DATUM SIZEOF_VOID_P
How UUID Abbreviated Keys Are Built
The uuid type provides a straightforward example of SortSupport in action. In Postgres, UUIDs are physically stored as the struct pg_uuid_t, defined in uuid.h:
/* uuid size in bytes */
#define UUID_LEN 16
typedef struct pg_uuid_t
{
unsigned char data[UUID_LEN];
} pg_uuid_t;
Although UUIDs are often displayed in string form (e.g., 123e4567-e89b-12d3-a456-426655440000), pg_uuid_t stores only the raw 16 bytes, avoiding any wasted space.
A SortSupport implementation defines a conversion function that takes the original value and emits a datum containing an abbreviated key. For UUIDs, that function is in uuid.c:
static Datum
uuid_abbrev_convert(Datum original, SortSupport ssup)
{
pg_uuid_t *authoritative = DatumGetUUIDP(original);
Datum res;
memcpy(&res, authoritative->data, sizeof(Datum));
...
/*
* Byteswap on little-endian machines.
*
* This is needed so that uuid_cmp_abbrev() (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);
return res;
}
The memcpy call copies the 4 or 8 most significant bytes from the pg_uuid_t into a result. This truncated representation is sufficient for most comparisons, although not all.
DatumBigEndianToNative supports an important optimization. Rather than comparing abbreviated keys byte-by-byte with memcmp, which is perfectly functional, Postgres treats the datums as integers. CPUs are highly optimized for integer comparison, so converting the byte sequence to a native integer can make comparisons measurably faster. This integer-based comparison is visible in the UUID abbreviated-key comparator:
static int
uuid_cmp_abbrev(Datum x, Datum y, SortSupport ssup)
{
if (x > y)
return 1;
else if (x == y)
return 0;
else
return -1;
}
Treating a byte sequence as an integer introduces an endianness concern. Some architectures store multi-byte values with the most significant byte first (big-endian); others, including Intel x86 and ARM’s default mode, use the opposite order (little-endian). If the big-endian output of the memcpy were used unchanged on a little-endian machine, the resulting integer would be incorrect. A byteswap corrects the order:
The definition of DatumBigEndianToNative in pg_bswap.h shows it is a no-op on big-endian systems and a byteswap of the appropriate size otherwise:
#ifdef WORDS_BIGENDIAN
#define DatumBigEndianToNative(x) (x)
#else
#if SIZEOF_DATUM == 8
#define DatumBigEndianToNative(x) pg_bswap64(x)
#else
#define DatumBigEndianToNative(x) pg_bswap32(x)
#endif
#endif
Aborting Conversion with HyperLogLog
Abbreviated keys carry a risk for data sets with very low cardinality, i.e., many duplicate values. If abbreviated keys frequently show equality, Postgres must fall back to the authoritative, full-value comparator more often. In that scenario, SortSupport would add overhead rather than remove it.
To prevent a performance regression, SortSupport includes a mechanism to abort abbreviated-key conversion. When Postgres determines the data set’s cardinality is below a certain threshold, it stops abbreviating, reverts keys already converted, and disables further abbreviation for that sort operation.
Cardinality is estimated using HyperLogLog, a memory-efficient algorithm for approximating the count of distinct values in a data set. The conversion routine feeds new values into the HyperLogLog state while an abort is still possible:
uss->input_count += 1;
if (uss->estimating)
{
uint32 tmp;
#if SIZEOF_DATUM == 8
tmp = (uint32) res ^ (uint32) ((uint64) res >> 32);
#else
tmp = (uint32) res;
#endif
addHyperLogLog(&uss->abbr_card, DatumGetUInt32(hash_uint32(tmp)));
}
The decision to abort appears in uuid.c:
static bool
uuid_abbrev_abort(int memtupcount, SortSupport ssup)
{
...
abbr_card = estimateHyperLogLog(&uss->abbr_card);
/*
* If we have >100k distinct values, then even if we were
* sorting many billion rows we'd likely still break even,
* and the penalty of undoing that many rows of abbrevs would
* probably not be worth it. Stop even counting at that point.
*/
if (abbr_card > 100000.0)
{
uss->estimating = false;
return false;
}
/*
* Target minimum cardinality is 1 per ~2k of non-null inputs.
* 0.5 row fudge factor allows us to abort earlier on genuinely
* pathological data where we've had exactly one abbreviated
* value in the first 2k (non-null) rows.
*/
if (abbr_card < uss->input_count / 2000.0 + 0.5)
{
return true;
}
...
}
Aborting also handles cases where the data set is poorly suited to the abbreviated-key format. For instance, consider a million UUIDs sharing a common prefix in their first eight bytes but differing in the last eight. Such patterns are unusual in practice, so aborts rarely occur for UUIDs; they are more realistic for variable-length string types, where users store free-form content.
Sort Tuples and Their Data Structures
Postgres sorts in-memory structures known as sort tuples. Each holds a reference to the actual “true” tuple, plus a datum and an isnull flag that records whether the first field is NULL (NULLs have distinct sorting semantics). The names datum1 and isnull1 reflect that they contain only a single field’s information; a multi-column sort must fall back to comparing later fields when the first is equal. The definition is in tuplesort.c:
/*
* The objects we actually sort are SortTuple structs. These contain
* a pointer to the tuple proper (might be a MinimalTuple or IndexTuple),
* which is a separate palloc chunk --- we assume it is just one chunk and
* can be freed by a simple pfree() (except during merge, when we use a
* simple slab allocator). SortTuples also contain the tuple's first key
* column in Datum/nullflag format, and an index integer.
*/
typedef struct
{
void *tuple; /* the tuple itself */
Datum datum1; /* value of first key column */
bool isnull1; /* is first key column NULL? */
int tupindex; /* see notes above */
} SortTuple;
Sort tuples may point to a heap tuple, which has several possible struct layouts. The variant used by the sort algorithm is HeapTupleHeaderData, from htup_details.h:
struct HeapTupleHeaderData
{
union
{
HeapTupleFields t_heap;
DatumTupleFields t_datum;
} t_choice;
ItemPointerData t_ctid; /* current TID of this or newer tuple (or a
* speculative insertion token) */
...
}
Heap tuple structure is intricate and beyond this article’s scope, but note the ItemPointerData field. This struct encodes the precise location of the data within the heap, as defined in itemptr.h:
/*
* ItemPointer:
*
* This is a pointer to an item within a disk page of a known file
* (for example, a cross-link from an index to its parent table).
* blkid tells us which block, posid tells us which entry in the linp
* (ItemIdData) array we want.
*/
typedef struct ItemPointerData
{
BlockIdData ip_blkid;
OffsetNumber ip_posid;
}
Putting the Comparator to Work
The abbreviated-key comparison algorithm is duplicated across Postgres’ source for different sort operations. The version used for heap-based sorting is comparetup_heap in tuplesort.c; it runs, for instance, when an ORDER BY references a column without a supporting index:
static int
comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
{
SortSupport sortKey = state->sortKeys;
HeapTupleData ltup;
HeapTupleData rtup;
TupleDesc tupDesc;
int nkey;
int32 compare;
AttrNumber attno;
Datum datum1,
datum2;
bool isnull1,
isnull2;
/* Compare the leading sort key */
compare = ApplySortComparator(a->datum1, a->isnull1,
b->datum1, b->isnull1,
sortKey);
if (compare != 0)
return compare;
ApplySortComparator produces a result consistent with C’s strcmp semantics: -1 for a < b, 0 for equality, and 1 for a > b. It compares abbreviated keys where available and applies NULL-specific ordering rules. If the comparison result is non-zero, the algorithm returns immediately. Otherwise, it checks whether abbreviated keys were involved and, if so, runs the authoritative comparison against the full values:
if (sortKey->abbrev_converter)
{
attno = sortKey->ssup_attno;
datum1 = heap_getattr(<up, attno, tupDesc, &isnull1);
datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
compare = ApplySortAbbrevFullComparator(datum1, isnull1,
datum2, isnull2,
sortKey);
if (compare != 0)
return compare;
}
Once again, a non-zero result ends the comparison. If the authoritative comparison confirms equality, the algorithm moves on to any additional sort fields for multi-column sorts:
...
sortKey++;
for (nkey = 1; nkey < state->nKeys; nkey++, sortKey++)
{
attno = sortKey->ssup_attno;
datum1 = heap_getattr(<up, attno, tupDesc, &isnull1);
datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
compare = ApplySortComparator(datum1, isnull1,
datum2, isnull2,
sortKey);
if (compare != 0)
return compare;
}
return 0;
}
If abbreviated keys, full values, and all additional fields are identical, the routine returns 0 in classic libc fashion, indicating the two tuples are fully equal.
Optimization Worth Reusing
SortSupport exemplifies the kind of low-level tuning that most application developers would rarely consider, but that pays off enormously inside a heavily leveraged system like a relational database. As more type implementations adopt SortSupport, the tens of thousands of users who upgrade receive immediate, automatic speedups in common operations such as DISTINCT, ORDER BY, and CREATE INDEX.
Credit belongs to Peter Geoghegan for early exploration and implementations for UUID and a generalized SortSupport system for variable-length string types; Robert Haas and Tom Lane for adding the infrastructure; and Andrew Gierth for a difficult numeric implementation.
