Keep useful pages through a large scan

Our shop repeatedly reads product page A and stock page B. The engine has two frames, so both pages fit. A reporting query then reads pages C and D once. Should those one-time reads replace A and B?

You already know the distinction between a page and a frame. Here we examine replacement policy: how the engine chooses which eligible page to evict when it needs a frame.

Trace a policy before judging it

Consider least recently used, or LRU. Among eligible pages, it evicts the one whose most recent use was furthest in the past. Assume every page in this example is clean and unpinned, so eviction does not lose changes or interrupt an active reader.

Use A, then B
Frames hold A and B. A was used less recently.
Report reads C
Evict A. Frames now hold C and B.
Report reads D
Evict B. Frames now hold C and D.
Shop needs A again
A must be fetched again, although the report may never reuse C or D.

A one-time scan has displaced the repeatedly used pages. Cache size stayed constant; cache contents became less useful.

LRU followed its rule correctly. The problem is that recent use was a poor predictor of future use for this mixture of requests. Admission policy asks a separate question: should the newly read page occupy the main cache at all? An engine might give scan pages limited space or wait for evidence of reuse before promoting them.

There is no perfect policy for unknown future requests. Use a workload trace to compare policies, including the cost of maintaining their bookkeeping.

Eligibility still comes before preference

A page that a caller has pinned cannot be replaced until the caller releases it. A modified, or dirty, page cannot simply be discarded. Its changes must be handled under the engine’s writeback and recovery rules.

Pinning protects the frame’s identity while it is in use. It does not by itself stop two callers from changing its bytes together. Later, short-lived structural locks will protect those changes. Keeping these responsibilities separate prevents “it was pinned” from becoming a false explanation of thread safety.

If every frame is pinned, the engine needs a controlled wait or failure path. Quietly reusing a frame would make a caller read the wrong page.

Change the access pattern

Suppose the workload repeats A, B, C forever, but only two frames are available. Can any policy keep all three resident?

Separate policy from capacity

No. Three distinct pages cannot all occupy two frames simultaneously. A better policy may improve a particular sequence, but it cannot remove the capacity constraint. Enlarging the pool, changing the access pattern, or tolerating some misses are different responses to that problem.

We can now explain why a buffer pool needs both correctness rules and workload-aware choices. When we study indexes, remember that fewer page visits and more cache hits are different ways to reduce storage work.

CMU’s buffer-pool project gives an implementation setting for these responsibilities; its selected replacement algorithm differs from this simple LRU trace.

Extended reference

The extended chapter preserves the original technical coverage, additional examples, and citations. The explanation above supplies the concepts needed for this page; the reference develops the specialist cases.

Find a section from the original chapter