Message-ID: <4136ffa0812121001x3fde1871t558fd8c58070b7d@mail.gmail.com>
Date: Fri, 12 Dec 2008 18:01:40 +0000
From: "Greg Stark" <stark@enterprisedb.com>
To: "Simon Riggs" <simon@2ndquadrant.com>
Subject: Re: benchmarking the query planner
Cc: "Robert Haas" <robertmhaas@gmail.com>, "Tom Lane" <tgl@sss.pgh.pa.us>,
	"Kevin Grittner" <Kevin.Grittner@wicourts.gov>,
	"jd@commandprompt.com" <jd@commandprompt.com>,
	"Josh Berkus" <josh@agliodbs.com>,
	"Greg Smith" <gsmith@gregsmith.com>, pgsql-hackers@postgresql.org
In-Reply-To: <1229103209.8673.62.camel@ebony.2ndQuadrant>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <603c8f070812061019r5aca3aajeaa5493b11c5feff@mail.gmail.com>
	<1229039044.13078.193.camel@hp_dx2400_1>
	<4136ffa0812111823u645b6ec9wdca60b3da4b00499@mail.gmail.com>
	<1229072675.13078.196.camel@hp_dx2400_1>
	<603c8f070812120344m67ef2c1fs41806cfb4ff9e396@mail.gmail.com>
	<1229093975.13078.275.camel@ebony.2ndQuadrant>
	<87tz99s7bu.fsf@oxford.xeocode.com>
	<1229100057.8673.29.camel@ebony.2ndQuadrant>
	<87hc59s4qx.fsf@oxford.xeocode.com>
	<1229103209.8673.62.camel@ebony.2ndQuadrant>

On Fri, Dec 12, 2008 at 5:33 PM, Simon Riggs <simon@2ndquadrant.com> wrote:
>> Incidentally we *do* do block sampling. We pick random blocks and then pick
>> random records within those blocks. This was new in, uh, 7.4? 8.0? Sometime
>> around then. It dramatically reduced the i/o requirements but there were long
>> discussions of how to do it without introducing biases.
>
> No, we pick random rows. On bigger tables, they get further apart
> typically and so we miss any clustering. I mean that we should pick a
> random block and read all rows on it.

I think what's happening here is that our sampling method is based on
the assumption that a records location is not related to its value.

Consider a table which is clustered and has two copies of each value.
When we look at a block and see n/2 values and we know there are 1000
blocks then a human would conjecture that there are 1000*n/2 distinct
values throughout the table and every value is represented twice
throughout the whole table. But if we're assuming the records are
randomly distributed then looking at the whole block will actually
throw us off completely. We'll deduce from the fact that we saw every
value twice that there must be hundreds of copies spread throughout
the database and there must be a lot less than 1000*n/2 distinct
values.

I think you need to find two different formulas, one which represents
a clustered table and one which represents randomly distributed data.
Then you need a way to measure just how clustered the data is so you
know how much weight to give each formula. Perhaps comparing the
number of duplicates in whole-block samples versus overall random
selections would give that measure.

-- 
greg