From: Greg Stark <gsstark@mit.edu>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Greg Stark <gsstark@mit.edu>
Cc: Dennis Bjorklund <db@zigo.dhs.org>
Cc: Bruno Wolff III <bruno@wolff.to>
Cc: Jim C. Nasby <jim@nasby.net>
Cc: pgsql-performance@postgresql.org
Subject: Re: Horribly slow hash join
Date: 19 Apr 2004 08:12:54 -0400
Message-ID: <87vfjw5fp5.fsf@stark.xeocode.com> (raw)
In-Reply-To: <16041.1082354970@sss.pgh.pa.us>
References: <Pine.LNX.4.44.0404190640010.4551-100000@zigo.dhs.org>
<874qrg7cy8.fsf@stark.xeocode.com>
<16041.1082354970@sss.pgh.pa.us>
Tom Lane <tgl@sss.pgh.pa.us> writes:
> Greg Stark <gsstark@mit.edu> writes:
> > If the hash tables were made a power of two then it would be possible to mix
> > the bits of the 32 bit value and just mask off the unneeded bits. I've found
> > one page via google that mentions mixing bits in a hash function, but I would
> > look for a more serious treatment somewhere.
> Modding by a *non* power of 2 (esp. a prime) mixes the bits quite well,
> and is likely faster than any multiple-instruction way to do the same.
Well a) any number that has any factors of two fails to mix in some bits.
That's a lot more common than non powers of two. b) The postgres code makes no
attempt to make the number of buckets a prime and c) Even if the number of
buckets were prime then it seems it would still be too easy to find real-world
data where all the data have that prime as a factor. As it is they only need
to have common factors to lose.
> The quoted article seems to be by someone who has spent a lot of time
> counting assembly cycles and none at all reading the last thirty years
> worth of CS literature.
Yes, well I did note that.
--
greg
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: gsstark@mit.edu, tgl@sss.pgh.pa.us, db@zigo.dhs.org, bruno@wolff.to, jim@nasby.net
Subject: Re: Horribly slow hash join
In-Reply-To: <87vfjw5fp5.fsf@stark.xeocode.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