Normalized keys, radix sort and sort avoidance

How do normalized keys and (prefix, pointer) arrays make a CPU-bound sort fast, and when can the sort be avoided altogether?

Radix sort and normalized keys

Follow the chain of reasoning: I/O stopped being the limit, so comparison cost is the limit, so the target is the comparison itself.

A typed comparison of a multi-column sort key does a lot: type dispatch for each field, null checks, collation lookups for strings, and a loop that can exit at a data-dependent point. It has many branches that the CPU cannot predict, and it cannot use vector (SIMD) instructions.

A normalized key replaces all of that. Encode the whole sort key into a byte string whose memcmp order equals its semantic order (memcmp compares two byte arrays from the first byte on). The comparison becomes one branch-free, vector-friendly instruction sequence that does not know or care which types were involved. A speedup of 2 to 10 times is typical, and it is largest exactly where sorting is slowest: wide multi-column keys with strings.

The encodings that make this work are a data-format topic. In short: flip the sign bit and use big-endian byte order for integers, use a sign/magnitude transform for floats, use the bitwise complement for descending order, add a leading marker byte for NULLs, and use precomputed collation weights for text. What matters here is why a sort wants a normalized key and what it costs: an extra encoding pass over the data, plus key expansion. Expansion is harmless for fixed-width numbers but large for collated text, where a sort key can be several times the size of the string it encodes.

Radix sort

Once keys are byte strings, radix sort becomes possible. It distributes records into buckets by one byte at a time, in O(N·k) time for k key bytes, with no comparisons at all. The usual hybrid is most-significant-byte radix sort, with a comparison sort for small buckets. This is the one place here that escapes the comparison lower bound (the proof that comparison sorts need about N log N steps). The escape is legitimate, not clever: nothing is compared; the key's representation is used directly. Key normalization is what makes it possible, so the two techniques arrive together.

Sort a compact array of (prefix, pointer)

The third move is usually the biggest practical win. Sort a compact array of (key prefix, row pointer) pairs instead of the rows. Take the first 8 bytes of the normalized key plus an 8-byte pointer: 16 bytes per row, whether the row is 40 bytes or 4 KB.

This is the granularity mismatch principle in a form that is easy to miss. The unit the sort works on is a key. The unit the data is stored in is a row. The mismatch is paid as memory traffic until you separate the two.

The boundary condition. Sorting pointers means the final step is a random gather: reading the rows in the new order. In memory that is fine. If the rows are on disk or in object storage, the gather is random I/O and the optimization reverses. You must then carry the rows with the keys and pay for the wide sort. So the choice depends on where the rows live, not on the sort.

Sort avoidance: the property model, cashed in

An order is a physical property. Operators require it, provide it, preserve it or destroy it. The whole economics of sorting is bookkeeping over this.

Role	Operators
Provide order	sort; merge join (on the join key); clustered or index scan; sorted or bucketed table scan; sort-based aggregation (on the group key); merging already-sorted inputs; LSM/SSTable reads
Require order	merge join; sort-based aggregation; window functions; `ORDER BY`; streaming dedup; `LIMIT` with order; range-partitioned output
Preserve order	filter; projection; `LIMIT`; unnest (keeps the parent's order); the probe side of a hash join
Destroy order	hash aggregation; the build side of a hash join; union; any hash repartition or shuffle

Four rules make this stronger than matching column lists. The last one is the one most people never learn.

1. Prefixes are free. A sort on (a, b) also provides an order on (a). One enforcement can satisfy several requirements if they are prefix-compatible. Choosing the sort columns to maximize prefix overlap with downstream requirements is a free gain.

2. Equality predicates create constants. Under WHERE a = 5, an order on (b) satisfies a requirement for (a, b), because a is constant within the stream. Real optimizers track functional dependencies and constant columns in their property model for this reason. A model that tracks only column lists will enforce sorts it does not need.

3. A partial order needs only a segmented sort. If the input is already sorted on (a) and the requirement is (a, b), you do not need a global sort. You need to sort within each a-group. Memory falls from O(N) to O(largest group), and the operation becomes streaming: each group is sorted and emitted as it closes. For most groupings this turns a spilling sort into an in-memory one.

4. Grouping and sorting are different properties, and mixing them up over-enforces. An aggregation requires that all rows of a group be contiguous (together). It does not require that groups appear in order. ORDER BY requires order. Hash partitioning provides co-location of a group on one partition without any order. Treating "grouped" as a weaker form of "sorted" (rather than the same thing) is what lets an engine run sort-based aggregation on hash-shuffled input, and it is why a query that groups but does not order should never pay for a global sort. Hash partitioning alone puts all rows of a group on one machine; making them contiguous inside that machine takes a local step, such as a local sort or hash table. No global order is needed.

The decision rule: count the requirements that one order satisfies

One requirement: sort competes against hash on the merits and usually loses.
Two or more: sorting once beats hashing repeatedly.

Then extend the count beyond this query. A clustered layout, a bucketed table, an index or an LSM file order amortizes the same sort over every query that will ever run on the table. It is the same arithmetic with a much larger denominator, and it is the entire argument for physical design. (Searching the space of plans for the arrangement that keeps the most useful orders is the optimizer's job. What belongs here is the algebra it searches over.)

Case, resolvedConstructed case · Omar and Tarini at Shopsy

Five full sorts in one plan

Five window functions produced five full sorts of 2 billion orders, deep OFFSET pages kept getting slower, and a large sort ran at 100% CPU with an idle disk. Where it started: Sorting →

Tarini opens Omar's five-window query plan. Three of the five windows use PARTITION BY customer_id ORDER BY order_ts. She rewrites the OVER clauses so the sort columns share a prefix (customer_id, order_ts), and the engine sorts once and reuses the order for all three. Another window needs ORDER BY order_ts inside a group that is already sorted by customer_id; a segmented sort handles that inside each customer, in memory. Five sorts become two.

For the sort that was slow with an idle disk, the sort key was a collated string, and the CPU was the limit. Normalizing the key and sorting (prefix, pointer) pairs makes the working set 12.5x smaller. For the biggest ordering jobs she tells the platform team to check the splitter sample: the sorted files were being sampled from the first rows of each file, which are the oldest orders.

The paging problem is the bounded-answer lesson of set operators and keyset pagination. OFFSET 100000 forces the engine to sort or scan and then throw away 100,000 rows before the page starts, so the state grows with the offset. Keyset pagination (WHERE (order_ts, order_id) > (last_ts, last_id) ORDER BY order_ts, order_id LIMIT 50) turns the growing offset state into a simple predicate, and with an index in that order each page reads only 50 rows. An ORDER BY ... LIMIT k query needs only a heap of size k, not a full sort: state falls from O(N) to O(k).