Re: Hashtable entry recycling algorithm in pg_stat_statements

On Fri, Jan 2, 2009 at 17:22, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> A couple of other possibilities that seem a bit saner:
>
> 1. Use a self-organizing list: any time an entry is referenced,
> move it to front, and when you need a new entry take the oldest
> one off the back.  I don't see a way to do that without a global
> lock that protects the list links, but there could be a spinlock
> that's held only long enough to manipulate the list links.
>
> 2. Use a clock sweep algorithm similar to bufmgr's.
>
> Either of these trades off accuracy of deciding which existing cache
> entries are "least interesting" in order to reduce the maintenance
> overhead --- but it doesn't appear to me that the code implements usage
> counts in a way that would justify treating them as sacrosanct
> indicators of relative usefulness anyhow.
>
> The first option seems attractively simple and predictable in
> performance --- all operations are O(1).

Its seems to me a linear list would make the "common" case where the
query is already in the list but we need to update the stats slow.  Or
am I just thinking to abstractly and the list is not a pg_list.h list
but just a c array and use a simple hash. (or I guess we could "hash"
and the use list_nth_cel()... but that *seems* slow)?