SQL 103 🛢️ Buffer Pool Management and Page Replacement Algorithms - KandZ

⏱️ Estimated read: 14 min | |

The buffer pool is the database’s cache of disk pages in memory. Every query that reads a row, every index lookup, and every update touches a page in the buffer pool before it touches the disk. When the requested page is already in memory, the read is served without I/O. When it is not, the database must evict a page to make room, and the eviction policy determines which page goes and which stays. The policy is not a minor tuning detail. A poorly chosen page can evict a hot index page that every query needs, replacing it with a cold table page that no one will read again. The difference between a good and a bad replacement decision is the difference between a cache hit rate of 95% and one of 60%, and the performance gap is measured in orders of magnitude.

Each major database implements a different replacement algorithm, and each one is shaped by the workload it was designed for. PostgreSQL uses a clock sweep, a simple and low-overhead approximation of LRU. InnoDB uses a midpoint-insertion LRU that protects against table scans by inserting new pages into the middle of the list rather than the head. Oracle uses a touch-count LRU with separate pools for different access patterns. SQL Server uses a clock algorithm with a single pool. The common thread is that every database has moved away from strict LRU, because strict LRU has a fatal flaw: a single large scan can evict the entire working set.

Key point: The buffer pool caches pages in memory and uses a page replacement algorithm to decide which page to evict when the pool is full. PostgreSQL uses a clock sweep; InnoDB uses a midpoint-insertion LRU that inserts new pages at 3/8 from the tail; Oracle uses a touch-count LRU with a keep pool. Strict LRU is vulnerable to sequential flooding, where a large scan evicts the entire working set, and every modern database uses a variant that mitigates this.

Why strict LRU fails and what replaced it

The sequential flooding problem. A strict LRU list moves every accessed page to the head. When a query performs a full table scan, it reads every page of the table and moves each one to the head. If the table is larger than the buffer pool, the scan evicts every page that was previously in the pool, including the hot index pages that the next query will need. The scan does not reuse the pages it reads, but it destroys the cache for everyone else. This is called sequential flooding, and it is the reason no major database uses strict LRU .

The midpoint insertion solution. InnoDB addresses the flooding problem by inserting new pages at the midpoint of the LRU list, not at the head. The list is divided into a “new” sublist (the hot pages) and an “old” sublist (the eviction candidates). By default, 3/8 of the pool is devoted to the old sublist. When a page is read, it is inserted at the head of the old sublist. If it is accessed again, it moves to the new sublist. If it is not accessed again, it ages out from the old sublist without ever displacing a hot page . A table scan inserts pages into the old sublist, and they are evicted before they can reach the new sublist. The hot pages in the new sublist are protected.

The clock sweep approximation. PostgreSQL uses a clock sweep, which is a lower-overhead approximation of LRU. Each buffer has a usage count. When a page is accessed, its usage count is incremented. When eviction is needed, the clock hand sweeps through the buffers, decrementing the usage count of each buffer it passes. A buffer with a usage count of 0 is evicted. The sweep does not maintain a linked list, so the overhead per access is a single atomic increment rather than a list manipulation. The trade-off is that the approximation is coarser: a page that was accessed once recently and a page that was accessed many times recently are treated similarly until the clock hand sweeps past them.

The touch-count problem. Oracle’s buffer cache uses a touch-count mechanism. Each buffer has a touch count that is incremented on access. The LRU list is ordered by touch count, and buffers with lower touch counts are evicted first. Oracle also provides a keep pool for tables that should be preferentially retained, and a recycle pool for tables that should be evicted quickly . The keep pool does not pin blocks; it changes the part of the cache where the blocks are stored, and the same LRU aging applies .

a. PostgreSQL: the clock sweep

PostgreSQL’s buffer pool is the shared_buffers area. The default is set based on the instance’s available memory, and the pool holds pages that are or were being used by application connections . The eviction policy is a clock sweep, which the AWS RDS documentation describes as the mechanism that evicts a less frequently used page when a new request requires a page that is not in memory .

