Where the database keeps its pages while it works

1 Why a buffer pool?

In Session 3 we saw that a database stores its data on disk as fixed-size pages (often 4 KB, 8 KB, or 16 KB blocks) inside heap files. The problem: the engine can't run code directly on data sitting on disk. It has to copy a page into memory (RAM) first, work on it there, and (if it changed) copy it back. The buffer pool is the piece of the DBMS that manages this copying.

Just how big is the speed gap?

This is the whole reason the buffer pool exists, so it's worth feeling the numbers. Memory and disk are not "a bit different" in speed — they're different by orders of magnitude.

This is just caching — a universal idea

A cache is any small, fast store that holds copies of things from a big, slow store, betting you'll want them again soon. You meet caches everywhere:

• Your browser caches images so a page loads instantly on a second visit.
• Your CPU caches recently-used memory so it doesn't wait on RAM.
• A CDN caches website files near you so they don't travel across the world.

The buffer pool is exactly this pattern: a fast cache (RAM) in front of a slow store (disk). Two bets make it pay off, and both are usually true for database workloads:

• Temporal locality — if a page was used recently, it's likely to be used again soon (think a hot "users" page touched by every login).
• Spatial locality — if you used a page, you'll probably use nearby pages too (scanning a table reads page after page in order).

Why not just let the operating system do it?

Here's a fair question. The OS already caches disk pages for every program (it's called the OS page cache). So why does a database build its own buffer pool instead of leaning on the OS? Because the DBMS knows things the OS can't:

2 Buffer pool design — frames & the page table

The buffer pool is a big chunk of memory the DBMS carves up into equal-sized slots. Each slot is called a frame, and each frame is exactly the size of one disk page — so any page from disk fits perfectly into any frame. If the buffer pool is 1 GB and pages are 8 KB, you get about 1 GB / 8 KB ≈ 131,000 frames.

The page table — the "notebook"

To find a page in memory quickly, the buffer pool keeps a page table: an in-memory lookup (a hash map) from a page id (which page on disk) to the frame that currently holds it. A lookup is O(1) on average — basically instant.

Alongside the page table, each frame carries a little bit of metadata the pool needs to manage it. We'll meet most of these in Topic 3, but here's the shape:

The fetch path: hit vs miss

Every time some part of the database needs a page, it asks the buffer pool: getPage(page_id). Two things can happen — the two most important words in this whole session:

• Cache hit — the page is already in a frame. The pool finds it via the page table and hands it back immediately. No disk I/O. Fast.
• Cache miss — the page isn't in memory. The pool must find a free frame (or evict something — Topic 4) and read the page from disk into it. Disk I/O happens. Slow.

The hit rate — the fraction of requests that are hits — is the headline number for buffer pool health. A well-sized pool on a typical workload hits 95–99% of the time, so the vast majority of page requests never touch the disk at all.

Pseudocode: getPage

Here is the core routine, with the eviction details deferred to Topic 4 and the pinning details to Topic 3. Read it slowly — it's the heart of the buffer pool.

# Fetch a page into memory and return the frame holding it.
function getPage(page_id):
    # --- Cache HIT: already in memory? ---
    if page_id in page_table:
        frame = page_table[page_id]
        frame.pin_count = frame.pin_count + 1   # mark "in use" (Topic 3)
        return frame                            # no disk I/O 🎉

    # --- Cache MISS: must bring it in from disk ---
    frame = findFreeFrame()                      # a truly empty frame, if any
    if frame is None:
        frame = evictVictim()                    # pick & free a victim (Topic 4)
        if frame is None:
            throw "buffer pool full: every page is pinned"

    # 'frame' is now empty and ours to use
    frame.data    = disk.readPage(page_id)       # the slow part
    frame.page_id = page_id
    frame.is_dirty = false
    frame.pin_count = 1
    page_table[page_id] = frame                  # write the new notebook line
    return frame

3 Pin counts & dirty flags

Pin counts — "don't evict, I'm using it"

When a part of the database asks for a page, it's going to read or write the bytes in that frame for a while. It would be a disaster if the buffer pool evicted that frame mid-use and reused it for a different page. So before handing a frame out, the pool pins it: it increments the frame's pin count (also called the reference count). A frame with pin_count > 0 is off-limits for eviction.

When the caller is done, it must unpin the page (decrement the count). A frame only becomes eligible for eviction once its pin count drops back to zero — meaning nobody is using it anymore.

The dirty flag — "this page changed in memory"

When a transaction modifies a page (inserts a row, updates a value), it changes the copy in the frame — not the disk yet. That frame is now out of sync with disk. The pool marks it with a dirty flag (is_dirty = true). A dirty page holds the only up-to-date version of that data; a clean page is identical to what's on disk.

When do dirty pages actually get written back?

The DBMS deliberately delays writing dirty pages — it's called delayed writeback — so that many changes can be batched and a hot page can be modified repeatedly without paying for a disk write each time. A dirty page is flushed when:

• It's chosen as an eviction victim and is dirty — flush, then reuse the frame.
• A background writer / checkpointer runs — a thread that periodically flushes dirty pages so evictions later are cheap and recovery after a crash is fast.
• A checkpoint forces it — recovery logic occasionally flushes everything to create a known-good snapshot.

