From: Tom Lane <tgl@sss.pgh.pa.us>
To: Manfred Koizar <mkoi-pg@aon.at>
Cc: Robert Treat <xzilla@users.sourceforge.net>
Cc: pgsql-performance@postgresql.org
Subject: Re: query slows down with more accurate stats
Date: Fri, 16 Apr 2004 10:34:49 -0400
Message-ID: <29060.1082126089@sss.pgh.pa.us> (raw)
In-Reply-To: <hjau701l6u8kavv7ukrqprugi2bkuocd2a@email.aon.at>
References: <1081879359.25537.526.camel@camel>
<25556.1081883922@sss.pgh.pa.us>
<ri5u70du80gnnt326k2hhuei5nlnimonbs@email.aon.at>
<22642.1082074729@sss.pgh.pa.us>
<hjau701l6u8kavv7ukrqprugi2bkuocd2a@email.aon.at>
Manfred Koizar <mkoi-pg@aon.at> writes:
> If the number of pages is B and the sample size is n, a perfect sampling
> method collects a sample where all tuples come from different pages with
> probability (in OpenOffice.org syntax):
> p = prod from{i = 0} to{n - 1} {{c(B - i)} over {cB - i}}
So? You haven't proven that either sampling method fails to do the
same.
The desired property can also be phrased as "every tuple should be
equally likely to be included in the final sample". What we actually
have in the case of your revised algorithm is "every page is equally
likely to be sampled, and of the pages included in the sample, every
tuple is equally likely to be chosen". Given that there are B total
pages of which we sample b pages that happen to contain T tuples (in any
distribution), the probability that a particular tuple gets chosen is
(b/B) * (n/T)
assuming that the two selection steps are independent and unbiased.
Now b, B, and n are not dependent on which tuple we are talking about.
You could argue that a tuple on a heavily populated page is
statistically likely to see a higher T when it's part of the page sample
pool than a tuple on a near-empty page is likely to see, and therefore
there is some bias against selection of the former tuple. But given a
sample over a reasonably large number of pages, the contribution of any
one page to T should be fairly small and so this effect ought to be
small. In fact, because T directly determines our estimate of the total
number of tuples in the relation, your experiments showing that the new
method gives a reliable tuple count estimate directly prove that T is
pretty stable regardless of exactly which pages get included in the
sample. So I think this method is effectively unbiased at the tuple
level. The variation in probability of selection of individual tuples
can be no worse than the variation in the overall tuple count estimate.
regards, tom lane
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: tgl@sss.pgh.pa.us, mkoi-pg@aon.at, xzilla@users.sourceforge.net
Subject: Re: query slows down with more accurate stats
In-Reply-To: <29060.1082126089@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox