Re: Sorting Improvements for 8.4 - Mailing list pgsql-hackers

Has anyone looked into sorting algorithms that could use
more than one CPU or core at a time?

Benchmarks I see[1][2] suggest that sorting is an area that
improves greatly with multiple processors and even with
multi-threading on a single core processor.
  "For 1-processor and 2-threads (1p2t), the algorithm sorts  the relation about 48% faster than the single-threaded
version with a speedup of 31% during the quicksort and 58% during the  mergesort. The dual-processor (2p2t) version
providesan even  faster total speedup of 86% over the single-threaded version  with a speedup of 60% during the
quicksortand 100% during  the merge sort."       [from the acm paper on link 2 below]
 

PS: Yeah, I know multi-threading is a hot-button on these
lists; but sorting seems a relatively isolated of the code
and I'd wonder if it'd be isolate-able enough that multiple
CPUs could be used there.

[1]
http://www.cs.cmu.edu/~damon2005/damonpdf/4%20best%20paper%20-%20multithreaded%20architectures%20and%20the%20sort%20benchmark.pdf
[2]
http://delivery.acm.org/10.1145/1120000/1114254/DaMoN_103.pdf?key1=1114254&key2=5713023711&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618