From: Andrew Dunstan <andrew@dunslane.net>
To: josh@agliodbs.com
Cc: gsstark@mit.edu
Cc: marko.ristola@kolumbus.fi
Cc: pgsql-performance@postgresql.org
Cc: pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
Date: Sat, 23 Apr 2005 18:44:28 -0500 (CDT)
Message-ID: <1963.24.211.165.134.1114299868.squirrel@www.dunslane.net> (raw)
In-Reply-To: <200504231639.11897.josh@agliodbs.com>
References: <200504231639.11897.josh@agliodbs.com>
Josh Berkus said:
>
>
> Well, unusual distributions are certainly tough. But I think the
> problem exists even for relatively well-distributed populations.
> Part of it is, I believe, the formula we are using:
>
> n*d / (n - f1 + f1*n/N)
>
[snip]
>
> This is so broken, in fact, that I'm wondering if we've read the paper
> right? I've perused the paper on almaden, and the DUJ1 formula
> appears considerably more complex than the formula we're using.
>
> Can someone whose math is more recent than calculus in 1989 take a look
> at that paper, and look at the formula toward the bottom of page 10,
> and see if we are correctly interpreting it? I'm particularly
> confused as to what "q" and "d-sub-n" represent. Thanks!
>
Math not too recent ...
I quickly read the paper and independently came up with the same formula you
say above we are applying. The formula is on the page that is numbered 6,
although it's the tenth page in the PDF.
q = n/N = ratio of sample size to population size
d_sub_n = d = number of distinct classes in sample
cheers
andrew
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 from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-performance@postgresql.org
Cc: andrew@dunslane.net, josh@agliodbs.com, gsstark@mit.edu, marko.ristola@kolumbus.fi, pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
In-Reply-To: <1963.24.211.165.134.1114299868.squirrel@www.dunslane.net>
References: <200504231639.11897.josh@agliodbs.com> <1963.24.211.165.134.1114299868.squirrel@www.dunslane.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