From: Josh Berkus <josh@agliodbs.com>
To: Andrew Dunstan <andrew@dunslane.net>
Cc: gsql-perform <pgsql-performance@postgresql.org>
Cc: pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
Date: Sun, 24 Apr 2005 11:30:50 -0700
Message-ID: <200504241130.50218.josh@agliodbs.com> (raw)
In-Reply-To: <426BDE32.4070004@dunslane.net>
References: <200504191209.05181.josh@agliodbs.com>
<25382.1114318139@sss.pgh.pa.us>
<426BDE32.4070004@dunslane.net>
Andrew,
> The math in the paper does not seem to look at very low levels of q (=
> sample to pop ratio).
Yes, I think that's the failing. Mind you, I did more testing and found out
that for D/N ratios of 0.1 to 0.3, the formula only works within 5x accuracy
(which I would consider acceptable) with a sample size of 25% or more (which
is infeasable in any large table). The formula does work for populations
where D/N is much lower, say 0.01. So overall it seems to only work for 1/4
of cases; those where n/N is large and D/N is low. And, annoyingly, that's
probably the population where accurate estimation is least crucial, as it
consists mostly of small tables.
I've just developed (not original, probably, but original to *me*) a formula
that works on populations where n/N is very small and D/N is moderate (i.e.
0.1 to 0.4):
N * (d/n)^(sqrt(N/n))
However, I've tested it only on (n/N < 0.005 and D/N > 0.1 and D/N < 0.4)
populations, and only 3 of them to boot. I'd appreciate other people trying
it on their own data populations, particularly very different ones, like D/N
> 0.7 or D/N < 0.01.
Further, as Andrew points out we presumably do page sampling rather than
purely random sampling so I should probably read the paper he referenced.
Working on it now ....
--
Josh Berkus
Aglio Database Solutions
San Francisco
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: josh@agliodbs.com, andrew@dunslane.net, pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
In-Reply-To: <200504241130.50218.josh@agliodbs.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