How MySQL's Midpoint Insertion Strategy Prevents Cache Pollution

Understanding Database Caching and Locality of Reference

Databases heavily rely on caching to minimize latency, leveraging the significant speed difference between RAM and disk. While RAM lookups take a baseline X time, SSD lookups can take 4X, and HDD lookups 80X. To optimize performance, databases utilize RAM effectively.

Pages: The Unit of Database Operation

The fundamental unit of data transfer and caching in a database is a page, typically 4KB, 8KB, or 16KB. Even if only a single row is requested, the entire page containing that row is read from disk and cached in memory. A single page can contain multiple rows; for instance, a 4KB page might hold four 1KB rows.

Locality of Reference

Caching strategies are built upon two key principles of locality:

1. Spatial Locality: If a particular data item (e.g., a row) is accessed, there’s a high probability that nearby data items (e.g., adjacent rows on the same page) will be accessed soon. This makes caching entire pages a good strategy.
2. Temporal Locality: If a data item (e.g., a page) is accessed, there’s a high probability that the same item will be accessed again in the near future. This justifies keeping recently accessed pages in memory.

The Standard LRU Caching Approach

Databases maintain a buffer pool in RAM, which is a pool of cached pages. To manage this limited resource, a common eviction policy is Least Recently Used (LRU). A typical LRU implementation uses a doubly linked list:

• Head: Contains the Most Recently Used (MRU) pages.
• Tail: Contains the Least Recently Used (LRU) pages.

When a page is accessed, it’s moved to the head of the list. When the buffer pool is full and a new page needs to be cached, the page at the tail of the list (the LRU page) is evicted to make space.

The Problem: Cache Pollution During Full Table Scans

While standard LRU works well for many workloads, it suffers from a critical flaw during sequential full table scans. Consider a scenario where an entire table is iterated, perhaps for a data dump or a large analytical query. As each page of the table is accessed:

1. It becomes the most recently used page.
2. It is moved to the head of the LRU list.
3. If the cache is full, a page from the tail is evicted.

This process continues until the entire table has been scanned. The result is that the entire buffer pool gets wiped out and filled with pages from the table that was just scanned. If this table is rarely or never referenced again (as is often the case after a full dump), the cache becomes polluted with irrelevant data. Subsequent queries for frequently accessed data will now incur disk I/O, significantly degrading performance.

MySQL’s Midpoint Insertion Strategy

To combat cache pollution from full table scans, MySQL’s InnoDB storage engine employs a clever midpoint insertion strategy for its buffer pool. Instead of a single LRU list, the buffer pool is conceptually divided into two smaller sublists:

1. Young Sublist: Contains frequently accessed,