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

Show quoted text

TIP 2: Don't 'kill -9' the postmaster

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

Show quoted text

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

TIP 2: Don't 'kill -9' the postmaster

"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)

Show quoted text

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

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

Show quoted text

TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

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

Show quoted text

generator? I would be happy to give it a test.

Regards,
Qingqing

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

The in-order check happens only once

Hm? What about that call inside qloop's loop?

regards, tom lane

-----Original Message-----
From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
Sent: Tuesday, December 13, 2005 7:38 PM
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:

The in-order check happens only once

Hm? What about that call inside qloop's loop?

You're right. Once per partition of size 50 or greater.

In my tests, it was a clear win. We'll see in the Qingqing Zhou test
setup if it helps or not. If there is some order to the data, it will
be of benefit. For purely random samples, there will be a small fixed
cost.

Qingqing,

On 12/13/05 10:28 AM, "Qingqing Zhou" <zhouqq@cs.toronto.edu> wrote:

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.

Great stuff - thanks for doing this.

From the results, it's clear that the scale test makes a huge difference in
the relative performance. I'm wondering if it's an L2 cache effect, as it
seems to occur in that range.

Overall - I'd say that the BSD routine is showing the best overall results
when the scale test is included. The qsortG routine has some significantly
better performance in certain cases at smaller sort set sizes - it could
probably be improved for better L2 use, but BSD is already there.

Based on this it seems like we should expose the option to choose the BSD
qsort routine at configure time.

- Luke

On Wed, 14 Dec 2005, Luke Lonergan wrote:

Overall - I'd say that the BSD routine is showing the best overall results
when the scale test is included. The qsortG routine has some significantly
better performance in certain cases at smaller sort set sizes - it could
probably be improved for better L2 use, but BSD is already there.

Based on this it seems like we should expose the option to choose the BSD
qsort routine at configure time.

Before we pin down this, I hope more extensive tests on various platforms
could be done. So we could give some suggestions when we should enable the
"--enable-bsdqsort" option. I can post a result on a SunOS machine (but
the problem is that many ppl share this machine) and a windows machine.

Regards,
Qingqing

On Thu, Dec 15, 2005 at 12:10:37AM -0500, Qingqing Zhou wrote:

On Wed, 14 Dec 2005, Luke Lonergan wrote:

Overall - I'd say that the BSD routine is showing the best overall results
when the scale test is included. The qsortG routine has some significantly
better performance in certain cases at smaller sort set sizes - it could
probably be improved for better L2 use, but BSD is already there.

Based on this it seems like we should expose the option to choose the BSD
qsort routine at configure time.

Before we pin down this, I hope more extensive tests on various platforms
could be done. So we could give some suggestions when we should enable the
"--enable-bsdqsort" option. I can post a result on a SunOS machine (but
the problem is that many ppl share this machine) and a windows machine.

I have access to both some (SLOW) ultra5's and a machine running
opensolaris on AMD if testing there would help. I'll need a pointer to a
patch and test-case though...

Oh, I also have access to an old SGI...
--
Jim C. Nasby, Sr. Engineering Consultant jnasby@pervasive.com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461

On Thu, 15 Dec 2005, Jim C. Nasby wrote:

I have access to both some (SLOW) ultra5's and a machine running
opensolaris on AMD if testing there would help. I'll need a pointer to a
patch and test-case though...

Thanks! I've patched the program with the following changes:
(1) add gcc-mingw support;
(2) move the check_sort() out of do_sort() - the previous program is
actually measuring the time of qsort plus result verification. Though that
one "fairly" add equal cost to every competitor, which will not affect the
confidence of the result, it is a defeat, sorry about that;

The new results with SunOS and Windows tests are published at the same
place:
http://www.cs.toronto.edu/~zhouqq/postgresql/sort/sort.html

As Luke suggested, BSD seems a good choice for scalable and stable
consideration. But I also sent an email to the author of qsortG, and he
might take a look at the small-range performance problem during the
holiday. So if he can help that, then we will have another candidate.

By the way, I do spend some time on fighting the win32 gettimeofday()
emulation. I would suggest adding a comment like "don't use this method in
windows to get high precision time, use elapsed_time() instead" ...

