Re: Hash support for arrays

From: Kenneth Marshall <ktm(at)rice(dot)edu>
To: Nicolas Barbier <nicolas(dot)barbier(at)gmail(dot)com>
Cc: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Robert Haas <robertmhaas(at)gmail(dot)com>, marcin mank <marcin(dot)mank(at)gmail(dot)com>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: Hash support for arrays
Date: 2010-11-03 13:23:14
Message-ID: 20101103132314.GZ27429@aart.is.rice.edu
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Wed, Nov 03, 2010 at 10:24:16AM +0100, Nicolas Barbier wrote:
> 2010/11/2 Kenneth Marshall <ktm(at)rice(dot)edu>:
>
> > Given that our hash implimentation mixes the input data well (It does.
> > I tested it.) then a simple rotate-and-xor method is all that should
> > be needed to maintain all of the needed information. The original
> > hash function has done the heavy lifting in this case.
>
> Even with the perfect hash function for the elements, certain
> combinations of elements could still lead to massive collisions. E.g.,
> if repeated values are typical in the input data we are talking about,
> then the rotate-and-xor method would still lead to collisions between
> any array of the same values of certain lengths, regardless of the
> value. In Tom's implementation, as he mentioned before, those
> problematical lengths would be multiples of 32 (e.g., an array of 32
> 1s would collide with an array of 32 2s would collide with an array of
> 32 3s, etc).
>
> Nicolas
>

True. I just took another look at our defined hash functions and it
looks like we can make a simple variant of hash_uint32() that we
can use as a stream checksum. The only thing missing is that ability
to pass in the current 32-bit hash value as a starting seed to add
the next 32-bit value. Something like this should work:

Datum
hash_uint32(uint32 k, uint32 initval)
{
register uint32 a,
b,
c;

a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095 + initval;
a += k;

final(a, b, c);

/* report the result */
return UInt32GetDatum(c);
}

Then if you pass in the current value as the initval, it should mix
well each additional 32-bit hash value.

Regards,
Ken

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2010-11-03 14:31:55 Re: pgsql: Bootstrap WAL to begin at segment logid=0 logseg=1 (000000010000
Previous Message Heikki Linnakangas 2010-11-03 10:00:31 Re: pgsql: Bootstrap WAL to begin at segment logid=0 logseg=1 (000000010000