The clock sweep works on an array of buffer descriptors. Each descriptor has a usage count, an atomic integer that is incremented when the buffer is pinned or accessed. When the buffer manager needs a free buffer, it advances a clock hand through the array. For each buffer it passes, it checks the usage count. If the count is zero, the buffer is evicted. If the count is greater than zero, the count is decremented, and the hand moves to the next buffer. The hand wraps around the array, sweeping repeatedly until it finds a buffer with a zero count. The algorithm is O(1) amortized, and the per-access overhead is a single atomic increment rather than a linked-list update.

The weakness of the clock sweep is that it does not distinguish between a page that was accessed once and a page that was accessed a thousand times, as long as both have a positive usage count when the hand passes. The usage count is a small integer, and it saturates quickly. A hot page and a warm page can have the same count, and the hand may evict the hot page if it happens to pass it at the wrong moment. The mitigation is the size of the pool: a larger pool means the hand passes less frequently, and the hot pages are more likely to survive.

b. InnoDB: the midpoint-insertion LRU

InnoDB’s buffer pool is divided into a new sublist and an old sublist. The boundary between them is the midpoint. By default, 3/8 of the pool is devoted to the old sublist, controlled by the innodb_old_blocks_pct parameter (default 37) . The new sublist holds the frequently used pages; the old sublist holds the eviction candidates.

When a page is read into the pool, it is inserted at the midpoint, which is the head of the old sublist. The first access to the page moves it to the head of the new sublist, making it “young.” If the page is never accessed again, it ages toward the tail of the old sublist and is eventually evicted. A page that is read by a table scan is inserted at the midpoint, and because the scan does not access it again, it never reaches the new sublist. The hot pages in the new sublist are not displaced.

The innodb_old_blocks_time parameter adds a time window (default 1000 ms) after the first access during which a page can be accessed without being moved to the new sublist. This prevents a scan that accesses each page a few times in quick succession from promoting all the scanned pages to the hot sublist. The page is only promoted if it is accessed after the time window has passed . The combination of midpoint insertion and the time window is what makes InnoDB’s buffer pool resistant to scans.

The cost of the midpoint insertion is that a genuinely hot page that is read for the first time must be accessed twice before it reaches the new sublist. The first access inserts it at the midpoint; the second access promotes it. For a workload with a large number of one-time reads, this is correct. For a workload with a small number of frequently accessed pages, the extra access is a minor delay.

c. Oracle and SQL Server: touch counts and clock

Oracle’s buffer cache uses a touch-count LRU. Each buffer has a touch count that is incremented when the buffer is accessed. The LRU list is ordered by touch count, and the buffers with the lowest counts are evicted first. Oracle also provides multiple pools: the default pool, the keep pool for tables that should be retained, and the recycle pool for tables that should be evicted quickly . The keep pool changes the part of the cache where the blocks are stored, but the same LRU aging applies; it does not pin the blocks. The ALTER TABLE ... CACHE attribute is a hint, not a guarantee, and the documentation warns that a full scan of a large table can still clean most of the other blocks out of the cache .

SQL Server uses a single buffer pool with a clock replacement algorithm. The clock hand sweeps through the buffer descriptors, and each descriptor has a reference bit. When a page is accessed, the reference bit is set. When the hand passes, it clears the bit and moves on. If the bit was already clear, the page is evicted. This is the same clock sweep as PostgreSQL, with the same trade-off: low overhead, coarse approximation. SQL Server also supports buffer page reservations for queries that require large amounts of memory, such as sorts and hashes, so that a single large query does not evict the entire pool .

Complete Example Session

The following session traces a table scan in InnoDB and shows how the midpoint insertion protects the hot pages in the new sublist.

// ============================================
// PART 1: THE BUFFER POOL STATE
// ============================================
// The pool has two sublists:
// New sublist (3/8 of the pool): hot pages, recently accessed
// Old sublist (5/8 of the pool): eviction candidates
//
// The hot pages include the index root and the frequently
// accessed user pages. They are at the head of the new sublist.

// ============================================
// PART 2: A TABLE SCAN
// ============================================
// A query performs a full scan of a large table.
// The table is not in the pool.
// For each page read:
// 1. The page is inserted at the midpoint (head of old sublist)
// 2. The page is not accessed again
// 3. The page ages toward the tail of the old sublist
// 4. The page is evicted when it reaches the tail

