From: Greg Stark <gsstark@mit.edu>
To: josh@agliodbs.com
Cc: Marko Ristola <marko.ristola@kolumbus.fi>
Cc: pgsql-perform <pgsql-performance@postgresql.org>
Subject: Re: Bad n_distinct estimation; hacks suggested?
Date: 23 Apr 2005 04:02:05 -0400
Message-ID: <8764ydapky.fsf@stark.xeocode.com> (raw)
In-Reply-To: <200504221336.08325.josh@agliodbs.com>
References: <200504191209.05181.josh@agliodbs.com>
<426944D0.6040706@kolumbus.fi>
<200504221152.51736.josh@agliodbs.com>
<200504221336.08325.josh@agliodbs.com>
Josh Berkus <josh@agliodbs.com> writes:
> ... I think the problem is in our heuristic sampling code. I'm not the first
> person to have this kind of a problem. Will be following up with tests ...
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.
n_distinct requires you to estimate how frequently very rare things occur. You
can't apply the law of large numbers because even a single instance of a value
out of a large pool alters the results disproportionately.
To get a valid estimate for n_distinct you would need to sample a fixed
percentage of the table. Not a fixed size sample. That just isn't practical.
Moreover, I think the percentage would have to be quite large. Even if you
sampled half the table I think the confidence interval would be quite wide.
The situation is worsened because it's unclear how to interpolate values for
subsets of the table. If the histogram says you have a million records and
you're adding a clause that has a selectivity of 50% then half a million is a
good guess. But if what you care about is n_distinct and you start with a
million records with 1,000 distinct values and then apply a clause that
filters 50% of them, how do you estimate the resulting n_distinct? 500 is
clearly wrong, but 1,000 is wrong too. You could end up with anywhere from 0
to 1,000 and you have no good way to figure out where the truth lies.
So I fear this is fundamentally a hopeless situation. It's going to be
difficult to consistently get good plans for any queries that depend on good
estimates for n_distinct.
--
greg
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: gsstark@mit.edu, josh@agliodbs.com, marko.ristola@kolumbus.fi
Subject: Re: Bad n_distinct estimation; hacks suggested?
In-Reply-To: <8764ydapky.fsf@stark.xeocode.com>
* 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