Regards,
Qingqing

Based on this it seems like we should expose the option to choose the BSD
qsort routine at configure time.

I have a related question. qsort is only used in the postgres source in a few
places. If postgres used an internal implementation instead of the library
source it could have implementations that don't use function pointers. This
might perform faster for a few reasons. The comparator is much more likely to
be eligible for inlining for one.

It also opens the door to using different sort algorithms for different
applications. There may be some cases where the input is never sorted and the
sample size is small so qsort is a good choice, and others where the inputs
can be large and using a better algorithm with worse overhead like mergesort
might make more sense.

Unfortunately there isn't just a single qsort call though. I count 6
comparators in the source tree I have. So perhaps this is a non-starter.
Having 6 qsort implementations around sounds pretty sketchy.

--
greg

Greg Stark <gsstark@mit.edu> writes:

I have a related question. qsort is only used in the postgres source in a few
places. If postgres used an internal implementation instead of the library
source it could have implementations that don't use function pointers.

There are calls to qsort in upwards of 40 different source files; many
of those files contain multiple comparator functions. Doesn't look like
"a few" to me. But I'll grant that the vast majority are not
performance critical. One could imagine putting a custom implementation
into only tuplesort.c, say, where you could certainly get rid of one
level of function call (qsort_comparetup) by providing a saner API that
passes a state pointer as well as a function pointer to the qsort code.
Whether that would be worth the trouble is a question for experiment ...

regards, tom lane

On Thu, 15 Dec 2005, Greg Stark wrote:

I have a related question. qsort is only used in the postgres source in a few
places. If postgres used an internal implementation instead of the library
source it could have implementations that don't use function pointers. This
might perform faster for a few reasons. The comparator is much more likely to
be eligible for inlining for one.

It also opens the door to using different sort algorithms for different
applications. There may be some cases where the input is never sorted and the
sample size is small so qsort is a good choice, and others where the inputs
can be large and using a better algorithm with worse overhead like mergesort
might make more sense.

Unfortunately there isn't just a single qsort call though. I count 6
comparators in the source tree I have. So perhaps this is a non-starter.
Having 6 qsort implementations around sounds pretty sketchy.

[also with reply to Tom] Both ideas look like doable (or at least
testable) for me. I agree that the only interesting pot is in tuplesort.c.
For the 2nd idea, for smaller range, we may consider radix sort, which is
definitely faster - but this may need some work that enable query
optimizer know the *exact* data range.

Regards,
Qingqing

-----Original Message-----
From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
owner@postgresql.org] On Behalf Of Qingqing Zhou
Sent: Thursday, December 15, 2005 3:16 PM
To: Greg Stark
Cc: Jim C. Nasby; Luke Lonergan; Tom Lane; Neil Conway; Bruce Momjian;
pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Which qsort is used

On Thu, 15 Dec 2005, Greg Stark wrote:

I have a related question. qsort is only used in the postgres source

in

a few

places. If postgres used an internal implementation instead of the

library

source it could have implementations that don't use function

pointers.

This

might perform faster for a few reasons. The comparator is much more

likely to

be eligible for inlining for one.

It also opens the door to using different sort algorithms for

different

applications. There may be some cases where the input is never

sorted

and the

sample size is small so qsort is a good choice, and others where the

inputs

can be large and using a better algorithm with worse overhead like

mergesort

might make more sense.

Unfortunately there isn't just a single qsort call though. I count 6
comparators in the source tree I have. So perhaps this is a

non-starter.

Having 6 qsort implementations around sounds pretty sketchy.

[also with reply to Tom] Both ideas look like doable (or at least
testable) for me. I agree that the only interesting pot is in

tuplesort.c.

For the 2nd idea, for smaller range, we may consider radix sort, which

is

definitely faster - but this may need some work that enable query
optimizer know the *exact* data range.

Radix sort can also be made completely generic by using a callback
function.

The function gives back n-bits at a time, from the most significant bits
to the least significant.

So, for char string, and a radix of 256, you just return the first char,
then the second char, etc. to get the classical radix sort.

Radix sort is no advantage for long, similar strings. Suppose that you
have a comparison sort that is O(n*log(n)). If n is one billion items,
then log2(n) is 32 and therefore LSD radix 256 sorts of 33 character
fields will be slower than a comparison sort, even for one billion
items.

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

