Skip site navigation (1) Skip section navigation (2)

Re: Distinct-Sampling (Gibbons paper) for Postgres

From: a3a18850(at)telus(dot)net
To: pgsql-performance(at)postgresql(dot)org, pgsql-hackers(at)postgresql(dot)org
Cc: Mischa(at)telus(dot)net, Sandberg(at)telus(dot)net
Subject: Re: Distinct-Sampling (Gibbons paper) for Postgres
Date: 2005-04-29 05:10:18
Message-ID: 1114751418.4271c1ba12544@webmail.telus.net (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-performance
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 ... 


In response to

Responses

pgsql-performance by date

Next:From: Josh BerkusDate: 2005-04-29 05:22:51
Subject: Re: Distinct-Sampling (Gibbons paper) for Postgres
Previous:From: Michael FuhrDate: 2005-04-29 03:28:34
Subject: Re: index on different types

pgsql-hackers by date

Next:From: Josh BerkusDate: 2005-04-29 05:22:51
Subject: Re: Distinct-Sampling (Gibbons paper) for Postgres
Previous:From: Christopher BrowneDate: 2005-04-29 04:57:58
Subject: Re: Feature freeze date for 8.1

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group