From: Marko Kreen <markokr@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Kenneth Marshall <ktm@rice.edu>
Cc: Simon Riggs <simon@2ndquadrant.com>
Cc: pgsql-patches@postgresql.org
Cc: twraney@comcast.net
Cc: neilc@samurai.com
Subject: Re: updated hash functions for postgresql v1
Date: Mon, 7 Apr 2008 10:42:51 +0300
Message-ID: <e51f66da0804070042g6fa1f903g29b93540a8ae3153@mail.gmail.com> (raw)
In-Reply-To: <711.1207497745@sss.pgh.pa.us>
References: <20071027201557.GW27320@it.is.rice.edu>
<1193592458.4242.713.camel@ebony.site>
<20071028180558.GY27320@it.is.rice.edu>
<1193602018.4242.737.camel@ebony.site>
<23832.1207424435@sss.pgh.pa.us>
<20080405214050.GA4802@it.is.rice.edu>
<711.1207497745@sss.pgh.pa.us>
On 4/6/08, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> So adopting the mixing changes would make it faster yet. What we need
> to be certain of is that this doesn't expose us to poorer hashing.
> We know that it is critical that all bits of the input affect all bits
> of the hash fairly uniformly --- otherwise we are subject to very
> serious performance hits at higher levels in hash join, for instance.
> The comments in the new code led me to worry that Jenkins had
> compromised on that property in search of speed. I looked at his
> website but couldn't find any real discussion of the design principles
> for the new mixing code ...
Scroll at the end of doobs.html, there is the longer discussion.
My understanding is following:
His design is based on 2 properties of mixing function:
- reversible - that means for each input tuple of (a,b,c) corresponds
exactly one output tuple of (a,b,c). Such property guarantees that
after repeatedly applying mixing function, no bits get lost.
- avalanche - that means any single bit change in input (a,b,c)
half of the output bits are affected.
His "insight" (as he called it) when creating lookup3 was that
the bulk mixing that is applied repeatedly does not need to
have avalanche, it only needs to be reversible, meaning all the
bits that went in, are still there after mixing repeatedly.
And only final mixing needs to have avalanche as it produces
final result, but it does not need to be reversible as it wont
be applied repeatedly and most of the result is dropped anyway.
IMHO his choices are reasonable.
--
marko
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-patches@postgresql.org
Cc: markokr@gmail.com, tgl@sss.pgh.pa.us, ktm@rice.edu, simon@2ndquadrant.com, twraney@comcast.net, neilc@samurai.com
Subject: Re: updated hash functions for postgresql v1
In-Reply-To: <e51f66da0804070042g6fa1f903g29b93540a8ae3153@mail.gmail.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