Radix sort can also be made completely generic by using a callback
function.
The function gives back n-bits at a time, from the most significant bits
to the least significant.

That's mighty handwavy --- it assumes that the datatype permits a simple
breakdown into small pieces that can be sorted lexicographically. Seems
to me that's a much stronger requirement than assuming that you can tell
which of two whole values is smaller. What's worse, it needs to be the
same number of pieces for every value, which makes it hard to deal with
variable-length data.

So, for char string, and a radix of 256, you just return the first char,
then the second char, etc. to get the classical radix sort.

Uh, no, you'd need to work right-to-left, after having padded all the
strings to the same length somehow.

regards, tom lane

[Face flushed begin]

Thanks for Greg "let" me take a second look at qsortB.c - there is
paste-and-copy error there, so when it perform recursive sort, it calls
glibc's qsort ... Really sorry, and feel a little bit gun-shy now ...

[Face flushed continue]

After I re-tested it, now BSD qsort is the obvious winner in most
situations.

[Face flushed end]

Regards,
Qingqing

Qingqing,

On 12/15/05 6:33 PM, "Qingqing Zhou" <zhouqq@cs.toronto.edu> wrote:

Thanks for Greg "let" me take a second look at qsortB.c - there is
paste-and-copy error there, so when it perform recursive sort, it calls
glibc's qsort ... Really sorry, and feel a little bit gun-shy now ...

After I re-tested it, now BSD qsort is the obvious winner in most
situations.

:-D

Can you post the new results like the last post?

- Luke

On Fri, 16 Dec 2005, Luke Lonergan wrote:

Can you post the new results like the last post?

Yeah, it is at the same website (I disabled Jim's result since he hasn't
updated using the new program).

Regards,
Qingqing

-----Original Message-----
From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
Sent: Thursday, December 15, 2005 6:24 PM
To: Dann Corbit
Cc: Qingqing Zhou; Greg Stark; Jim C. Nasby; Luke Lonergan; Neil

Conway;

Bruce Momjian; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Which qsort is used

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

Radix sort can also be made completely generic by using a callback
function.
The function gives back n-bits at a time, from the most significant

bits

to the least significant.

That's mighty handwavy --- it assumes that the datatype permits a

simple

breakdown into small pieces that can be sorted lexicographically.

It's not so hard. For fixed length character strings, the mapping is
just the character. For integers the mapping is obvious [msb to lsb or
lsb to msb of the integer, depending on whether you are doing msd or lsd
radix sort]. For intel floating point, the transformation is:

#include <assert.h>
#include "inteltyp.h"

uint32
float2key(float f)
{
uint32 sign,
mant,
mask;

assert(sizeof(float) == sizeof(uint32));
mant = *(uint32 *) & f; /* Load float as array of bits */
sign = mant & SB_MASK32; /* Isolate the leading sign bit */
mant ^= SB_MASK32; /* Invert the sign bit, making + > - */
mask = sign - (sign >> 31); /* Either 0 or 0x7fffffff */
mant ^= mask; /* Invert exp and mant if negative */
return mant;
}

uint64
double2key(double d)
{
uint64 sign,
mant,
mask;

assert(sizeof(double) == sizeof(uint64));
mant = *(uint64 *) & d; /* Load float as array of bits */
sign = mant & SB_MASK64; /* Isolate the leading sign bit */
mant ^= SB_MASK64; /* Invert the sign bit, making + > - */
mask = sign - (sign >> 63); /* Either 0 or 0x7fffffffffffffff */
mant ^= mask; /* Invert exp and mant if negative */
return mant;
}

Where the contents of inteltyp.h are as follows:
/*
** Typdefs for Intel formats.
** See keyxfrm.c for usage.
*/

typedef unsigned long uint32;
#define SB_MASK32 0x80000000UL

#ifdef _MSC_VER
typedef unsigned __int64 uint64;
typedef __int64 sint64;
#define SB_MASK64 0x8000000000000000ui64
#else
typedef unsigned long long uint64;
typedef long long sint64;
#define SB_MASK64 0x8000000000000000ULL
#endif
extern uint32 float2key(float f);
uint64 double2key(double d);

