DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=mime-version:in-reply-to:references:date:message-id:subject:from:to
	:cc:content-type:content-transfer-encoding;
	b=vusFq/RhX93/VCuPxj319iCFgfBsbjXRFUlzpOZZF8Xo7jukUI5ceu264NFmGyRvo9
	QZoKPXaNoS5KwvF63eO06/Q1LZSR1fIPyGa/R0KDs5/uYFsUvfKK2y0N8ndF55PRCXXO
	Vt82Tc4G1fkTnyU5xewy6qzvj4oxt0N8EiAcg=
MIME-Version: 1.0
In-Reply-To: <17814.1237757356@sss.pgh.pa.us>
References: <49A295F0.5010405@saparev.com> <49A2A450.20002@archonet.com>
	<49A2DFFA.8000001@saparev.com> <18725.1235412110@sss.pgh.pa.us>
	<49A429A3.9010803@saparev.com> <17814.1237757356@sss.pgh.pa.us>
Date: Mon, 23 Mar 2009 01:12:14 +0100
Message-ID: <b1b9fac60903221712n255525a6w8575ccb4a75d56bb@mail.gmail.com>
Subject: Re: LIMIT confuses the planner
From: marcin mank <marcin.mank@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: kouber@saparev.com, pgsql-performance@postgresql.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

> So the bottom line here is just that the estimated n_distinct is too
> low. =A0We've seen before that the equation we use tends to do that more
> often than not. =A0I doubt that consistently erring on the high side woul=
d
> be better though :-(. =A0Estimating n_distinct from a limited sample of
> the population is known to be a statistically hard problem, so we'll
> probably not ever have perfect answers, but doing better is on the
> to-do list.
>

I hit an interestinhg paper on n_distinct calculation:

http://www.pittsburgh.intel-research.net/people/gibbons/papers/distinct-val=
ues-chapter.pdf

the PCSA algorithm described there requires O(1) calculation per
value. Page 22 describes what to do with updates streams.

This I think (disclaimer: I know little about PG internals) means that
the n_distinct estimation can be done during vacuum time (it would
play well with the visibility map addon).

What do You think?

Greetings
Marcin