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 |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers pgsql-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
From | Date | Subject | |
---|---|---|---|
Next Message | Peter Eisentraut | 2006-02-16 01:36:01 | Generating config stuff from single source |
Previous Message | Tom Lane | 2006-02-16 00:59:44 | Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour) |
From | Date | Subject | |
---|---|---|---|
Next Message | Dann Corbit | 2006-02-16 01:37:58 | Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour) |
Previous Message | Tom Lane | 2006-02-16 00:59:44 | Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour) |