=======================================================
After the above transformation, you just use the same buckets as for
integers.

In general, the creation of the mapping function is no more difficult
than the creation of a comparison function.

Seems
to me that's a much stronger requirement than assuming that you can

tell

which of two whole values is smaller. What's worse, it needs to be

the

same number of pieces for every value, which makes it hard to deal

with

variable-length data.

No. The number of pieces is irrelevant. And you can use MSD radix sort
for variable length data.

So, for char string, and a radix of 256, you just return the first

char,

then the second char, etc. to get the classical radix sort.

Uh, no, you'd need to work right-to-left, after having padded all the
strings to the same length somehow.

Unless you use MSD radix sort (which is usually better anyway).

Show quoted text

regards, tom lane

Here's some results for a 2.5Ghz G5 and a 933Mhz G4

http://www.jefftrout.com/sort/

--
Jeff Trout <jeff@jefftrout.com>
http://www.jefftrout.com/
http://www.stuarthamm.net/

Luke Lonergan wrote:

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.

At this point, I think we have done enough testing on enough platforms
to just use port/qsort on all platforms in 8.2. It seems whenever
someone tries to improve the BSD qsort, they make it worse.

Were the BSD programmers geniuses and we are all idiots now, or what?

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

On Fri, 16 Dec 2005, Bruce Momjian wrote:

At this point, I think we have done enough testing on enough platforms
to just use port/qsort on all platforms in 8.2. It seems whenever
someone tries to improve the BSD qsort, they make it worse.

Not necessariliy true. Dann Corbit sent me an implementation a while ago
(you can see it on the same site). BSD qsort is improved, though not that
much, by two methods. Since Dann write the program from scratch, so I am
not sure if we are afford to take the efforts for the improvement.

Regards,
Qingqing

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

On Fri, 16 Dec 2005, Bruce Momjian wrote:

At this point, I think we have done enough testing on enough

platforms

to just use port/qsort on all platforms in 8.2. It seems whenever
someone tries to improve the BSD qsort, they make it worse.

Not necessariliy true. Dann Corbit sent me an implementation a while

ago

(you can see it on the same site). BSD qsort is improved, though not

that

much, by two methods. Since Dann write the program from scratch, so I

am

not sure if we are afford to take the efforts for the improvement.

Both of them are modified versions of Bentley's sort algorithm.

I just added the in-order check to both of them, and the reversed
partition check for the second method (in the case of the subfiles
because insertion sort is allergic to reversed partitions).

At any rate, neither is much of an improvement on Bentley's version.
For the rare cases of completely ordered or completely reversed, it will
be a monumental improvement. But that is a pretty rare case.

If I could use C++, I could do much better. It is very difficult for me
to write an ADT in C instead of in C++.

Luke Lonergan wrote:

Qingqing,

On 12/15/05 6:33 PM, "Qingqing Zhou" <zhouqq@cs.toronto.edu> wrote:

Thanks for Greg "let" me take a second look at qsortB.c - there is
paste-and-copy error there, so when it perform recursive sort, it calls
glibc's qsort ... Really sorry, and feel a little bit gun-shy now ...

After I re-tested it, now BSD qsort is the obvious winner in most
situations.

:-D

Can you post the new results like the last post?

- Luke

Here is a result from a dual 0.8G x86 running Freebsd 6.0-RELEASE:

http://homepages.paradise.net.nz/markir/download/sort-fbsd.out

(after patching the bug with qsortB calling qsort). Clearly in this
case, there is no glibc version, hence I've relabeled the 1st case as
"native qsort".

Cheers

Mark

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

Both of them are modified versions of Bentley's sort algorithm.

Jon Bentley of Bell Labs? Small world ... he was my thesis adviser
for awhile when he was at CMU. He's a good algorithms man, for sure.

I just added the in-order check to both of them, and the reversed
partition check for the second method (in the case of the subfiles
because insertion sort is allergic to reversed partitions).

