Horton

Re: A qsort template

David Rowley <dgrowleyml@gmail.com>

View thread View on postgr.es
From: David Rowley <dgrowleyml@gmail.com>
To: Thomas Munro <thomas.munro@gmail.com>
Cc: Andres Freund <andres@anarazel.de>, Justin Pryzby <pryzby@telsasoft.com>, John Naylor <john.naylor@enterprisedb.com>, Peter Geoghegan <pg@bowt.ie>, pgsql-hackers <pgsql-hackers@postgresql.org>, Robert Haas <rhaas@postgresql.org>
Date: 2022-04-10T22:34:27Z
Lists: pgsql-hackers

Attachments

On Mon, 11 Apr 2022 at 09:44, Thomas Munro <thomas.munro@gmail.com> wrote:
> David Rowley privately reported a performance regression when sorting
> single ints with a lot of duplicates, in a case that previously hit
> qsort_ssup() but now hits qsort_tuple_int32() and then has to call the
> tiebreaker comparator.  Note that this comes up only for sorts in a
> query, not for eg index builds which always have to tiebreak on item
> ptr.  I don't have data right now but that'd likely be due to:

Yeah, I noticed this when running some sort benchmarks to compare v14
with master (as of Thursday last week).

The biggest slowdown I saw was the test that sorted 1 million tuples
on a BIGINT column with 100 distinct values.  The test in question
does sorts on the same column each time, but continually adds columns,
which I was doing to check how wider tuples changed the performance
(this was for the exercise of 40af10b57 rather than this work).

With this particular test, v15 is about 15% *slower* than v14.  I
didn't know what to blame at first, so I tried commenting out the sort
specialisations and got the results in the red bars in the graph. This
made it about 7.5% *faster* than v14. So looks like this patch is to
blame.  I then hacked the comparator function that's used in the
specialisations for BIGINT to comment out the tiebreak to remove the
indirect function call, which happens to do nothing in this 1 column
sort case.  The aim here was to get an idea what the performance would
be if there was a specialisation for single column sorts. That's the
yellow bars, which show about 10% *faster* than master.

Commits

  1. Remove debug messages from tuplesort_sort_memtuples()

  2. Fix performance regression in tuplesort specializations

  3. Fix tuplesort optimization for CLUSTER-on-expression.

  4. Initial pgindent and pgperltidy run for v14.

  5. Specialize checkpointer sort functions.

  6. Use sort_template.h for qsort() and qsort_arg().

  7. Use sort_template.h for qsort_tuple() and qsort_ssup().

  8. Add sort_template.h for making sort functions.

  9. Use abbreviated keys for faster sorting of text datums.