From: Mark Lewis <mark.lewis@mir3.com>
To: Mischa Sandberg <mischa.sandberg@telus.net>
Cc: pgsql-general@postgresql.org
Cc: pgsql-performance@postgresql.org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Date: Tue, 10 May 2005 15:46:04 -0700
Message-ID: <1115765164.13684.25.camel@amateljan.mirlogic.com> (raw)
In-Reply-To: <1115760957.4281293e0155b@webmail.telus.net>
References: <427F6853.90308@cs.concordia.ca>
<427F757A.8000407@samurai.com>
<59d991c405050908271b55e673@mail.gmail.com>
<427F8321.5030702@samurai.com>
<20050509163423.GH35026@decibel.org>
<427F9211.2090008@samurai.com>
<20050509165133.GJ35026@decibel.org>
<427FFCD3.1010803@samurai.com>
<20050510153245.GA31103@decibel.org>
<1115760957.4281293e0155b@webmail.telus.net>
If the original paper was published in 1984, then it's been more than 20
years. Any potential patents would already have expired, no?
-- Mark Lewis
On Tue, 2005-05-10 at 14:35, Mischa Sandberg wrote:
> Quoting "Jim C. Nasby" <decibel@decibel.org>:
>
> > Well, in a hash-join right now you normally end up feeding at least
> > one
> > side of the join with a seqscan. Wouldn't it speed things up
> > considerably if you could look up hashes in the hash index instead?
>
> You might want to google on "grace hash" and "hybrid hash".
>
> The PG hash join is the simplest possible: build a hash table in memory,
> and match an input stream against it.
>
> *Hybrid hash* is where you spill the hash to disk in a well-designed
> way. Instead of thinking of it as building a hash table in memory, think
> of it as partitioning one input; if some or all of it fits in memory,
> all the better. The boundary condition is the same.
>
> The real wizard of hybrid hash has to be Goetz Graefe, who sadly has now
> joined the MS Borg. He demonstrated that for entire-table joins, hybrid
> hash completely dominates sort-merge. MSSQL now uses what he developed
> as an academic, but I don't know what the patent state is.
>
> "Grace hash" is the original implementation of hybrid hash:
> Kitsuregawa, M., Tanaka, H., and Moto-oka, T. (1984).
> Architecture and Performance of Relational Algebra Machine Grace.
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo@postgresql.org so that your
> message can get through to the mailing list cleanly
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 using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: mark.lewis@mir3.com, mischa.sandberg@telus.net, pgsql-general@postgresql.org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
In-Reply-To: <1115765164.13684.25.camel@amateljan.mirlogic.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