Why Replacement Policies Matter
When a buffer pool is full and a new page must be loaded, the system must choose a victim frame to evict. The replacement policy determines which page gets evicted, and the choice has an enormous impact on cache hit rate and overall database performance.
LRU (Least Recently Used)
The simplest approach: evict the page that was accessed least recently. LRU works well for many workloads but has a critical weakness — sequential scan pollution. A single full-table scan loads every page in the table, evicting hot pages that were serving frequent point queries. After the scan, the cache is filled with pages that may never be accessed again.
LRU-K
LRU-K tracks the K-th most recent access for each page (typically K=2). Instead of evicting the page with the oldest last access, it evicts the page whose K-th most recent access is the oldest. Pages accessed only once (like scan pages) have no K-th access recorded and are evicted first. This makes LRU-K scan-resistant — a sequential scan will not pollute the cache because scan pages only accumulate a single access timestamp.
The algorithm maintains a history of the last K access timestamps for each page. When choosing a victim, it compares the K-th oldest timestamp across all unpinned pages and evicts the one with the smallest (oldest) value. Pages with fewer than K accesses are always preferred for eviction.
Clock Algorithm
The clock algorithm is an efficient approximation of LRU. It arranges frames in a circular buffer and maintains a clock hand that sweeps around:
- Each frame has a reference bit (initially 0).
- When a page is accessed, set its reference bit to 1.
- To find a victim: advance the clock hand. If the current frame's reference bit is 1, clear it to 0 and move on (giving it a "second chance"). If the reference bit is already 0 and the frame is unpinned, evict it.
Clock is O(1) amortized and uses much less bookkeeping than true LRU. PostgreSQL uses a variant called clock-sweep for its buffer pool.
Other Policies
- FIFO — evict the oldest page. Simple but ignores frequency entirely.
- Random — pick a random victim. Surprisingly decent average case, zero overhead.
- MRU (Most Recently Used) — useful for repeated sequential scans of the same data.
| Policy | Scan-resistant? | Overhead | Used by |
|---|---|---|---|
| LRU | No | Medium | Many systems |
| LRU-K | Yes | High | SQL Server |
| Clock | Partially | Low | PostgreSQL |
| FIFO | No | Very low | Simple caches |
Sequential Scan Pollution
Consider a buffer pool with 4 frames holding hot pages A, B, C, D — all frequently accessed by point queries. Now a SELECT * FROM large_table scans 100 pages sequentially.
With plain LRU:
- Page 1 of the scan evicts A (least recently used).
- Page 2 evicts B. Page 3 evicts C. Page 4 evicts D.
- The buffer pool is now full of scan pages that will never be read again.
- Subsequent point queries for A, B, C, D all miss — performance collapses.
With LRU-2 (K=2):
- Pages A, B, C, D each have 2+ recent accesses recorded. Their 2nd-most-recent access is still relatively fresh.
- Scan page 1 has only 1 access. It is the preferred victim.
- Scan page 2 replaces scan page 1 (which also has only 1 access).
- Hot pages A, B, C, D remain in the cache throughout the scan.
- Point queries continue to hit — no performance degradation.
With Clock:
- A, B, C, D have reference bits set to 1 from recent queries.
- The clock hand sweeps, clearing their bits (second chance), and may eventually evict one. But scan pages get their bits set too, so clock is partially resistant — not as strong as LRU-K but much better than plain LRU.