From: a3a18850@telus.net
To: pgsql-performance@postgresql.org
To: pgsql-hackers@postgresql.org
Cc: Mischa@telus.net
Cc: Sandberg@telus.net
Subject: Re: Distinct-Sampling (Gibbons paper) for Postgres
Date: Thu, 28 Apr 2005 22:10:18 -0700
Message-ID: <1114751418.4271c1ba12544@webmail.telus.net> (raw)
In-Reply-To: <426F9703.4010108@dunslane.net>
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>
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 ...
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-performance@postgresql.org
Cc: a3a18850@telus.net, pgsql-hackers@postgresql.org, Mischa@telus.net, Sandberg@telus.net
Subject: Re: Distinct-Sampling (Gibbons paper) for Postgres
In-Reply-To: <1114751418.4271c1ba12544@webmail.telus.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