From: Greg Stark <gsstark@mit.edu>
To: Rod Taylor <rbt@sitesell.com>
Cc: Greg Stark <gsstark@mit.edu>
Cc: Gurmeet Manku <manku@cs.stanford.edu>
Cc: pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] Bad n_distinct estimation; hacks suggested?
Date: 26 Apr 2005 19:28:21 -0400
Message-ID: <87oec15d9m.fsf@stark.xeocode.com> (raw)
In-Reply-To: <1114557011.77587.107.camel@home>
References: <Pine.LNX.4.44.0504261443340.12051-100000@xenon.Stanford.EDU>
<87u0lt5efo.fsf@stark.xeocode.com>
<1114557011.77587.107.camel@home>
Rod Taylor <rbt@sitesell.com> writes:
> On Tue, 2005-04-26 at 19:03 -0400, Greg Stark wrote:
> > This one looks *really* good.
> >
> > http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/dist_sampl.pdf
> >
> > It does require a single full table scan
>
> Ack.. Not by default please.
>
> I have a few large append-only tables (vacuum isn't necessary) which do
> need stats rebuilt periodically.
The algorithm can also naturally be implemented incrementally. Which would be
nice for your append-only tables. But that's not Postgres's current philosophy
with statistics. Perhaps some trigger function that you could install yourself
to update statistics for a newly inserted record would be useful.
The paper is pretty straightforward and easy to read, but here's an executive
summary:
The goal is to gather a uniform sample of *distinct values* in the table as
opposed to a sample of records.
Instead of using a fixed percentage sampling rate for each record, use a hash
of the value to determine whether to include it. At first include everything,
but if the sample space overflows throw out half the values based on their
hash value. Repeat until finished.
In the end you'll have a sample of 1/2^n of your distinct values from your
entire data set where n is large enough for you sample to fit in your
predetermined constant sample space.
--
greg
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: gsstark@mit.edu, rbt@sitesell.com, manku@cs.stanford.edu, pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] Bad n_distinct estimation; hacks suggested?
In-Reply-To: <87oec15d9m.fsf@stark.xeocode.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