Thread: Re: [PERFORM] Bad n_distinct estimation; hacks suggested?

Greg,

> I looked into this a while back when we were talking about changing the
> sampling method. The conclusions were discouraging. Fundamentally, using
> constant sized samples of data for n_distinct is bogus. Constant sized
> samples only work for things like the histograms that can be analyzed
> through standard statistics population sampling which depends on the law of
> large numbers.

Well, unusual distributions are certainly tough.  But I think the problem
exists even for relatively well-distributed populations.    Part of it is, I
believe, the formula we are using:

n*d / (n - f1 + f1*n/N)

This is an estimation formula from Haas and Stokes in IBM Research Report RJ
10025, and is called the DUJ1 formula.
(http://www.almaden.ibm.com/cs/people/peterh/jasa3rj.pdf)  It appears to
suck.   For example, take my table:

rows: 26million (N)
distinct values: 3.4million

I took a random sample of 1000 rows (n) from that table.   It contained:
968 values that occurred only once (f1)
981 distinct values (d)

Any human being looking at that sample would assume a large number of distinct
values; after all, 96.8% of the values occurred only once.   But the formula
gives us:

1000*981 / ( 1000 - 968 + ( 968 * 1000/26000000 ) ) = 30620

This is obviously dramatically wrong, by a factor of 100.  The math gets worse
as the sample size goes down:

Sample 250, 248 distinct values, 246 unique values:

250*248 / ( 250 - 246 + ( 246 * 250 / 26000000 ) ) = 15490

Even in a case with an ovewhelming majority of unique values, the formula gets
it wrong:

999 unque values in sample
998 appearing only once:

1000*999 / ( 1000 - 998 + ( 998 * 1000 / 26000000 ) ) = 490093

This means that, with a sample size of 1000 a table of 26million rows cannot
ever have with this formula more than half a million distinct values, unless
the column is a unique column.

Overall, our formula is inherently conservative of n_distinct.   That is, I
believe that it is actually computing the *smallest* number of distinct
values which would reasonably produce the given sample, rather than the
*median* one.  This is contrary to the notes in analyze.c, which seem to
think that we're *overestimating* n_distinct.

This formula appears broken everywhere:

Table: 969000 rows
Distinct values: 374000
Sample Size: 1000
Unique values in sample: 938
Values appearing only once: 918

1000*938 / ( 1000 - 918 + ( 918 * 1000 / 969000 ) ) = 11308

Again, too small by a factor of 20x.

This is so broken, in fact, that I'm wondering if we've read the paper right?
I've perused the paper on almaden, and the DUJ1 formula appears considerably
more complex than the formula we're using.

Can someone whose math is more recent than calculus in 1989 take a look at
that paper, and look at the formula toward the bottom of page 10, and see if
we are correctly interpreting it?    I'm particularly confused as to what "q"
and "d-sub-n" represent.  Thanks!

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco

People,

> Can someone whose math is more recent than calculus in 1989 take a look at
> that paper, and look at the formula toward the bottom of page 10, and see
> if we are correctly interpreting it?    I'm particularly confused as to
> what "q" and "d-sub-n" represent.  Thanks!

Actually, I managed to solve for these and it appears we are using the formula
correctly.  It's just a bad formula.

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco

Josh Berkus said:
>
>
> Well, unusual distributions are certainly tough.  But I think the
> problem  exists even for relatively well-distributed populations.
> Part of it is, I  believe, the formula we are using:
>
> n*d / (n - f1 + f1*n/N)
>
[snip]
>
> This is so broken, in fact, that I'm wondering if we've read the paper
> right?   I've perused the paper on almaden, and the DUJ1 formula
> appears considerably  more complex than the formula we're using.
>
> Can someone whose math is more recent than calculus in 1989 take a look
> at  that paper, and look at the formula toward the bottom of page 10,
> and see if  we are correctly interpreting it?    I'm particularly
> confused as to what "q"  and "d-sub-n" represent.  Thanks!
>

Math not too recent ...

I quickly read the paper and independently came up with the same formula you
say above we are applying. The formula is on the page that is numbered 6,
although it's the tenth page in the PDF.

q = n/N  = ratio of sample size to population size
d_sub_n = d = number of distinct classes in sample

cheers

andrew

Josh Berkus <josh@agliodbs.com> writes:
> Overall, our formula is inherently conservative of n_distinct.   That is, I
> believe that it is actually computing the *smallest* number of distinct
> values which would reasonably produce the given sample, rather than the
> *median* one.  This is contrary to the notes in analyze.c, which seem to
> think that we're *overestimating* n_distinct.

Well, the notes are there because the early tests I ran on that formula
did show it overestimating n_distinct more often than not.  Greg is
correct that this is inherently a hard problem :-(

I have nothing against adopting a different formula, if you can find
something with a comparable amount of math behind it ... but I fear
it'd only shift the failure cases around.

            regards, tom lane

Tom Lane wrote:

>Josh Berkus <josh@agliodbs.com> writes:
>
>
>>Overall, our formula is inherently conservative of n_distinct.   That is, I
>>believe that it is actually computing the *smallest* number of distinct
>>values which would reasonably produce the given sample, rather than the
>>*median* one.  This is contrary to the notes in analyze.c, which seem to
>>think that we're *overestimating* n_distinct.
>>
>>
>
>Well, the notes are there because the early tests I ran on that formula
>did show it overestimating n_distinct more often than not.  Greg is
>correct that this is inherently a hard problem :-(
>
>I have nothing against adopting a different formula, if you can find
>something with a comparable amount of math behind it ... but I fear
>it'd only shift the failure cases around.
>
>
>
>

The math in the paper does not seem to look at very low levels of q (=
sample to pop ratio).

The formula has a range of [d,N]. It appears intuitively (i.e. I have
not done any analysis) that at very low levels of q, as f1 moves down
from n, the formula moves down from N towards d very rapidly. I did a
test based on the l_comments field in a TPC lineitems table. The test
set has N = 6001215, D =  2921877. In my random sample of 1000 I got d =
976 and f1 = 961, for a DUJ1 figure of 24923, which is too low by 2
orders of magnitude.

I wonder if this paper has anything that might help:
http://www.stat.washington.edu/www/research/reports/1999/tr355.ps - if I
were more of a statistician I might be able to answer :-)

cheers

andrew

Andrew,

> The math in the paper does not seem to look at very low levels of q (=
> sample to pop ratio).

Yes, I think that's the failing.   Mind you, I did more testing and found out
that for D/N ratios of 0.1 to 0.3, the formula only works within 5x accuracy
(which I would consider acceptable) with a sample size of 25% or more (which
is infeasable in any large table).    The formula does work for populations
where D/N is much lower, say 0.01.  So overall it seems to only work for 1/4
of cases; those where n/N is large and D/N is low.   And, annoyingly, that's
probably the population where accurate estimation is least crucial, as it
consists mostly of small tables.

I've just developed (not original, probably, but original to *me*) a formula
that works on populations where n/N is very small and D/N is moderate (i.e.
0.1 to 0.4):

N * (d/n)^(sqrt(N/n))

However, I've tested it only on (n/N < 0.005 and D/N > 0.1 and D/N < 0.4)
populations, and only 3 of them to boot.   I'd appreciate other people trying
it on their own data populations, particularly very different ones, like D/N
> 0.7 or D/N < 0.01.

Further, as Andrew points out we presumably do page sampling rather than
purely random sampling so I should probably read the paper he referenced.
Working on it now ....

--
Josh Berkus
Aglio Database Solutions
San Francisco

Folks,

> I wonder if this paper has anything that might help:
> http://www.stat.washington.edu/www/research/reports/1999/tr355.ps - if I
> were more of a statistician I might be able to answer :-)

Actually, that paper looks *really* promising.   Does anyone here have enough
math to solve for D(sub)Md on page 6?   I'd like to test it on samples of <
0.01%.

Tom, how does our heuristic sampling work?   Is it pure random sampling, or
page sampling?

--
Josh Berkus
Aglio Database Solutions
San Francisco

Here is my opinion.
I hope this helps.

Maybe there is no one good formula:

On boolean type, there are at most 3 distinct values.
There is an upper bound for fornames in one country.
There is an upper bound for last names in one country.
There is a fixed number of states and postal codes in one country.

On the other hand, with timestamp, every value could be distinct.
A primary key with only one column has only distinct values.
If the integer column refers with a foreign key into another table's
only primary key, we could take advantage of that knolege.
A column with a unique index has only distinct values.

First ones are for classifying and the second ones measure continuous
or discrete time or something like the time.

The upper bound for classifying might be 3 (boolean), or it might be
one million. The properties of the distribution might be hard to guess.

Here is one way:

1. Find out the number of distinct values for 500 rows.
2. Try to guess, how many distinct values are for 1000 rows.
    Find out the real number of distinct values for 1000 rows.
3. If the guess and the reality are 50% wrong, do the iteration for
2x1000 rows.
Iterate using a power of two to increase the samples, until you trust the
estimate enough.

So, in the phase two, you could try to guess with two distinct formulas:
One for the classifying target (boolean columns hit there).
Another one for the timestamp and numerical values.

If there are one million classifications on one column, how you
can find it out, by other means than checking at least two million
rows?

This means, that the user should have a possibility to tell the lower
bound for the number of rows for sampling.


Regards,
Marko Ristola

Tom Lane wrote:

>Josh Berkus <josh@agliodbs.com> writes:
>
>
>>Overall, our formula is inherently conservative of n_distinct.   That is, I
>>believe that it is actually computing the *smallest* number of distinct
>>values which would reasonably produce the given sample, rather than the
>>*median* one.  This is contrary to the notes in analyze.c, which seem to
>>think that we're *overestimating* n_distinct.
>>
>>
>
>Well, the notes are there because the early tests I ran on that formula
>did show it overestimating n_distinct more often than not.  Greg is
>correct that this is inherently a hard problem :-(
>
>I have nothing against adopting a different formula, if you can find
>something with a comparable amount of math behind it ... but I fear
>it'd only shift the failure cases around.
>
>            regards, tom lane
>
>---------------------------(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
>
>

Josh Berkus <josh@agliodbs.com> writes:
> Tom, how does our heuristic sampling work?   Is it pure random sampling, or
> page sampling?

Manfred probably remembers better than I do, but I think the idea is
to approximate pure random sampling as best we can without actually
examining every page of the table.

            regards, tom lane

On Sat, 2005-04-23 at 16:39 -0700, Josh Berkus wrote:
Greg Stark wrote
> > I looked into this a while back when we were talking about changing the
> > sampling method. The conclusions were discouraging. Fundamentally, using
> > constant sized samples of data for n_distinct is bogus. Constant sized
> > samples only work for things like the histograms that can be analyzed
> > through standard statistics population sampling which depends on the law of
> > large numbers.

ISTM Greg's comments are correct. There is no way to calculate this with
consistent accuracy when using a constant sized sample. (If it were,
then people wouldnt bother to hold large databases...)

> Overall, our formula is inherently conservative of n_distinct.   That is, I
> believe that it is actually computing the *smallest* number of distinct
> values which would reasonably produce the given sample, rather than the
> *median* one.  This is contrary to the notes in analyze.c, which seem to
> think that we're *overestimating* n_distinct.

The only information you can determine from a sample is the smallest
number of distinct values that would reasonably produce the given
sample. There is no meaningful concept of a median one... (You do have
an upper bound: the number of rows in the table, but I cannot see any
meaning from taking (Nrows+estimatedN_distinct)/2 ).

Even if you use Zipf's Law to predict the frequency of occurrence, you'd
still need to estimate the parameters for the distribution.

Most other RDBMS make optimizer statistics collection an unsampled
scan. Some offer this as one of their options, as well as the ability to
define the sample size in terms of fixed number of rows or fixed
proportion of the table.

My suggested hack for PostgreSQL is to have an option to *not* sample,
just to scan the whole table and find n_distinct accurately. Then
anybody who doesn't like the estimated statistics has a clear path to
take.

The problem of poorly derived base statistics is a difficult one. When
considering join estimates we already go to the trouble of including MFV
comparisons to ensure an upper bound of join selectivity is known. If
the statistics derived are themselves inaccurate the error propagation
touches every other calculation in the optimizer. GIGO.

What price a single scan of a table, however large, when incorrect
statistics could force scans and sorts to occur when they aren't
actually needed ?

Best Regards, Simon Riggs

Simon Riggs <simon@2ndquadrant.com> writes:
> My suggested hack for PostgreSQL is to have an option to *not* sample,
> just to scan the whole table and find n_distinct accurately.
> ...
> What price a single scan of a table, however large, when incorrect
> statistics could force scans and sorts to occur when they aren't
> actually needed ?

It's not just the scan --- you also have to sort, or something like
that, if you want to count distinct values.  I doubt anyone is really
going to consider this a feasible answer for large tables.

            regards, tom lane

On Mon, 2005-04-25 at 11:23 -0400, Tom Lane wrote:
> Simon Riggs <simon@2ndquadrant.com> writes:
> > My suggested hack for PostgreSQL is to have an option to *not* sample,
> > just to scan the whole table and find n_distinct accurately.
> > ...
> > What price a single scan of a table, however large, when incorrect
> > statistics could force scans and sorts to occur when they aren't
> > actually needed ?
>
> It's not just the scan --- you also have to sort, or something like
> that, if you want to count distinct values.  I doubt anyone is really
> going to consider this a feasible answer for large tables.

Assuming you don't use the HashAgg plan, which seems very appropriate
for the task? (...but I understand the plan otherwise).

If that was the issue, then why not keep scanning until you've used up
maintenance_work_mem with hash buckets, then stop and report the result.

The problem is if you don't do the sort once for statistics collection
you might accidentally choose plans that force sorts on that table. I'd
rather do it once...

The other alternative is to allow an ALTER TABLE command to set
statistics manually, but I think I can guess what you'll say to that!

Best Regards, Simon Riggs

Simon, Tom:

While it's not possible to get accurate estimates from a fixed size sample, I
think it would be possible from a small but scalable sample: say, 0.1% of all
data pages on large tables, up to the limit of maintenance_work_mem.

Setting up these samples as a % of data pages, rather than a pure random sort,
makes this more feasable; for example, a 70GB table would only need to sample
about 9000 data pages (or 70MB).  Of course, larger samples would lead to
better accuracy, and this could be set through a revised GUC (i.e.,
maximum_sample_size, minimum_sample_size).

I just need a little help doing the math ... please?

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco

Guys,

> While it's not possible to get accurate estimates from a fixed size sample,
> I think it would be possible from a small but scalable sample: say, 0.1% of
> all data pages on large tables, up to the limit of maintenance_work_mem.

BTW, when I say "accurate estimates" here, I'm talking about "accurate enough
for planner purposes" which in my experience is a range between 0.2x to 5x.

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco

Josh Berkus wrote:

>Simon, Tom:
>
>While it's not possible to get accurate estimates from a fixed size sample, I
>think it would be possible from a small but scalable sample: say, 0.1% of all
>data pages on large tables, up to the limit of maintenance_work_mem.
>
>Setting up these samples as a % of data pages, rather than a pure random sort,
>makes this more feasable; for example, a 70GB table would only need to sample
>about 9000 data pages (or 70MB).  Of course, larger samples would lead to
>better accuracy, and this could be set through a revised GUC (i.e.,
>maximum_sample_size, minimum_sample_size).
>
>I just need a little help doing the math ... please?
>
>


After some more experimentation, I'm wondering about some sort of
adaptive algorithm, a bit along the lines suggested by Marko Ristola,
but limited to 2 rounds.

The idea would be that we take a sample (either of fixed size, or some
small proportion of the table) , see how well it fits a larger sample
(say a few times the size of the first sample), and then adjust the
formula accordingly to project from the larger sample the estimate for
the full population. Math not worked out yet - I think we want to ensure
that the result remains bounded by [d,N].

cheers

andrew

Simon Riggs <simon@2ndquadrant.com> writes:
> On Mon, 2005-04-25 at 11:23 -0400, Tom Lane wrote:
>> It's not just the scan --- you also have to sort, or something like
>> that, if you want to count distinct values.  I doubt anyone is really
>> going to consider this a feasible answer for large tables.

> Assuming you don't use the HashAgg plan, which seems very appropriate
> for the task? (...but I understand the plan otherwise).

The context here is a case with a very large number of distinct
values... keep in mind also that we have to do this for *all* the
columns of the table.  A full-table scan for each column seems
right out to me.

            regards, tom lane

On Sun, 2005-04-24 at 00:48 -0400, Tom Lane wrote:
> Josh Berkus <josh@agliodbs.com> writes:
> > Overall, our formula is inherently conservative of n_distinct.   That is, I
> > believe that it is actually computing the *smallest* number of distinct
> > values which would reasonably produce the given sample, rather than the
> > *median* one.  This is contrary to the notes in analyze.c, which seem to
> > think that we're *overestimating* n_distinct.
>
> Well, the notes are there because the early tests I ran on that formula
> did show it overestimating n_distinct more often than not.  Greg is
> correct that this is inherently a hard problem :-(
>
> I have nothing against adopting a different formula, if you can find
> something with a comparable amount of math behind it ... but I fear
> it'd only shift the failure cases around.
>

Perhaps the formula is not actually being applied?

The code looks like this...
 if (nmultiple == 0)
 {
    /* If we found no repeated values, assume it's a unique column */
    stats->stadistinct = -1.0;
 }
 else if (toowide_cnt == 0 && nmultiple == ndistinct)
 {
    /*
     * Every value in the sample appeared more than once.  Assume
     * the column has just these values.
     */
    stats->stadistinct = ndistinct;
 }
 else
 {
    /*----------
     * Estimate the number of distinct values using the estimator
     * proposed by Haas and Stokes in IBM Research Report RJ 10025:


The middle chunk of code looks to me like if we find a distribution
where values all occur at least twice, then we won't bother to apply the
Haas and Stokes equation. That type of frequency distribution would be
very common in a set of values with very high ndistinct, especially when
sampled.

The comment
     * Every value in the sample appeared more than once.  Assume
     * the column has just these values.
doesn't seem to apply when using larger samples, as Josh is using.

Looking at Josh's application it does seem likely that when taking a
sample, all site visitors clicked more than once during their session,
especially if they include home page, adverts, images etc for each page.

Could it be that we have overlooked this simple explanation and that the
Haas and Stokes equation is actually quite good, but just not being
applied?

Best Regards, Simon Riggs

Simon,

> Could it be that we have overlooked this simple explanation and that the
> Haas and Stokes equation is actually quite good, but just not being
> applied?

That's probably part of it, but I've tried Haas and Stokes on a pure random
sample and it's still bad, or more specifically overly conservative.

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco

On Mon, 2005-04-25 at 17:10 -0400, Tom Lane wrote:
> Simon Riggs <simon@2ndquadrant.com> writes:
> > On Mon, 2005-04-25 at 11:23 -0400, Tom Lane wrote:
> >> It's not just the scan --- you also have to sort, or something like
> >> that, if you want to count distinct values.  I doubt anyone is really
> >> going to consider this a feasible answer for large tables.
>
> > Assuming you don't use the HashAgg plan, which seems very appropriate
> > for the task? (...but I understand the plan otherwise).
>
> The context here is a case with a very large number of distinct
> values...

Yes, but is there another way of doing this other than sampling a larger
proportion of the table? I don't like that answer either, for the
reasons you give.

The manual doesn't actually say this, but you can already alter the
sample size by setting one of the statistics targets higher, but all of
those samples are fixed sample sizes, not a proportion of the table
itself. It seems reasonable to allow an option to scan a higher
proportion of the table. (It would be even better if you could say "keep
going until you run out of memory, then stop", to avoid needing to have
an external sort mode added to ANALYZE).

Oracle and DB2 allow a proportion of the table to be specified as a
sample size during statistics collection. IBM seem to be ignoring their
own research note on estimating ndistinct...

> keep in mind also that we have to do this for *all* the
> columns of the table.

You can collect stats for individual columns. You need only use an
option to increase sample size when required.

Also, if you have a large table and the performance of ANALYZE worries
you, set some fields to 0. Perhaps that should be the default setting
for very long text columns, since analyzing those doesn't help much
(usually) and takes ages. (I'm aware we already don't analyze var length
column values > 1024 bytes).

> A full-table scan for each column seems
> right out to me.

Some systems analyze multiple columns simultaneously.

Best Regards, Simon Riggs

Simon Riggs wrote:

>The comment
>     * Every value in the sample appeared more than once.  Assume
>     * the column has just these values.
>doesn't seem to apply when using larger samples, as Josh is using.
>
>Looking at Josh's application it does seem likely that when taking a
>sample, all site visitors clicked more than once during their session,
>especially if they include home page, adverts, images etc for each page.
>
>Could it be that we have overlooked this simple explanation and that the
>Haas and Stokes equation is actually quite good, but just not being
>applied?
>
>
>
>

No, it is being aplied.  If every value in the sample appears more than
once, then f1 in the formula is 0, and the result is then just d, the
number of distinct values in the sample.

cheers

andrew

Quoting Andrew Dunstan <andrew@dunslane.net>:

> After some more experimentation, I'm wondering about some sort of
> adaptive algorithm, a bit along the lines suggested by Marko
Ristola, but limited to 2 rounds.
>
> The idea would be that we take a sample (either of fixed size, or
> some  small proportion of the table) , see how well it fits a larger
sample
> > (say a few times the size of the first sample), and then adjust
the > formula accordingly to project from the larger sample the
estimate for the full population. Math not worked out yet - I think we
want to ensure that the result remains bounded by [d,N].

Perhaps I can save you some time (yes, I have a degree in Math). If I
understand correctly, you're trying extrapolate from the correlation
between a tiny sample and a larger sample. Introducing the tiny sample
into any decision can only produce a less accurate result than just
taking the larger sample on its own; GIGO. Whether they are consistent
with one another has no relationship to whether the larger sample
correlates with the whole population. You can think of the tiny sample
like "anecdotal" evidence for wonderdrugs.
--
"Dreams come true, not free." -- S.Sondheim, ITW

 Hi everybody!

 Perhaps the following papers are relevant to the discussion here
 (their contact authors have been cc'd):


 1. The following proposes effective algorithms for using block-level
    sampling for n_distinct estimation:

 "Effective use of block-level sampling in statistics estimation"
 by Chaudhuri, Das and Srivastava, SIGMOD 2004.

 http://www-db.stanford.edu/~usriv/papers/block-sampling.pdf


 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


 3. In fact, Gibbon's basic idea has been extended to "sliding windows"
    (this extension is useful in streaming systems like Aurora / Stream):

 "Distributed streams algorithms for sliding windows"
 by Gibbons and Tirthapura, SPAA 2002.

 http://home.eng.iastate.edu/~snt/research/tocs.pdf


 Thanks,
 Gurmeet

 ----------------------------------------------------
 Gurmeet Singh Manku                      Google Inc.
 http://www.cs.stanford.edu/~manku    (650) 967 1890
 ----------------------------------------------------

Mischa Sandberg wrote:

>
>Perhaps I can save you some time (yes, I have a degree in Math). If I
>understand correctly, you're trying extrapolate from the correlation
>between a tiny sample and a larger sample. Introducing the tiny sample
>into any decision can only produce a less accurate result than just
>taking the larger sample on its own; GIGO. Whether they are consistent
>with one another has no relationship to whether the larger sample
>correlates with the whole population. You can think of the tiny sample
>like "anecdotal" evidence for wonderdrugs.
>
>
>

Ok, good point.

I'm with Tom though in being very wary of solutions that require even
one-off whole table scans. Maybe we need an additional per-table
statistics setting which could specify the sample size, either as an
absolute number or as a percentage of the table. It certainly seems that
where D/N ~ 0.3, the estimates on very large tables at least are way way
out.

Or maybe we need to support more than one estimation method.

Or both ;-)

cheers

andrew

Mischa,

> >Perhaps I can save you some time (yes, I have a degree in Math). If I
> >understand correctly, you're trying extrapolate from the correlation
> >between a tiny sample and a larger sample. Introducing the tiny sample
> >into any decision can only produce a less accurate result than just
> >taking the larger sample on its own; GIGO. Whether they are consistent
> >with one another has no relationship to whether the larger sample
> >correlates with the whole population. You can think of the tiny sample
> >like "anecdotal" evidence for wonderdrugs.

Actually, it's more to characterize how large of a sample we need.  For
example, if we sample 0.005 of disk pages, and get an estimate, and then
sample another 0.005 of disk pages and get an estimate which is not even
close to the first estimate, then we have an idea that this is a table which
defies analysis based on small samples.   Wheras if the two estimates are <
1.0 stdev apart, we can have good confidence that the table is easily
estimated.  Note that this doesn't require progressively larger samples; any
two samples would work.

> I'm with Tom though in being very wary of solutions that require even
> one-off whole table scans. Maybe we need an additional per-table
> statistics setting which could specify the sample size, either as an
> absolute number or as a percentage of the table. It certainly seems that
> where D/N ~ 0.3, the estimates on very large tables at least are way way
> out.

Oh, I think there are several other cases where estimates are way out.
Basically the estimation method we have doesn't work for samples smaller than
0.10.

> Or maybe we need to support more than one estimation method.

Yes, actually.   We need 3 different estimation methods:
1 for tables where we can sample a large % of pages (say, >= 0.1)
1 for tables where we sample a small % of pages but are "easily estimated"
1 for tables which are not easily estimated by we can't afford to sample a
large % of pages.

If we're doing sampling-based estimation, I really don't want people to lose
sight of the fact that page-based random sampling is much less expensive than
row-based random sampling.   We should really be focusing on methods which
are page-based.

--
Josh Berkus
Aglio Database Solutions
San Francisco

Quoting Josh Berkus <josh@agliodbs.com>:

> > >Perhaps I can save you some time (yes, I have a degree in Math). If I
> > >understand correctly, you're trying extrapolate from the correlation
> > >between a tiny sample and a larger sample. Introducing the tiny sample
> > >into any decision can only produce a less accurate result than just
> > >taking the larger sample on its own; GIGO. Whether they are consistent
> > >with one another has no relationship to whether the larger sample
> > >correlates with the whole population. You can think of the tiny sample
> > >like "anecdotal" evidence for wonderdrugs.
>
> Actually, it's more to characterize how large of a sample we need.  For
> example, if we sample 0.005 of disk pages, and get an estimate, and then
> sample another 0.005 of disk pages and get an estimate which is not even
> close to the first estimate, then we have an idea that this is a table
which
> defies analysis based on small samples.   Wheras if the two estimates
are <
> 1.0 stdev apart, we can have good confidence that the table is easily
> estimated.  Note that this doesn't require progressively larger
samples; any
> two samples would work.

We're sort of wandering away from the area where words are a good way
to describe the problem. Lacking a common scratchpad to work with,
could I suggest you talk to someone you consider has a background in
stats, and have them draw for you why this doesn't work?

About all you can get out of it is, if the two samples are
disjunct by a stddev, yes, you've demonstrated that the union
of the two populations has a larger stddev than either of them;
but your two stddevs are less info than the stddev of the whole.
Breaking your sample into two (or three, or four, ...) arbitrary pieces
and looking at their stddevs just doesn't tell you any more than what
you start with.

--
"Dreams come true, not free." -- S.Sondheim, ITW

> Now, if we can come up with something better than the ARC algorithm ...

Tom already did.  His clock-sweep patch is already in the 8.1 source.

--
Josh Berkus
Aglio Database Solutions
San Francisco

Well, this guy has it nailed. He cites Flajolet and Martin, which was (I
thought) as good as you could get with only a reasonable amount of memory per
statistic. Unfortunately, their hash table is a one-shot deal; there's no way
to maintain it once the table changes. His incremental update doesn't degrade
as the table changes. If there isn't the same wrangle of patent as with the
ARC algorithm, and if the existing stats collector process can stand the extra
traffic, then this one is a winner.

Many thanks to the person who posted this reference in the first place; so
sorry I canned your posting and can't recall your name.

Now, if we can come up with something better than the ARC algorithm ...

 Actually, the earliest paper that solves the distinct_n estimation
 problem in 1 pass is the following:

    "Estimating simple functions on the union of data streams"
    by Gibbons and Tirthapura, SPAA 2001.
    http://home.eng.iastate.edu/~snt/research/streaming.pdf

 The above paper addresses a more difficult problem (1 pass
 _and_ a distributed setting).


 Gibbon's followup paper in VLDB 2001 limits the problem to a
 single machine and contains primarily experimental results (for
 a database audience). The algorithmic breakthrough had already been
 accomplished in the SPAA paper.

 Gurmeet

--
 ----------------------------------------------------
 Gurmeet Singh Manku                      Google Inc.
 http://www.cs.stanford.edu/~manku    (650) 967 1890
 ----------------------------------------------------

Hi, Josh,

Josh Berkus wrote:

> Yes, actually.   We need 3 different estimation methods:
> 1 for tables where we can sample a large % of pages (say, >= 0.1)
> 1 for tables where we sample a small % of pages but are "easily estimated"
> 1 for tables which are not easily estimated by we can't afford to sample a
> large % of pages.
>
> If we're doing sampling-based estimation, I really don't want people to lose
> sight of the fact that page-based random sampling is much less expensive than
> row-based random sampling.   We should really be focusing on methods which
> are page-based.

Would it make sense to have a sample method that scans indices? I think
that, at least for tree based indices (btree, gist), rather good
estimates could be derived.

And the presence of a unique index should lead to 100% distinct values
estimation without any scan at all.

Markus

Quoting Markus Schaber <schabi@logix-tt.com>:

> Hi, Josh,
>
> Josh Berkus wrote:
>
> > Yes, actually.   We need 3 different estimation methods:
> > 1 for tables where we can sample a large % of pages (say, >= 0.1)
> > 1 for tables where we sample a small % of pages but are "easily
> estimated"
> > 1 for tables which are not easily estimated by we can't afford to
> sample a
> > large % of pages.
> >
> > If we're doing sampling-based estimation, I really don't want
> people to lose
> > sight of the fact that page-based random sampling is much less
> expensive than
> > row-based random sampling.   We should really be focusing on
> methods which
> > are page-based.

Okay, although given the track record of page-based sampling for
n-distinct, it's a bit like looking for your keys under the streetlight,
rather than in the alley where you dropped them :-)

How about applying the distinct-sampling filter on a small extra data
stream to the stats collector?

--
Engineers think equations approximate reality.
Physicists think reality approximates the equations.
Mathematicians never make the connection.

Mischa,

> Okay, although given the track record of page-based sampling for
> n-distinct, it's a bit like looking for your keys under the streetlight,
> rather than in the alley where you dropped them :-)

Bad analogy, but funny.

The issue with page-based vs. pure random sampling is that to do, for example,
10% of rows purely randomly would actually mean loading 50% of pages.  With
20% of rows, you might as well scan the whole table.

Unless, of course, we use indexes for sampling, which seems like a *really
good* idea to me ....

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco

John,

> But doesn't an index only sample one column at a time, whereas with
> page-based sampling, you can sample all of the columns at once.

Hmmm.  Yeah, we're not currently doing that though.  Another good idea ...

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco

Quoting Josh Berkus <josh@agliodbs.com>:

> Mischa,
>
> > Okay, although given the track record of page-based sampling for
> > n-distinct, it's a bit like looking for your keys under the
> streetlight,
> > rather than in the alley where you dropped them :-)
>
> Bad analogy, but funny.

Bad analogy? Page-sampling effort versus row-sampling effort, c'est
moot. It's not good enough for stats to produce good behaviour on the
average. Straight random sampling, page or row, is going to cause
enough untrustworthy engine behaviour,for any %ages small enough to
allow sampling from scratch at any time.

I'm curious what the problem is with relying on a start-up plus
incremental method, when the method in the distinct-sampling paper
doesn't degenerate: you can start when the table is still empty.
Constructing an index requires an initial full scan plus incremental
update; what's the diff?

> Unless, of course, we use indexes for sampling, which seems like a
> *really
> good* idea to me ....

"distinct-sampling" applies for indexes, too. I started tracking the
discussion of this a bit late.  Smart method for this is in VLDB'92:
Gennady Antoshenkov, "Random Sampling from Pseudo-ranked B+-trees". I
don't think this is online anywhere, except if you have a DBLP
membership. Does nybod else know better?
Antoshenkov was the brains behind some of the really cool stuff in DEC
Rdb (what eventually became Oracle). Compressed bitmap indices,
parallel competing query plans, and smart handling of keys with
hyperbolic distributions.
--
Engineers think equations approximate reality.
Physicists think reality approximates the equations.
Mathematicians never make the connection.

Josh Berkus wrote:
> Mischa,
>
>
>>Okay, although given the track record of page-based sampling for
>>n-distinct, it's a bit like looking for your keys under the streetlight,
>>rather than in the alley where you dropped them :-)
>
>
> Bad analogy, but funny.
>
> The issue with page-based vs. pure random sampling is that to do, for example,
> 10% of rows purely randomly would actually mean loading 50% of pages.  With
> 20% of rows, you might as well scan the whole table.
>
> Unless, of course, we use indexes for sampling, which seems like a *really
> good* idea to me ....
>

But doesn't an index only sample one column at a time, whereas with
page-based sampling, you can sample all of the columns at once. And not
all columns would have indexes, though it could be assumed that if a
column doesn't have an index, then it doesn't matter as much for
calculations such as n_distinct.

But if you had 5 indexed rows in your table, then doing it index wise
means you would have to make 5 passes instead of just one.

Though I agree that page-based sampling is important for performance
reasons.

John
=:->