pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Josh Berkus <josh@agliodbs.com>
To: Andrew Dunstan <andrew@dunslane.net>
Cc: gsql-perform <pgsql-performance@postgresql.org>
Cc: pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
Date: Sun, 24 Apr 2005 11:30:50 -0700
Message-ID: <200504241130.50218.josh@agliodbs.com> (raw)
In-Reply-To: <426BDE32.4070004@dunslane.net>
References: <200504191209.05181.josh@agliodbs.com>
	<25382.1114318139@sss.pgh.pa.us>
	<426BDE32.4070004@dunslane.net>

Andrew,

> The math in the paper does not seem to look at very low levels of q (=
> sample to pop ratio).

Yes, I think that's the failing.   Mind you, I did more testing and found out 
that for D/N ratios of 0.1 to 0.3, the formula only works within 5x accuracy 
(which I would consider acceptable) with a sample size of 25% or more (which 
is infeasable in any large table).    The formula does work for populations 
where D/N is much lower, say 0.01.  So overall it seems to only work for 1/4 
of cases; those where n/N is large and D/N is low.   And, annoyingly, that's 
probably the population where accurate estimation is least crucial, as it 
consists mostly of small tables.

I've just developed (not original, probably, but original to *me*) a formula 
that works on populations where n/N is very small and D/N is moderate (i.e. 
0.1 to 0.4):

N * (d/n)^(sqrt(N/n))

However, I've tested it only on (n/N < 0.005 and D/N > 0.1 and D/N < 0.4) 
populations, and only 3 of them to boot.   I'd appreciate other people trying 
it on their own data populations, particularly very different ones, like D/N 
> 0.7 or D/N < 0.01.

Further, as Andrew points out we presumably do page sampling rather than 
purely random sampling so I should probably read the paper he referenced.  
Working on it now ....

-- 
Josh Berkus
Aglio Database Solutions
San Francisco



view thread (53+ messages)  latest in thread

Message-ID: <200504241130.50218.josh@agliodbs.com>
Permalink:  ../200504241130.50218.josh@agliodbs.com/
Also on:    postgresql.org/message-id/200504241130.50218.josh@agliodbs.com

 · 

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: josh@agliodbs.com, andrew@dunslane.net, pgsql-hackers@postgresql.org
  Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
  In-Reply-To: <200504241130.50218.josh@agliodbs.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