Received: from localhost (unknown [200.46.204.183]) by developer.postgresql.org (Postfix) with ESMTP id 491C72E00D5 for ; Mon, 9 Jun 2008 20:02:35 -0300 (ADT) Received: from developer.postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 94168-04 for ; Mon, 9 Jun 2008 20:02:19 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from oxford.xeocode.com (87-127-95-198.no-dns-yet.enta.net [87.127.95.198]) by developer.postgresql.org (Postfix) with ESMTP id EC5F52E0092 for ; Mon, 9 Jun 2008 20:01:59 -0300 (ADT) Received: from localhost ([127.0.0.1] helo=oxford.xeocode.com) by oxford.xeocode.com with esmtp (Exim 4.69) (envelope-from ) id 1K5qN0-0001gV-3O; Tue, 10 Jun 2008 00:01:46 +0100 To: "Hakan Kocaman" Cc: "Josh Berkus" , "Joshua D. Drake" , "Tom Lane" , "Robert Treat" , , "Peter Eisentraut" , "Greg Smith" , "Andreas Pflug" , "Decibel!" Subject: Re: Overhauling GUCS In-Reply-To: <48ca23600806091417u546f3b6dm6314bc55aaa147f6@mail.gmail.com> (Hakan Kocaman's message of "Mon\, 9 Jun 2008 23\:17\:08 +0200") User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.1 (gnu/linux) X-Draft-From: ("nnimap+mail01.enterprisedb.com:INBOX" 87074) 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> From: Gregory Stark Organization: EnterpriseDB Date: Tue, 10 Jun 2008 00:01:45 +0100 Message-ID: <87ve0ius9y.fsf@oxford.xeocode.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200806/424 X-Sequence-Number: 119537 "Hakan Kocaman" writes: > On 6/9/08, Gregory Stark 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!