Re: Improving N-Distinct estimation by ANALYZE

Trent,

> Sorry to interupt. The discussion is interesting, but I need some help to
> follow along.

Thought-out commentary is welcome.

> Is "replace the algorithm" the same as saying "contextually use some estimate
> of D that is not Chaudhuri?

Yes. I favor a block-based approach like Brutlag, largely because it
allows us to increase the sample size without dramatically increasing I/O.

> So Chaudhuri's estimate of D is appropriate (and is working) when making
> decisions about joins.

Some kinds of joins. It avoids, for example, risky use of nested loops.

>>However, PostgreSQL now has a whole set of hash operations and other
>>query types for which a
>>too-low estimate of D causes query lockup.
>
>
> Why?

Two specific examples, both of which I've encountered in the field:

1) too-low D will cause an aggregate query to use a hashagg which is
larger than memory resulting in swapping (or disk spill when it's fixed)
which makes the query very much slower than if the hashagg was not used.

2) much too-low D will cause the planner to pick a seq scan when it's
not necessary, resulting in increased query times.

> Do you *really* want the median estimate in these case? Are you certain you
> do not want something with the opposite behavior of Chaudhuri's estimate so
> that for small sample sizes the bias is toward a high estimate of D?
> (Converges on D from the right instead of the left.)
>
> Chaudhuri's <-----D------------------> needed
> Estimate estimate

Hmmm. Yeah, I see what you mean. True, the ideal approach would to
deterime for each query operation whether a too-low D or a too-high D
was more risky, and then use the more conservative number. However,
that would complicate the query planner enough that I think Tom would
leave us. :-p

> These statements are at odds with my admittedly basic understanding of
> statistics. Isn't the power of a sample more related to the absolute size of
> the sample than the sample as fraction of the population? Why not just pick
> a smallish sample size, say about 3000, and apply it to all the tables, even
> the ones with just a single row (modify appropriately from block sampling).

Nope, it's definitely proportional. As a simple example, a sample of
500 rows in a table of 1000 rows should yeild stats estimates with 90%+
accuracy. But a sample of 500 rows in a 600,000,000 row table is so
small as to be nearly useless; it's quite possible to get all the same
value in a random sample of < 0.1% even on a column with a D/N of 0.001.
If you look at the papers cited, almost all researchers more recent
than Chaudhuri use a proportional sample size.

And we're taking the fixed-sample-size approach now, and it's not
working very well for large tables.

--Josh Berkus