← Notes

Radix sort for integer ORDER BY

Setup

The benchmark is bench_large_sort: 50,000 rows, 10 iterations of a multi-column ORDER BY. Measured as wall-clock latency through the PostgreSQL wire protocol.

CREATE TABLE events (
    id INT, user_id INT, score INT,
    amount NUMERIC(10,2), label TEXT, ts TIMESTAMP
);
-- 50,000 rows inserted

SELECT * FROM events ORDER BY score DESC, id ASC;
-- repeated 10 times

Problem

Sorting 50,000 rows by integer columns using a comparison-based sort (qsort) requires approximately N×log2(N) ≈ 780,000 comparisons. Each comparison invokes a function pointer, decodes the column type, and performs the actual comparison. For multi-column sorts, this multiplies by the number of sort keys.

Cause

The generic sort path used qsort with a comparator that dispatched on column type for every comparison. For integer columns, the type dispatch and function-pointer overhead dominated the actual comparison cost. The comparator also handled NULLs, multi-column tiebreaking, and ASC/DESC direction on every call.

Fix

Three radix sort variants in plan.c:

• radix_sort_u32 — 4 passes of 8-bit radix for 32-bit integer keys (INT, SMALLINT).
• radix_sort_u64 — 8 passes for 64-bit integer keys (BIGINT).
• radix_sort_f64 — 8 passes with IEEE 754 bit-flip (sign bit inversion + conditional complement) so that the numeric order of doubles matches the bitwise order.

For multi-column ORDER BY, the sort applies radix sort on the least-significant key first and works toward the most-significant key, exploiting radix sort’s stability. Each pass is O(N) with a 256-bucket histogram, making the total cost O(N×k) where k is the number of bytes in the key.

DESC order is handled by inverting the key bits before sorting. NULL handling is done by mapping NULLs to the highest or lowest key value (depending on NULLS FIRST/LAST) before the radix passes.

Result

Same query, same machine:

Radix sort closes most of the gap with DuckDB on integer sorts. DuckDB still wins because its sort is SIMD-optimized for columnar data. The remaining difference is in the materialization and wire serialization of 50,000 sorted rows, not the sort itself.