> -----Original Message-----
> From: Ron Peacetree [mailto:rjpeace@earthlink.net] 
> Sent: Tuesday, April 08, 2003 3:07 PM
> To: pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] No merge sort?
> 
> 
> ""Dann Corbit"" <DCorbit@connx.com> wrote in message 
> news:D90A5A6C612A39408103E6ECDD77B829408AC4@voyager.corporate.connx.co
> m...
> > There can be a problem here Distribution & Radix sorts.  Imagine the
> following query:
> > SELECT company, division, plant, sum(revenue) FROM corporate GROUP
> BY
> > company, division, plant ORDER BY company, division, plant
> >
> > Let's suppose further that company, division, and plant are all char
> 20.
> > For a given section of company + division, the first 40 characters
> will
> > be the same.  So a radix or distribution sort will need 40 passes
> over
> > the identical data before it even gets to the differentiating field 
> > plant.
> >
> 1= Distribution sort does not have this problem.  Any data 
> that can be constrained by the "pigeon hole principle" can be 
> sorted in o(n) time. 

Distribution sort is not an algorithm.  It is a general technique.  Both
counting sort and radix sort are distribution sorts.  I think you are
talking about counting sort here.  In order to insert a technique into a
database, you must solve the general case.

>2= For Radis sort, that's iff ("if and 
> only if") you use =characters= as the radix of a radix sort 
> and do a MSB aka partition-exchange sort. The appropriate 
> radix here is a =field= not a character.  Since there are 3 
> fields vs 60 characters the problem becomes 2/3 wasted passes 
> instead of 40/60.  

This is lunacy.  If you count the field or use it as a radix, you will
need a radix of 40*8 bits = 320 bits.  That means you will have 2^320 =
2.136e96 bins.

>We can do even better by making one field for
> company+division and one for plant.  Now we have no wasted passes and
> an O(n) sort.  Since PostgreSQL has wonderful built in 
> support for string handling and regexp, this is clearly an 
> easy to implement and superior approach.

You have no idea what you are talking about.
 
> Since a comparison based sorting algorithm would be best 
> implemented by working on the same atomic units, the fair 
> comparison becomes the
> log(n!) behavior of that sort vs the O(n) behavior of 
> Distribution or Radix sort on data of that atomic size.  The 
> constants involved in each ordering operation are bigger for 
> the two O(n) sorts, but despite that you'll find that for 
> reasonable sizes of real world data, you'll complete the O(n) 
> sorts 2-3X faster.

With 2e96 * 4 space requirement (assuming that 4 billion is the largest
row count allowed in the database).  If we could build a memory that
large, how long would it take to reach the last bin?  There are an
estimated 10^80 elementary particles in the universe.
 
> Of course, internal sorting performance is vastly dominated 
> by disk I/O costs if there is even a moderate amount disk I/O 
> involved.  However, there are ways to combine decent internal 
> sorting with efficient disk merging, getting the best 
> possible out of both subsystems.

You are confusing terms here.  An internal sort is performed 100% in
memory.  It is an external sort that uses disk space.

> > If they are fixed width, we could use LSD radix sort and count all
> the
> > bins in one pass.  But that technique will fail with varchar. 
> > Naturally, most long character fields will be varchar.  The basic
> upshot
> > is that radix and distribution sorts work best with short keys.
> >
> More accurate would be say that such searches work best with 
> keys that have as little in common as possible to each other. 
>  Length isn't the problem, =the number of unique keys= and 
> having few equal keys is. Large quantities of equal keys can 
> trash the performance of many sorting algorithms, including 
> quicksort, unless steps are taken to either modify the 
> algorithm to handle it or the data to minimize such an occurrence.

I would guess that you have never done any sorting work.
> ---------------------------(end of 
> broadcast)---------------------------
> TIP 1: subscribe and unsubscribe commands go to 
> majordomo@postgresql.org
> 


Wed, 9 Apr 2003 10:54:39 -0700
"Dann Corbit" <DCorbit@connx.com>
Re: No merge sort?
""Dann Corbit"" <DCorbit@connx.com> wrote in message
news:D90A5A6C612A39408103E6ECDD77B829408AC6@voyager.corporate.connx.co
m...
> Distribution sort is not an algorithm.  It is a general technique.
Both
> counting sort and radix sort are distribution sorts.  I think you
are
> talking about counting sort here.  In order to insert a technique
into a
> database, you must solve the general case.
>
Terminology problem.  Please look in the references I posted.


> > 2= For Radix sort, that's iff ("if and only if") you use
> > =characters= as the radix of a radix sort
> > and do a MSB aka partition-exchange sort. The appropriate
> > radix here is a =3Dfield=3D not a character.  Since there are 3
> > fields vs 60 characters the problem becomes 2/3 wasted passes
> > instead of 40/60.
>
> This is lunacy.  If you count the field or use it as a radix, you
will
> need a radix of 40*8 bits= 320 bits.  That means you will have 2^320
> 2.136e96 bins.
>
You only need as many bins as you have unique key values silly ;-)
Remember, at its core Radix sort is just a distribution counting sort
(that's the name I learned for the general technique).  The simplest
implementation uses bits as the atomic unit, but there's nothing
saying you have to...  In a DB, we know all the values of the fields
we currently have stored in the DB.  We can take advantage of that.

As you correctly implied, the goal is to minimize the number of unique
bins you have to, err, distribute, items into.  That and having as few
duplicates as feasible are the important points.

If, for example, we have <= 255 possible values for the each radix
(Using your previous example, let's say you have <= 255 unique values
for the combined field "Company+Division" in the DB and the same for
"Plant" ), and 4 sets of radix to sort over, it doesn't matter if we
are sorting a 32b quantity using a radix of 8b, or a 4 field quantity
using a radix of one field (TBF, we should use key and index
techniques to minimize the amount of actual data we retrieve and
manipulate from disk during the sort.  We want to minimize disk I/O,
particularly seeking disk I/O).  The situations are analogous.

Note TANSTAAFL (as Heinlein would've said):  We have to use extra
space for mapping the radix values to the radix keys, and our "inner
loop" for the sorting operation is considerably more complicated than
that for a quicksort or a mergesort.  Hence the fact that even though
this is an O(n) technique, in real world terms you can expect only a
2-3X performance improvement over say quicksort for realistic amounts
of data.

Oh and FTR, IME for most "interesting" sorts in the DB domain, even
for "internal" sorting techniques, the time to read data from disk and
(possibly) write results back to disk tends to dominate the time spent
actually doing the internal sort...

I learned tricks like this 20 years ago.  I thought this stuff was
part of general lore in the DB field... *shrug*


Wed, 09 Apr 2003 19:38:13 GMT
"Ron Peacetree" <rjpeace@earthlink.net>
Re: No merge sort?