Message-ID: <1115770466.42814e62cb0e1@webmail.telus.net>
Date: Tue, 10 May 2005 17:14:26 -0700
From: Mischa Sandberg <mischa.sandberg@telus.net>
To: pgsql-general@postgresql.org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
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>
	<1115765164.13684.25.camel@amateljan.mirlogic.com>
In-Reply-To: <1115765164.13684.25.camel@amateljan.mirlogic.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
User-Agent: Internet Messaging Program (IMP) 3.1-cvs

Quoting Mark Lewis <mark.lewis@mir3.com>:

> If the original paper was published in 1984, then it's been more than
> 20 years.  Any potential patents would already have expired, no?

Don't know, but the idea is pervasive among different vendors ...
perhaps that's a clue. 

And having now read beyond the start of ExecHashJoin(), I can see that
PG does indeed implement Grace hash; and the implementation is nice and
clean.

If there were room for improvement, (and I didn't see it in the source)
it would be the logic to:

- swap inner and outer inputs (batches) when the original inner turned
out to be too large for memory, and the corresponding outer did not. If
you implement that anyway (complicates the loops) then it's no trouble
to just hash the smaller of the two, every time; saves some CPU.

- recursively partition batches where both inner and outer input batch
ends up being too large for memory, too; or where the required number of
batch output buffers alone is too large for working RAM. This is only
for REALLY big inputs.

Note that you don't need a bad hash function to get skewed batch sizes;
you only need a skew distribution of the values being hashed.