SEO

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/xr...n/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/bugdatab...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.



---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org

Zdenek Kotala <Zdenek.Kotala@Sun.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

---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

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



---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

Neil Conway <neilc@samurai.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

---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

Neil Conway <neilc@samurai.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

---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

Tom Lane wrote:
> Zdenek Kotala <Zdenek.Kotala@Sun.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

---------------------------(end of broadcast)---------------------------
TIP 6: explain analyze is your friend

Tom Lane wrote:
> Neil Conway <neilc@samurai.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

---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

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



---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org

Neil Conway <neilc@samurai.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

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

Tom Lane <tgl@sss.pgh.pa.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

---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org