Keeping the right pages in memory

1 The weakness of plain LRU

First, let's recall the setup from Session 4. The buffer pool is a region of the database's RAM divided into fixed-size slots called frames. Each frame can hold one disk page (a fixed-size block, often 4 KB–16 KB). When a query needs a page, the system checks the buffer pool first:

That step 3 — choosing which page to kick out — is the job of the replacement policy (also called the eviction policy). A cache hit means the page was already in RAM (cheap, nanoseconds); a cache miss forces a disk read (expensive, often thousands of times slower). The whole game is to maximise the hit rate by keeping the pages we're most likely to reuse.

Recalling LRU

LRU (Least Recently Used) is the classic policy: when you must evict, throw out the page that hasn't been touched for the longest time. The bet is simple and usually good — recently used pages are likely to be used again soon (this is called temporal locality). LRU is typically implemented with a doubly-linked list (or an equivalent) where every access moves the page to the "most recently used" front; the victim is always the page at the "least recently used" back.

Here is a complete O(1) LRU frame manager: a hash map from page_id to a node, plus a doubly-linked list ordering nodes from most- to least-recently-used. Every access splices the node to the front; eviction unlinks the node at the back.

# Classic LRU buffer-pool frame manager: hash map + doubly-linked list, O(1)
class Node:
    def __init__(self, page_id):
        self.page_id = page_id
        self.prev = self.next = None

class LRUBufferPool:
    def __init__(self, capacity):
        self.capacity = capacity
        self.table = {}                 # page_id -> Node
        # sentinel head (MRU side) and tail (LRU side)
        self.head, self.tail = Node(None), Node(None)
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, n):
        n.prev.next, n.next.prev = n.next, n.prev

    def _push_front(self, n):       # insert right after head = MRU
        n.prev, n.next = self.head, self.head.next
        self.head.next.prev = n
        self.head.next = n

    def access(self, page_id):       # returns "HIT" or "MISS"
        n = self.table.get(page_id)
        if n is not None:
            self._unlink(n)
            self._push_front(n)         # promote to MRU
            return "HIT"
        if len(self.table) >= self.capacity:
            self._evict()
        n = Node(page_id)
        self.table[page_id] = n
        self._push_front(n)
        return "MISS"

    def _evict(self):                # victim = node before tail (LRU)
        victim = self.tail.prev
        self._unlink(victim)
        del self.table[victim.page_id]
        return victim.page_id

if __name__ == "__main__":
    bp = LRUBufferPool(3)
    for p in [1, 2, 3, 1, 4, 2]:   # access 4 evicts LRU page 2 (then 2 misses again)
        print(p, bp.access(p))

// Classic LRU buffer-pool frame manager: hash map + doubly-linked list, O(1)
#include <iostream>
#include <unordered_map>
#include <list>

class LRUBufferPool {
    size_t capacity_;
    std::list<int> order_;                                  // front = MRU, back = LRU
    std::unordered_map<int, std::list<int>::iterator> table_;  // page_id -> node
public:
    explicit LRUBufferPool(size_t capacity) : capacity_(capacity) {}

    std::string access(int page_id) {                       // returns "HIT" or "MISS"
        auto it = table_.find(page_id);
        if (it != table_.end()) {
            order_.splice(order_.begin(), order_, it->second);  // promote to MRU
            return "HIT";
        }
        if (table_.size() >= capacity_) evict();
        order_.push_front(page_id);
        table_[page_id] = order_.begin();
        return "MISS";
    }

    int evict() {                                          // victim = back of list (LRU)
        int victim = order_.back();
        order_.pop_back();
        table_.erase(victim);
        return victim;
    }
};

int main() {
    LRUBufferPool bp(3);
    for (int p : {1, 2, 3, 1, 4, 2})        // access 4 evicts LRU page 2
        std::cout << p << " " << bp.access(p) << "\n";
}

// Classic LRU buffer-pool frame manager: hash map + doubly-linked list, O(1)
import java.util.HashMap;

public class LRUBufferPool {
    static class Node {
        int pageId;
        Node prev, next;
        Node(int pageId) { this.pageId = pageId; }
    }

    private final int capacity;
    private final HashMap<Integer, Node> table = new HashMap<>();
    private final Node head = new Node(-1), tail = new Node(-1);  // sentinels

    public LRUBufferPool(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }

    private void pushFront(Node n) {              // insert after head = MRU
        n.prev = head; n.next = head.next;
        head.next.prev = n; head.next = n;
    }

