> -----Original Message-----
> From: Greg Stark [mailto:gsstark@mit.edu] 
> Sent: Monday, April 07, 2003 1:50 PM
> To: Dann Corbit
> Cc: Greg Stark; pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] No merge sort?
> 
> 
> 
> > floats are typically 64 - 96 bytes, bigints can be 
> arbitrarily large.
> > 
> > Floats are generally 8 bytes.
> 
> Er, I meant "bits" there. oops.
> 
> I'm still reading the other stuff.
> 
> Most of this usually comes down to differences between theory 
> and practice. The constants often matter a whole lot, and the 
> cache behaviour and memory usage can matter a whole lot. 
> quicksort after all is actually O(n^2) worst case...

By the use of a randomized sample of min(n,max(3,log(n))) elements, the
probability of choosing the worst case median is so close to zero as to
never happen in practice.  In real life, a well written quicksort will
beat the pants off of heapsort and mergesort.

In database work, the disk I/O is the most important issue.  Hence,
replacement selection or a priority-queue based approach should be used.

When sorting data, if all the information fits into memory any good
O(n*log(n)) technique is probably good enough. For one million records,
n*log2(n) is just 20 million.  20 million comparison and exchange
operations are an eye-blink on fast, modern hardware when performed in
memory.  The thing we should worry about is what happens when disk I/O
rears its ugly head.  You have a better solution to that situation, and
you have a better sorting routine for a database.


Mon, 7 Apr 2003 14:00:51 -0700
"Dann Corbit" <DCorbit@connx.com>
Re: No merge sort?

"Dann Corbit" <DCorbit@connx.com> writes:

> By the use of a randomized sample of min(n,max(3,log(n))) elements, the
> probability of choosing the worst case median is so close to zero as to
> never happen in practice.  

Not exactly. In fact the probability is no different than otherwise, but it
won't be repeatable and it won't be on common data sets like pre-sorted data.

> When sorting data, if all the information fits into memory any good
> O(n*log(n)) technique is probably good enough. For one million records,
> n*log2(n) is just 20 million.  20 million comparison and exchange
> operations are an eye-blink on fast, modern hardware when performed in
> memory.  

Woah, this is extremely dangerous thinking. For all you know the application
needs to execute this sort 200 times per second... 

Applications that can execute their queries entirely in memory are frequently
OLTP applications that need response within a hard upper limit. Often that
upper limit is measured in milliseconds...

> The thing we should worry about is what happens when disk I/O rears its ugly
> head. You have a better solution to that situation, and you have a better
> sorting routine for a database.

Not "better" just different. When dealing with disk I/O the database has to
use an algorithm that doesn't require too much random access reads. Disk is
quite fast at reading and writing sequentially but extremely slow and random
access.


While I/O bandwidth is often the bottleneck on databases it's also a lot
easier to deal with. You can make huge stripesets and use super fast i/o
controllers, to the point of saturating the machine's internal bus. It's much
harder to increase the amount of cpu cycles available.

Actually, in my experience cpu has been a bottleneck as often as disk i/o. But
my experience is quite heavily skewed to OLTP applications.

--
greg


07 Apr 2003 18:05:56 -0400
Greg Stark <gsstark@mit.edu>
Re: No merge sort?