pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Simon Riggs <simon@2ndquadrant.com>
To: Gurmeet Manku <manku@CS.Stanford.EDU>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: josh@agliodbs.com, Greg Stark <gsstark@mit.edu>
Cc: Marko Ristola <marko.ristola@kolumbus.fi>
Cc: pgsql-perform <pgsql-performance@postgresql.org>
Cc: pgsql-hackers@postgresql.org, Utkarsh Srivastava <usriv@xenon.Stanford.EDU>
Cc: snt@iastate.edu
Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
Date: Wed, 27 Apr 2005 08:45:10 +0100
Message-ID: <1114587910.21529.394.camel@localhost.localdomain> (raw)
In-Reply-To: <Pine.LNX.4.44.0504261443340.12051-100000@xenon.Stanford.EDU>
References: <Pine.LNX.4.44.0504261443340.12051-100000@xenon.Stanford.EDU>

On Tue, 2005-04-26 at 15:00 -0700, Gurmeet Manku wrote:

>  2. In a single scan, it is possible to estimate n_distinct by using
>     a very simple algorithm:
> 
>  "Distinct sampling for highly-accurate answers to distinct value
>   queries and event reports" by Gibbons, VLDB 2001.
> 
>  http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/dist_sampl.pdf

That looks like the one...

...though it looks like some more complex changes to the current
algorithm to use it, and we want the other stats as well...

>  3. In fact, Gibbon's basic idea has been extended to "sliding windows" 
>     (this extension is useful in streaming systems like Aurora / Stream):
> 
>  "Distributed streams algorithms for sliding windows"
>  by Gibbons and Tirthapura, SPAA 2002.
> 
>  http://home.eng.iastate.edu/~snt/research/tocs.pdf
> 

...and this offers the possibility of calculating statistics at load
time, as part of the COPY command

Best Regards, Simon Riggs




view thread (53+ messages)  latest in thread

Message-ID: <1114587910.21529.394.camel@localhost.localdomain>
Permalink:  ../1114587910.21529.394.camel@localhost.localdomain/
Also on:    postgresql.org/message-id/1114587910.21529.394.camel@localhost.localdomain

 · 

reply

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: simon@2ndquadrant.com, manku@CS.Stanford.EDU, tgl@sss.pgh.pa.us, gsstark@mit.edu, marko.ristola@kolumbus.fi, usriv@xenon.Stanford.EDU, snt@iastate.edu
  Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
  In-Reply-To: <1114587910.21529.394.camel@localhost.localdomain>

* 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