Re: tuple radix sort

On Sat, Nov 15, 2025 at 1:05 AM David Geier <geidav.pg@gmail.com> wrote:
> 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.

The patch is independently beneficial, but is also just a stepping
stone toward something larger, and I don't yet know exactly how it's
going to look. Premature abstractions are just going to get in the
way. I'd be open to hear proposals for possible wider application
after the dust settles, but that's not going to happen during the PG19
cycle.

--
John Naylor
Amazon Web Services

On Sat, Nov 15, 2025 at 1:05 AM David Geier <geidav.pg@gmail.com> wrote:
>
> 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
>


--
John Naylor
Amazon Web Services