Re: [PERFORM] A Better External Sort?

[Gregory Maxwell <gmaxwell(at)gmail(dot)com>]

On 9/28/05, Ron Peacetree <rjpeace(at)earthlink(dot)net> wrote:
> 2= We use my method to sort two different tables.  We now have these
> very efficient representations of a specific ordering on these tables.  A
> join operation can now be done using these Btrees rather than the
> original data tables that involves less overhead than many current
> methods.

If we want to make joins very fast we should implement them using RD
trees. For the example cases where a join against a very large table
will produce a much smaller output, a RD tree will provide pretty much
the optimal behavior at a very low memory cost.

On the subject of high speed tree code for in-core applications, you
should check out http://judy.sourceforge.net/ . The performance
(insert, remove, lookup, AND storage) is really quite impressive.
Producing cache friendly code is harder than one might expect, and it
appears the judy library has already done a lot of the hard work. 
Though it is *L*GPLed, so perhaps that might scare some here away from
it. :) and good luck directly doing joins with a LC-TRIE. ;)