Re: PG qsort vs. Solaris

Postgres has own implementation of qsort. It is used only for Solaris,
because in some cases Solaris implementation was terrible slow.

Now, New qsort is present in the Solaris from version 9 update 6 and I
performed some quick test and the speed is very similarly with pg
implementation see bellow. The Solaris qsort only does not have test for
preordered array.

Is it time to "remove" PG qsort and use libc version for solaris 9, 10...?

There some useful links:
solaris qsort implementation
http://cvs.opensolaris.org/source/xref/on/usr/src/common/util/qsort.c
discuss about qsort
http://momjian.postgresql.org/cgi-bin/pgtodo?qsort

Regards Zdenek

PS: Test program is located on
http://bugs.opensolaris.org/bugdatabase/view_bug.do?bug_id=4489885

There is test result:

mode 1 2 3 4 5 6 7 8
pg 3.440 54.259 42.251 40.967 38.214 29.730 21.668 39.142
pg2 39.492 53.598 44.697 40.546 38.027 29.572 21.598 38.756
solaris 41.207 41.957 41.873 41.616 35.895 29.502 26.906 39.492

Pg2 test is without sort array prechecking.

Zdenek Kotala <Zdenek(dot)Kotala(at)Sun(dot)COM> writes:
> Is it time to "remove" PG qsort and use libc version for solaris 9, 10...?

I have no particular desire to introduce a version number check until we
have to. If you can show that the newer versions have a qsort that
substantially *out-performs* ours, it would be worth doing that, but
merely being competitive isn't enough to make it worth the trouble.

regards, tom lane

On Tue, 2006-10-03 at 10:48 -0400, Tom Lane wrote:
> I have no particular desire to introduce a version number check until we
> have to. If you can show that the newer versions have a qsort that
> substantially *out-performs* ours

Are there any platform-local variants of qsort() that substantially
outperform our implementation? (I don't remember hearing of one, but I
might have missed it.) 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. That way we'd get the same behavior across all platforms, and
we can at least verify that our implementation behaves reasonably for
the special cases we're interested in (presorted input, many-equal-keys,
etc.), and doesn't do crazy stuff like randomly switch to merge sort for
certain inputs.

-Neil

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've been heard to argue against that in the past, but I'm beginning to
see the merit of the idea. One good reason for doing it is that we
could stop worrying about the possibility of large-scale memory leaks
due to erroring out of glibc's qsort --- in particular it would be OK
to add CHECK_FOR_INTERRUPTS into the comparison callback as was
requested recently.

regards, tom lane

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

Tom Lane wrote:
> Zdenek Kotala <Zdenek(dot)Kotala(at)Sun(dot)COM> writes:
>> Is it time to "remove" PG qsort and use libc version for solaris 9, 10...?
>
> I have no particular desire to introduce a version number check until we
> have to. If you can show that the newer versions have a qsort that
> substantially *out-performs* ours, it would be worth doing that, but
> merely being competitive isn't enough to make it worth the trouble.
>

The implementation in the solaris uses same ideas like postgres
implementation exclude sort array detection. There are small difference
with threshold when median uses 9 items and threshold for insertion
sort. Performance is similarly - no winer (only on sorted array).

Zdenek

Tom Lane wrote:
> 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.
>

<snip>

> I propose that we do the following:
>
> 1. Switch to using port/qsort.c all the time.

1.5 Move it to another directory - e.g. backend/utils/sort?

> 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.

4. replace KR function definition by the ANSI style :-)

regards Zdenek

On Tue, 2006-10-03 at 15:44 -0400, Tom Lane wrote:
> 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.

+1 from me.

I can implement this (for 8.3, naturally), unless you'd prefer to do it
yourself.

-Neil

Neil Conway <neilc(at)samurai(dot)com> writes:
> On Tue, 2006-10-03 at 15:44 -0400, Tom Lane wrote:
>> 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.

> +1 from me.