    public String access(int pageId) {           // returns "HIT" or "MISS"
        Node n = table.get(pageId);
        if (n != null) {
            unlink(n); pushFront(n);             // promote to MRU
            return "HIT";
        }
        if (table.size() >= capacity) evict();
        n = new Node(pageId);
        table.put(pageId, n);
        pushFront(n);
        return "MISS";
    }

    public int evict() {                          // victim = node before tail (LRU)
        Node victim = tail.prev;
        unlink(victim);
        table.remove(victim.pageId);
        return victim.pageId;
    }

    public static void main(String[] args) {
        LRUBufferPool bp = new LRUBufferPool(3);
        for (int p : new int[]{1, 2, 3, 1, 4, 2})  // access 4 evicts LRU page 2
            System.out.println(p + " " + bp.access(p));
    }
}

So where does LRU break?

LRU has one fatal blind spot: it only looks at how recently a page was touched, never at how often. To LRU, a page touched once a moment ago looks more valuable than a page touched a thousand times but a little while back. A single large query that reads many pages exactly once — a full table scan — can therefore stream a flood of "use-once" pages through the cache, each marked "most recently used," pushing out the genuinely hot pages.

The takeaway is not "LRU is bad" — for ordinary workloads it's great. The takeaway is that LRU has a known failure mode under large scans, and smarter policies try to tell "used once by accident" apart from "genuinely hot." That's exactly what Topic 2 builds.

2 LRU-K: counting references, not just recency

LRU-K (O'Neil, O'Neil & Weikum, 1993) generalises LRU. Plain LRU only remembers the single most recent access to each page. LRU-K instead remembers the timestamps of the last K accesses. From those it estimates each page's reuse distance — roughly, "how long until I'd expect to touch this page again." It evicts the page whose predicted next use is farthest away.

The key quantity: backward K-distance

