Re: tuple radix sort

cca5507 <cca5507@qq.com>

From: cca5507 <cca5507@qq.com>

To: John Naylor <johncnaylorls@gmail.com>

Cc: zengman <zengman@halodbtech.com>, pgsql-hackers <pgsql-hackers@lists.postgresql.org>

Date: 2026-03-31T04:36:32Z

Lists: pgsql-hackers

Hi John,

> This turned out to be a loser, but in the course of trying it a better
> idea occurred to me. v8's prefix detection was really a special-case
> optimization where the sort key is all non-negative integers (or all
> negative, but that's not common). It's wasted work when the input is
> mixed in sign, and for abbreviated keys. It's not much of a waste, but
> we can do better.
> 
> v9 computes the common prefix during every recursion at the same time
> we populate the SortTuple's current byte. That should be practically
> free given a modest amount of instruction-level parallelism.

+1 and v9-0001 LGTM.

--
Regards,
ChangAo Chen

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

Cosmetic fixes for radix sort
- ca9807dfec5b 19 (unreleased) landed
Skip common prefixes during radix sort
- f6bd9f0fe25a 19 (unreleased) landed
Perform radix sort on SortTuples with pass-by-value Datums
- ef3c3cf6d021 19 (unreleased) landed
Grab the low-hanging fruit from forcing sizeof(Datum) to 8.
- 6aebedc38497 19 (unreleased) cited
Add missing Datum conversions
- ff89e182d420 19 (unreleased) cited