I've still got a problem with these checks; I think they are a net
waste of cycles on average. They would only be a win if you expected a
nontrivial percentage of perfectly-in-order or perfectly-reverse-order
inputs. What I think is much more probable in the Postgres environment
is almost-but-not-quite-ordered inputs --- eg, a table that was
perfectly ordered by key when filled, but some of the tuples have since
been moved by UPDATEs. This is the worst possible case for the in-order
checks, because they can then grovel over large percentages of the file
before failing ... and when they fail, those cycles are entirely wasted;
you have not advanced the state of the sort at all.

For the "usual" case of randomly ordered input, of course it doesn't
matter much at all because the in-order checks will fail after examining
not too many items. But to argue that the checks are worth making, you
have to assume that perfectly-ordered inputs are more common than
almost-ordered inputs, and I think that is exactly the wrong assumption
for the Postgres environment. I sure haven't seen any evidence that
it's a good assumption.

regards, tom lane

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

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

Both of them are modified versions of Bentley's sort algorithm.

Jon Bentley of Bell Labs? Small world ... he was my thesis adviser
for awhile when he was at CMU. He's a good algorithms man, for sure.

I just added the in-order check to both of them, and the reversed
partition check for the second method (in the case of the subfiles
because insertion sort is allergic to reversed partitions).

I've still got a problem with these checks; I think they are a net
waste of cycles on average. They would only be a win if you expected

a

nontrivial percentage of perfectly-in-order or perfectly-reverse-order
inputs. What I think is much more probable in the Postgres

environment

is almost-but-not-quite-ordered inputs --- eg, a table that was
perfectly ordered by key when filled, but some of the tuples have

since

been moved by UPDATEs. This is the worst possible case for the

in-order

checks, because they can then grovel over large percentages of the

file

before failing ... and when they fail, those cycles are entirely

wasted;

you have not advanced the state of the sort at all.

For the "usual" case of randomly ordered input, of course it doesn't
matter much at all because the in-order checks will fail after

examining

not too many items. But to argue that the checks are worth making,

you

have to assume that perfectly-ordered inputs are more common than
almost-ordered inputs, and I think that is exactly the wrong

assumption

for the Postgres environment. I sure haven't seen any evidence that
it's a good assumption.

The benchmarks say that they (order checks) are a good idea on average
for ordered data, random data, and partly ordered data.

It does not require perfectly ordered data for the checks to be useful.
On mostly ordered data, it is likely that some partitions are perfectly
ordered.

If you trace the algorithms in a debugger you will be surprised at how
often the partitions are ordered, even with random sets as input.

On Sat, 17 Dec 2005, Dann Corbit wrote:

The benchmarks say that they (order checks) are a good idea on average
for ordered data, random data, and partly ordered data.

I interpret that in linux, 5000000 seems a divide for qsortpdq. Before
that number, it wins, after that, bsd wins more. On SunOS, qsortpdq takes
the lead till the last second -- I suspect this is due to the rand()
function:

Linux - #define RAND_MAX 2147483647
SunOS - #define RAND_MAX 32767

So in SunOS, the data actually not that scattered - so more favourate for
sorted() or reversed() check?

Regards,
Qingqing

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

On Sat, 17 Dec 2005, Dann Corbit wrote:

The benchmarks say that they (order checks) are a good idea on

average

for ordered data, random data, and partly ordered data.

I interpret that in linux, 5000000 seems a divide for qsortpdq. Before
that number, it wins, after that, bsd wins more. On SunOS, qsortpdq

takes

the lead till the last second -- I suspect this is due to the rand()
function:

Linux - #define RAND_MAX 2147483647
SunOS - #define RAND_MAX 32767

So in SunOS, the data actually not that scattered - so more favourate

for

sorted() or reversed() check?

There is a lot of variability from system to system even for the same
tests. I see different results depending on whether I use GCC or Intel
or MS compilers.

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

I've still got a problem with these checks; I think they are a net
waste of cycles on average.

The benchmarks say that they (order checks) are a good idea on average
for ordered data, random data, and partly ordered data.

There are lies, damn lies, and benchmarks ;-)

The problem with citing a benchmark for this discussion is that a
benchmark can't tell you anything about real-world probabilities;
it only tells you about the probabilities occuring in the benchmark
case. You need to make the case that the benchmark reflects the
real world, which you didn't.

