Thread

1. parallel quicksort

   Mark Wong <markwkm@gmail.com> — 2010-08-08T22:04:07Z

   Hi everyone,
   
   I've been playing around with a process based parallel quicksort
   (http://github.com/markwkm/quicksort) and I tried to shoehorn it into
   postgres because I wanted to see if I could sort more than integers.
   I've attached a patch that creates a new GUC to control the degree of
   parallelism and only modified the quicksort algorithm in quicksort.c.
   Trying to 'make install' quickly shows me the patch breaks zic and
   Andrew Gierth further pointed out on irc (a couple months back now)
   that user defined comparison functions won't work as expected in the
   forked processes (if I remember that correctly).
   
   Hoping this could be useful, I wanted to put out what I had so far and
   see how far away this is from something workable.  Not to mention that
   there are probably some improvements that could be make to the
   parallel quicksort algorithm.
   
   In case anyone is interested in a parallel merge sort algorithm, I
   have started something fairly basic here:
   http://github.com/markwkm/mergesort
   
   Regards,
   Mark
   

2. Re: parallel quicksort

   Markus Wanner <markus@bluegap.ch> — 2010-08-09T07:28:52Z

   Hi,
   
   On 08/09/2010 12:04 AM, Mark Wong wrote:
   > I've been playing around with a process based parallel quicksort
   > (http://github.com/markwkm/quicksort) and I tried to shoehorn it into
   > postgres because I wanted to see if I could sort more than integers.
   > I've attached a patch that creates a new GUC to control the degree of
   > parallelism and only modified the quicksort algorithm in quicksort.c.
   > Trying to 'make install' quickly shows me the patch breaks zic and
   > Andrew Gierth further pointed out on irc (a couple months back now)
   > that user defined comparison functions won't work as expected in the
   > forked processes (if I remember that correctly).
   
   I'm not sure what the problems are, but the background worker 
   infrastructure I recently posted could possibly solve this problem, as 
   those are more like normal backends. (Assuming you were forking from the 
   backend).
   
   > Hoping this could be useful, I wanted to put out what I had so far and
   > see how far away this is from something workable.  Not to mention that
   > there are probably some improvements that could be make to the
   > parallel quicksort algorithm.
   
   Thanks for sharing.
   
   Regards
   
   Markus Wanner