X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id B9D3C53BA1; Sun, 24 Apr 2005 15:31:43 -0300 (ADT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 42529-01; Sun, 24 Apr 2005 18:31:34 +0000 (GMT) Received: from davinci.ethosmedia.com (server227.ethosmedia.com [209.128.84.227]) by svr1.postgresql.org (Postfix) with ESMTP id AA18353B16; Sun, 24 Apr 2005 15:31:30 -0300 (ADT) X-EthosMedia-Virus-Scanned: no infections found Received: from [63.195.55.98] (account josh@agliodbs.com HELO spooky) by davinci.ethosmedia.com (CommuniGate Pro SMTP 4.1.8) with ESMTP id 7278925; Sun, 24 Apr 2005 11:33:28 -0700 From: Josh Berkus Organization: Aglio Database Solutions To: Andrew Dunstan Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested? Date: Sun, 24 Apr 2005 11:30:50 -0700 User-Agent: KMail/1.6.2 Cc: gsql-perform , pgsql-hackers@postgresql.org References: <200504191209.05181.josh@agliodbs.com> <25382.1114318139@sss.pgh.pa.us> <426BDE32.4070004@dunslane.net> In-Reply-To: <426BDE32.4070004@dunslane.net> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200504241130.50218.josh@agliodbs.com> X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.009 tagged_above=0 required=5 tests=AWL X-Spam-Level: X-Archive-Number: 200504/665 X-Sequence-Number: 12062 Andrew, > The math in the paper does not seem to look at very low levels of q (= > sample to pop ratio). Yes, I think that's the failing. Mind you, I did more testing and found out that for D/N ratios of 0.1 to 0.3, the formula only works within 5x accuracy (which I would consider acceptable) with a sample size of 25% or more (which is infeasable in any large table). The formula does work for populations where D/N is much lower, say 0.01. So overall it seems to only work for 1/4 of cases; those where n/N is large and D/N is low. And, annoyingly, that's probably the population where accurate estimation is least crucial, as it consists mostly of small tables. I've just developed (not original, probably, but original to *me*) a formula that works on populations where n/N is very small and D/N is moderate (i.e. 0.1 to 0.4): N * (d/n)^(sqrt(N/n)) However, I've tested it only on (n/N < 0.005 and D/N > 0.1 and D/N < 0.4) populations, and only 3 of them to boot. I'd appreciate other people trying it on their own data populations, particularly very different ones, like D/N > 0.7 or D/N < 0.01. Further, as Andrew points out we presumably do page sampling rather than purely random sampling so I should probably read the paper he referenced. Working on it now .... -- Josh Berkus Aglio Database Solutions San Francisco