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: Mon, 19 Apr 2004 12:00:10 -0400
Message-ID: <25762.1082390410@sss.pgh.pa.us> (raw)
In-Reply-To: <gdi08094ik0v3jdlklbc7b0rju02dnovj2@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>
<29060.1082126089@sss.pgh.pa.us>
<gdi08094ik0v3jdlklbc7b0rju02dnovj2@email.aon.at>
Manfred Koizar <mkoi-pg@aon.at> writes:
> Random sampling is more like "every possible sample is equally likely to
> be collected", and two-stage sampling doesn't satisfy this condition.
Okay, I finally see the point here: in the limit as the number of pages
B goes to infinity, you'd expect the probability that each tuple in your
sample came from a different page to go to 1. But this doesn't happen
in the two-stage sampling method: the probability doesn't increase
beyond the value it would have for B=n. On the average each sample page
would supply one tuple, but the odds that this holds *exactly* would be
pretty low.
However the existing sampling method has glaring flaws of its own,
in particular having to do with the fact that a tuple whose slot is
preceded by N empty slots is N times more likely to be picked than one
that has no empty-slot predecessors. The fact that the two-stage
method artificially constrains the sample to come from only n pages
seems like a minor problem by comparison; I'd happily accept it to get
rid of the empty-slot bias.
A possible compromise is to limit the number of pages sampled to
something a bit larger than n, perhaps 2n or 3n. I don't have a feeling
for the shape of the different-pages probability function; would this
make a significant difference, or would it just waste cycles?
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: <25762.1082390410@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