Re: Clock sweep not caching enough B-Tree leaf pages?

Jim Nasby <jim(at)nasby(dot)net> wrote:

> In our case this could maybe be handled by simply not
> incrementing counts when there's no eviction... but I'm more a
> fan of separate polls/clocks, because that means you can do
> things like a LFU for active and an LRU for inactive.

I have hesitated to mention some benchmarks I did for optimal
caching techniques for a database load, because they were so old,
but maybe the ideas might spark something of value in the
discussion.  I'm talking about early 1985 on 80286 hardware on DOS
with a Terminate and Stay Resident (TSR) cache external to the
database.  The external cache used LRU caching, and I was looking
at what caching I could do inside the database to improve real
database workloads which tended to include both OLTP and reporting.

I found two types of caches improved performance.  Neither was a
substitute for the LRU cache closer to the hardware, and
eliminating either reduced performance over having both.  One was
index-specific -- each connection caused to be held in cache the
last page at each level of the index.  This proved useful because
in our real life applications it turned out that the next "random"
access on an index was very often the same or near the previous.
The other was a "weighted average" of access counts -- each access
bumped a count and after a certain number of bumps all counts were
reduced by 25%.  This was accomplished by setting each count to the
sum of it's existing value shifted right by one and shifted right
by two.

I understand that with the much larger RAM caches available 30
years later there could be some problems with passing all the
counts atomically without causing a noticeable pause, and the
higher connection counts may cause more contention issues.  But if
those issues could be solved (or somehow dodged for a proof of
concept benchmark) it might be interesting to see how that worked
out.

FWIW, I recall that we used a one byte counter for each page,
running 0 to 255.  I don't recall the number at which we
effectively multiplied by 0.75, and there was nothing particularly
magic about that multiplier other than it was pretty fast and
worked better that 0.5 in my benchmarks.  I also don't remember
what we used as the initial value on a page load.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company