pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Manfred Koizar <mkoi-pg@aon.at>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Robert Treat <xzilla@users.sourceforge.net>
Cc: pgsql-performance@postgresql.org
Subject: Re: query slows down with more accurate stats
Date: Sat, 17 Apr 2004 00:26:22 +0200
Message-ID: <gdi08094ik0v3jdlklbc7b0rju02dnovj2@email.aon.at> (raw)
In-Reply-To: <29060.1082126089@sss.pgh.pa.us>
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>
	<29060.1082126089@sss.pgh.pa.us>

On Fri, 16 Apr 2004 10:34:49 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> 	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.

On the contrary, I believe that above formula is more or less valid for
both methods.  The point is in what I said next:
| This probability grows with increasing B.

For the one-stage sampling method B is the number of pages of the whole
table.  With two-stage sampling we have to use n instead of B and get a
smaller probability (for n < B, of course).  So this merely shows that
the two sampling methods are not equivalent.

>The desired property can also be phrased as "every tuple should be
>equally likely to be included in the final sample".

Only at first sight.  You really expect more from random sampling.
Otherwise I'd just put one random tuple and its n - 1 successors (modulo
N) into the sample.  This satisfies your condition but you wouldn't call
it a random sample.

Random sampling is more like "every possible sample is equally likely to
be collected", and two-stage sampling doesn't satisfy this condition.

But if in your opinion the difference is not significant, I'll stop
complaining against my own idea.  Is there anybody else who cares?

>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.

It is even better:  Storing a certain number of tuples on heavily
populated pages takes less pages than to store them on sparsely
populated pages (due to tuple size or to dead tuples).  So heavily
populated pages are less likely to be selected in stage one, and this
exactly offsets the effect of increasing T.

>So I think this method is effectively unbiased at the tuple level.

Servus
 Manfred



view thread (9+ messages)  latest in thread

Message-ID: <gdi08094ik0v3jdlklbc7b0rju02dnovj2@email.aon.at>
Permalink:  ../gdi08094ik0v3jdlklbc7b0rju02dnovj2@email.aon.at/
Also on:    postgresql.org/message-id/gdi08094ik0v3jdlklbc7b0rju02dnovj2@email.aon.at

 · 

reply

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: mkoi-pg@aon.at, tgl@sss.pgh.pa.us, xzilla@users.sourceforge.net
  Subject: Re: query slows down with more accurate stats
  In-Reply-To: <gdi08094ik0v3jdlklbc7b0rju02dnovj2@email.aon.at>

* 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