pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Tom Lane <tgl@sss.pgh.pa.us>
To: nickf@ontko.com
Cc: Pgsql-Performance@Postgresql. Org <pgsql-performance@postgresql.org>
Cc: Ray Ontko <rayo@ontko.com>
Subject: Re: n_distinct way off, but following a pattern.
Date: Fri, 14 Nov 2003 17:12:27 -0500
Message-ID: <5809.1068847947@sss.pgh.pa.us> (raw)
In-Reply-To: <NEBBLAAHGLEEPCGOBHDGEEFLJHAA.nickf@ontko.com>
References: <NEBBLAAHGLEEPCGOBHDGEEFLJHAA.nickf@ontko.com>

"Nick Fankhauser" <nickf@ontko.com> writes:
> I'm seeing estimates for n_distinct that are way off for a large table

Estimating n_distinct from a small sample is inherently a hard problem.
I'm not surprised that the estimates would get better as the sample size
increases.  But maybe we can do better.  The method we are currently
using is this:

            /*----------
             * Estimate the number of distinct values using the estimator
             * proposed by Haas and Stokes in IBM Research Report RJ 10025:
             *        n*d / (n - f1 + f1*n/N)
             * where f1 is the number of distinct values that occurred
             * exactly once in our sample of n rows (from a total of N),
             * and d is the total number of distinct values in the sample.
             * This is their Duj1 estimator; the other estimators they
             * recommend are considerably more complex, and are numerically
             * very unstable when n is much smaller than N.

It would be interesting to see exactly what inputs are going into this
equation.  Do you feel like adding some debug printouts into this code?
Or just looking at the variables with a debugger?  In 7.3 it's about
line 1060 in src/backend/commands/analyze.c.

BTW, this is already our second try at this problem, the original 7.2
equation didn't last long at all ...

			regards, tom lane



view thread (3+ messages)  latest in thread

Message-ID: <5809.1068847947@sss.pgh.pa.us>
Permalink:  ../5809.1068847947@sss.pgh.pa.us/
Also on:    postgresql.org/message-id/5809.1068847947@sss.pgh.pa.us

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-performance@postgresql.org
  Cc: tgl@sss.pgh.pa.us, nickf@ontko.com, rayo@ontko.com
  Subject: Re: n_distinct way off, but following a pattern.
  In-Reply-To: <5809.1068847947@sss.pgh.pa.us>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox