From: Simon Riggs <simon@2ndquadrant.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Gary Doades <gpd@gpdnet.co.uk>
Cc: pgsql-performance@postgresql.org
Cc: pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Date: Thu, 16 Feb 2006 01:56:55 +0000
Message-ID: <1140055015.12131.232.camel@localhost.localdomain> (raw)
In-Reply-To: <21455.1140051584@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>
<21455.1140051584@sss.pgh.pa.us>
On Wed, 2006-02-15 at 19:59 -0500, Tom Lane wrote:
> 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.
"The worst-case behavior of replacement-selection is very close to its
average behavior, while the worst-case behavior of QuickSort is terrible
(N2) – a strong argument in favor of replacement-selection. Despite this
risk, QuickSort is widely used because, in practice, it has superior
performance." p.8, "AlphaSort: A Cache-Sensitive Parallel External
Sort", Nyberg et al, VLDB Journal 4(4): 603-627 (1995)
I think your other comment about flipping to insertion sort too early
(and not returning...) is a plausible cause for the poor pg qsort
behaviour, but the overall spread of values seems as expected.
Some test results I've seen seem consistent with the view that
increasing memory also increases run-time for larger settings of
work_mem/maintenance_work_mem. Certainly, as I observed a while back,
having a large memory settings doesn't help you at all when you are
doing final run merging on the external sort. Whatever we do, we should
look at the value high memory settings bring to each phase of a sort
separately from the other phases.
There is work underway on improving external sorts, so I hear (not me).
Plus my WIP on randomAccess requirements.
Best Regards, Simon Riggs
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: simon@2ndquadrant.com, tgl@sss.pgh.pa.us, gpd@gpdnet.co.uk, pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
In-Reply-To: <1140055015.12131.232.camel@localhost.localdomain>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox