Message-ID: <a2ca34fd-7693-4406-9250-2f3435353001@gmail.com>
Date: Wed, 12 Nov 2025 15:28:37 +0100
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: tuple radix sort
To: John Naylor <johncnaylorls@gmail.com>,
 PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Cc: Peter Geoghegan <pg@bowt.ie>
References: 
 <CANWCAZYzx7a7E9AY16Jt_U3+GVKDADfgApZ-42SYNiig8dTnFA@mail.gmail.com>
Content-Language: en-US
From: David Geier <geidav.pg@gmail.com>
In-Reply-To: 
 <CANWCAZYzx7a7E9AY16Jt_U3+GVKDADfgApZ-42SYNiig8dTnFA@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Archived-At: 
 <https://www.postgresql.org/message-id/a2ca34fd-7693-4406-9250-2f3435353001%40gmail.com>
Precedence: bulk

On 29.10.2025 07:28, John Naylor wrote:
> 
> Next steps: Try to find regressions (help welcome here). The v1 patch
> has some optimizations, but in other ways things are simple and/or
> wasteful. Exactly how things fit together will be informed by what, if
> anything, has to be done to avoid regressions. I suspect the challenge
> will be multikey sorts when the first key has low cardinality. This is
> because tiebreaks are necessarily postponed rather than taken care of
> up front. I'm optimistic, since low cardinality cases can be even
> faster than our B&M qsort, so we have some headroom:

Hi John,

I've also been looking into radix sort the last days to accelerate GIN
index builds. Ordering and removing duplicates requires a fast sort in
generate_trgm(). My own implementation (likely slower than the
algorithms you used) also showed a decent speedup.

Beyond that there are many more places in the code base that could be
changed to use radix sort instead of qsort.

What would be great is if we could build a generic radix sort
implementation, similarly to sort_template.h that can be used in other
places. We would have to think a bit about the interface because instead
of a comparator we would require some radix extraction callback.

If you're open to that idea I could give abstracting the code a try.

--
David Geier