pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Mischa Sandberg <mischa.sandberg@telus.net>
To: pgsql-perform <pgsql-performance@postgresql.org>
To: pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] Bad n_distinct estimation; hacks suggested?
Date: Tue,  3 May 2005 19:52:16 -0700
Message-ID: <1115175136.427838e0ae263@webmail.telus.net> (raw)
In-Reply-To: <200505031443.44859.josh@agliodbs.com>
References: <200504191209.05181.josh@agliodbs.com>
	<4277774F.7040205@logix-tt.com>
	<1115155990.4277ee16aba34@webmail.telus.net>
	<200505031443.44859.josh@agliodbs.com>

Quoting Josh Berkus <josh@agliodbs.com>: 
 
> Mischa, 
>  
> > Okay, although given the track record of page-based sampling for 
> > n-distinct, it's a bit like looking for your keys under the 
> streetlight, 
> > rather than in the alley where you dropped them :-) 
>  
> Bad analogy, but funny. 
 
Bad analogy? Page-sampling effort versus row-sampling effort, c'est 
moot. It's not good enough for stats to produce good behaviour on the 
average. Straight random sampling, page or row, is going to cause 
enough untrustworthy engine behaviour,for any %ages small enough to 
allow sampling from scratch at any time. 
 
I'm curious what the problem is with relying on a start-up plus 
incremental method, when the method in the distinct-sampling paper 
doesn't degenerate: you can start when the table is still empty. 
Constructing an index requires an initial full scan plus incremental 
update; what's the diff? 
 
> Unless, of course, we use indexes for sampling, which seems like a 
> *really  
> good* idea to me .... 
 
"distinct-sampling" applies for indexes, too. I started tracking the 
discussion of this a bit late.  Smart method for this is in VLDB'92: 
Gennady Antoshenkov, "Random Sampling from Pseudo-ranked B+-trees". I 
don't think this is online anywhere, except if you have a DBLP 
membership. Does nybod else know better? 
Antoshenkov was the brains behind some of the really cool stuff in DEC 
Rdb (what eventually became Oracle). Compressed bitmap indices, 
parallel competing query plans, and smart handling of keys with 
hyperbolic distributions.  
--  
Engineers think equations approximate reality. 
Physicists think reality approximates the equations. 
Mathematicians never make the connection. 




view thread (53+ messages)

Message-ID: <1115175136.427838e0ae263@webmail.telus.net>
Permalink:  ../1115175136.427838e0ae263@webmail.telus.net/
Also on:    postgresql.org/message-id/1115175136.427838e0ae263@webmail.telus.net

 · 

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: mischa.sandberg@telus.net, pgsql-hackers@postgresql.org
  Subject: Re: [PERFORM] Bad n_distinct estimation; hacks suggested?
  In-Reply-To: <1115175136.427838e0ae263@webmail.telus.net>

* 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