Skip site navigation (1) Skip section navigation (2)

Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Ron <rjpeace(at)earthlink(dot)net>
Cc: pgsql-performance(at)postgresql(dot)org, pgsql-hackers(at)postgresql(dot)org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)
Date: 2006-02-16 01:21:33
Message-ID: 21615.1140052893@sss.pgh.pa.us (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-performance
Ron <rjpeace(at)earthlink(dot)net> writes:
> How are we choosing our pivots?

See qsort.c: it looks like median of nine equally spaced inputs (ie,
the 1/8th points of the initial input array, plus the end points),
implemented as two rounds of median-of-three choices.  With half of the
data inputs zero, it's not too improbable for two out of the three
samples to be zeroes in which case I think the med3 result will be zero
--- so choosing a pivot of zero is much more probable than one would
like, and doing so in many levels of recursion causes the problem.

I think.  I'm not too sure if the code isn't just being sloppy about the
case where many data values are equal to the pivot --- there's a special
case there to switch to insertion sort, and maybe that's getting invoked
too soon.  It'd be useful to get a line-level profile of the behavior of
this code in the slow cases...

			regards, tom lane

In response to

Responses

pgsql-performance by date

Next:From: Dann CorbitDate: 2006-02-16 01:37:58
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)
Previous:From: Tom LaneDate: 2006-02-16 00:59:44
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)

pgsql-hackers by date

Next:From: Peter EisentrautDate: 2006-02-16 01:36:01
Subject: Generating config stuff from single source
Previous:From: Tom LaneDate: 2006-02-16 00:59:44
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group