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