If you trace the algorithms in a debugger you will be surprised at how
often the partitions are ordered, even with random sets as input.

Well, I do agree that checking for orderedness on small partitions would
succeed more often than on larger partitions or the whole file --- but
the code-as-given checks all the way down. Moreover, the argument given
for spending these cycles is that insertion sort sucks on reverse-order
input ... where "sucks" means that it spends O(N^2) time. But it spends
O(N^2) in the average case, too.

regards, tom lane

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

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

I've still got a problem with these checks; I think they are a net
waste of cycles on average.

The benchmarks say that they (order checks) are a good idea on

average

for ordered data, random data, and partly ordered data.

There are lies, damn lies, and benchmarks ;-)

The problem with citing a benchmark for this discussion is that a
benchmark can't tell you anything about real-world probabilities;
it only tells you about the probabilities occuring in the benchmark
case. You need to make the case that the benchmark reflects the
real world, which you didn't.

If you trace the algorithms in a debugger you will be surprised at

how

often the partitions are ordered, even with random sets as input.

Well, I do agree that checking for orderedness on small partitions

would

succeed more often than on larger partitions or the whole file --- but
the code-as-given checks all the way down. Moreover, the argument

given

for spending these cycles is that insertion sort sucks on

reverse-order

input ... where "sucks" means that it spends O(N^2) time. But it

spends

O(N^2) in the average case, too.

I agree that in general these checks are not important and they
complicate what is a simple and elegant algorithm.

The cases where the checks are important (highly ordered data sets) are
rare and so the value added is minimal.

I am actually quite impressed with the excellence of Bentley's sort out
of the box. It's definitely the best library implementation of a sort I
have seen.

On Fri, Dec 16, 2005 at 10:43:58PM -0800, Dann Corbit wrote:

I am actually quite impressed with the excellence of Bentley's sort out
of the box. It's definitely the best library implementation of a sort I
have seen.

I'm not sure whether we have a conclusion here, but I do have one
question: is there a significant difference in the number of times the
comparison routines are called? Comparisons in PostgreSQL are fairly
expensive given the fmgr overhead and when comparing tuples it's even
worse.

We don't want to accedently pick a routine that saves data shuffling by
adding extra comparisons. The stats at [1]http://www.cs.toronto.edu/~zhouqq/postgresql/sort/sort.html don't say. They try to
factor in CPU cost but they seem to use unrealistically small values. I
would think a number around 50 (or higher) would be more
representative.

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

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

Show quoted text

Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
tool for doing 5% of the work and then sitting around waiting for someone
else to do the other 95% so you can sue them.

Martin,

On 12/19/05 3:37 AM, "Martijn van Oosterhout" <kleptog@svana.org> wrote:

I'm not sure whether we have a conclusion here, but I do have one
question: is there a significant difference in the number of times the
comparison routines are called? Comparisons in PostgreSQL are fairly
expensive given the fmgr overhead and when comparing tuples it's even
worse.

It would be interesting to note the comparison count of the different
routines.

Something that really grabbed me about the results though is that the
relative performance of the routines dramatically shifted when the indirect
references in the comparators went in. The first test I did sorted an array
of int4 - these tests that Qingqing did sorted arrays using an indirect
pointer list, at which point the same distributions performed very
differently.

I suspect that it is the number of comparisons that caused this, and further
that the indirection has disabled the compiler optimizations for memory
prefetch and other things that it could normally recognize. Given the usage
pattern in Postgres, where sorted things are a mix of strings and intrinsic
types, I'm not sure those optimizations could be done by one routine.

I haven't verified this, but it certainly seems that the NetBSD routine is
the overall winner for the type of use that Postgres has (sorting the using
a pointer list).

- Luke

On Sat, 17 Dec 2005 00:03:25 -0500, Tom Lane <tgl@sss.pgh.pa.us>
wrote:

I've still got a problem with these checks; I think they are a net
waste of cycles on average. [...]
and when they fail, those cycles are entirely wasted;
you have not advanced the state of the sort at all.

How can we make the initial check "adavance the state of the sort"?
One answer might be to exclude the sorted sequence at the start of the
array from the qsort, and merge the two sorted lists as the final
stage of the sort.

