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 -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
