X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id 839DD53A62; Wed, 27 Apr 2005 04:48:36 -0300 (ADT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 69993-02; Wed, 27 Apr 2005 07:48:32 +0000 (GMT) Received: from cmailg1.svr.pol.co.uk (cmailg1.svr.pol.co.uk [195.92.195.171]) by svr1.postgresql.org (Postfix) with ESMTP id 793C853626; Wed, 27 Apr 2005 04:48:31 -0300 (ADT) Received: from modem-3262.lion.dialup.pol.co.uk ([217.135.172.190] helo=192.168.0.102) by cmailg1.svr.pol.co.uk with esmtp (Exim 4.41) id 1DQhHW-0000aW-Dx; Wed, 27 Apr 2005 08:48:26 +0100 Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested? From: Simon Riggs To: Gurmeet Manku Cc: Tom Lane , josh@agliodbs.com, Greg Stark , Marko Ristola , pgsql-perform , pgsql-hackers@postgresql.org, Utkarsh Srivastava , snt@iastate.edu In-Reply-To: References: Content-Type: text/plain Organization: 2nd Quadrant Date: Wed, 27 Apr 2005 08:45:10 +0100 Message-Id: <1114587910.21529.394.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Evolution 2.0.2 (2.0.2-3) Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.05 tagged_above=0 required=5 tests=AWL, FORGED_RCVD_HELO X-Spam-Level: X-Archive-Number: 200504/720 X-Sequence-Number: 12117 On Tue, 2005-04-26 at 15:00 -0700, Gurmeet Manku wrote: > 2. In a single scan, it is possible to estimate n_distinct by using > a very simple algorithm: > > "Distinct sampling for highly-accurate answers to distinct value > queries and event reports" by Gibbons, VLDB 2001. > > http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/dist_sampl.pdf That looks like the one... ...though it looks like some more complex changes to the current algorithm to use it, and we want the other stats as well... > 3. In fact, Gibbon's basic idea has been extended to "sliding windows" > (this extension is useful in streaming systems like Aurora / Stream): > > "Distributed streams algorithms for sliding windows" > by Gibbons and Tirthapura, SPAA 2002. > > http://home.eng.iastate.edu/~snt/research/tocs.pdf > ...and this offers the possibility of calculating statistics at load time, as part of the COPY command Best Regards, Simon Riggs