X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.2]) by svr1.postgresql.org (Postfix) with ESMTP id 2B12ED1E956 for ; Mon, 19 Apr 2004 13:00:21 -0300 (ADT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (neptune.hub.org [200.46.204.2]) (amavisd-new, port 10024) with ESMTP id 77386-10 for ; Mon, 19 Apr 2004 13:00:19 -0300 (ADT) Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by svr1.postgresql.org (Postfix) with ESMTP id D49F9D1E413 for ; Mon, 19 Apr 2004 13:00:16 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.12.11/8.12.11) with ESMTP id i3JG0AQT025763; Mon, 19 Apr 2004 12:00:11 -0400 (EDT) To: Manfred Koizar Cc: Robert Treat , pgsql-performance@postgresql.org Subject: Re: query slows down with more accurate stats In-reply-to: References: <1081879359.25537.526.camel@camel> <25556.1081883922@sss.pgh.pa.us> <22642.1082074729@sss.pgh.pa.us> <29060.1082126089@sss.pgh.pa.us> Comments: In-reply-to Manfred Koizar message dated "Sat, 17 Apr 2004 00:26:22 +0200" Date: Mon, 19 Apr 2004 12:00:10 -0400 Message-ID: <25762.1082390410@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new at postgresql.org X-Archive-Number: 200404/271 X-Sequence-Number: 6571 Manfred Koizar 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