Re: ARC patent - Mailing list pgsql-hackers

From Neil Conway
Subject Re: ARC patent
Date
Msg-id 1106087629.22946.157.camel@localhost.localdomain
Whole thread Raw
In response to Re: ARC patent  (Andrew Dunstan <andrew@dunslane.net>)
List pgsql-hackers
On Mon, 2005-01-17 at 15:11 -0500, Andrew Dunstan wrote:
> There's a very recent paper at 
> http://carmen.cs.uiuc.edu/~zchen9/paper/TPDS-final.ps on an alternative 
> to ARC which claims superior performance ...

>From a quick glance, this doesn't look applicable. The authors are
discussing buffer replacement strategies for a multi-level cache
hierarchy (e.g. they would call the DBMS buffer cache "L1", and the
kernel I/O cache "L2" -- note that despite the terminology, this has
little in common with L1/L2 caches in processors). They don't really
address caching for the L1-only case -- they're concerned with proposing
algorithms to manage the L2 cache (with or without explicit knowledge
about the content of the L1 cache).

A few years ago Tom implemented the LRU-K replacement policy[1], but
AFAIK the performance results from that weren't very positive (since the
implementation of LRU-K requires a heap and is therefore logarithmic
rather than constant time, that makes sense). The 2Q algorithm looks
like it might be worth investigating[2].

-Neil

[1] http://citeseer.ist.psu.edu/16869.html
[2] http://citeseer.ist.psu.edu/63909.html



pgsql-hackers by date:

Previous
From: Reini Urban
Date:
Subject: Re: Some things I like to pick from the TODO list ...
Next
From: Sailesh Krishnamurthy
Date:
Subject: Re: Much Ado About COUNT(*)