Which qsort is used

Qingqing Zhou wrote:

Seems we don't link against the port/qsort.c - is there any reason for
that? My tests indicates our qsort is much much faster than the libc's.

We haven't been able to determine if the OS's qsort or pgport's is
faster. Right now we only force pgport qsort on Solaris (from
configure.in):

# Solaris has a very slow qsort in certain cases, so we replace it.
if test "$PORTNAME" = "solaris"; then
AC_LIBOBJ(qsort)
fi

Are you willing to say that we should always prefer pgport over glibc's
qsort()?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

"Bruce Momjian" <pgman@candle.pha.pa.us> wrote

Are you willing to say that we should always prefer pgport over glibc's
qsort()?

At least for Linux and windows. My test is performed on a dataset ranges
from 10 to 15000000 elements. Each elements contains a 64 bytes garbage
character area and an integer key, which is uniformly distributed from 1 to
RANGE. RANGE takes values from 2 to 2^31. In all cases, our qsort absolutely
wins. Maybe skewed distribution should be tested?

Another interesting thing is that the qsort on RANGE=2 or other small number
in windows is terriblly slow - our version does not have this problem.

The test code could be found here (Note: it mixed with some other
experiements I am doing but might be a good start point to construct your
own tests):

http://www.cs.toronto.edu/~zhouqq/sort.c

Regards,
Qingqing

On Mon, 2005-12-12 at 11:50 -0500, Bruce Momjian wrote:

Are you willing to say that we should always prefer pgport over glibc's
qsort()?

glibc's qsort is actually implemented via merge sort. I'm not sure why
the glibc folks chose to do that, but as a result, it's not surprising
that BSD qsort beats it for typical inputs. Whether we should go to the
trouble of second-guessing glibc is a separate question, though: it
would be good to see some performance figures for real-world queries.

BTW, Luke Lonergan recently posted some performance results for a fairly
efficient public domain implementation of qsort to the bizgres list:

http://lists.pgfoundry.org/pipermail/bizgres-general/2005-December/000294.html

-Neil

On Mon, 12 Dec 2005, Neil Conway wrote:

Whether we should go to the trouble of second-guessing glibc is a
separate question, though: it would be good to see some performance
figures for real-world queries.

For qsort, due to its simple usage, I think simulation test should be
enough. But we have to consider many situations like cardinality, data
distribution etc. Maybe not easy to find real world queries providing so
many variations.

BTW, Luke Lonergan recently posted some performance results for a fairly
efficient public domain implementation of qsort to the bizgres list:

http://lists.pgfoundry.org/pipermail/bizgres-general/2005-December/000294.html

Ooops, more interesting than the thread itself ;-)

Regards,
Qingqing

Neil Conway <neilc@samurai.com> writes:

BTW, Luke Lonergan recently posted some performance results for a fairly
efficient public domain implementation of qsort to the bizgres list:
http://lists.pgfoundry.org/pipermail/bizgres-general/2005-December/000294.html

As those results suggest, there can be huge differences in sort
performance depending on whether the input is random, nearly sorted,
nearly reverse sorted, possesses many equal keys, etc. It would be very
dangerous to say "implementation A is better than implementation B"
without having tested all those scenarios. IIRC, the reason we reject
Solaris' qsort is not that it is so bad in the typical case, but that it
has some horrible corner-case behaviors.

regards, tom lane

Tom,

On 12/12/05 2:47 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:

As those results suggest, there can be huge differences in sort
performance depending on whether the input is random, nearly sorted,
nearly reverse sorted, possesses many equal keys, etc. It would be very
dangerous to say "implementation A is better than implementation B"
without having tested all those scenarios.

Yes. The Linux glibc qsort is proven terrible in the general case by these
examples though.

Bruce's point on that thread was that we shouldn't be replacing the OS
routine in the general case. On the other hand, there is the precedent of
replacing Solaris' routine with the NetBSD version.

Based on the current testing, I think it would be a good idea to expose a
"--with-qsort" option in configure to allow for it's selection as suggested
by other posters.

IIRC, the reason we reject
Solaris' qsort is not that it is so bad in the typical case, but that it
has some horrible corner-case behaviors.

Do you have a test suite you can recommend with those edge cases? I built
the one in the bizgres-general thread based on edge cases for Solaris that I
found on a sun mailing list. The edge case referred to there was the all
zero one, which does seem to have a significant advantage in the NetBSD.

- Luke

On Mon, 12 Dec 2005, Luke Lonergan wrote:

Do you have a test suite you can recommend with those edge cases?

I have at least those factors in mind:

+ f1: number of elements
  - in {10^3, 10^4, 10^5, 10^6, 10^7}

+ f2: key comparators measured by cpu cost
  - in {1, 10, 100+};

+ f3: data distribution
  - in {uniform, Gussian, 95% sorted, 95% reverse sorted}

+ f4: data value range
  - in {2, 32, 1024, unlimited}: radix sort might be better for small