Qsorting N elements costs O(N*lnN), so excluding H elements from the
sort reduces the cost by at least O(H*lnN). The merge step costs O(N)
plus some (<=50%) more memory, unless someone knows a fast in-place
merge. So depending on the constant factors involved there might be a
usable solution.

I've been playing with some numbers and assuming the constant factors
to be equal for all the O()'s this method starts to pay off at
H for N
20 100
130 1000
8000 100000
Servus
Manfred

On Thu, Dec 22, 2005 at 01:43:34AM +0100, Manfred Koizar wrote:

Qsorting N elements costs O(N*lnN), so excluding H elements from the
sort reduces the cost by at least O(H*lnN). The merge step costs O(N)
plus some (<=50%) more memory, unless someone knows a fast in-place
merge. So depending on the constant factors involved there might be a
usable solution.

But where are you including the cost to check how many cells are
already sorted? That would be O(H), right? This is where we come back
to the issue that comparisons in PostgreSQL are expensive. The cpu_cost
in the tests I saw so far is unrealistically low.

I've been playing with some numbers and assuming the constant factors
to be equal for all the O()'s this method starts to pay off at
H for N
20 100 20%
130 1000 13%
8000 100000 8%

Hmm, what are the chances you have 100000 unordered items to sort and
that the first 8% will already be in order. ISTM that that probability
will be close enough to zero to not matter...

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

Show quoted text

Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
tool for doing 5% of the work and then sitting around waiting for someone
else to do the other 95% so you can sue them.

On Thu, 22 Dec 2005 08:01:00 +0100, Martijn van Oosterhout
<kleptog@svana.org> wrote:

But where are you including the cost to check how many cells are
already sorted? That would be O(H), right?

Yes. I didn't mention it, because H < N.

This is where we come back
to the issue that comparisons in PostgreSQL are expensive.

So we agree that we should try to reduce the number of comparisons.
How many comparisons does it take to sort 100000 items? 1.5 million?

Hmm, what are the chances you have 100000 unordered items to sort and
that the first 8% will already be in order. ISTM that that probability
will be close enough to zero to not matter...

If the items are totally unordered, the check is so cheap you won't
even notice. OTOH in Tom's example ...

|What I think is much more probable in the Postgres environment
|is almost-but-not-quite-ordered inputs --- eg, a table that was
|perfectly ordered by key when filled, but some of the tuples have since
|been moved by UPDATEs.

... I'd not be surprised if H is 90% of N.
Servus
Manfred

An interesting article on sorting and comparison count:
http://www.acm.org/jea/ARTICLES/Vol7Nbr5.pdf

Here is the article, the code, and an implementation that I have been
toying with:
http://cap.connx.com/chess-engines/new-approach/algos.zip

Algorithm quickheap is especially interesting because it does not
require much additional space (just an array of integers up to size
log(element_count) and in addition, it has very few data movements.

-----Original Message-----
From: Manfred Koizar [mailto:mkoi-pg@aon.at]
Sent: Thursday, December 22, 2005 1:59 PM
To: Martijn van Oosterhout
Cc: Tom Lane; Dann Corbit; Qingqing Zhou; Bruce Momjian; Luke

Lonergan;

Neil Conway; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Re: Which qsort is used

On Thu, 22 Dec 2005 08:01:00 +0100, Martijn van Oosterhout
<kleptog@svana.org> wrote:

But where are you including the cost to check how many cells are
already sorted? That would be O(H), right?

Yes. I didn't mention it, because H < N.

This is where we come back
to the issue that comparisons in PostgreSQL are expensive.

So we agree that we should try to reduce the number of comparisons.
How many comparisons does it take to sort 100000 items? 1.5 million?

Hmm, what are the chances you have 100000 unordered items to sort and
that the first 8% will already be in order. ISTM that that

probability

will be close enough to zero to not matter...

If the items are totally unordered, the check is so cheap you won't
even notice. OTOH in Tom's example ...

|What I think is much more probable in the Postgres environment
|is almost-but-not-quite-ordered inputs --- eg, a table that was
|perfectly ordered by key when filled, but some of the tuples have

since

Show quoted text

|been moved by UPDATEs.

... I'd not be surprised if H is 90% of N.
Servus
Manfred