Re: [HACKERS] Bad n_distinct estimation; hacks suggested?

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