From: marcin mank <marcin.mank@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: kouber@saparev.com
Cc: pgsql-performance@postgresql.org
Subject: Re: LIMIT confuses the planner
Date: Mon, 23 Mar 2009 01:12:14 +0100
Message-ID: <b1b9fac60903221712n255525a6w8575ccb4a75d56bb@mail.gmail.com> (raw)
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>
> So the bottom line here is just that the estimated n_distinct is too
> low. We've seen before that the equation we use tends to do that more
> often than not. I doubt that consistently erring on the high side would
> be better though :-(. Estimating 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-values-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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: marcin.mank@gmail.com, tgl@sss.pgh.pa.us, kouber@saparev.com
Subject: Re: LIMIT confuses the planner
In-Reply-To: <b1b9fac60903221712n255525a6w8575ccb4a75d56bb@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox