estimating # of distinct values

Hi everyone,

about two weeks ago I've started a thread about cross-column stats. One
of the proposed solutions is based on number of distinct values, and the
truth is the current distinct estimator has some problems.

I've done some small research - I have read about 20 papers on this, and
I'd like to present a short summary here, possible solutions etc.

The simple truth is

1) sampling-based estimators are a dead-end
2) there are very interesting stream-based estimators
3) the stream-based estimators have some disadvantages

I wrote a more thorough summary on a wiki
(http://wiki.postgresql.org/wiki/Estimating_Distinct) with a list of the
most interesting papers etc. so just a very short explanation.

1) sampling-based estimators are a dead-end

The paper from Charikar & Chaudhuri states (and proves) that for
each sampling-based estimator, there's a data set where the estimator
produces arbitrary error (with an indispensable probability). So
replacing one sampling-based estimator with another generally does
not improve the situation - fixes one dataset, breaks another one.

The error is directly related to the size of the sample, so the
truth is that to get a good distinct estimate you need to scan a
significant portion of the table (almost all of it).

So the estimators based on tiny samples are a dead end.

2) there are very interesting stream-based estimators

A very interesting idea comes from the field of data streams. These
estimates are based no a one pass through the data, and then
incremental updates. A very nice thing is that these algorithms
don't need that much space, as they don't store the actual values.

The idea behind this is similar to the Bloom filter, i.e. set bits
of a bitmap using a hash of the value. But in this case it's not
required to be able to answer questions like 'is this an element
of the set X?' so it's actually even more space efficient. For an
introduction see the first paper published in 1985 by Flajolet
(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7100)

One of the recent articles (published in June 2010) actually presents
an optimal algorithm with O(e^-2 + log(n)) space complexity and O(1)
update complexity. The "e" means precision, i.e. that the estimate
will be within [(1-e)F, (1+e)F] where F is the real value.

The paper on self-learning bitmap states that to track 10^9 distinct
values with 1% relative error you need about 61 kilobits of space
(which is absolutely awesome). The optimal algorithm needs a bit more
space I think,

A very interesting solution id "distinct sampling" that somehow
extends the Wegman's adaptive sampling approach.

3) the stream-based estimators have some disadvantages

Not everything is perfect, though - the most serious disadvantage is
that those algorithms (usually) don't handle removal of elements.
Inserts are easy to handle, but deletes are hard (just as in case of
Bloom filters).

So using this stream-based approach might lead to degradation in
case of heavily updated tables :-(

I see two possible solutions here:

(a) use counters instead of bits, and track actual counts - but this
is tricky, especially with 'probabilistic' algorithms and needs
much more space (but still, 32x 61kb is just 250kB)

(b) count how many deletes/updates were performed, and if needed
rebuild the whole bitmap

But even though these disadvantages, there really is no other
way to enhance the estimates. I don't think this should be a
default behavior - just as in case of cross-column stats this should
be optional when the current estimator does not work well.

regards
Tomas