pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
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




view thread (24+ messages)  latest in thread

Message-ID: <87vfjw5fp5.fsf@stark.xeocode.com>
Permalink:  ../87vfjw5fp5.fsf@stark.xeocode.com/
Also on:    postgresql.org/message-id/87vfjw5fp5.fsf@stark.xeocode.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 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