Re: Parallel Sort

On Fri, May 24, 2013 at 01:13:21PM -0500, Jim Nasby wrote:
> On 5/13/13 9:28 AM, Noah Misch wrote:
>> It would be great if one client session could take advantage of multiple CPU
>> cores.  EnterpriseDB wishes to start the trek into this problem space for 9.4
>> by implementing parallel internal (i.e. not spilling to disk) sort.  This
>> touches on a notable subset of the infrastructure components we'll need for
>> parallel general query.  My intent is to map out the key design topics, hear
>> about critical topics I hadn't considered, and solicit feedback on the quality
>> of the high-level plan.  Full designs for key pieces will come later.
>
> Have you considered GPU-based sorting? I know there's been discussion in the past.

I had considered it briefly.

Parallel sort is mainly valuable for expensive comparison operators.  Sorting
int4, for example, is too cheap for parallelism to be compelling.  (In my test
build of a 16 GiB int4 index, sorting took 11s of the 391s build time.)
However, expensive operators are also liable to be difficult to reimplement
for the GPU.  In particular, implementing a GPU-based strcoll() for bttextcmp
sounds like quite a project in its own right.

> To me, the biggest advantage of GPU sorting is that most of the concerns you've laid out go away; a backend that
needsto sort just throws data at the GPU to do the actual sorting; all the MVCC issues and what not remain within the
scopeof a single backend.
 

Those are matters we would eventually need to address as we parallelize more
things, so I regard confronting them as an advantage.  Among other benefits,
this project is a vehicle for emplacing some infrastructure without inviting
the full complexity entailed by loftier goals.

Thanks,
nm

-- 
Noah Misch
EnterpriseDB                                 http://www.enterprisedb.com