To: Ron <rjpeace@earthlink.net>
cc: pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour) 
In-reply-to: <7.0.1.0.2.20060215194635.03b55da0@earthlink.net> 
References: <43F38867.6010701@gpdnet.co.uk> <19510.1140036968@sss.pgh.pa.us>
	<19779.1140038874@sss.pgh.pa.us> <43F39E53.1020009@gpdnet.co.uk>
	<20781.1140046109@sss.pgh.pa.us>
	<7.0.1.0.2.20060215194635.03b55da0@earthlink.net>
Comments: In-reply-to Ron <rjpeace@earthlink.net>
	message dated "Wed, 15 Feb 2006 19:57:51 -0500"
Date: Wed, 15 Feb 2006 20:21:33 -0500
Message-ID: <21615.1140052893@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Ron <rjpeace@earthlink.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