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 50136540DD; Sun, 24 Apr 2005 14:58:44 -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 26878-06; Sun, 24 Apr 2005 17:58:34 +0000 (GMT) Received: from trolak.mydnsbox2.com (ns1.mydnsbox2.com [207.44.142.118]) by svr1.postgresql.org (Postfix) with ESMTP id D22A054304; Sun, 24 Apr 2005 14:58:32 -0300 (ADT) Received: from [192.168.1.103] (cpe-024-211-165-134.nc.res.rr.com [24.211.165.134]) (authenticated (0 bits)) by trolak.mydnsbox2.com (8.11.6/8.11.6) with ESMTP id j3OH9gG12483; Sun, 24 Apr 2005 12:09:43 -0500 Message-ID: <426BDE32.4070004@dunslane.net> Date: Sun, 24 Apr 2005 13:58:10 -0400 From: Andrew Dunstan User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.7) Gecko/20050417 Fedora/1.7.7-1.3.1 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Tom Lane Cc: josh@agliodbs.com, Greg Stark , Marko Ristola , pgsql-perform , pgsql-hackers@postgresql.org Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested? References: <200504191209.05181.josh@agliodbs.com> <200504221336.08325.josh@agliodbs.com> <8764ydapky.fsf@stark.xeocode.com> <200504231639.11897.josh@agliodbs.com> <25382.1114318139@sss.pgh.pa.us> In-Reply-To: <25382.1114318139@sss.pgh.pa.us> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.024 tagged_above=0 required=5 tests=AWL X-Spam-Level: X-Archive-Number: 200504/712 X-Sequence-Number: 12109 Tom Lane wrote: >Josh Berkus writes: > > >>Overall, our formula is inherently conservative of n_distinct. That is, I >>believe that it is actually computing the *smallest* number of distinct >>values which would reasonably produce the given sample, rather than the >>*median* one. This is contrary to the notes in analyze.c, which seem to >>think that we're *overestimating* n_distinct. >> >> > >Well, the notes are there because the early tests I ran on that formula >did show it overestimating n_distinct more often than not. Greg is >correct that this is inherently a hard problem :-( > >I have nothing against adopting a different formula, if you can find >something with a comparable amount of math behind it ... but I fear >it'd only shift the failure cases around. > > > > The math in the paper does not seem to look at very low levels of q (= sample to pop ratio). The formula has a range of [d,N]. It appears intuitively (i.e. I have not done any analysis) that at very low levels of q, as f1 moves down from n, the formula moves down from N towards d very rapidly. I did a test based on the l_comments field in a TPC lineitems table. The test set has N = 6001215, D = 2921877. In my random sample of 1000 I got d = 976 and f1 = 961, for a DUJ1 figure of 24923, which is too low by 2 orders of magnitude. I wonder if this paper has anything that might help: http://www.stat.washington.edu/www/research/reports/1999/tr355.ps - if I were more of a statistician I might be able to answer :-) cheers andrew