Re: pg_stat_statements normalization: re-review

On 23 February 2012 11:09, Peter Geoghegan <peter(at)2ndquadrant(dot)com> wrote:
> On 23 February 2012 09:58, Daniel Farina <daniel(at)heroku(dot)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