// ============================================
// PART 3: THE HOT PAGES SURVIVE
// ============================================
// The hot pages in the new sublist are not displaced
// by the scan, because the scanned pages never reach
// the new sublist. They are inserted at the midpoint
// and evicted from the old sublist.
//
// The scan churns the old sublist, not the new sublist.

// ============================================
// PART 4: A HOT PAGE ACCESS
// ============================================
// A query accesses a hot page.
// The page is already in the new sublist.
// The access moves it to the head of the new sublist.
// No eviction is needed.

// ============================================
// PART 5: A COLD PAGE ACCESS
// ============================================
// A query accesses a page that is not in the pool.
// The page is inserted at the midpoint.
// The page is accessed again within the same query.
// The access moves it to the new sublist.
// The page is now a candidate for retention.

// ============================================
// PART 6: THE CLOCK SWEEP (POSTGRESQL)
// ============================================
// PostgreSQL's clock sweep:
// 1. The clock hand advances through the buffer array
// 2. For each buffer, if usage_count > 0, decrement and move on
// 3. If usage_count == 0, evict the buffer
// 4. The hand wraps around and continues
//
// A page that was accessed recently has a positive count
// and survives the first pass. A page that was not accessed
// has a count of zero and is evicted immediately.

The six parts cover the buffer pool state, the table scan, the survival of hot pages, the hot page access, the cold page access, and the clock sweep. What the session demonstrates is that the midpoint insertion is the mechanism that protects the hot pages from a scan, and the clock sweep is the lower-overhead approximation that PostgreSQL uses.

Quick Reference

Buffer Pool Parameters

Engine	Parameter	Default	Effect
PostgreSQL	`shared_buffers`	128 MB	Size of the buffer pool
InnoDB	`innodb_buffer_pool_size`	128 MB	Size of the buffer pool
InnoDB	`innodb_old_blocks_pct`	37	Percentage of old sublist
InnoDB	`innodb_old_blocks_time`	1000 ms	Promotion delay

Page Replacement Algorithms

Engine	Algorithm	Key Feature
PostgreSQL	Clock sweep	Usage count, single hand
InnoDB	Midpoint-insertion LRU	New/old sublists, 3/8 split
Oracle	Touch-count LRU	Keep/recycle pools
SQL Server	Clock	Reference bit, single pool

Eviction Behavior

Scenario	PostgreSQL	InnoDB
Table scan	Evicts pages with count 0	Inserts at midpoint, evicts from old
Hot page access	Count incremented	Moved to new sublist
Cold page access	Count incremented	Inserted at midpoint
Scan resistance	Low	High (midpoint + time window)

Best Practices

✅ Do This:

# Size the buffer pool to hold the working set
shared_buffers = 25% of RAM

# InnoDB: keep the default midpoint insertion for scan resistance
innodb_old_blocks_pct = 37
innodb_old_blocks_time = 1000

❌ Don’t Do This:

# Set the buffer pool too small
shared_buffers = 128M # for a 64 GB server

# Set innodb_old_blocks_pct to 95
# This makes InnoDB close to strict LRU, vulnerable to scans

Common Pitfalls

Pitfall	Why It Happens	Fix
Low cache hit rate	Buffer pool too small	Increase `shared_buffers` or `innodb_buffer_pool_size`
Scan evicts hot pages	Strict LRU behavior	Use InnoDB’s midpoint insertion
Clock sweep evicts hot page	Usage count saturated	Larger pool, or use a different engine
Buffer pool contention	Single pool, many cores	Split into multiple instances (InnoDB)

Real-World Examples

1. PostgreSQL buffer pool

SHOW shared_buffers;

2. InnoDB buffer pool size

SHOW VARIABLES LIKE 'innodb_buffer_pool_size';

3. InnoDB old blocks percentage

SHOW VARIABLES LIKE 'innodb_old_blocks_pct';

4. InnoDB old blocks time

SHOW VARIABLES LIKE 'innodb_old_blocks_time';

5. Buffer pool hit rate

SHOW ENGINE INNODB STATUS\G
-- Look for "Buffer pool hit rate"

