Skip site navigation (1) Skip section navigation (2)

Re: GPU Accelerated Sorting

From: Scott Carey <scott(at)richrelevance(dot)com>
To: Yeb Havinga <yebhavinga(at)gmail(dot)com>
Cc: Greg Smith <greg(at)2ndquadrant(dot)com>, Eliot Gable<egable+pgsql-performance(at)gmail(dot)com>, "pgsql-performance(at)postgresql(dot)org"<pgsql-performance(at)postgresql(dot)org>
Subject: Re: GPU Accelerated Sorting
Date: 2010-08-31 01:17:48
Message-ID: A4002E6D-07FE-4655-B383-7C1F05B2BBB6@richrelevance.com (view raw or flat)
Thread:
Lists: pgsql-performance
On a similar note, is Postgres' Quicksort a dual-pivot quicksort?  This can be up to 2x as fast as a normal quicksort (25% fewer swap operations, and swap operations are more expensive than compares for most sorts).

Just google 'dual pivot quicksort' for more info.  


And before anyone asks -- two pivots (3 partitions) is optimal.  See http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-September/002676.html


On Aug 30, 2010, at 12:25 PM, Yeb Havinga wrote:

> Greg Smith wrote:
>> This comes up every year or so.  The ability of GPU offloading to help 
>> with sorting has to overcome the additional latency that comes from 
>> copying everything over to it and then getting all the results back.  
>> If you look at the typical types of sorting people see in PostgreSQL, 
>> it's hard to find ones that are a) big enough to benefit from being 
>> offloaded to the GPU like that, while also being b) not so 
>> bottlenecked on disk I/O that speeding up the CPU part matters.  And 
>> if you need to sort something in that category, you probably just put 
>> an index on it instead and call it a day.
>> 
>> If you made me make a list of things I'd think would be worthwhile to 
>> spend effort improving in PostgreSQL, this would be on the research 
>> list, but unlikely to even make my personal top 100 things that are 
>> work fiddling with.
> Related is 'Parallelizing query optimization' 
> (http://www.vldb.org/pvldb/1/1453882.pdf) in which they actually 
> experiment with PostgreSQL. Note that their target platform is general 
> purpose CPU, not a SIMD GPU processor.
> 
> -- Yeb
> 
> 
> -- 
> Sent via pgsql-performance mailing list (pgsql-performance(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-performance


In response to

Responses

pgsql-performance by date

Next:From: Jose Ildefonso Camargo TolosaDate: 2010-08-31 01:29:35
Subject: Re: Performance on new 64bit server compared to my 32bit desktop
Previous:From: David FetterDate: 2010-08-31 00:31:13
Subject: Re: slow DDL creation

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group