> I can implement this (for 8.3, naturally), unless you'd prefer to do it
> yourself.

I was planning to do it right now, on the grounds that #2 and #3 are bug
fixes, and that fixing the existing memory leakage hazard is a good
thing too.

regards, tom lane

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

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

Actually what I was more concerned about was things like on data structures
with complex comparison routines. Things like sorting on arrays or ROWs.

For that matter it seems to me that sorting on a single column is a pretty
unrealistic scenario too. Most of the time I find queries have long lists of
columns in the ORDER BY clause.

Do those numbers look very different if you have lots of columns or if you're
sorting on something like an array or a ROW?

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Tom Lane wrote:
> Neil Conway <neilc(at)samurai(dot)com> writes:
> > On Tue, 2006-10-03 at 15:44 -0400, Tom Lane wrote:
> >> 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.
>
> > +1 from me.
>
> > I can implement this (for 8.3, naturally), unless you'd prefer to do it
> > yourself.
>
> I was planning to do it right now, on the grounds that #2 and #3 are bug
> fixes, and that fixing the existing memory leakage hazard is a good
> thing too.

I am OK with doing it now, but calling it a bug fix seems like a
stretch. ;-)

--
Bruce Momjian bruce(at)momjian(dot)us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Bruce Momjian <bruce(at)momjian(dot)us> writes:
> Tom Lane wrote:
>> I was planning to do it right now, on the grounds that #2 and #3 are bug
>> fixes, and that fixing the existing memory leakage hazard is a good
>> thing too.

> I am OK with doing it now, but calling it a bug fix seems like a
> stretch. ;-)

How so? The lack of a CHECK_FOR_INTERRUPTS was reported as a bug to
start with; it was only while investigating that that we realized there
was a memory-leak hazard, but that doesn't make the latter less real.

regards, tom lane

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> Actually what I was more concerned about was things like on data structures
> with complex comparison routines. Things like sorting on arrays or ROWs.

The important point here is that blowing up the cost of the comparison
function by a factor of 3 (by switching from strcmp to strcoll) was not
sufficient to overcome the disadvantage --- which says to me that some
of the disadvantage is inbuilt and actually scales with the cost of the
comparisons. I suspect what we are looking at here is cache effect on
the tuple accesses: quicksort has more locality of reference than
mergesort, and that applies not only to the tuple pointers that qsort
itself is manipulating, but the data they point at.

> For that matter it seems to me that sorting on a single column is a pretty
> unrealistic scenario too.

Not really; even if you are sorting on multi keys, most of the time the
first column determines the comparison result. But since you insist,
here's a test case deliberately skewed to not do that:

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

glibc:
LOG: begin tuple sort: nkeys = 2, workMem = 204800, randomAccess = f
LOG: performsort starting: CPU 0.10s/1.03u sec elapsed 1.14 sec
LOG: performsort done: CPU 0.12s/5.83u sec elapsed 5.95 sec
LOG: internal sort ended, 71452 KB used, 18675458 comparisons: CPU 0.12s/6.10u sec elapsed 6.22 sec

ours:
LOG: begin tuple sort: nkeys = 2, workMem = 204800, randomAccess = f
LOG: performsort starting: CPU 0.10s/1.01u sec elapsed 1.12 sec
LOG: performsort done: CPU 0.10s/3.96u sec elapsed 4.06 sec
LOG: internal sort ended, 71452 KB used, 21047424 comparisons: CPU 0.10s/4.23u sec elapsed 4.33 sec

In any case I don't see that there's anything much left to argue about:
every single test we have done says that glibc's qsort is a loser.
Speculating about how it might not lose on sufficiently unusual cases
doesn't really counter the argument that it does lose on typical
scenarios. Between that and the other advantages of controlling our own
destiny sorting-wise, I think the decision has become pretty clear-cut.

regards, tom lane

