Skip site navigation (1) Skip section navigation (2)

Re: More thoughts about planner's cost estimates

From: Greg Stark <gsstark(at)mit(dot)edu>
To: josh(at)agliodbs(dot)com
Cc: Greg Stark <gsstark(at)mit(dot)edu>, David Fetter <david(at)fetter(dot)org>, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: More thoughts about planner's cost estimates
Date: 2006-06-02 20:23:14
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-hackers
Josh Berkus <josh(at)agliodbs(dot)com> writes:

> >     Using a variety of synthetic and real-world data sets, we show that
> >     distinct sampling gives estimates for distinct values queries that
> > are within 0%-10%, whereas previous methods were typically 50%-250% off,
> > across the spectrum of data sets and queries studied.
> Aha.  It's a question of the level of error permissable.   For our 
> estimates, being 100% off is actually OK.  That's why I was looking at 5% 
> block sampling; it stays within the range of +/- 50% n-distinct in 95% of 
> cases.

Well, let's see. Say for example we're scanning 50,000 records out of 1M
records. Using the Theorem from Charikar et al quoted as Theorem 1 in section
2 we get that there is at least a 5% chance of getting a result with a ratio
error at least sqrt((1M-50k)/100k ln(20)) or 5.33.

So no, even assuming you have a good unbiased sample, a 5% sample is only
going to get you to a result within 19%-533% of the real values 95% of the
time. Not 50-250%. And that's a negative result, so it's *at best* 19-533%. On
some distributions it may be outside that range even more than 95% of the

This is entirely unlike the histograms where we have a solid foundation for a
positive result. We can guarantee that the result will be outside +/- x% *at
most* 5% of the time. For most distributions it'll be outside that range even

And a 5% sample is a pretty big. In fact my tests earlier showed the i/o from
5% block sampling took just as long as reading all the blocks. Even if we
figure out what's causing that (IMHO surprising) result and improve matters I
would only expect it to be 3-4x faster than a full scan.


In response to


pgsql-hackers by date

Next:From: Tom LaneDate: 2006-06-02 20:38:59
Subject: Re: COPY (query) TO file
Previous:From: Tino WildenhainDate: 2006-06-02 19:43:04
Subject: Re: COPY (query) TO file

Privacy Policy | About PostgreSQL
Copyright © 1996-2017 The PostgreSQL Global Development Group