Re: qsort again (was Re: [PERFORM] Strange Create Index - Mailing list pgsql-hackers

From Simon Riggs
Subject Re: qsort again (was Re: [PERFORM] Strange Create Index
Date
Msg-id 1140055015.12131.232.camel@localhost.localdomain
Whole thread Raw
In response to Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)  (Tom Lane <tgl@sss.pgh.pa.us>)
List pgsql-hackers
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




pgsql-hackers by date:

Previous
From: Christopher Kings-Lynne
Date:
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour)
Next
From: Neil Conway
Date:
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index