Tom Lane wrote:
> 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've been heard to argue against that in the past, but I'm beginning to
> see the merit of the idea. One good reason for doing it is that we
> could stop worrying about the possibility of large-scale memory leaks
> due to erroring out of glibc's qsort --- in particular it would be OK
> to add CHECK_FOR_INTERRUPTS into the comparison callback as was
> requested recently.
>

I think this is a great idea - having predictable sort performance on
all platforms makes a lot of sense.

Cheers

Mark

+1

- Luke

On 10/3/06 2:58 PM, "Mark Kirkwood" <markir(at)paradise(dot)net(dot)nz> wrote:

> Tom Lane wrote:
>> 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've been heard to argue against that in the past, but I'm beginning to
>> see the merit of the idea. One good reason for doing it is that we
>> could stop worrying about the possibility of large-scale memory leaks
>> due to erroring out of glibc's qsort --- in particular it would be OK
>> to add CHECK_FOR_INTERRUPTS into the comparison callback as was
>> requested recently.
>>
>
> I think this is a great idea - having predictable sort performance on
> all platforms makes a lot of sense.
>
> Cheers
>
> Mark
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/docs/faq
>

On Tue, Oct 03, 2006 at 03:44:38PM -0400, Tom Lane wrote:
> select count(*) from
> (select random()::text from generate_series(1,1000000) order by 1) ss;
> ...
> postgres=# select count(*) from (select random() from generate_series(1,1000000) order by 1) ss;

I'm wondering whether 'order by 1' is representative of a real sort, from
the perspective of benchmarks.

I wonder why 'order by CONSTANT' might not be safe to optimize away as
no sort at all?

For sort functions that incrementally improve the sort order, I would
expect 'order by 1' to be a worst case scenario. Is that the intention?
Or is qsort unaffected by this use?

Cheers,
mark

--
mark(at)mielke(dot)cc / markm(at)ncf(dot)ca / markm(at)nortel(dot)com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada

One ring to rule them all, one ring to find them, one ring to bring them all
and in the darkness bind them...

http://mark.mielke.cc/

mark(at)mark(dot)mielke(dot)cc writes:
> I'm wondering whether 'order by 1' is representative of a real sort, from
> the perspective of benchmarks.

Better re-read
http://www.postgresql.org/docs/8.1/static/sql-select.html#SQL-ORDERBY

regards, tom lane

Sorry. Stupid question. I didn't realize SQL allowed for the column
to be identified by number. I've never seen that before. :-)

Cheers,
mark

On Tue, Oct 03, 2006 at 06:47:35PM -0400, mark(at)mark(dot)mielke(dot)cc wrote:
> On Tue, Oct 03, 2006 at 03:44:38PM -0400, Tom Lane wrote:
> > select count(*) from
> > (select random()::text from generate_series(1,1000000) order by 1) ss;
> > ...
> > postgres=# select count(*) from (select random() from generate_series(1,1000000) order by 1) ss;
>
> I'm wondering whether 'order by 1' is representative of a real sort, from
> the perspective of benchmarks.
>
> I wonder why 'order by CONSTANT' might not be safe to optimize away as
> no sort at all?
>
> For sort functions that incrementally improve the sort order, I would
> expect 'order by 1' to be a worst case scenario. Is that the intention?
> Or is qsort unaffected by this use?

--
mark(at)mielke(dot)cc / markm(at)ncf(dot)ca / markm(at)nortel(dot)com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada

One ring to rule them all, one ring to find them, one ring to bring them all
and in the darkness bind them...

http://mark.mielke.cc/

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

> Do those numbers look very different if you have lots of
> columns or if you're sorting on something like an array or a ROW?

Imho, that also is an argument for using our own qsort.
It can be extended to deal with high comparison function cost directly.

Thus I would opt to add a "comparison function cost" arg to qsort_arg
iff
we find scenarios where our qsort performs too bad.
This cost can be used to switch to merge sort for very high cost values.

Andreas