Received: from localhost (unknown [200.46.204.183]) by developer.postgresql.org (Postfix) with ESMTP id DEF772E0041 for ; Wed, 30 Apr 2008 19:54:21 -0300 (ADT) Received: from developer.postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 26944-02 for ; Wed, 30 Apr 2008 19:54:14 -0300 (ADT) X-Greylist: delayed 00:07:08.018569 by SQLgrey-1.7.5 Received: from wr-out-0506.google.com (wr-out-0506.google.com [64.233.184.231]) by developer.postgresql.org (Postfix) with ESMTP id 994D42E003B for ; Wed, 30 Apr 2008 19:54:18 -0300 (ADT) Received: by wr-out-0506.google.com with SMTP id 76so588456wra.10 for ; Wed, 30 Apr 2008 15:54:17 -0700 (PDT) Received: by 10.141.132.1 with SMTP id j1mr555234rvn.64.1209595628410; Wed, 30 Apr 2008 15:47:08 -0700 (PDT) Received: from dogma.ljc.laika.com ( [209.162.219.253]) by mx.google.com with ESMTPS id g22sm1734499rvb.7.2008.04.30.15.47.07 (version=SSLv3 cipher=RC4-MD5); Wed, 30 Apr 2008 15:47:07 -0700 (PDT) Subject: Re: Understanding histograms From: Jeff Davis To: Tom Lane Cc: len@pdx.edu, len@cs.pdx.edu, pgsql-performance@postgresql.org In-Reply-To: <18628.1209566591@sss.pgh.pa.us> References: <4817FC00.50609@cs.pdx.edu> <14251.1209532791@sss.pgh.pa.us> <18628.1209566591@sss.pgh.pa.us> Content-Type: text/plain Date: Wed, 30 Apr 2008 15:47:02 -0700 Message-Id: <1209595622.14025.112.camel@dogma.ljc.laika.com> Mime-Version: 1.0 X-Mailer: Evolution 2.0.4 (2.0.4-7) Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200804/473 X-Sequence-Number: 29966 On Wed, 2008-04-30 at 10:43 -0400, Tom Lane wrote: > > Instead I would expect an estimate of "rows=0" for values of const > > that are not in the MCV list and not in the histogram. > > Surely that's not very sane? The MCV list plus histogram generally > don't include every value in the table. IIRC the estimate for values > not present in the MCV list is (1 - sum(MCV frequencies)) divided by > (n_distinct - number of MCV entries), which amounts to assuming that > all values not present in the MCV list occur equally often. The weak > spot of course is that the n_distinct estimate may be pretty inaccurate. My understanding of Len's question is that, although the MCV list plus the histogram don't include every distinct value in the general case, they do include every value in the specific case where the histogram is not full. Essentially, this seems like using the histogram to extend the MCV list such that, together, they represent all distinct values. This idea only seems to help when the number of distinct values is greater than the max size of MCVs, but less than the max size of MCVs plus histogram bounds. I'm not sure how much of a gain this is, because right now that could be accomplished by increasing the statistics for that column (and therefore all of your distinct values would fit in the MCV list). Also the statistics aren't guaranteed to be perfectly up-to-date, so an estimate of zero might be risky. Regards, Jeff Davis