range

The element size doesn't matter since the main usage of our qsort is
on pointer array. Element data type is covered by f2 and f4.

This will gives us a 5*3*4*4 = 240 tests ...

Regards,
Qingqing

Qingqing,

On 12/12/05 5:08 PM, "Qingqing Zhou" <zhouqq@cs.toronto.edu> wrote:

This will gives us a 5*3*4*4 = 240 tests ...

Looks good - I'm not going to be able to implement this matrix of tests
quickly, but each dimension seems right.

Might you have time to implement these within the testing framework I
published previously? It has both the NetBSD and qsortG included along with
a timing routine, etc.

BTW - the edge case reported to the Sun mailing list was here:
http://forum.sun.com/thread.jspa?forumID=4&amp;threadID=7231

- Luke

Tom,

 IIRC, the reason we reject
Solaris' qsort is not that it is so bad in the typical case, but that it
has some horrible corner-case behaviors.

Sun claims to have fixed these. Hopefully they'll do some testing which will
prove it.

--
Josh Berkus
Aglio Database Solutions
San Francisco

On 12/12/05, Bruce Momjian <pgman@candle.pha.pa.us> wrote:

Qingqing Zhou wrote:

Seems we don't link against the port/qsort.c - is there any reason for
that? My tests indicates our qsort is much much faster than the libc's.

Are you willing to say that we should always prefer pgport over glibc's
qsort()?

I searched the archives and found this:

http://sourceware.org/ml/libc-alpha/2000-03/msg00139.html

Seems glibc guys once tested some implementation of quicksort vs. merge sort
and found out that

"For small sets and smaller data types (arrays of ints and
arrays of doubles) mergesort is definitly faster and behaves better."

If the qsort in Postgres is called usually on wide data - on full rows
not on pointers to rows, then indeed it would be wise to use out own
sort. Especially considering that qsort is not anything OS or machine
-specific, better algorithm beats assembly-optimizations. If we have
a very good good implementation we could use it everywhere.

OTOH, someone should notify glibc devs that their qsort is mediocre,
I don't see much activity on the lists around around that topic.

--
marko

Marko Kreen <markokr@gmail.com> writes:

http://sourceware.org/ml/libc-alpha/2000-03/msg00139.html
Seems glibc guys once tested some implementation of quicksort vs. merge sort
and found out that
"For small sets and smaller data types (arrays of ints and
arrays of doubles) mergesort is definitly faster and behaves better."

If the qsort in Postgres is called usually on wide data - on full rows
not on pointers to rows, then indeed it would be wise to use out own
sort.

But I can assure you that it is never called on any such thing. Since
qsort only works on fixed-size items, it'd be essentially impossible
to use it directly on rows; we *always* use it on pointers instead.
(We could only do the other if we had a separate code path for rows
containing only fixed-width-never-null columns, which we do not, and
it'd be pretty silly to add one in view of the increased data-copying
work that would result.)

The referenced message is pretty interesting for this discussion,
particularly its pointer to someone's sort test routines --- wonder
if those are still available? It was also eye-opening to read that
glibc actually contains two separate algorithms to use depending on
the size of the target array. If that's still true then it throws a
lot of the testing so far into doubt.

regards, tom lane

On Mon, 12 Dec 2005, Luke Lonergan wrote:

Might you have time to implement these within the testing framework I
published previously? It has both the NetBSD and qsortG included along with
a timing routine, etc.

Here we go:

http://www.cs.toronto.edu/~zhouqq/postgresql/sort/sort.html

The source tar ball and linux 2.4G gcc 2.96 test results is on the page.
There is a clear loser glibc, not sure qsortB or qsortG which is better.

Regards,
Qingqing

Here is a sort template (that can very easily be turned into a C
routine).

It is an introspective sort. Bentley & McIlroy proved that every qsort
routine will degrade into quadratic behavior with a worst-case input.
This function detects quadratic behavior and switches to qsort when
needed.

Use of this template is totally unrestricted.

I sent a copy to the author of FastDB and it is what he uses for
ordering data, as he found it to be an excellent performer.

It uses all the standard tricks to ensure good performance.

-----Original Message-----
From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
owner@postgresql.org] On Behalf Of Qingqing Zhou
Sent: Tuesday, December 13, 2005 10:29 AM
To: Luke Lonergan
Cc: Tom Lane; Neil Conway; Bruce Momjian; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Which qsort is used

On Mon, 12 Dec 2005, Luke Lonergan wrote:

Might you have time to implement these within the testing framework

I

published previously? It has both the NetBSD and qsortG included

along

with

a timing routine, etc.

Here we go:

http://www.cs.toronto.edu/~zhouqq/postgresql/sort/sort.html

The source tar ball and linux 2.4G gcc 2.96 test results is on the

page.

There is a clear loser glibc, not sure qsortB or qsortG which is

better.

Regards,
Qingqing

---------------------------(end of

broadcast)---------------------------

