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 0566D54EE4; Mon, 25 Apr 2005 06:01:27 -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 34229-10; Mon, 25 Apr 2005 09:01:18 +0000 (GMT) Received: from cmailg1.svr.pol.co.uk (cmailg1.svr.pol.co.uk [195.92.195.171]) by svr1.postgresql.org (Postfix) with ESMTP id A457B54CF5; Mon, 25 Apr 2005 06:01:08 -0300 (ADT) Received: from modem-3531.lynx.dialup.pol.co.uk ([217.135.205.203] helo=192.168.0.102) by cmailg1.svr.pol.co.uk with esmtp (Exim 4.41) id 1DPzSa-0004tn-79; Mon, 25 Apr 2005 10:00:56 +0100 Subject: Re: Bad n_distinct estimation; hacks suggested? From: Simon Riggs To: josh@agliodbs.com Cc: Greg Stark , Marko Ristola , pgsql-perform , pgsql-hackers@postgresql.org 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> Content-Type: text/plain Organization: 2nd Quadrant Date: Mon, 25 Apr 2005 09:57:47 +0100 Message-Id: <1114419467.21529.210.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Evolution 2.0.2 (2.0.2-3) Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.05 tagged_above=0 required=5 tests=AWL, FORGED_RCVD_HELO X-Spam-Level: X-Archive-Number: 200504/671 X-Sequence-Number: 12068 On Sat, 2005-04-23 at 16:39 -0700, Josh Berkus wrote: Greg Stark wrote > > I looked into this a while back when we were talking about changing the > > sampling method. The conclusions were discouraging. Fundamentally, using > > constant sized samples of data for n_distinct is bogus. Constant sized > > samples only work for things like the histograms that can be analyzed > > through standard statistics population sampling which depends on the law of > > large numbers. ISTM Greg's comments are correct. There is no way to calculate this with consistent accuracy when using a constant sized sample. (If it were, then people wouldnt bother to hold large databases...) > 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. The only information you can determine from a sample is the smallest number of distinct values that would reasonably produce the given sample. There is no meaningful concept of a median one... (You do have an upper bound: the number of rows in the table, but I cannot see any meaning from taking (Nrows+estimatedN_distinct)/2 ). Even if you use Zipf's Law to predict the frequency of occurrence, you'd still need to estimate the parameters for the distribution. Most other RDBMS make optimizer statistics collection an unsampled scan. Some offer this as one of their options, as well as the ability to define the sample size in terms of fixed number of rows or fixed proportion of the table. My suggested hack for PostgreSQL is to have an option to *not* sample, just to scan the whole table and find n_distinct accurately. Then anybody who doesn't like the estimated statistics has a clear path to take. The problem of poorly derived base statistics is a difficult one. When considering join estimates we already go to the trouble of including MFV comparisons to ensure an upper bound of join selectivity is known. If the statistics derived are themselves inaccurate the error propagation touches every other calculation in the optimizer. GIGO. What price a single scan of a table, however large, when incorrect statistics could force scans and sorts to occur when they aren't actually needed ? Best Regards, Simon Riggs