hashtext () and collisions

From: "Leon Mergen" <leon(at)solatis(dot)com>
To: pgsql-general(at)postgresql(dot)org
Subject: hashtext () and collisions
Date: 2007-04-11 22:00:20
Message-ID: 5eaaef180704111500g6294f530pa904d8cac97bd96@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

Hello,

Okay, I have some troubles trying to determine how to most efficiently
store a database which will contain a couple of huge tables (think
5bil+ rows). These tables each have a bigint id and a character
varying value. Now, I'm currently partitioning these tables based on
the hashtext (value) % 1000, to determine which subtable a certain
value should be stored in.

However, I often also need to find a value for an id; instead of using
the sequential numbering that a BIGSERIAL would provide, I am
thinking: wouldn't it make some kind of sense if I used the value of
hashtext('value') to determine the id ? Then, if I need to determine
the value that belongs to a certain id, I can just % 1000 the value
and know which subtable the value is stored in, reducing the amount of
tables to search with a factor 500.

Now, my question is: how big is the chance that a collision happens
between hashes ? I noticed that the function only returns a 32 bit
number, so I figure it must be at least once in the 4 billion values.
If this approach is not recommended (using hashes as keys), any other
suggestions on how to make the subtable name derivable from an
identification number ?

--
Leon Mergen
http://www.solatis.com

Browse pgsql-general by date

  From Date Subject
Next Message Thomas F. O'Connell 2007-04-11 22:18:06 pg_standby: Unremovable Trigger File
Previous Message Leon Mergen 2007-04-11 21:55:07 hashtext () and collisions