Buffer Pool Management

Every time you run a query, your database has to read data. That data lives on disk — and a random disk read can take 10 milliseconds, while reading the same byte from RAM takes 100 nanoseconds. That is a factor of 100,000.

The buffer pool is the database's answer to this gap. It is a fixed region of RAM that holds recently used pages (the fixed-size blocks that databases use to organize data on disk). When a query needs a page, the engine checks the buffer pool first. A cache hit costs nothing; a cache miss pays the full disk penalty.

The hard question is: when the pool is full and a new page must load, which page do you throw out? Evict the wrong one — one that the next query needs — and you've just manufactured an extra disk read. The answer shapes the performance of every database engine you have ever used.

The demo below simulates a buffer pool with 4 frames. A fixed sequence of page requests arrives one at a time. Watch how the pool fills up, how evictions happen, and how the hit rate (hits / total requests) changes with each policy.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{lbl_policy}}
    <select id="policy">
      <option value="lru">LRU</option>
      <option value="clock">Clock</option>
    </select>
  </label>
  <label>{{lbl_speed}}
    <select id="speed">
      <option value="800">{{spd_slow}}</option>
      <option value="350" selected>{{spd_med}}</option>
      <option value="120">{{spd_fast}}</option>
    </select>
  </label>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="stats">
  <span>{{lbl_requests}}: <strong id="stat-req">0</strong></span>
  <span>{{lbl_hits}}: <strong id="stat-hit">0</strong></span>
  <span>{{lbl_misses}}: <strong id="stat-miss">0</strong></span>
  <span>{{lbl_hit_rate}}: <strong id="stat-rate">—</strong></span>
