Re: Page replacement algorithm in buffer cache

Ants Aasma <ants@cybertec.at> writes:
> You might want to check out the LIRS cache replacement algorithm [1].
> That algorithm tries to estimate least frequently used instead of
> least recently used. Mysql uses it for their buffer replacement
> policy. There is also a clock sweep based approximation called
> CLOCK-Pro. Papers describing and evaluating both are available on the
> net. The evaluations in the papers showed significantly better
> performance for both of those compared to regular clock sweep or even
> ARC.

I seem to recall that CLOCK-Pro, or something named similarly to that,
was one of the alternatives discussed when we went over to the current
clock-sweep approach.  And we definitely looked at ARC.  It might be
worth checking the archives from back then to see what's already been
considered.

> However, I think the main issue isn't finding new algorithms that are
> better in some specific circumstances. The hard part is figuring out
> whether their performance is better in general.

Yeah. You can prove almost anything with the right set of test cases :-(
        regards, tom lane