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 509AC5340F; Fri, 29 Apr 2005 02:10:30 -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 27596-03; Fri, 29 Apr 2005 05:10:20 +0000 (GMT) Received: from priv-edtnes51.telusplanet.net (outbound04.telus.net [199.185.220.223]) by svr1.postgresql.org (Postfix) with ESMTP id 64FB55294C; Fri, 29 Apr 2005 02:10:18 -0300 (ADT) Received: from localhost ([199.185.220.240]) by priv-edtnes51.telusplanet.net (InterMail vM.6.01.04.04 201-2131-118-104-20050224) with ESMTP id <20050429051018.XYME14099.priv-edtnes51.telusplanet.net@localhost>; Thu, 28 Apr 2005 23:10:18 -0600 Received: from 64.180.225.200 ( [64.180.225.200]) as user a3a18850@192.168.200.1 by webmail.telus.net with HTTP; Thu, 28 Apr 2005 22:10:18 -0700 Message-ID: <1114751418.4271c1ba12544@webmail.telus.net> Date: Thu, 28 Apr 2005 22:10:18 -0700 From: a3a18850@telus.net To: pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org Cc: Mischa@telus.net, Sandberg@telus.net Subject: Re: Distinct-Sampling (Gibbons paper) for Postgres References: <200504191209.05181.josh@agliodbs.com> <19276.1114442580@sss.pgh.pa.us> <1114454941.21529.245.camel@localhost.localdomain> <200504251213.18565.josh@agliodbs.com> <426D565E.8040400@dunslane.net> <1114580284.426f253cc0087@webmail.telus.net> <426F9703.4010108@dunslane.net> In-Reply-To: <426F9703.4010108@dunslane.net> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.1-cvs X-Originating-IP: 64.180.225.200 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=2.418 tagged_above=0 required=5 tests=DNS_FROM_RFC_POST, FORGED_RCVD_HELO, FROM_ENDS_IN_NUMS, FROM_HAS_MIXED_NUMS, NO_REAL_NAME X-Spam-Level: ** X-Archive-Number: 200504/766 X-Sequence-Number: 12163 Well, this guy has it nailed. He cites Flajolet and Martin, which was (I thought) as good as you could get with only a reasonable amount of memory per statistic. Unfortunately, their hash table is a one-shot deal; there's no way to maintain it once the table changes. His incremental update doesn't degrade as the table changes. If there isn't the same wrangle of patent as with the ARC algorithm, and if the existing stats collector process can stand the extra traffic, then this one is a winner. Many thanks to the person who posted this reference in the first place; so sorry I canned your posting and can't recall your name. Now, if we can come up with something better than the ARC algorithm ...