6. PostgreSQL buffer cache

SELECT * FROM pg_buffercache;

7. Oracle keep pool

ALTER TABLE t STORAGE (BUFFER_POOL KEEP);

8. SQL Server buffer pool

SELECT * FROM sys.dm_os_buffer_descriptors;

9. InnoDB multiple pool instances

innodb_buffer_pool_instances = 8

10. PostgreSQL clock sweep

-- The clock hand is internal; no SQL interface

Visual

InnoDB LRU Sublists

┌──────────────────────────────────────────────┐
│  NEW SUBLIST (3/8)      OLD SUBLIST (5/8)    │
│  ┌───────────────┐      ┌───────────────┐    │
│  │ Hot page 1    │      │ New page      │    │
│  │ Hot page 2    │      │ (midpoint)    │    │
│  │ Hot page 3    │      │ Cold page     │    │
│  │ ...           │      │ ...           │    │
│  └───────────────┘      └───────────────┘    │
│         ▲                      ▲             │
│         │                      │             │
│    accessed again          inserted here     │
│    → moved here            → ages out        │
└──────────────────────────────────────────────┘

Clock Sweep

┌──────────────────────────────────────────────┐
│  Buffer array:                               │
│  [B1:1] [B2:0] [B3:2] [B4:0] [B5:1] ...     │
│         ▲                                    │
│         │                                    │
│  Hand passes:                                │
│  B2 count 0 → evict                         │
│  B1 count 1 → decrement to 0, move on       │
│  B3 count 2 → decrement to 1, move on       │
│  B4 count 0 → evict                         │
└──────────────────────────────────────────────┘

Sequential Flooding

┌──────────────────────────────────────────────┐
│  STRICT LRU:                                 │
│  Scan reads every page of a large table      │
│  → every page moves to head                  │
│  → hot pages evicted                         │
│  → next query re-reads from disk             │
│                                              │
│  MIDPOINT INSERTION:                         │
│  Scan inserts pages at midpoint              │
│  → pages age out from old sublist            │
│  → hot pages in new sublist survive          │
└──────────────────────────────────────────────┘

Summary

Item	Value
Buffer pool	In-memory cache of disk pages
PostgreSQL algorithm	Clock sweep
InnoDB algorithm	Midpoint-insertion LRU
Oracle algorithm	Touch-count LRU with keep pool
SQL Server algorithm	Clock with reference bit
InnoDB old sublist	37% of pool
InnoDB promotion delay	1000 ms
Scan resistance	Midpoint insertion (InnoDB)

Key takeaways:

The buffer pool is the cache that makes queries fast. Every read and write goes through it. A larger pool means more pages stay in memory and fewer disk reads are needed .
Strict LRU is vulnerable to sequential flooding. A table scan moves every page to the head, evicting the hot working set. Every major database uses a variant that mitigates this .
InnoDB uses midpoint insertion. New pages are inserted at the midpoint of the LRU list, so a scan churns the old sublist without displacing the hot pages in the new sublist. The innodb_old_blocks_pct and innodb_old_blocks_time parameters tune this behavior .
PostgreSQL uses a clock sweep. It is a low-overhead approximation of LRU that uses a usage count and a single hand, rather than a linked list. It is simpler and faster per access, but coarser in its decisions.
The buffer pool size is the most important tuning parameter. A pool that is too small forces constant eviction and disk I/O. A pool that is too large wastes memory that the OS could use for its own page cache.

Remember: The buffer pool is the database’s most important performance structure. Every query’s speed depends on whether its pages are in the pool. The replacement algorithm determines which pages stay and which go. InnoDB’s midpoint insertion is a direct response to the sequential flooding problem: it protects the hot pages by making new pages prove their worth before they can displace the working set. PostgreSQL’s clock sweep is a lower-overhead approximation that trades some precision for speed. The choice between them is the choice between scan resistance and simplicity, and the right choice depends on the workload. A database that serves a mix of scans and point lookups needs the scan resistance. A database that serves only point lookups can afford the simpler algorithm.

Stop using slow, ad-bloated tool sites! 🤮

🔎 Search “KandZ Tools” on Google to use many professional utilities for free.

KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)

⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free

🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!