Skip site navigation (1) Skip section navigation (2)

Re: pg_stat_statements normalization: re-review

From: Peter Geoghegan <peter(at)2ndquadrant(dot)com>
To: Daniel Farina <daniel(at)heroku(dot)com>
Cc: pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: pg_stat_statements normalization: re-review
Date: 2012-02-23 12:37:51
Message-ID: CAEYLb_XS2aB8F_J+T3NDVbz+nrEQGmga7AXh9QnfYYddq_2+qA@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
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

In response to

pgsql-hackers by date

Next:From: Jeroen VermeulenDate: 2012-02-23 13:08:28
Subject: Re: foreign key locks, 2nd attempt
Previous:From: Simon RiggsDate: 2012-02-23 12:36:15
Subject: Re: Initial 9.2 pgbench write results

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group