Sorry about the delay for this update to the new hash
index implementation. I was trying to get the WAL logging
in place and forgot to post the actual patch. The WAL
for hash indexes will need to wait for 8.5, but I did
want to add back in the piece of the Bob Jenkins 2006
hash function that was stripped out of the initial
patch on application due to concerns about the randomness
of the resulting hash values. Here is a re-post of my
initial findings comparing the old/new Jenkins hash
from lookup2 and lookup3. I have added a third column
containing the results for the hash_any() resulting
from the attached patch as well as simple timing test
for a DB reindex both before and after patching.
Also attached is a simple documentation patch updating
the note attached to the hash index description.
Regards,
Ken
----------------------------------------------------
Hi,
I have finally had a chance to do some investigation on
the performance of the old hash mix() function versus
the updated mix()/final() in the new hash function. Here
is a table of my current results for both the old and the
new hash function. In this case cracklib refers to the
cracklib-dict containing 1648379 unique words massaged
in various ways to generate input strings for the hash
functions. The result is the number of collisions in the
hash values generated.
hash input old new newv2
---------- --- --- -----
cracklib 338 316 338
cracklib x 2 (i.e. clibclib) 305 319 300
cracklib x 3 (clibclibclib) 323 329 315
cracklib x 10 302 310 329
cracklib x 100 350 335 298
cracklib x 1000 314 309 315
cracklib x 100 truncated to char(100) 311 327 320
uint32 from 1-1648379 309 319 347
(uint32 1-1948379)*256 309 314 304
(uint32 1-1948379)*16 310 314 324
"a"uint32 (i.e. a00001,a0002...) 320 321 312
uint32uint32 (i.e. uint64) 321 287 309
The different result columns are old = Jenkins 1996 hash
function(lookup2.c), new = Jenkins 2006 hash function
(lookup3.c), and newv2 = adaptation of current hash_any()
to incorporate the separate mix()/final() functions. As
you can see from the results, spliting the mix() and final()
apart does not result in any perceptible loss of randomness
in the hash assignment. I also ran a crude timing for a
reindex of the following database:
CREATE TABLE dict (word text);
CREATE INDEX wordhash ON dict USING hash (word);
INSERT INTO dict (word) VALUES('s;lhkjdpyoijxfg;lktjgh;sdlhkjo');
INSERT INTO dict (SELECT MAX(word)||MAX(word) FROM dict);
... (21 times)
REINDEX TABLE
...
The average time to reindex the table using our current
hash_any() without the separate mix()/final() was 1696ms
and 1482ms with the separate mix()/final() stages giving
almost 13% better performance for this stupid metric.