pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Gregory Maxwell <gmaxwell@gmail.com>
To: Ron Peacetree <rjpeace@earthlink.net>
Cc: Jeffrey W. Baker <jwbaker@acm.org>
Cc: pgsql-hackers@postgresql.org
Cc: pgsql-performance@postgresql.org
Subject: Re: [PERFORM] A Better External Sort?
Date: Fri, 30 Sep 2005 22:07:16 -0400
Message-ID: <e692861c0509301907r7f1cd5b8h8b2b1f3a85321313@mail.gmail.com> (raw)
In-Reply-To: <21402654.1127923414088.JavaMail.root@elwamui-polski.atl.sa.earthlink.net>
References: <21402654.1127923414088.JavaMail.root@elwamui-polski.atl.sa.earthlink.net>

On 9/28/05, Ron Peacetree <rjpeace@earthlink.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. ;)



view thread (112+ messages)  latest in thread

Message-ID: <e692861c0509301907r7f1cd5b8h8b2b1f3a85321313@mail.gmail.com>
Permalink:  ../e692861c0509301907r7f1cd5b8h8b2b1f3a85321313@mail.gmail.com/
Also on:    postgresql.org/message-id/e692861c0509301907r7f1cd5b8h8b2b1f3a85321313@mail.gmail.com

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-performance@postgresql.org
  Cc: gmaxwell@gmail.com, rjpeace@earthlink.net, jwbaker@acm.org, pgsql-hackers@postgresql.org
  Subject: Re: [PERFORM] A Better External Sort?
  In-Reply-To: <e692861c0509301907r7f1cd5b8h8b2b1f3a85321313@mail.gmail.com>
  References: <21402654.1127923414088.JavaMail.root@elwamui-polski.atl.sa.earthlink.net> <e692861c0509301907r7f1cd5b8h8b2b1f3a85321313@mail.gmail.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox