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

Hi John!

On 13.11.2025 05:01, John Naylor wrote:
> If that's the case then I suggest first seeing if dfd8e6c73ee made
> things any worse. A simpler possible improvement is to use a similar
> normalization step for the chars, if needed, then do the sort and
> quinique with a specialization for unsigned chars. (We don't yet
> specialize qunique, but that can be remedied). If you're interested,
> please start a separate thread for that.

It did but only a bit. I worked around it by having two sort
specializations, one for signed and one for unsigned. I also wanted to
try to use a hash table to filter out duplicates and then only sort the
remaining unique trigams, which are, most of the times, a lot less.

Generally speaking, the GIN code is death by a thousand cuts. I've got a
patch coming up that cuts CREATE INDEX runtime in half for columns with
relatively short strings and yields even better results for columns with
longer strings. But that's not only changing the sort but requires a few
 changes in a couple of places. More details in the upcoming thread.

I thought qunique() is already pretty optimal because it's defined in a
header file. I believe that even the comparator gets inlined. What would
be useful though is if qunique() used an equality comparator which only
returns true/false instead of a sort comparator. In the GIN code this
also shaved off a few percent. I'll take a closer look at qunique() at
open a thread with the findings / ideas for changes.

Anyways. In this context GIN was just one example for where a generic
radix sort would be useful and there are certainly more.

> 
> That's moving the goalposts too far IMO. I want to get to a place
> where I feel comfortable with the decisions made, and that already
> requires a lot of testing. Also, I don't want to risk introducing
> abstractions that make future improvements to tuplesort more
> cumbersome.

On a quick glance it looks like you didn't specialize much. So the
testing seems related to if the new algo introduces regressions, not if
the abstraction would cause problems. So it should be possible to
extract out the code fairly easily without invalidating your existing
benchmark results.

I understand that you want to make progress with the use case at hand
but I feel like we're missing out on a lot of opportunity where the
introduced code would also be very beneficial. Beyond that we could
nicely test the new sort code in the spirit of test_rbtree.c and
friends. Maybe you want to give it a 2nd thought.

--
David Geier