</div>
<div class="pool-label">{{lbl_pool}} (4 {{lbl_frames}})</div>
<div id="pool" class="pool"></div>
<div class="queue-label">{{lbl_queue}}</div>
<div id="queue" class="queue"></div>
<div id="status" class="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin-bottom: .6rem; }
label { display: flex; align-items: center; gap: .3rem; font-weight: 600; }
select { font: inherit; border: 1px solid #9ab; border-radius: 6px; padding: .2rem .4rem; background: #f4f7f9; }
button { font: 600 13px system-ui; padding: .35rem .85rem; border-radius: 7px; cursor: pointer;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
.stats { display: flex; flex-wrap: wrap; gap: .5rem 1.2rem; margin-bottom: .5rem; }
.stats span { font-size: 13px; }
.pool-label, .queue-label { font-weight: 700; font-size: 12px; text-transform: uppercase;
                            letter-spacing: .06em; color: #5a7088; margin: .4rem 0 .2rem; }
/* {{c_css_pool}} */
.pool { display: flex; gap: 6px; margin-bottom: .3rem; }
.frame { width: 54px; height: 54px; border-radius: 10px; border: 2px solid #cdd9e3;
         display: flex; flex-direction: column; align-items: center; justify-content: center;
         font: 700 18px ui-monospace, monospace; position: relative; transition: background .2s; }
.frame .ref-bit { position: absolute; top: 3px; right: 5px; font-size: 10px; font-weight: 700;
                  color: #e07b00; font-family: ui-monospace, monospace; }
.frame .lru-rank { position: absolute; bottom: 2px; right: 5px; font-size: 9px; color: #888; }
.frame.empty { background: #f0f3f5; color: #bbb; border-style: dashed; }
.frame.loaded { background: #e8eef3; color: #1d3557; }
.frame.hit { background: #d0f0dc; border-color: #43b06c; color: #0a7d33; }
.frame.miss { background: #fde8ea; border-color: #e06070; color: #c92f3c; }
.frame.evict { background: #fff3cd; border-color: #d4a200; color: #8a6000; }
.frame.hand { border-color: #e07b00; }
/* {{c_css_queue}} */
.queue { display: flex; flex-wrap: wrap; gap: 4px; min-height: 30px; margin-bottom: .4rem; }
.pg { width: 30px; height: 30px; border-radius: 6px; border: 1.5px solid #cdd9e3;
      display: flex; align-items: center; justify-content: center;
      font: 700 13px ui-monospace, monospace; color: #1d3557; background: #e8eef3; }
.pg.active { background: #1d3557; color: #fff; border-color: #1d3557; }
.pg.done-hit { background: #d0f0dc; border-color: #43b06c; color: #0a7d33; }
.pg.done-miss { background: #fde8ea; border-color: #e06070; color: #c92f3c; }
.pg.done-plain { background: #dce3e8; border-color: #adb5bd; color: #555; }
/* {{c_css_status}} */
.status { min-height: 1.5em; font-weight: 600; font-size: 13px; }
.status.hit-msg { color: #0a7d33; }
.status.miss-msg { color: #c92f3c; }
.status.done-msg { color: #1d3557; }

// Code not found

Notice how LRU tracks recency perfectly but requires maintaining an ordered list with every access. Clock approximates LRU with a single reference bit per frame and a rotating hand — almost as accurate, far cheaper to implement. Real engines like PostgreSQL use a variant of Clock for exactly this reason.

Choosing which page to evict is easy to state but surprisingly deep:

• LRU (Least Recently Used): evict the page that was accessed longest ago. It runs in $O(1)$ per access with a hash map plus a doubly-linked list, and it matches real workloads well. But it can be fooled by sequential scans — reading every page once in order evicts exactly the page the scan needs next.
• Clock (Second Chance): pages carry a single reference bit. On access the bit is set; the "clock hand" clears bits it passes and evicts the first page it finds with a cleared bit. Nearly as good as LRU, with $O(1)$ overhead and almost no bookkeeping.
• Belady's MIN algorithm: always evict the page whose next use is farthest in the future. Proved optimal by László Bélády in 1966. The catch: it requires knowing the future. It is an offline algorithm — useless in practice, invaluable as a benchmark.
• The fundamental limit: no online algorithm can match Belady's MIN on every possible access sequence. The competitive ratio of any deterministic online algorithm versus the optimal offline is at least $k$ for a pool of $k$ frames — a classic result in online algorithms. This is the same flavor of gap that appears in dynamic-shortest-paths and other online problems.

So the practical task — building a replacement policy that is fast to execute and close to optimal — sits permanently in the space between a clean $O(1)$ heuristic and a theoretically optimal oracle that can never exist online.

"Keep the hot data close, push the cold data out" is a pattern that recurs at every level of computing:

• Relational databases: PostgreSQL, MySQL, Oracle, and SQL Server all ship their own buffer pool managers. Tuning pool size and eviction policy is one of the first knobs a DBA reaches for.
• Operating system virtual memory: the OS page-replacement algorithm (usually a Clock variant) performs the same job between RAM and the swap partition. A thrashing system — one that evicts a page it immediately needs again — is a buffer pool gone wrong at the OS level.
• CPU caches: L1/L2/L3 caches use hardware-managed LRU-like policies. The principle is identical; the timescale is nanoseconds instead of milliseconds.
• Content delivery networks: a CDN decides which objects to keep at each edge node. The eviction policy (often LRU-K or LIRS) controls bandwidth costs and response time for millions of users.
• Connection to caching theory: buffer pool management is a concrete instance of the $k$-server problem — one of the canonical models of online resource allocation.

Understanding buffer pool management means understanding the tradeoff that sits at the center of systems performance: you can be fast, or you can be optimal, but you cannot always be both.

The buffer pool is one of the oldest ideas in systems software — and one that never stops mattering. Bélády showed in 1966 what the ideal looks like: always evict the page you need least soon. Decades of engineering have produced LRU, Clock, and dozens of variants that get surprisingly close — without ever seeing the future.

That gap between the achievable heuristic and the optimal oracle is not a failure of engineering. It is a fundamental limit: online algorithms cannot be perfect when the future is hidden. The same insight runs through operating systems, CDNs, and CPU caches. Every time your computer decides what to keep in memory and what to discard, it is running a small, imperfect instance of a provably unsolvable optimization.