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

Re: Hashtable entry recycling algorithm in pg_stat_statements

From: "Alex Hunsaker" <badalex(at)gmail(dot)com>
To: "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: "ITAGAKI Takahiro" <itagaki(dot)takahiro(at)oss(dot)ntt(dot)co(dot)jp>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: Hashtable entry recycling algorithm in pg_stat_statements
Date: 2009-01-03 01:20:19
Message-ID: 34d269d40901021720n3e74ed73o32c03b6ad6377d75@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
On Fri, Jan 2, 2009 at 17:22, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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)?

In response to

Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 2009-01-03 01:23:52
Subject: Re: Hashtable entry recycling algorithm in pg_stat_statements
Previous:From: Tom LaneDate: 2009-01-03 00:51:39
Subject: Re: posix_fadvise v22

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