From: Gregory Stark <stark@enterprisedb.com>
To: Hakan Kocaman <hkocam@googlemail.com>
Cc: Josh Berkus <josh@agliodbs.com>
Cc: Joshua D. Drake <jd@commandprompt.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Robert Treat <xzilla@users.sourceforge.net>
Cc: pgsql-hackers@postgresql.org
Cc: Peter Eisentraut <peter_e@gmx.net>
Cc: Greg Smith <gsmith@gregsmith.com>
Cc: Andreas Pflug <pgadmin@pse-consulting.de>
Cc: Decibel! <decibel@decibel.org>
Subject: Re: Overhauling GUCS
Date: Tue, 10 Jun 2008 00:01:45 +0100
Message-ID: <87ve0ius9y.fsf@oxford.xeocode.com> (raw)
In-Reply-To: <48ca23600806091417u546f3b6dm6314bc55aaa147f6@mail.gmail.com>
References: <48409D1E.3070208@agliodbs.com>
<29525.1212613052@sss.pgh.pa.us>
<200806061435.01196.peter_e@gmx.net>
<200806061624.29105.xzilla@users.sourceforge.net>
<8358.1212797962@sss.pgh.pa.us>
<1212800891.14299.35.camel@jd-laptop>
<87hcc3le52.fsf@oxford.xeocode.com>
<484D6C1C.5070004@agliodbs.com>
<87d4mqwdm8.fsf@oxford.xeocode.com>
<48ca23600806091417u546f3b6dm6314bc55aaa147f6@mail.gmail.com>
"Hakan Kocaman" <hkocam@googlemail.com> writes:
> On 6/9/08, Gregory Stark <stark@enterprisedb.com> wrote:
>>
>> n_distinct. For that Josh is right, we *would* need a sample size
>> proportional to the whole data set which would practically require us to
>> scan the whole table (and have a technique for summarizing the results in a
>> nearly constant sized data structure).
>
> is this (summarizing results in a constant sized data structure) something
> which could be achived by Bloom-Filters ?
Uhm, it would be a bit of a strange application of them but actually it seems
to me that would be a possible approach. It would need a formula for
estimating the number of distinct values given the number of bits set in the
bloom filter. That should be a tractable combinatorics problem (in fact it's
pretty similar to the combinatorics I posted a while back about getting all
the drives in a raid array busy). And if you have a dynamic structure where
the filter size grows then it would overestimate because extra copied bits
would be set.
--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's RemoteDBA services!
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-hackers@postgresql.org
Cc: stark@enterprisedb.com, hkocam@googlemail.com, josh@agliodbs.com, jd@commandprompt.com, tgl@sss.pgh.pa.us, xzilla@users.sourceforge.net, peter_e@gmx.net, gsmith@gregsmith.com, pgadmin@pse-consulting.de, decibel@decibel.org
Subject: Re: Overhauling GUCS
In-Reply-To: <87ve0ius9y.fsf@oxford.xeocode.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