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

> -----Original Message-----
> From: Gurmeet Manku [mailto:manku(at)CS(dot)Stanford(dot)EDU]
> Sent: Tuesday, April 26, 2005 5:01 PM
> To: Simon Riggs
> Cc: Tom Lane; josh(at)agliodbs(dot)com; Greg Stark; Marko Ristola;
> pgsql-perform; pgsql-hackers(at)postgresql(dot)org; Utkarsh Srivastava;
> snt(at)iastate(dot)edu
> Subject: Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks
> suggested?
>
> [...]
> 2. In a single scan, it is possible to estimate n_distinct by using
> a very simple algorithm:
>
> "Distinct sampling for highly-accurate answers to distinct value
> queries and event reports" by Gibbons, VLDB 2001.
>
> http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/dist_sampl.pdf
>
> [...]

This paper looks the most promising, and isn't too different
from what I suggested about collecting stats over the whole table
continuously. What Gibbons does is give a hard upper bound on
the sample size by using a logarithmic technique for storing
sample information. His technique appears to offer very good
error bounds and confidence intervals as shown by tests on
synthetic and real data. I think it deserves a hard look from
people hacking the estimator.

__
David B. Held
Software Engineer/Array Services Group
200 14th Ave. East, Sartell, MN 56377
320.534.3637 320.253.7800 800.752.8129