DBMS

Storage And Indexing

The Buffer Pool

BUFFER POOL ── a fixed-size array of page-sized

JrCodex·8 min read

Jr Codex DBMS Notes

Level: Intermediate Prerequisites: Chapter 4: Choosing Indexes Time to complete: ~20 minutes

Table of Contents

  1. The Cache Between Disk and Query
  2. Reading a Page
  3. Eviction Policies
  4. Dirty Pages and Writing Back
  5. The Working Set
  6. Sizing and Monitoring
  7. Summary & Next Steps

1. The Cache Between Disk and Query

Where It Sits
─────────────────────────────────────────
  QUERY EXECUTOR
        │  "give me page 4,921"
        ▼
  BUFFER POOL  ── a fixed-size array of page-sized
        │         frames in RAM
        │  hit?  return it. ~100 nanoseconds.
        │  miss? read from disk. ~100 microseconds.
        ▼
  DISK
─────────────────────────────────────────

Why It Decides Almost Everything
─────────────────────────────────────────
  A buffer pool hit is roughly a THOUSAND times
  faster than a miss.

  So a database's real performance is mostly
  determined by its HIT RATE — and the hit rate is
  determined by whether the data you actually touch
  fits in RAM.

  Every earlier chapter feeds into this: narrower
  rows, smaller indexes and partial indexes all
  mean more of what matters fits in the pool.
─────────────────────────────────────────

2. Reading a Page

class BufferPool:
    def __init__(self, capacity_pages):
        self.capacity = capacity_pages
        self.frames   = {}          # page_id -> page data
        self.pin      = {}          # page_id -> in-use count
        self.dirty    = set()
        self.hits = self.misses = 0
 
    def get(self, page_id):
        if page_id in self.frames:
            self.hits += 1
            self.touch(page_id)                     # note the access, for eviction
            return self.frames[page_id]
 
        self.misses += 1
        if len(self.frames) >= self.capacity:
            self.evict()                            # must free a frame first
        self.frames[page_id] = disk_read(page_id)   # ~100µs — the expensive line
        self.touch(page_id)
        return self.frames[page_id]
 
    def hit_rate(self):
        total = self.hits + self.misses
        return self.hits / total if total else 0.0
Pinning
─────────────────────────────────────────
  A page being read by an active query is PINNED —
  it cannot be evicted while in use, or the query
  would be reading freed memory.

  Pin count reaches zero when no query holds it,
  and only then is it an eviction candidate.

  A long-running query holding many pins reduces
  the pool available to everyone else, which is one
  more reason to keep transactions short
  (Module 3, Chapter 6).
─────────────────────────────────────────

3. Eviction Policies

When the pool is full, something must go.

The Policies
─────────────────────────────────────────
  LRU  Least Recently Used
       Evict whatever was untouched longest.
       Simple, and usually decent.

       WEAKNESS: one big sequential scan touches
       every page once and evicts the ENTIRE
       working set — pages that were being used
       constantly. A single reporting query can
       wreck performance for every other user.

  LRU-K  tracks the last K accesses
       A page must be accessed K times to be
       considered "hot", so a one-off scan does not
       promote its pages. Fixes LRU's weakness.

  CLOCK  approximates LRU cheaply
       A reference bit per frame, swept in a
       circle. No linked-list bookkeeping per
       access. What most real databases use.
─────────────────────────────────────────

How Real Databases Defend the Pool
─────────────────────────────────────────
  POSTGRESQL   a RING BUFFER for large sequential
               scans — they get a small dedicated
               area and cannot evict the main pool.

  INNODB       the LRU list is split into YOUNG and
               OLD sublists. New pages enter the
               OLD end and are only promoted if
               accessed again after a delay.

  Both solve the same problem: stop a table scan
  from destroying the cache for everyone else.
─────────────────────────────────────────

4. Dirty Pages and Writing Back

The Rule
─────────────────────────────────────────
  A page MODIFIED in memory is DIRTY. It differs
  from the copy on disk.

  Writes go to the buffer pool, NOT to the table
  file. The page is written back later, in the
  background.

  This is why a database can accept thousands of
  writes per second: they are memory writes.
─────────────────────────────────────────

The Obvious Question
─────────────────────────────────────────
  "If the change is only in RAM, what happens when
   the power fails?"

  Answer: the WRITE-AHEAD LOG.

  Before any page is modified, the change is
  recorded in the log, and the LOG is flushed to
  disk on commit. The table pages can be written
  lazily because the log can reconstruct them.

  This is durability (Module 1, Chapter 4), and
  Module 8 covers the mechanism in full.
─────────────────────────────────────────

