Horton

Re: A qsort template

Peter Geoghegan <pg@bowt.ie>

View thread View on postgr.es
From: Peter Geoghegan <pg@bowt.ie>
To: Thomas Munro <thomas.munro@gmail.com>
Cc: Andres Freund <andres@anarazel.de>, Justin Pryzby <pryzby@telsasoft.com>, John Naylor <john.naylor@enterprisedb.com>, pgsql-hackers <pgsql-hackers@postgresql.org>, Robert Haas <rhaas@postgresql.org>, David Rowley <dgrowleyml@gmail.com>
Date: 2022-04-10T21:54:44Z
Lists: pgsql-hackers 
On Sun, Apr 10, 2022 at 2:44 PM 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.

That's not good.

The B&M quicksort implementation that we adopted is generally
extremely fast for that case, since it uses 3 way partitioning (based
on the Dutch National Flag algorithm). This essentially makes sorting
large groups of duplicates take only linear time (not linearithmic
time).

-- 
Peter Geoghegan

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.