Strike "switches to qsort" insert "switches to heapsort"

-----Original Message-----
From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
owner@postgresql.org] On Behalf Of Dann Corbit
Sent: Tuesday, December 13, 2005 10:40 AM
To: Qingqing Zhou; Luke Lonergan
Cc: Tom Lane; Neil Conway; Bruce Momjian; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Which qsort is used

Here is a sort template (that can very easily be turned into a C
routine).

It is an introspective sort. Bentley & McIlroy proved that every

qsort

routine will degrade into quadratic behavior with a worst-case input.
This function detects quadratic behavior and switches to qsort when

heapsort

needed.

Use of this template is totally unrestricted.

I sent a copy to the author of FastDB and it is what he uses for
ordering data, as he found it to be an excellent performer.

It uses all the standard tricks to ensure good performance.

-----Original Message-----
From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
owner@postgresql.org] On Behalf Of Qingqing Zhou
Sent: Tuesday, December 13, 2005 10:29 AM
To: Luke Lonergan
Cc: Tom Lane; Neil Conway; Bruce Momjian;

pgsql-hackers@postgresql.org

Subject: Re: [HACKERS] Which qsort is used

On Mon, 12 Dec 2005, Luke Lonergan wrote:

Might you have time to implement these within the testing

framework

"Dann Corbit" <DCorbit@connx.com> writes:

Here is a sort template (that can very easily be turned into a C
routine).

Right offhand I'd guess this to be a loser on not-quite-sorted input,
because the tests it makes to try to prove the input is already sorted
can add significant overhead before failing.

regards, tom lane

The test is O(n)

The test is designed especially for database systems, which are likely
to be clustered on data or index (and in the general case are sometimes
loaded in physically sorted order). In the clustered case, the only
time the data will not be ordered is when there has been a page split
and the statistics have not been updated.

The in-order check happens only once and there will not be a significant
performance hit for removal (except that it will be absurdly fast when
the data is already ordered or in reverse order if left as-is.)

Ordered and reverse-ordered are two cases where qsort goes quadratic
(without a test). Of course, introspective sort does not suffer from
this defect, even with the test removed.

-----Original Message-----
From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
owner@postgresql.org] On Behalf Of Dann Corbit
Sent: Tuesday, December 13, 2005 11:53 AM
To: Tom Lane
Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
hackers@postgresql.org
Subject: Re: [HACKERS] Which qsort is used

The test is O(n)

-----Original Message-----
From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
Sent: Tuesday, December 13, 2005 10:51 AM
To: Dann Corbit
Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
hackers@postgresql.org
Subject: Re: [HACKERS] Which qsort is used

"Dann Corbit" <DCorbit@connx.com> writes:

Here is a sort template (that can very easily be turned into a C
routine).

Right offhand I'd guess this to be a loser on not-quite-sorted

input,

because the tests it makes to try to prove the input is already

sorted

can add significant overhead before failing.

regards, tom lane

---------------------------(end of

broadcast)---------------------------

On Tue, 13 Dec 2005, Dann Corbit wrote:

The test is designed especially for database systems, which are likely
to be clustered on data or index (and in the general case are sometimes
loaded in physically sorted order). In the clustered case, the only
time the data will not be ordered is when there has been a page split
and the statistics have not been updated.

The in-order check happens only once and there will not be a significant
performance hit for removal (except that it will be absurdly fast when
the data is already ordered or in reverse order if left as-is.)

Ordered and reverse-ordered are two cases where qsort goes quadratic
(without a test). Of course, introspective sort does not suffer from
this defect, even with the test removed.

Yeah, I would think O(n) in-order check doesn't matter for random data
set. For nearly-ordered set, may be not true. I am not good at C++, so can
you patch the test program with your sort method and the page-split-data
generator? I would be happy to give it a test.

Regards,
Qingqing

I will send you an ANSI C version.

-----Original Message-----
From: Qingqing Zhou [mailto:zhouqq@cs.toronto.edu]
Sent: Tuesday, December 13, 2005 1:08 PM
To: Dann Corbit
Cc: Tom Lane; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
hackers@postgresql.org
Subject: RE: [HACKERS] Which qsort is used

On Tue, 13 Dec 2005, Dann Corbit wrote:

The test is designed especially for database systems, which are

likely

to be clustered on data or index (and in the general case are

sometimes

loaded in physically sorted order). In the clustered case, the only
time the data will not be ordered is when there has been a page

split

and the statistics have not been updated.

The in-order check happens only once and there will not be a

significant

performance hit for removal (except that it will be absurdly fast

when

the data is already ordered or in reverse order if left as-is.)

Ordered and reverse-ordered are two cases where qsort goes quadratic
(without a test). Of course, introspective sort does not suffer

from

this defect, even with the test removed.

Yeah, I would think O(n) in-order check doesn't matter for random data
set. For nearly-ordered set, may be not true. I am not good at C++, so

can

you patch the test program with your sort method and the

page-split-data