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 B7DBB536CC; Sun, 24 Apr 2005 01:49:18 -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 76635-06; Sun, 24 Apr 2005 04:49:13 +0000 (GMT) Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by svr1.postgresql.org (Postfix) with ESMTP id 57F1553596; Sun, 24 Apr 2005 01:49:12 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.13.1/8.13.1) with ESMTP id j3O4mxGl025383; Sun, 24 Apr 2005 00:48:59 -0400 (EDT) To: josh@agliodbs.com Cc: Greg Stark , Marko Ristola , pgsql-perform , pgsql-hackers@postgresql.org Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested? In-reply-to: <200504231639.11897.josh@agliodbs.com> References: <200504191209.05181.josh@agliodbs.com> <200504221336.08325.josh@agliodbs.com> <8764ydapky.fsf@stark.xeocode.com> <200504231639.11897.josh@agliodbs.com> Comments: In-reply-to Josh Berkus message dated "Sat, 23 Apr 2005 16:39:11 -0700" Date: Sun, 24 Apr 2005 00:48:59 -0400 Message-ID: <25382.1114318139@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.006 tagged_above=0 required=5 tests=AWL X-Spam-Level: X-Archive-Number: 200504/662 X-Sequence-Number: 12059 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. regards, tom lane