X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org
Received: from localhost (av.hub.org [200.46.204.144])
	by postgresql.org (Postfix) with ESMTP id E67AE9DCC10;
	Wed, 15 Feb 2006 20:59:45 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
	with ESMTP id 72204-02; Wed, 15 Feb 2006 20:59:48 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-
X-Greylist: from auto-whitelisted by SQLgrey-
Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130])
	by postgresql.org (Postfix) with ESMTP id 5CCEB9DCC4F;
	Wed, 15 Feb 2006 20:59:41 -0400 (AST)
Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1])
	by sss.pgh.pa.us (8.13.1/8.13.1) with ESMTP id k1G0xiiT021456;
	Wed, 15 Feb 2006 19:59:44 -0500 (EST)
To: Gary Doades <gpd@gpdnet.co.uk>
cc: pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour) 
In-reply-to: <21152.1140049020@sss.pgh.pa.us> 
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> <43F3BF72.6000202@gpdnet.co.uk>
	<21152.1140049020@sss.pgh.pa.us>
Comments: In-reply-to Tom Lane <tgl@sss.pgh.pa.us>
	message dated "Wed, 15 Feb 2006 19:17:00 -0500"
Date: Wed, 15 Feb 2006 19:59:44 -0500
Message-ID: <21455.1140051584@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, score=0.11 required=5 tests=[AWL=0.110]
X-Spam-Score: 0.11
X-Spam-Level: 
X-Archive-Number: 200602/594
X-Sequence-Number: 79732

I wrote:
> Gary Doades <gpd@gpdnet.co.uk> writes:
>> Ouch! That confirms my problem. I generated the random test case because 
>> it was easier than including the dump of my tables, but you can 
>> appreciate that tables 20 times the size are basically crippled when it 
>> comes to creating an index on them.

> Actually... we only use qsort when we have a sorting problem that fits
> within the allowed sort memory.  The external-sort logic doesn't go
> through that code at all.  So all the analysis we just did on your test
> case doesn't necessarily apply to sort problems that are too large for
> the sort_mem setting.

I increased the size of the test case by 10x (basically s/100000/1000000/)
which is enough to push it into the external-sort regime.  I get
amazingly stable runtimes now --- I didn't have the patience to run 100
trials, but in 30 trials I have slowest 11538 msec and fastest 11144 msec.
So this code path is definitely not very sensitive to this data
distribution.

While these numbers aren't glittering in comparison to the best-case
qsort times (~450 msec to sort 10% as much data), they are sure a lot
better than the worst-case times.  So maybe a workaround for you is
to decrease maintenance_work_mem, counterintuitive though that be.
(Now, if you *weren't* using maintenance_work_mem of 100MB or more
for your problem restore, then I'm not sure I know what's going on...)

We still ought to try to fix qsort of course.

			regards, tom lane