> -----Original Message-----
> From: Gurmeet Manku [mailto:[EMAIL PROTECTED]
> Sent: Tuesday, April 26, 2005 5:01 PM
> To: Simon Riggs
> Cc: Tom Lane; [email protected]; Greg Stark; Marko Ristola;
> pgsql-perform; [email protected]; Utkarsh Srivastava;
> [EMAIL PROTECTED]
> 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
---------------------------(end of broadcast)---------------------------
TIP 9: the planner will ignore your desire to choose an index scan if your
joining column's datatypes do not match
