Re: Query optimizer 8.0.1 (and 8.0)

On Mon, Feb 07, 2005 at 17:45:23 -0500,
Greg Stark <gsstark(at)mit(dot)edu> wrote:
>
> However for discrete values like the "top ten most common values" and the
> "total number of distinct values" it's not so clear at all that you can
> extrapolate from a sample at all. And it's certainly not clear that a fixed
> size sample gives you at all the same confidence for a large population as it
> does for a small population.

If you were to keep a complete histogram for the sample points (which may
or may not be practical) you should be able to estimate the number of
distinct values under some assumptions. Such as, that all values outside
of the top N values have the same likelihood. I don't think this is
unreasonable.

>
> If you sampled across the country and found your sample of 600 people had 4
> different top choices for president, how do you extrapolate that to calculate
> the total number of top choices for president the 300 million+ people will
> have across the country? You could multiply by 500k but that's not going to be
> right. Hell you're probably better off just going with "4" but that's clearly
> not right either.

Well you can put some bounds on the number. Since no 5th candidate was
picked by any of the 600 people, you would expect that the number of
people prefering other candidates is on the order of 500000 or less, so
that the number of distinct values is going to be 500000 or less.

I think the histogram idea will work well for estimating the number of
rows with particular values, but if you are interested in the number
of unique values, you are going to have problems with some data sets.
(Ones with a few very common values and lots of extremely rare items.)
In this case there may be some way to use information from indexes on
the data to get better results.