Thread: Which qsort is used

Which qsort is used

From
Qingqing Zhou
Date:
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.

Regards,
Qingqing


Re: Which qsort is used

From
Bruce Momjian
Date:
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";
thenAC_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,
Pennsylvania19073
 


Re: Which qsort is used

From
"Qingqing Zhou"
Date:
"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 




Re: Which qsort is used

From
Neil Conway
Date:
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




Re: Which qsort is used

From
Qingqing Zhou
Date:

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


Re: Which qsort is used

From
Tom Lane
Date:
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


Re: Which qsort is used

From
"Luke Lonergan"
Date:
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




Re: Which qsort is used

From
Qingqing Zhou
Date:
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


Re: Which qsort is used

From
"Luke Lonergan"
Date:
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&threadID=7231

- Luke




Re: Which qsort is used

From
Josh Berkus
Date:
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


Re: Which qsort is used

From
Marko Kreen
Date:
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
behavesbetter." 

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

Re: Which qsort is used

From
Tom Lane
Date:
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


Re: Which qsort is used

From
Qingqing Zhou
Date:

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


Re: Which qsort is used

From
"Dann Corbit"
Date:
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)---------------------------
> TIP 2: Don't 'kill -9' the postmaster

Attachment

Re: Which qsort is used

From
"Dann Corbit"
Date:
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
> 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


Re: Which qsort is used

From
Tom Lane
Date:
"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


Re: Which qsort is used

From
"Dann Corbit"
Date:
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


Re: Which qsort is used

From
"Dann Corbit"
Date:
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)---------------------------
> 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


Re: Which qsort is used

From
Qingqing Zhou
Date:

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


Re: Which qsort is used

From
"Dann Corbit"
Date:
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
> generator? I would be happy to give it a test.
>
> Regards,
> Qingqing


Re: Which qsort is used

From
Tom Lane
Date:
"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


Re: Which qsort is used

From
"Dann Corbit"
Date:
> -----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.



Re: Which qsort is used

From
"Luke Lonergan"
Date:
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 




Re: Which qsort is used

From
Qingqing Zhou
Date:
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


Re: Which qsort is used

From
"Jim C. Nasby"
Date:
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


Re: Which qsort is used

From
Qingqing Zhou
Date:


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



Re: Which qsort is used

From
Greg Stark
Date:
> > > 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



Re: Which qsort is used

From
Tom Lane
Date:
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


Re: Which qsort is used

From
Qingqing Zhou
Date:

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






Re: Which qsort is used

From
"Dann Corbit"
Date:
> -----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.



Re: Which qsort is used

From
Tom Lane
Date:
"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


Re: Which qsort is used

From
"Qingqing Zhou"
Date:
[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 




Re: Which qsort is used

From
"Luke Lonergan"
Date:
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




Re: Which qsort is used

From
Qingqing Zhou
Date:

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


Re: Which qsort is used

From
"Dann Corbit"
Date:
> -----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
mantif 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).

>             regards, tom lane


Re: Which qsort is used

From
Jeff Trout
Date:
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/




Re: Re: Which qsort is used

From
Bruce Momjian
Date:
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,
Pennsylvania19073
 


Re: Re: Which qsort is used

From
Qingqing Zhou
Date:

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





Re: Re: Which qsort is used

From
"Dann Corbit"
Date:
> -----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++.


Re: Which qsort is used

From
Mark Kirkwood
Date:
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


Re: Re: Which qsort is used

From
Tom Lane
Date:
"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


Re: Re: Which qsort is used

From
"Dann Corbit"
Date:
> -----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.


Re: Re: Which qsort is used

From
Qingqing Zhou
Date:

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        2147483647SunOS - #define       RAND_MAX        32767

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

Regards,
Qingqing


Re: Re: Which qsort is used

From
"Dann Corbit"
Date:
> -----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.


Re: Re: Which qsort is used

From
Tom Lane
Date:
"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


Re: Re: Which qsort is used

From
"Dann Corbit"
Date:
> -----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.


Re: Re: Which qsort is used

From
Martijn van Oosterhout
Date:
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] 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/
> 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.

Re: Re: Which qsort is used

From
"Luke Lonergan"
Date:
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




Re: Re: Which qsort is used

From
Manfred Koizar
Date:
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      10008000    100000
ServusManfred


Re: Re: Which qsort is used

From
Martijn van Oosterhout
Date:
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/
> 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.

Re: Re: Which qsort is used

From
Manfred Koizar
Date:
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.
ServusManfred


Re: Re: Which qsort is used

From
"Dann Corbit"
Date:
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
> |been moved by UPDATEs.
>
> ... I'd not be surprised if H is 90% of N.
> Servus
>  Manfred