> The simple truth is
>
> 1) sampling-based estimators are a dead-end
While I don't want to discourage you from working on steam-based
estimators ... I'd love to see you implement a proof-of-concept for
PostgreSQL, and test it ... the above is a non-argument. It requires us
to accept that sample-based estimates cannot ever be made to work,
simply because you say so.
The Charikar and Chaudhuri paper does not, in fact, say that it is
impossible to improve sampling-based estimators as you claim it does. In
fact, the authors offer several ways to improve sampling-based
estimators. Further, 2000 was hardly the end of sampling-estimation
paper publication; there are later papers with newer ideas.
For example, I still think we could tremendously improve our current
sampling-based estimator without increasing I/O by moving to block-based
estimation*. The accuracy statistics for block-based samples of 5% of
the table look quite good.
I would agree that it's impossible to get a decent estimate of
n-distinct from a 1% sample. But there's a huge difference between 5%
or 10% and "a majority of the table".
Again, don't let this discourage you from attempting to write a
steam-based estimator. But do realize that you'll need to *prove* its
superiority, head-to-head, against sampling-based estimators.
[* http://www.jstor.org/pss/1391058 (unfortunately, no longer
public-access)]
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com