From: Josh Berkus <josh@agliodbs.com>
Reply-To: josh@agliodbs.com
Organization: Aglio Database Solutions
To: Greg Stark <gsstark@mit.edu>
Subject: Re: More thoughts about planner's cost estimates
Date: Fri, 2 Jun 2006 12:23:34 -0700
User-Agent: KMail/1.8
Cc: David Fetter <david@fetter.org>, Tom Lane <tgl@sss.pgh.pa.us>,
	pgsql-hackers@postgresql.org
References: <14821.1149104747@sss.pgh.pa.us>
	<20060602010412.GI10906@fetter.org>
	<87ac8vfptu.fsf@stark.xeocode.com>
In-Reply-To: <87ac8vfptu.fsf@stark.xeocode.com>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200606021223.35168.josh@agliodbs.com>

Greg,

>     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.

> Doing a bit of basic searching around I think the tool we're looking for
> here is called a "chi-squared test for independence".

Augh.  I wrote a program (in Pascal) to do this back in 1988.   Now I can't 
remember the math.  For a two-column test it's relatively 
computation-light, though, as I recall ... but I don't remember standard 
chi square works with a random sample.


-- 
--Josh

Josh Berkus
PostgreSQL @ Sun
San Francisco