On 23 February 2012 11:09, Peter Geoghegan <pe...@2ndquadrant.com> wrote: > On 23 February 2012 09:58, Daniel Farina <dan...@heroku.com> wrote: >> * The small changes to hashing are probably not strictly required, >> unless collisions are known to get terrible. > > I imagine that collisions would be rather difficult to demonstrate at > all with a 32-bit value.
Assuming that the hash function exhibits a perfectly uniform distribution of values (FWIW, hash_any is said to exhibit the avalanche effect), the birthday problem provides a mathematical basis for estimating the probability of some 2 queries being alike. Assuming a population of 1,000 queries are in play at any given time (i.e. the default value of pg_stat_statements.max) and 2 ^ 32 "days of the year", that puts the probability of a collision at a vanishingly small number. I cannot calculate the number with Gnome calculator. Let's pretend that 2 ^ 32 is exactly 42 million, rather than approximately 4.2 *billion*. Even then, the probability of collision is a minuscule 0.000001857 . I'd have to agree that a uint32 hash is quite sufficient here. -- Peter Geoghegan http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training and Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
