From: Josh Berkus <josh@agliodbs.com>
Reply-To: josh@agliodbs.com
Organization: Aglio Database Solutions
To: pgsql-hackers@postgresql.org
Subject: Re: Overhauling GUCS
Date: Mon, 9 Jun 2008 16:49:21 -0700
User-Agent: KMail/1.8
References: <48409D1E.3070208@agliodbs.com> <484D6C1C.5070004@agliodbs.com>
	<87d4mqwdm8.fsf@oxford.xeocode.com>
In-Reply-To: <87d4mqwdm8.fsf@oxford.xeocode.com>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200806091649.22281.josh@agliodbs.com>

Greg,

> Speak to the statisticians. Our sample size is calculated using the same
> theory behind polls which sample 600 people to learn what 250 million
> people are going to do on election day. You do NOT need (significantly)
> larger samples for larger populations.

Your analogy is bad.  For elections, the voters have only a few choices.  
In a 300 million row table, there could be 300 million different values, 
and the histogram becomes less accurate for every order of magnitude 
smaller than 300 million it is.

> Also, our estimates for n_distinct are very unreliable. The math behind
> sampling for statistics just doesn't work the same way for properties
> like n_distinct. For that Josh is right, we *would* need a sample size
> proportional to the whole data set which would practically require us to
> scan the whole table (and have a technique for summarizing the results
> in a nearly constant sized data structure).

Actually, a number of papers have shown block-based algorithms which can 
arrive a reasonably confident (between 50% and 250% of accurate) estimates 
based on scanning only 5% of *blocks*.  Simon did some work on this a 
couple years ago, but he and I had difficultly convincing -hackers that a 
genuine problem existed.

You're correct that we'd need to change pg_statistic, though.  For one 
thing, we need to separate the sample size from the histogram size.

Also, we seem to be getting pretty far away from the original GUC 
discussion.

-- 
--Josh

Josh Berkus
PostgreSQL @ Sun
San Francisco