From: Mischa Sandberg <mischa.sandberg@telus.net>
To: pgsql-general@postgresql.org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Date: Tue, 10 May 2005 17:14:26 -0700
Message-ID: <1115770466.42814e62cb0e1@webmail.telus.net> (raw)
In-Reply-To: <1115765164.13684.25.camel@amateljan.mirlogic.com>
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>
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.
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: mischa.sandberg@telus.net, pgsql-general@postgresql.org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
In-Reply-To: <1115770466.42814e62cb0e1@webmail.telus.net>
* 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