On Tue, Jun 18, 2013 at 6:11 PM, Jim Nasby <j...@nasby.net> wrote: > IIRC there's some kind of compression or something used with on-disk sorts.
I think you're mistaken. > If that's correct then I think what's happening is that the "on-disk" sort > that fits into cache > is actually using less memory than quicksort. Or perhaps it was just a matter > of memory > locality within each tape. It's been too long since I looked at it. :( External sorts do of course use less memory, but quicksort is particularly good at taking advantage of memory locality. I think it's possible that what you recall is the days when we used the OS qsort(), and we were at the mercy of the implementation that the OS provided. When we effectively began to vendor our own sort routine in 2006, we chose a high-quality one with various protections against quadratic behaviors. Implementations that lacked these protections were prevalent at a surprisingly late stage. -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
