Build a Database from Zero (Part 9): The Buffer Pool — Why the Second Query Is Faster

Database

PostgreSQL

Build from Zero

2 hours ago1176 words·6 min read

What You'll Get Out of This

Build a buffer pool — a cache for pages — and see where the "second query is faster" magic comes from;
Implement a real eviction policy (LRU) and decide which page to drop when memory runs out;
Then tie the whole thing together to answer Part 1's big question: why is Seq Scan so expensive? — it's the number of pages.

Before We Start

Know Part 8: reading a page is expensive because of seek; rows are found via a page's directory;
Know how a hash table and a list work (we'll use both).

The Problem You've Probably Already Noticed

You've been reading pages from disk the whole time. But here's an obvious waste: a query asks for a page; you read it from disk. Later, another query might need the same page. You read it from disk again. Since disk is the most expensive thing in a database, re-reading it is wasted effort.

The fix is the same idea as the "desk vs filing cabinet" analogy from way back: keep recently-read pages on your desk (memory) so you don't walk to the cabinet (disk) for them again.

That's a buffer pool — a chunk of memory that caches pages.

Step 1: Build a Buffer Pool

Let's make a simple one. It holds pages in a dictionary keyed by page id:

class BufferPool {
  constructor(capacity = 8) {
    this.capacity = capacity;
    this.pages = new Map();   // pageId → page bytes
  }

  // get a page: from cache, or read from disk and cache it
  async getPage(file, pageId) {
    if (this.pages.has(pageId)) {
      console.log(`hit  : page ${pageId} (from memory)`);
      return this.pages.get(pageId);
    }
    console.log(`miss : page ${pageId} (from disk)`);
    const page = await readPage(file, pageId);
    this.put(pageId, page);
    return page;
  }

  put(pageId, page) {
    this.pages.set(pageId, page);
    if (this.pages.size > this.capacity) this.evict();
  }
}

Run a query twice and watch the log:

txt

miss : page 3 (from disk)     ← first time
hit  : page 3 (from memory)   ← second time — no disk!

There's your "first slow, second fast." The first run pulls the page from disk; the second finds it in memory.

Step 2: But Memory Is Limited — Evict Something

If the pool only holds 8 pages but 1000 are needed, you can't keep them all. When it's full, you must evict (drop) a page to make room. So the real question is: which one do you drop?

A terrible answer: drop a random one — you might drop a page you need again very soon. A better idea: guess which page is least likely to be needed next. The classic heuristic: drop the page that hasn't been used for the longest — on the assumption that "if it's been idle a while, it's probably not popular." That's LRU (Least Recently Used).

Step 3: Implement LRU

To track "which was used neast," we need to know order. A hash map alone doesn't remember order. So we pair the map with a linked list: most-recently-used at one end, least-recently-used at the other. On a hit, move the page to the "recent" end; on eviction, drop from the "old" end.

Let's implement a clean tish version using a JS array as our "ordered list" (real LRU uses an O(1) list+map, but the logic is identical):

class LruPool {
  constructor(capacity = 4) {
    this.capacity = capacity;
    this.order = [];              // pageIds, front = most recent
    this.pages = new Map();       // pageId → page bytes
  }

  getPage(file, pageId) {
    if (this.pages.has(pageId)) {
      // HIT: move to front (most recent)
      this.order.splice(this.order.indexOf(pageId), 1);
      this.order.unshift(pageId);
      console.log(`hit  : page ${pageId}`);
      return this.pages.get(pageId);
    }
    // MISS: read from disk
    console.log(`miss : page ${pageId} (disk)`);
    const page = readPage(file, pageId);
    this.pages.set(pageId, page);
    this.order.unshift(pageId);
    if (this.order.length > this.capacity) {
      const old = this.order.pop();        // least recently used
      this.pages.delete(old);
      console.log(`evict : page ${old}`);
    }
    return page;
  }
}

Walk through a small trace to see it working. With capacity 3, access pages in order A, B, C, B, D:

txt

add A: [A]
add B: [B, A]
add C: [C, B, A]
hit B → move B to front: [B, C, A]
add D → full! evict A (oldest): [D, B, C]

That's the whole idea: the page touched most recently stays; the one idle longest goes. It's a guess, but a good one — and it's what real databases use (well, PostgreSQL uses a variant).

Step 4: The Payoff — What This Explains

Now we can answer the question that's been hanging since Part 1: why is Seq Scan (scanning the whole table) so expensive?

Not because reading a single page is costly. But because a full scan touches every page in the table:

txt

Seq Scan:  read page 0, 1, 2, ..., N   →  touches N pages (first time)
Index Scan: read page 42 only          →  touches 1 page  (for a keyed lookup)

Even with the buffer pool, the first time you scan a big table, every page is a miss and must come from disk. The difference between Seq Scan and Index Scan isn't the price of one page — it's the number of pages you touch. That's the real, quantitative answer to the question you started this adventure with.

Hands-On Practice

Watch hit/miss: build the pool, run a query twice, and log each hit/miss. Confirm the second run is all hits — no disk.
Tune the capacity: set capacity to 2, access pages in a "working set" of 3, and count how many evictions happen. Now set capacity to 10 — how many?
Prove the LRU bet: access a sequence where a page is used, then many others, so it gets evicted. Then access it again and see the cold miss. Explain why LRU guessed wrong and when it'd guess right.

Summary and Keywords

A buffer pool caches pages in memory so a page read once isn't re-read from disk — that's "first slow, second fast.";
When memory is full, evict a page using a heuristic like LRU — drop the least-recently-used one;
The real cost of Seq Scan is the number of pages it touches, not the price of one page; Index Scan touches far fewer.

Keywords: buffer pool、page cache、hit / miss、eviction、LRU、shared_buffers、cache locality、Seq Scan vs Index Scan

What's Next

You've now assembled the whole machine: rows in pages, pages on disk, an index (B+ tree) pointing at TIDs, and a buffer pool so re-reading is cheap. In the parts before, each piece was a separate toy. Now it's time to glue them together.

That's Part 10 — the finale: a single, honest, minimal database that holds rows in pages, finds them by an index, and caches them. Then we look at the two storage philosophies (heap vs index-organized) and finally answer, with everything you've built: why can PostgreSQL have no primary key?