To: Rod Taylor <rbt@sitesell.com>
Cc: Greg Stark <gsstark@mit.edu>,
	Gurmeet Manku <manku@cs.stanford.edu>, pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] Bad n_distinct estimation; hacks suggested?
References: <Pine.LNX.4.44.0504261443340.12051-100000@xenon.Stanford.EDU>
	<87u0lt5efo.fsf@stark.xeocode.com> <1114557011.77587.107.camel@home>
In-Reply-To: <1114557011.77587.107.camel@home>
From: Greg Stark <gsstark@mit.edu>
Organization: The Emacs Conspiracy; member since 1992
Date: 26 Apr 2005 19:28:21 -0400
Message-ID: <87oec15d9m.fsf@stark.xeocode.com>
Lines: 37
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii

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