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

Michał Zaborowski wrote:<br /><blockquote cite="mid:e2289d9e0712190231u6d1cd5e0qe57643c99492e4a5@mail.gmail.com"
type="cite"><prewrap="">Ok - we want to sort table with quick sort and we want to do it on - N threads.
 
Every thread - gets begin and end of indices of the table. First step starts
at 0 and lasts with count -1. Single step:  find medium value and move
lover before it and bigger after. In normal case - we use recursive call - so
the same procedure is being called for that two parts. In thread we can put
indices at side list - and use queue of threads to pick up data from the list.
We can use common table, access to side list with indices has to be serialized. </pre></blockquote> Stupid question #2:
Isit well recognized that the CPU is the bottleneck in the PostgreSQL sorting mechanism? Or might it be memory
bandwidthand I/O?<br /><br /> It would seem to me that any sort worth parallelizing (administrative and synchronization
overhead),must have data larger than the L2 cache. If larger than the L2 cache, it becomes real memory speed. If real
memoryspeed, wouldn't one CPU without hardware synchronization, be able to fill the memory read/write pipe? If 'divide
andconquer' to parallize, wouldn't the values written<br /> from one thread, often (1 / N) need to be read from another
thread,requiring hardware data synchronization?<br /><br /> I see the wikipedia.org page describes how easy it is to
parallelizequick sort, and scale performance linearly with the number of processors, but I don't see references to back
thisclaim.<br /> At least some of these steps seem difficult or impractical to parallelize. For example, the initial
partitionreorder that moves items lower than the pivot to the left, and items higher than the pivot to the right, would
notbe easy to parallelize using an in-place re-order. It needs to move one partition down before it can 'divide and
conquer'.They say no synchronization is required, but I think they are missing the hardware synchronization required
(especiallyin the inner most loops where the thread task becomes shorter, and starts to fit in L1/L2). They say linear,
butthen talk about a 'new thread being created'. New thread creation has a cost, and if reduced to using a thread pool,
thensynchronization *is* required.<br /><br /> It sounds like a 'nice in theory' idea. :-) Which doesn't mean it is
wrong...<br/><br /> I am curious enough to write a test...<br /><blockquote
cite="mid:e2289d9e0712190231u6d1cd5e0qe57643c99492e4a5@mail.gmail.com"type="cite"><blockquote type="cite"><pre
wrap="">Ordo you mean being able to perform parts of the query plan fully in
 
parallel? If this, then one would need a lot more than ParallelSort..</pre></blockquote><pre wrap="">Nice to have, but
ratherfor data warehouses. In other cases... IE - backend
 
for Internet - there are many requests and every processor / core works nice. </pre></blockquote> I'm a fan of the
'eachplan item is a task, that is assigned to the pool, with each CPU grabbing tasks from the pool'. Another 'nice in
theory'idea (used by DB2?). As it is, though, I think PostgreSQL planning is heavily designed to maximize performance
ona single CPU, and single queries would not easily scale to multiple CPUs. (Perhaps hashing could be done on another
CPU,or as you describe above, sorting)<br /><br /> Cheers,<br /> mark<br /><br /><pre class="moz-signature"
cols="72">--
 
Mark Mielke <a class="moz-txt-link-rfc2396E" href="mailto:mark@mielke.cc"><mark@mielke.cc></a>
</pre>