Checkpoints
─────────────────────────────────────────
  Periodically the database flushes dirty pages to
  disk and records a CHECKPOINT.

  Recovery then only needs to replay the log SINCE
  the last checkpoint, rather than from the
  beginning of time.

  TRADE-OFF
    frequent checkpoints ──► fast recovery, more
                             steady write I/O
    rare checkpoints     ──► less I/O, slower
                             recovery, and large
                             write STORMS when one
                             does happen
─────────────────────────────────────────

5. The Working Set

The Definition
─────────────────────────────────────────
  The pages your queries ACTUALLY touch in a
  typical window — not the size of the database.

  A 2 TB database whose queries only ever touch
  last month's 30 GB has a 30 GB working set, and
  runs beautifully on a machine with 64 GB of RAM.
─────────────────────────────────────────

The Cliff
─────────────────────────────────────────
  Performance against working-set size is NOT a
  gentle curve. It falls off a cliff.

    working set < pool   ──► ~99% hit rate.
                             Everything is fast.
    working set ≈ pool   ──► hit rate starts
                             dropping
    working set > pool   ──► THRASHING. Pages are
                             evicted just before
                             they are needed again.
                             Hit rate collapses and
                             latency rises by
                             orders of magnitude.

  This is why a database can be perfectly healthy
  for months and then "suddenly" become slow. The
  data grew past the pool, and nothing else changed.
─────────────────────────────────────────

Shrinking the Working Set
─────────────────────────────────────────
  All of these buy you the same thing — more of
  what matters fits in RAM:

    - narrower rows (Chapter 1)
    - fewer and smaller indexes (Chapter 4)
    - PARTIAL indexes (Chapter 3)
    - covering indexes, which avoid touching heap
      pages at all
    - archiving or partitioning off cold data
    - selecting fewer columns
─────────────────────────────────────────

6. Sizing and Monitoring

Starting Points
─────────────────────────────────────────
  POSTGRESQL   shared_buffers ≈ 25% of RAM
               (it also relies on the OS page
                cache, so it deliberately does not
                take everything)

  MYSQL/INNODB innodb_buffer_pool_size ≈ 70-80%
               of RAM on a dedicated server
               (InnoDB bypasses the OS cache, so
                it takes the lion's share)

  The difference is architectural, not a
  disagreement. Do not copy one database's number
  to the other.
─────────────────────────────────────────

-- Hit rate (PostgreSQL). Below ~95% on an OLTP workload deserves investigation.
SELECT
    SUM(heap_blks_hit)  AS cache_hits,
    SUM(heap_blks_read) AS disk_reads,
    ROUND(100.0 * SUM(heap_blks_hit) /
          NULLIF(SUM(heap_blks_hit) + SUM(heap_blks_read), 0), 2) AS hit_pct
FROM pg_statio_user_tables;
-- Which tables are actually causing the disk reads?
SELECT relname,
       heap_blks_read AS disk_reads,
       heap_blks_hit  AS cache_hits,
       ROUND(100.0 * heap_blks_hit /
             NULLIF(heap_blks_hit + heap_blks_read, 0), 1) AS hit_pct
FROM pg_statio_user_tables
WHERE heap_blks_read > 0
ORDER BY heap_blks_read DESC
LIMIT 10;
Reading the Numbers Honestly
─────────────────────────────────────────
  A high hit rate is necessary, not sufficient.

  99% hits on a query reading 10,000,000 pages
  still means 100,000 disk reads. The fix there is
  an INDEX so the query reads fewer pages, not a
  bigger pool.

  Look at hit rate AND absolute pages read.
  Together they tell you whether you have a memory
  problem or a query problem.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

  • A buffer pool hit is about a thousand times faster than a miss, so hit rate largely determines real-world database performance.
  • Naive LRU lets one large sequential scan evict the entire working set, which is why real databases use ring buffers or split LRU lists to protect the pool.
  • Writes go to memory and are flushed lazily; the write-ahead log is what makes that safe, and checkpoints bound recovery time.
  • Performance against working-set size is a cliff rather than a curve — a database can be healthy for months and collapse when the data grows past the pool.

Module 5 Complete — What's Next

You now know how rows are stored, how indexes find them, and why memory decides everything. Module 6 puts it together: how the optimiser chooses between these access methods, and how to read the plan it produces.

Concept Check

  1. Why does a single large reporting query slow down unrelated queries under naive LRU, and how do real databases prevent it?
  2. If writes only modify pages in memory, what makes a committed transaction durable?
  3. Your hit rate is 99% and the query is still slow. What does that tell you, and what would you fix?

Next Module

→ Module 6: Query Processing & Optimization

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index