Re: PG qsort vs. Solaris

Neil Conway <neilc(at)samurai(dot)com> writes:
> Given the time that has been spent working around
> the braindamaged behavior of qsort() on various platforms, I would be
> more inclined to *always* use our qsort() instead of the platform's
> version.

I spent a bit of time looking into why we hadn't chosen to do this already.
The remaining uncertainty was expressed by Greg Stark: glibc's mergesort
has a small advantage over quicksort in terms of the average number of
calls of the comparison function, and considering that we tend to use
pretty heavyweight comparison functions, that seems like it ought to
favor the mergesort. Nobody bothered to check this out back in March
when the last discussion died off.

I made a small hack in tuplesort.c to actually count the
comparison-function calls, and then ran this test case with both our
qsort and glibc's (from Fedora Core 5 current glibc):

set trace_sort TO 1;
set client_min_messages TO log;
set work_mem TO '200MB';
select count(*) from
(select random()::text from generate_series(1,1000000) order by 1) ss;

In C locale the text comparison is relatively quick, and I see results
like

glibc:
LOG: begin tuple sort: nkeys = 1, workMem = 204800, randomAccess = f
LOG: performsort starting: CPU 0.15s/2.39u sec elapsed 2.54 sec
LOG: performsort done: CPU 0.18s/7.09u sec elapsed 7.27 sec
LOG: internal sort ended, 102701 KB used, 18674655 comparisons: CPU 0.18s/7.38u sec elapsed 7.56 sec
ours:
LOG: begin tuple sort: nkeys = 1, workMem = 204800, randomAccess = f
LOG: performsort starting: CPU 0.18s/2.34u sec elapsed 2.51 sec
LOG: performsort done: CPU 0.18s/5.18u sec elapsed 5.36 sec
LOG: internal sort ended, 102701 KB used, 21277970 comparisons: CPU 0.18s/5.46u sec elapsed 5.64 sec

In en_US.utf8 locale, strcoll is pretty slow, but:

glibc:
LOG: begin tuple sort: nkeys = 1, workMem = 204800, randomAccess = f
LOG: performsort starting: CPU 0.17s/2.35u sec elapsed 2.52 sec
LOG: performsort done: CPU 0.19s/15.94u sec elapsed 16.13 sec
LOG: internal sort ended, 102701 KB used, 18674910 comparisons: CPU 0.19s/16.23u sec elapsed 16.43 sec
ours:
LOG: begin tuple sort: nkeys = 1, workMem = 204800, randomAccess = f
LOG: performsort starting: CPU 0.18s/2.30u sec elapsed 2.49 sec
LOG: performsort done: CPU 0.18s/15.30u sec elapsed 15.48 sec
LOG: internal sort ended, 102701 KB used, 20972345 comparisons: CPU 0.18s/15.58u sec elapsed 15.76 sec

If you're sorting integer or float keys it's a lot worse:

postgres=# select count(*) from (select random() from generate_series(1,1000000) order by 1) ss;

glibc:
LOG: begin tuple sort: nkeys = 1, workMem = 204800, randomAccess = f
LOG: performsort starting: CPU 0.16s/0.70u sec elapsed 0.86 sec
LOG: performsort done: CPU 0.18s/5.10u sec elapsed 5.28 sec
LOG: internal sort ended, 71452 KB used, 18674509 comparisons: CPU 0.18s/5.38u sec elapsed 5.56 sec
ours:
LOG: begin tuple sort: nkeys = 1, workMem = 204800, randomAccess = f
LOG: performsort starting: CPU 0.11s/0.74u sec elapsed 0.86 sec
LOG: performsort done: CPU 0.11s/3.22u sec elapsed 3.33 sec
LOG: internal sort ended, 71452 KB used, 21123160 comparisons: CPU 0.11s/3.50u sec elapsed 3.62 sec

So basically, glibc's qsort is bad enough that even a
10%-more-comparisons advantage doesn't save it.

I propose that we do the following:

1. Switch to using port/qsort.c all the time.
2. Add a "qsort_arg" function that is identical to qsort except it also
passes a void pointer through to the comparison function. This will
allow us to get rid of the non-reentrant static variable and extra
level of function call in tuplesort.c.
3. Insert a CHECK_FOR_INTERRUPTS() call as was requested back in July.
With glibc out of the way, there's no longer a reason to fear memory
leakage from cancelling a sort.

regards, tom lane