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

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

From: Simon Riggs <simon(at)2ndquadrant(dot)com>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Gary Doades <gpd(at)gpdnet(dot)co(dot)uk>, pgsql-performance(at)postgresql(dot)org,pgsql-hackers(at)postgresql(dot)org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Date: 2006-02-16 01:56:55
Message-ID: 1140055015.12131.232.camel@localhost.localdomain (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-performance
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




In response to

pgsql-performance by date

Next:From: Neil ConwayDate: 2006-02-16 02:12:52
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Previous:From: Christopher Kings-LynneDate: 2006-02-16 01:52:46
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)

pgsql-hackers by date

Next:From: Neil ConwayDate: 2006-02-16 02:12:52
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Previous:From: Christopher Kings-LynneDate: 2006-02-16 01:52:46
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)

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