The latch/concurrency angle (briefly)

Many threads hit the buffer pool at once, so its internal structures — the page table and each frame's metadata — must be protected from races. Databases use latches (lightweight, short-held locks on in-memory structures, distinct from the higher-level transaction locks you'll meet later) to guard them. Two levels show up:

• A latch on the page table so two threads don't insert the same page into two frames.
• A latch on each frame so a reader doesn't see a page half-overwritten by a writer.

A subtle point: the pin count itself is a coordination tool. It's how the buffer pool layer says "this frame is in active use" without holding a heavy lock for the whole duration.

Pseudocode: unpin, and an eviction that respects both flags

# Caller is done with a page. dirtied = did I modify it?
function unpinPage(page_id, dirtied):
    frame = page_table[page_id]
    if dirtied:
        frame.is_dirty = true          # mark it; flush happens later
    frame.pin_count = frame.pin_count - 1
    # pin_count == 0 → now eligible for eviction (Topic 4)

# Free a frame for reuse, honouring pin & dirty rules.
function freeFrame(frame):
    if frame.pin_count > 0:
        throw "cannot evict a pinned page"   # someone's using it
    if frame.is_dirty:
        disk.writePage(frame.page_id, frame.data) # flush BEFORE reuse
        frame.is_dirty = false
    page_table.remove(frame.page_id)              # erase the notebook line
    frame.page_id = None

4 Replacement policy theory

Memory is finite, so the buffer pool fills up. When a miss happens and there's no free frame, the pool must throw one page out to make room — this is eviction. The rule it uses to choose the victim is the replacement policy (a.k.a. eviction policy). A good policy keeps the hit rate high by evicting pages you're least likely to need again soon. (Only pages with pin_count = 0 are even candidates — pinned pages are untouchable, from Topic 3.)

The theoretical best, and why we can't have it

The provably optimal policy, called Bélády's OPT, evicts the page that won't be needed for the longest time in the future. It's optimal — and impossible — because it requires seeing the future. So real policies guess the future from the past. The two classics you must know:

Policy 1 — LRU (Least Recently Used)

LRU evicts the page that was accessed the longest ago, betting (via temporal locality, Topic 1) that the recently-used pages will be used again soon. Conceptually you keep pages in a list ordered by last-use; on every access you move that page to the front; to evict, you drop the page at the back.

• Pro: simple, intuitive, and good for most workloads.
• Con: a precise LRU must update a shared, ordered list on every single access — including hits. Under heavy concurrency, all threads fighting over that one list (and its latch) becomes a bottleneck.

Policy 2 — Clock (a.k.a. Second-Chance)

Clock is a cheap approximation of LRU that avoids the per-access list churn. Picture all frames arranged in a circle with a single hand (like a clock), and each frame having one reference bit:

• On access, just set that frame's reference bit to 1. (Cheap — no list to reorder.)
• On eviction, sweep the hand forward. At each frame: if its bit is 1, give it a "second chance" — clear the bit to 0 and move on. If its bit is already 0 (and it's unpinned), evict it.

The effect: a page touched since the hand last passed survives one more lap; a page nobody has touched gets evicted. It approximates "least recently used" using just one bit per frame and no work on hits — which is why real systems (and the OS) favour Clock-family policies.

How the policy interacts with pinning

The replacement policy never gets to pick a pinned page. In Clock, when the hand lands on a frame with pin_count > 0, it simply skips it (leaving the bit alone) and keeps sweeping. In LRU, pinned pages are excluded from the candidate list. So pinning and replacement work as a team: pin count says "is this even allowed?", and the policy says "of the allowed ones, which is least valuable?"

★ Putting it all together

You just learned how a database keeps its working data in memory. Here's the one-paragraph story that connects all four topics:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
• 📘 Class handout: "DBMS Session 4 — Buffer Pool".
• 🛠️ Capstone: MiniDB — Milestone M1 (Buffer Pool) — implement frames, the page table, pin/unpin, the dirty flag, and a Clock or LRU replacement policy.
• ✍️ Written assignment: "Design a buffer pool" — specify the data structures, the getPage/unpin paths, and your eviction policy with its trade-offs.

Papers, docs & deep dives

• CMU 15-445/645 — Database Systems — the gold-standard course; see the "Buffer Pools / Database Storage" lectures and notes for this exact material.
• Database System Concepts (Silberschatz, Korth, Sudarshan) — the buffer management chapter is the classic textbook treatment of frames, pinning, and replacement.
• PostgreSQL docs — shared_buffers & resource config — how a real production system exposes and tunes its buffer pool.
• MySQL / InnoDB Buffer Pool documentation — a real LRU-based buffer pool with a "midpoint insertion" twist to resist sequential flooding.
• O'Neil, O'Neil & Weikum — "The LRU-K Page Replacement Algorithm" (1993) — the original paper behind the policy we study in Session 5.
• Cache replacement policies (overview) — a clear survey of OPT, LRU, Clock/second-chance, FIFO and friends.