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

I've been meaning to write this since PGConf and now isn't a great time
since I'm on my phone but I think it's time.

The way the clock sweep algorithm is meant to be thought about is that it's
an approximate lru. Each usage count corresponds to an ntile of the lru. So
we don't know which buffer is least recently used but it must be in the set
of buffers with usage count 0 and that should be 1/nth of all the buffers.

In order for that property to be maintained though the usage count for some
buffer should be getting decremented every time we touch a buffer. That is,
every time we promote one buffer to the most recently moved ntile we should
be demoting some other buffer.

The way our cache works we promote when a buffer is accessed but we only
demote when a buffer is flushed. We flush a lot less often than we touch
buffers so it's not surprising that the cache ends up full of buffers that
are all in the "most recently used" section.

Now it's complicated by the fact that we aren't promoting buffers directly
to the most recently used ntile. We're incrementing the usage count by one.
That makes it more of a "least frequently used" list rather than a lru. I
think that's a mistake but I recall some debate about that when it first
went in.