For each page, look back through history and find the timestamp of its K-th most recent access. The gap between "now" and that timestamp is the backward K-distance. A page with a small K-distance has been hit K times recently (it's hot); a page with a huge K-distance hasn't accumulated K recent hits (it's cold, or brand-new). The victim is the page with the largest backward K-distance.

Why LRU-2 resists flooding

The popular choice is LRU-2 (K = 2): track the last two references. Here's the magic. A scan touches each page exactly once, so a scanned page has only a first reference — it has no second-most-recent access, so its backward 2-distance is treated as infinite (or as the oldest possible time). That makes scanned, use-once pages the first to be evicted, while a hot page that was genuinely referenced twice keeps a small finite K-distance and survives. The scan can no longer push out the working set.

Pseudocode sketch

Each page keeps a small history of its last K access timestamps. HIST(p, K) is the timestamp of the K-th most recent access to page p, or 0 (treated as ∞ distance) if it has fewer than K accesses.

# LRU-K: keep last K access timestamps per page; evict the page whose
# K-th most recent access is OLDEST (largest backward K-distance).
from collections import deque

class LRUKBufferPool:
    def __init__(self, capacity, k):
        self.capacity = capacity
        self.k = k
        self.now = 0                     # logical clock, ticks per access
        self.hist = {}                    # page_id -> deque of last K timestamps

    def _kth_distance(self, page_id):     # backward K-distance; inf if < K refs
        h = self.hist[page_id]
        if len(h) < self.k:
            return float("inf")        # too few refs => evict first
        return self.now - h[0]         # h[0] = K-th most recent access

    def _record(self, page_id):
        self.now += 1
        h = self.hist.setdefault(page_id, deque(maxlen=self.k))
        h.append(self.now)                # oldest auto-dropped past K

    def access(self, page_id):           # returns "HIT" or "MISS"
        if page_id in self.hist:
            self._record(page_id)
            return "HIT"
        if len(self.hist) >= self.capacity:
            # victim = largest backward K-distance (ties: oldest most-recent ref)
            victim = max(self.hist, key=lambda q: (self._kth_distance(q), self.now - self.hist[q][-1]))
            del self.hist[victim]
        self._record(page_id)
        return "MISS"

if __name__ == "__main__":
    bp = LRUKBufferPool(capacity=3, k=2)            # LRU-2
    for p in [1, 2, 1, 2, 3, 4, 1, 2]:        # hot 1,2 survive scan 3,4
        print(p, bp.access(p))

// LRU-K: keep last K access timestamps per page; evict the page whose
// K-th most recent access is OLDEST (largest backward K-distance).
#include <iostream>
#include <unordered_map>
#include <deque>
#include <limits>

class LRUKBufferPool {
    size_t capacity_;
    size_t k_;
    long now_ = 0;                                       // logical clock
    std::unordered_map<int, std::deque<long>> hist_;       // page_id -> last K timestamps

    double kthDistance(int page_id) {                    // inf if < K refs
        const auto& h = hist_[page_id];
        if (h.size() < k_) return std::numeric_limits<double>::infinity();
        return static_cast<double>(now_ - h.front());     // front = K-th most recent
    }

    void record(int page_id) {
        ++now_;
        auto& h = hist_[page_id];
        h.push_back(now_);
        if (h.size() > k_) h.pop_front();                  // keep only last K
    }
public:
    LRUKBufferPool(size_t capacity, size_t k) : capacity_(capacity), k_(k) {}

    std::string access(int page_id) {                   // returns "HIT" or "MISS"
        if (hist_.count(page_id)) { record(page_id); return "HIT"; }
        if (hist_.size() >= capacity_) {
            int victim = -1;
            double best = -1;
            long bestRecent = 0;
            for (auto& [q, h] : hist_) {            // largest K-distance; tie: oldest recent ref
                double d = kthDistance(q);
                long recent = now_ - h.back();
                if (d > best || (d == best && recent > bestRecent)) {
                    best = d; bestRecent = recent; victim = q;
                }
            }
            hist_.erase(victim);
        }
        record(page_id);
        return "MISS";
    }
};

int main() {
    LRUKBufferPool bp(3, 2);                              // LRU-2
    for (int p : {1, 2, 1, 2, 3, 4, 1, 2})       // hot 1,2 survive scan 3,4
        std::cout << p << " " << bp.access(p) << "\n";
}

// LRU-K: keep last K access timestamps per page; evict the page whose
// K-th most recent access is OLDEST (largest backward K-distance).
import java.util.*;

public class LRUKBufferPool {
    private final int capacity, k;
    private long now = 0;                                  // logical clock
    private final Map<Integer, Deque<Long>> hist = new HashMap<>();  // page -> last K timestamps

    public LRUKBufferPool(int capacity, int k) { this.capacity = capacity; this.k = k; }

    private double kthDistance(int pageId) {            // inf if < K refs
        Deque<Long> h = hist.get(pageId);
        if (h.size() < k) return Double.POSITIVE_INFINITY;
        return now - h.peekFirst();                     // first = K-th most recent
    }

    private void record(int pageId) {
        now++;
        Deque<Long> h = hist.computeIfAbsent(pageId, x -> new ArrayDeque<>());
        h.addLast(now);
        if (h.size() > k) h.pollFirst();                 // keep only last K
    }

    public String access(int pageId) {              // returns "HIT" or "MISS"
        if (hist.containsKey(pageId)) { record(pageId); return "HIT"; }
        if (hist.size() >= capacity) {
            int victim = -1;
            double best = -1;
            long bestRecent = 0;
            for (int q : hist.keySet()) {           // largest K-distance; tie: oldest recent ref
                double d = kthDistance(q);
                long recent = now - hist.get(q).peekLast();
                if (d > best || (d == best && recent > bestRecent)) {
                    best = d; bestRecent = recent; victim = q;
                }
            }
            hist.remove(victim);
        }
        record(pageId);
        return "MISS";
    }

    public static void main(String[] args) {
        LRUKBufferPool bp = new LRUKBufferPool(3, 2);     // LRU-2
        for (int p : new int[]{1, 2, 1, 2, 3, 4, 1, 2})  // hot 1,2 survive scan 3,4
            System.out.println(p + " " + bp.access(p));
    }
}

3 Sequential flooding & scan-resistant policies

We met sequential flooding in Topic 1: a scan larger than the buffer pool reads each page once and, under LRU, evicts everything useful — including pages it will need again later in the same scan if it loops. Let's look at the problem precisely and then at the family of fixes.

Why the problem is fundamental

For a repeated sequential scan of N pages through a buffer holding B frames where N > B, LRU is pessimal — the worst possible policy. By the time the scan comes back to page 1, LRU evicted it long ago to make room for the most recent pages, so every access misses. This is sometimes called the "one bigger than the cache" pathology and it's a textbook example of LRU's weakness.

The family of scan-resistant techniques

How real databases handle large scans

PostgreSQL — the ring buffer. When PostgreSQL runs a large sequential scan, bulk COPY, or VACUUM, it doesn't let those pages roam the whole pool. It allocates a small private ring buffer (a "buffer access strategy" — for seq scans the default is a 256 KB ring, i.e. only 32 8 KB buffers) and recycles those few frames over and over. The scan thus reads at most that handful of frames' worth of pollution, leaving the shared buffers full of hot pages. The ring is the engineering form of "quarantine the scan."

MySQL InnoDB — midpoint insertion. InnoDB splits its LRU list into a "young" (new) sublist and an "old" (free-to-evict) sublist, joined at a midpoint (by default 3/8 of the way down). A freshly read page is inserted at the midpoint, into the old sublist — not at the hot front. It is only promoted to the young end if it is accessed again after a short delay. A one-pass scan therefore parks its pages in the old sublist, where they age out quickly without ever displacing the genuinely hot young pages.

Oracle & PostgreSQL clock-sweep — touch counts. Rather than an exact LRU list, PostgreSQL uses a clock-sweep algorithm: each frame has a small usage_count, incremented on access and decremented as a circular "clock hand" passes; a frame is evictable only when its count reaches 0. A scan page touched once has count 1, so it's reclaimed almost immediately, while hot pages keep being bumped back up. Oracle similarly uses a touch-count LRU. These are cheap, approximate ways to get LRU-2-like "must be used more than once" behaviour without per-page timestamp histories.

4 Prefetching & related I/O optimizations

Eviction policy decides what to keep. Prefetching attacks a different cost: the brutal latency of a disk read. A page miss can stall the query for the time it takes the disk to respond. Prefetching overlaps that I/O with computation by reading pages into the buffer pool before they're explicitly requested. This is also called read-ahead.

Sequential read-ahead

When the buffer manager detects a sequential access pattern — say a full table scan or a range scan reading pages 100, 101, 102… — it issues asynchronous reads for the next chunk of pages while the query is still processing the current one. By the time the query asks for page 103, it's already in RAM: the miss became a hit. The wait for the disk happened in the background, hidden behind useful work.

# Naive: query stalls on every page read
for pid in scan_range:          # 100, 101, 102, ...
    page = read_page(pid)        # BLOCKS on disk every miss 😴
    process(page)

# With read-ahead: fetch ahead so the next page is ready
prefetch(scan_range[0 : PREFETCH_DEPTH])   # kick off async reads
for i, pid in enumerate(scan_range):
    page = read_page(pid)        # usually a HIT now — already in RAM ✅
    if i + PREFETCH_DEPTH < len(scan_range):
        prefetch(scan_range[i + PREFETCH_DEPTH])  # stay one window ahead
    process(page)                # CPU works while disk fetches next

Buffer pool bypass for scans

Topic 3 taught us to keep a scan out of the main pool. Buffer pool bypass (or direct I/O for the scan) takes this further: for a large one-time scan the engine reads pages into a small local working area and discards them immediately after use, never inserting them into the shared buffer pool at all. PostgreSQL's ring buffer (Topic 3) is essentially this. It both prevents cache pollution and avoids the overhead of managing those throwaway pages in the global structures.

Parallel & asynchronous I/O

A single disk request leaves a lot of hardware idle. Modern storage (especially SSDs and disk arrays) can service many requests at once. Parallel I/O issues multiple page reads concurrently — across several disks or queue slots — so total wait time is the time of one request, not the sum of all of them. Combined with asynchronous I/O (the query thread fires a read and keeps working instead of blocking), the database can keep both the CPU and the disks busy at the same time.

★ Putting it all together

This session was one connected story about which pages live in memory and when. Here it is in a single paragraph:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
• DBMS Session 5 — Buffer Pool 2 (class handout for this session).

Papers, docs & deep dives

• CMU 15-445 — Database Systems (buffer pool lectures) — Andy Pavlo's course; the buffer-pool and replacement-policy lectures cover LRU, clock, LRU-K, and scan handling clearly.
• O'Neil, O'Neil & Weikum — "The LRU-K Page Replacement Algorithm for Database Disk Buffering" (1993) — the original LRU-K paper; defines backward K-distance and the correlated reference period.
• PostgreSQL documentation — Resource Consumption (shared_buffers & buffer management) — official docs for PostgreSQL's buffer pool, clock-sweep, and the ring-buffer access strategies for scans and VACUUM.
• MySQL Reference Manual — The InnoDB Buffer Pool — explains InnoDB's midpoint-insertion LRU (young/old sublists) and read-ahead, the production form of scan resistance.
• Megiddo & Modha — "ARC: A Self-Tuning, Low Overhead Replacement Cache" (2003) — a modern descendant of LRU-K that adapts between recency and frequency automatically.
• Silberschatz, Korth & Sudarshan — Database System Concepts (Storage & Buffer Management chapters) — the standard textbook treatment of buffer replacement, MRU-for-scans, and prefetching.