pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedGPU Accelerated Sorting
14+ messages / 12 participants
[nested] [flat]
* GPU Accelerated Sorting
@ 2010-08-30 13:46 Eliot Gable <egable@gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: Eliot Gable @ 2010-08-30 13:46 UTC (permalink / raw)
To: pgsql-performance
Not sure if anyone else saw this, but it struck me as an interesting
idea if it could be added to PostgreSQL. GPU accelerated database
operations could be very... interesting. Of course, this could be
difficult to do in a way that usefully increases performance of
PostgreSQL, but I'll leave that up to you guys to figure out.
http://code.google.com/p/back40computing/wiki/RadixSorting
--
Eliot Gable
"We do not inherit the Earth from our ancestors: we borrow it from our
children." ~David Brower
"I decided the words were too conservative for me. We're not borrowing
from our children, we're stealing from them--and it's not even
considered to be a crime." ~David Brower
"Esse oportet ut vivas, non vivere ut edas." (Thou shouldst eat to
live; not live to eat.) ~Marcus Tullius Cicero
^ permalink raw reply [nested|flat] 14+ messages in thread
* GPU Accelerated Sorting
@ 2010-08-30 13:51 Eliot Gable <egable+pgsql-performance@gmail.com>
0 siblings, 3 replies; 14+ messages in thread
From: Eliot Gable @ 2010-08-30 13:51 UTC (permalink / raw)
To: pgsql-performance
Not sure if anyone else saw this, but it struck me as an interesting
idea if it could be added to PostgreSQL. GPU accelerated database
operations could be very... interesting. Of course, this could be
difficult to do in a way that usefully increases performance of
PostgreSQL, but I'll leave that up to you guys to figure out.
http://code.google.com/p/back40computing/wiki/RadixSorting
--
Eliot Gable
"We do not inherit the Earth from our ancestors: we borrow it from our
children." ~David Brower
"I decided the words were too conservative for me. We're not borrowing
from our children, we're stealing from them--and it's not even
considered to be a crime." ~David Brower
"Esse oportet ut vivas, non vivere ut edas." (Thou shouldst eat to
live; not live to eat.) ~Marcus Tullius Cicero
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-30 14:05 Greg Smith <greg@2ndquadrant.com>
parent: Eliot Gable <egable+pgsql-performance@gmail.com>
2 siblings, 1 reply; 14+ messages in thread
From: Greg Smith @ 2010-08-30 14:05 UTC (permalink / raw)
To: Eliot Gable <egable+pgsql-performance@gmail.com>; +Cc: pgsql-performance
Eliot Gable wrote:
> Not sure if anyone else saw this, but it struck me as an interesting
> idea if it could be added to PostgreSQL. GPU accelerated database
> operations could be very... interesting. Of course, this could be
> difficult to do in a way that usefully increases performance of
> PostgreSQL, but I'll leave that up to you guys to figure out.
>
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.
--
Greg Smith 2ndQuadrant US Baltimore, MD
PostgreSQL Training, Services and Support
greg@2ndQuadrant.com www.2ndQuadrant.us
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-30 14:56 Gaël Le Mignot <gael@pilotsystems.net>
parent: Eliot Gable <egable+pgsql-performance@gmail.com>
2 siblings, 2 replies; 14+ messages in thread
From: gael@pilotsystems.net @ 2010-08-30 14:56 UTC (permalink / raw)
To: Eliot Gable <egable+pgsql-performance@gmail.com>; +Cc: pgsql-performance
Hello,
In my humble opinion, while it can sound interesting from a theorical
point of view to outloads some operations to the GPU, there is a huge
pratical problem in current world : databases which are big enough to
require such heavy optimization are usually runned on server hardware,
which very rarely have powerful GPU.
There may be a small target of computers having both GPU and heavy
database, but that sounds very exceptional to me, so investing effort
into it sounds a bit unjustified to me.
Except as a matter of scientific research, which is it of course
important for the future.
Regards,
--
Gaël Le Mignot - gael@pilotsystems.net
Pilot Systems - 9, rue Desargues - 75011 Paris
Tel : +33 1 44 53 05 55 - www.pilotsystems.net
Gérez vos contacts et vos newsletters : www.cockpit-mailing.com
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-30 18:49 Eliot Gable <egable+pgsql-performance@gmail.com>
parent: Gaël Le Mignot <gael@pilotsystems.net>
1 sibling, 0 replies; 14+ messages in thread
From: Eliot Gable @ 2010-08-30 18:49 UTC (permalink / raw)
To: Gaël Le Mignot <gael@pilotsystems.net>; +Cc: pgsql-performance
Well, from that perspective, it becomes a "chicken and egg" problem.
Without the software support to use a GPU in a server for
acceleration, nobody's going to build a server with a GPU.
However, as previously stated, I can understand the challenges with
determining whether the offloading would even be worthwhile (given
disk performance constraints and GPU memory loading constraints vs
payoff for acceleration), much less finding actual real-world queries
that would benefit from it. I am sure there are probably hundreds of
other performance improvements that could be made that would have much
more wide-spread appeal, but it's an interesting thing to consider.
This is not the first thing that's come up that a database could use a
GPU for in order to improve performance, and it won't be the last.
It's something to keep in mind, and if enough additional items come up
where GPUs can do better than CPUs, it might be worthwhile to start
implementing some of those things. Maybe if enough of them get
implemented, there will be enough overall performance increase to make
it worthwhile to put a GPU in a database server. Besides, if you can
sort data on a GPU faster than a CPU, you can probably also search for
data faster on the GPU than on the CPU under similar conditions. With
memory increasing like crazy in servers, it might be worthwhile to
keep indexes entirely in memory (but keep them sync'd to the disk,
obviously) and for extremely large tables, dump them to the GPU for a
massively parallel search. In fact, if you can get enough GPU memory
that you could keep them entirely in the GPU memory and keep them
updated there any time they change, you could see some real
performance pay-offs.
I'm not saying someone should just go out and do this right now, but
it might be worthwhile to keep it in mind as code is re-written or
updated in the future how it might be structured to more easily
implement something like this in the future.
On Mon, Aug 30, 2010 at 10:56 AM, Gaël Le Mignot <gael@pilotsystems.net> wrote:
> Hello,
>
> In my humble opinion, while it can sound interesting from a theorical
> point of view to outloads some operations to the GPU, there is a huge
> pratical problem in current world : databases which are big enough to
> require such heavy optimization are usually runned on server hardware,
> which very rarely have powerful GPU.
>
> There may be a small target of computers having both GPU and heavy
> database, but that sounds very exceptional to me, so investing effort
> into it sounds a bit unjustified to me.
>
> Except as a matter of scientific research, which is it of course
> important for the future.
>
> Regards,
>
> --
> Gaël Le Mignot - gael@pilotsystems.net
> Pilot Systems - 9, rue Desargues - 75011 Paris
> Tel : +33 1 44 53 05 55 - www.pilotsystems.net
> Gérez vos contacts et vos newsletters : www.cockpit-mailing.com
>
--
Eliot Gable
"We do not inherit the Earth from our ancestors: we borrow it from our
children." ~David Brower
"I decided the words were too conservative for me. We're not borrowing
from our children, we're stealing from them--and it's not even
considered to be a crime." ~David Brower
"Esse oportet ut vivas, non vivere ut edas." (Thou shouldst eat to
live; not live to eat.) ~Marcus Tullius Cicero
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-30 19:25 Yeb Havinga <yebhavinga@gmail.com>
parent: Greg Smith <greg@2ndquadrant.com>
0 siblings, 1 reply; 14+ messages in thread
From: Yeb Havinga @ 2010-08-30 19:25 UTC (permalink / raw)
To: Greg Smith <greg@2ndquadrant.com>; +Cc: Eliot Gable <egable+pgsql-performance@gmail.com>; pgsql-performance
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
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-30 20:43 Scott Marlowe <scott.marlowe@gmail.com>
parent: Gaël Le Mignot <gael@pilotsystems.net>
1 sibling, 1 reply; 14+ messages in thread
From: Scott Marlowe @ 2010-08-30 20:43 UTC (permalink / raw)
To: Gaël Le Mignot <gael@pilotsystems.net>; +Cc: Eliot Gable <egable+pgsql-performance@gmail.com>; pgsql-performance
On Mon, Aug 30, 2010 at 8:56 AM, Gaël Le Mignot <gael@pilotsystems.net> wrote:
> Hello,
>
> In my humble opinion, while it can sound interesting from a theorical
> point of view to outloads some operations to the GPU, there is a huge
> pratical problem in current world : databases which are big enough to
> require such heavy optimization are usually runned on server hardware,
> which very rarely have powerful GPU.
That's changed recently:
http://www.aberdeeninc.com/abcatg/GPUservers.htm
> There may be a small target of computers having both GPU and heavy
> database, but that sounds very exceptional to me, so investing effort
> into it sounds a bit unjustified to me.
I tend to agree. OTOH, imagine using a 400 core GPU for offloading
stuff that isn't just a sort, like travelling salesman type problems.
The beauty of if is, that with pgsql support dozens of scripting
languages, you wouldn't have to build anything into pg's backends, you
could just write it in a pl langauge.
--
To understand recursion, one must first understand recursion.
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-30 20:47 David Boreham <david_list@boreham.org>
parent: Scott Marlowe <scott.marlowe@gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: David Boreham @ 2010-08-30 20:47 UTC (permalink / raw)
To: pgsql-performance
Feels like I fell through a worm hole in space/time, back to inmos in
1987, and a guy from marketing has just
walked in the office going on about there's a customer who wants to use
our massively parallel hardware to speed up databases...
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-30 21:18 Chris Browne <cbbrowne@acm.org>
parent: David Boreham <david_list@boreham.org>
0 siblings, 1 reply; 14+ messages in thread
From: Chris Browne @ 2010-08-30 21:18 UTC (permalink / raw)
To: pgsql-performance
david_list@boreham.org (David Boreham) writes:
> Feels like I fell through a worm hole in space/time, back to inmos in
> 1987, and a guy from marketing has just
> walked in the office going on about there's a customer who wants to
> use our massively parallel hardware to speed up databases...
... As long as you're willing to rewrite PostgreSQL in Occam 2...
--
http://projects.cs.kent.ac.uk/projects/tock/trac/
The statistics on sanity are that one out of every four Americans is
suffering from some form of mental illness. Think of your three best
friends. If they're okay, then it's you. -- Rita Mae Brown
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-30 22:01 Jeff Davis <pgsql@j-davis.com>
parent: Eliot Gable <egable+pgsql-performance@gmail.com>
2 siblings, 0 replies; 14+ messages in thread
From: Jeff Davis @ 2010-08-30 22:01 UTC (permalink / raw)
To: Eliot Gable <egable+pgsql-performance@gmail.com>; +Cc: pgsql-performance
On Mon, 2010-08-30 at 09:51 -0400, Eliot Gable wrote:
> Not sure if anyone else saw this, but it struck me as an interesting
> idea if it could be added to PostgreSQL. GPU accelerated database
> operations could be very... interesting. Of course, this could be
> difficult to do in a way that usefully increases performance of
> PostgreSQL, but I'll leave that up to you guys to figure out.
>
> http://code.google.com/p/back40computing/wiki/RadixSorting
>
Radix sort is not a comparison sort. Comparison sorts work for any data
type for which you define a total order; and any total order is allowed.
Radix sort only works for some data types and some total orders.
However, it would be very nice to use radix sorting where it does work.
That would require some extensions to the type system, but it could be
done.
The GPU issue is orthogonal.
Regards,
Jeff Davis
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-30 22:37 David Boreham <david_list@boreham.org>
parent: Chris Browne <cbbrowne@acm.org>
0 siblings, 0 replies; 14+ messages in thread
From: David Boreham @ 2010-08-30 22:37 UTC (permalink / raw)
To: pgsql-performance
On 8/30/2010 3:18 PM, Chris Browne wrote:
> ... As long as you're willing to rewrite PostgreSQL in Occam 2...
Just re-write it in Google's new language 'Go' : it's close enough to
Occam and they'd probably fund the project..
;)
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-31 01:17 Scott Carey <scott@richrelevance.com>
parent: Yeb Havinga <yebhavinga@gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: Scott Carey @ 2010-08-31 01:17 UTC (permalink / raw)
To: Yeb Havinga <yebhavinga@gmail.com>; +Cc: Greg Smith <greg@2ndquadrant.com>; Eliot Gable <egable+pgsql-performance@gmail.com>; 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@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-08-31 01:58 Tom Lane <tgl@sss.pgh.pa.us>
parent: Scott Carey <scott@richrelevance.com>
0 siblings, 0 replies; 14+ messages in thread
From: Tom Lane @ 2010-08-31 01:58 UTC (permalink / raw)
To: Scott Carey <scott@richrelevance.com>; +Cc: Yeb Havinga <yebhavinga@gmail.com>; Greg Smith <greg@2ndquadrant.com>; Eliot Gable <egable+pgsql-performance@gmail.com>; pgsql-performance
Scott Carey <scott@richrelevance.com> writes:
> 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).
In Postgres, the swaps are pretty much free compared to the
comparisons. Sorry, but the above doesn't especially tempt me...
regards, tom lane
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: GPU Accelerated Sorting
@ 2010-09-21 19:27 Robert Haas <robertmhaas@gmail.com>
parent: Eliot Gable <egable@gmail.com>
0 siblings, 0 replies; 14+ messages in thread
From: Robert Haas @ 2010-09-21 19:27 UTC (permalink / raw)
To: Eliot Gable <egable@gmail.com>; +Cc: pgsql-performance
On Mon, Aug 30, 2010 at 9:46 AM, Eliot Gable <egable@gmail.com> wrote:
> Not sure if anyone else saw this, but it struck me as an interesting
> idea if it could be added to PostgreSQL. GPU accelerated database
> operations could be very... interesting. Of course, this could be
> difficult to do in a way that usefully increases performance of
> PostgreSQL, but I'll leave that up to you guys to figure out.
>
> http://code.google.com/p/back40computing/wiki/RadixSorting
It would be hard to use this because, in addition to the fact that
this is specific to a very particular type of hardware, it only works
if you're trying to do a very particular type of sort. For example,
it wouldn't handle multi-byte characters properly. And it wouldn't
handle integers properly either - you'd end up sorting negatives after
positives. You could possibly still find applications for it but
they'd be quite narrow, I think.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company
^ permalink raw reply [nested|flat] 14+ messages in thread
end of thread, other threads:[~2010-09-21 19:27 UTC | newest]
Thread overview: 14+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2010-08-30 13:46 GPU Accelerated Sorting Eliot Gable <egable@gmail.com>
2010-09-21 19:27 ` Robert Haas <robertmhaas@gmail.com>
2010-08-30 13:51 GPU Accelerated Sorting Eliot Gable <egable+pgsql-performance@gmail.com>
2010-08-30 14:05 ` Greg Smith <greg@2ndquadrant.com>
2010-08-30 19:25 ` Yeb Havinga <yebhavinga@gmail.com>
2010-08-31 01:17 ` Scott Carey <scott@richrelevance.com>
2010-08-31 01:58 ` Tom Lane <tgl@sss.pgh.pa.us>
2010-08-30 14:56 ` Gaël Le Mignot <gael@pilotsystems.net>
2010-08-30 18:49 ` Eliot Gable <egable+pgsql-performance@gmail.com>
2010-08-30 20:43 ` Scott Marlowe <scott.marlowe@gmail.com>
2010-08-30 20:47 ` David Boreham <david_list@boreham.org>
2010-08-30 21:18 ` Chris Browne <cbbrowne@acm.org>
2010-08-30 22:37 ` David Boreham <david_list@boreham.org>
2010-08-30 22:01 ` Jeff Davis <pgsql@j-davis.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox