Introduction

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.

Watch the Hit Rate Climb

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.

<!-- Buffer pool simulator — pool of 4 frames, sequence of page requests -->
<div class="controls">
  <label>Policy:
    <select id="policy">
      <option value="lru">LRU</option>
      <option value="clock">Clock</option>
    </select>
  </label>
  <label>Speed:
    <select id="speed">
      <option value="800">Slow</option>
      <option value="350" selected>Medium</option>
      <option value="120">Fast</option>
    </select>
  </label>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="stats">
  <span>Requests: <strong id="stat-req">0</strong></span>
  <span>Hits: <strong id="stat-hit">0</strong></span>
  <span>Misses: <strong id="stat-miss">0</strong></span>
  <span>Hit rate: <strong id="stat-rate">—</strong></span>
</div>
<div class="pool-label">Buffer pool (4 frames)</div>
<div id="pool" class="pool"></div>
<div class="queue-label">Page request sequence</div>
<div id="queue" class="queue"></div>
<div id="status" class="status"></div>

/* Buffer pool demo styles */
* { 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; }
/* Pool frames — colored by last event */
.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; }
/* Queue chips */
.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; }
/* Status line */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Buffer pool management demo — LRU and Clock eviction policies
// Page request sequence (pages 1-5, pool size 4)
const PAGES = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3];
const POOL_SIZE = 4;

// Simulation state
let policy = 'lru';
let frames = [];
let lruOrder = [];
let clockHand = 0;
let refBits = [];
let reqIdx = 0;
let hits = 0;
let misses = 0;
let running = false;
let timer = null;

function resetState() {
  frames = new Array(POOL_SIZE).fill(null);
  lruOrder = [];
  clockHand = 0;
  refBits = new Array(POOL_SIZE).fill(0);
  reqIdx = 0;
  hits = 0;
  misses = 0;
  running = false;
  clearTimeout(timer);
}

function renderPool(highlightSlot, mode) {
  // Draw each frame with its current state highlight
  const poolEl = document.getElementById('pool');
  poolEl.innerHTML = '';
  frames.forEach((pg, i) => {
    const d = document.createElement('div');
    let cls = pg === null ? 'empty' : 'loaded';
    if (i === highlightSlot) cls = mode;
    if (policy === 'clock' && i === clockHand && pg !== null) d.dataset.hand = '1';
    d.className = 'frame ' + cls;
    if (d.dataset.hand === '1') d.classList.add('hand');
    d.textContent = pg !== null ? String(pg) : '·';
    if (policy === 'clock' && pg !== null) {
      const rb = document.createElement('span');
      rb.className = 'ref-bit';
      rb.textContent = refBits[i] ? '1' : '0';
      d.appendChild(rb);
    }
    if (policy === 'lru' && pg !== null) {
      const pos = lruOrder.indexOf(i);
      const rnk = document.createElement('span');
      rnk.className = 'lru-rank';
      rnk.textContent = '#' + (pos + 1);
      d.appendChild(rnk);
    }
    poolEl.appendChild(d);
  });
}

function renderQueue(activeIdx, doneResults) {
  // Draw each page chip with hit/miss coloring
  const qEl = document.getElementById('queue');
  qEl.innerHTML = '';
  PAGES.forEach((pg, i) => {
    const d = document.createElement('div');
    let cls = 'pg';
    if (i === activeIdx) cls += ' active';
    else if (i < activeIdx) {
      const res = doneResults[i];
      cls += res === 'hit' ? ' done-hit' : res === 'miss' ? ' done-miss' : ' done-plain';
    }
    d.className = cls;
    d.textContent = String(pg);
    qEl.appendChild(d);
  });
}

function updateStats() {
  const total = hits + misses;
  document.getElementById('stat-req').textContent = String(total);
  document.getElementById('stat-hit').textContent = String(hits);
  document.getElementById('stat-miss').textContent = String(misses);
  document.getElementById('stat-rate').textContent = total ? (100 * hits / total).toFixed(1) + '%' : '—';
}

function lruEvict() {
  // LRU: evict the frame at the tail of the LRU order list
  const slot = lruOrder[lruOrder.length - 1];
  lruOrder.pop();
  return slot;
}

function clockEvict() {
  // Clock: scan hand, clear ref bits, evict first frame with ref=0
  while (true) {
    if (refBits[clockHand] === 1) {
      refBits[clockHand] = 0;
      clockHand = (clockHand + 1) % POOL_SIZE;
    } else {
      const slot = clockHand;
      clockHand = (clockHand + 1) % POOL_SIZE;
      return slot;
    }
  }
}

const doneResults = [];

function step() {
  if (reqIdx >= PAGES.length) {
    const statusEl = document.getElementById('status');
    statusEl.textContent = i18nFmt('Done — %h% hits, %m% misses, hit rate %r%%', { h: hits, m: misses, r: (100 * hits / PAGES.length).toFixed(1) });
    statusEl.className = 'status done-msg';
    running = false;
    document.getElementById('btn-run').textContent = 'Run';
    return;
  }
  const pg = PAGES[reqIdx];
  const slot = frames.indexOf(pg);
  const isHit = slot !== -1;
  let targetSlot = slot;

  if (isHit) {
    hits++;
    doneResults.push('hit');
    if (policy === 'lru') {
      const idx = lruOrder.indexOf(slot);
      if (idx !== -1) lruOrder.splice(idx, 1);
      lruOrder.unshift(slot);
    } else {
      refBits[slot] = 1;
    }
    renderPool(slot, 'hit');
    const statusEl = document.getElementById('status');
    statusEl.textContent = i18nFmt('Page %pg% — hit! Already in pool.', { pg });
    statusEl.className = 'status hit-msg';
  } else {
    misses++;
    doneResults.push('miss');
    const emptySlot = frames.indexOf(null);
    if (emptySlot !== -1) {
      targetSlot = emptySlot;
    } else {
      targetSlot = policy === 'lru' ? lruEvict() : clockEvict();
    }
    frames[targetSlot] = pg;
    if (policy === 'lru') {
      const idx = lruOrder.indexOf(targetSlot);
      if (idx !== -1) lruOrder.splice(idx, 1);
      lruOrder.unshift(targetSlot);
    } else {
      refBits[targetSlot] = 1;
    }
    renderPool(targetSlot, emptySlot !== -1 ? 'miss' : 'evict');
    const statusEl = document.getElementById('status');
    statusEl.textContent = emptySlot !== -1
      ? i18nFmt('Page %pg% — miss. Loaded into empty frame.', { pg })
      : i18nFmt('Page %pg% — miss. Evicted a frame to make room.', { pg });
    statusEl.className = 'status miss-msg';
  }
  renderQueue(reqIdx, doneResults);
  updateStats();
  reqIdx++;
  timer = setTimeout(step, parseInt(document.getElementById('speed').value, 10));
}

function doRun() {
  if (running) {
    // Toggle pause
    running = false;
    clearTimeout(timer);
    document.getElementById('btn-run').textContent = 'Run';
    return;
  }
  if (reqIdx >= PAGES.length) doReset();
  policy = document.getElementById('policy').value;
  running = true;
  document.getElementById('btn-run').textContent = 'Pause';
  step();
}

function doReset() {
  resetState();
  doneResults.length = 0;
  renderPool(-1, '');
  renderQueue(-1, []);
  updateStats();
  document.getElementById('status').textContent = '';
  document.getElementById('status').className = 'status';
  document.getElementById('btn-run').textContent = 'Run';
}

document.getElementById('btn-run').addEventListener('click', doRun);
document.getElementById('btn-reset').addEventListener('click', doReset);
// Initialize on load
doReset();
Result
Console

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.

The Real Complexity

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)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)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 kk for a pool of kk 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)O(1) heuristic and a theoretically optimal oracle that can never exist online.

Where It Matters

"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 kk-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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/buffer-pool-management/Content licensed under CC BY-NC 4.0.