Cache-Aware I/O Cost Modeling for Disk-Based Learned Indexes

Zhanwei Shi, Meng Zhang, Guangyi Zhang, Sha Hu, Jianwei Liao, Jingshu Peng, Qiyu Liu, Yingxia ShaoarXiv 2026 · arXiv

TL;DR

Disk-based learned indexes offer great space savings but suffer from unpredictable I/O costs due to the complex interplay between "last-mile" search windows and database page buffers. This paper introduces CAM (Cache-Aware I/O Cost Model), the first framework to analytically predict physical disk accesses across various cache eviction policies without requiring slow, full-trace simulations. By accurately balancing index size against buffer capacity, CAM accelerates index tuning by up to 17× and speeds up database joins by up to 8.8×.

What Problem Does This Paper Address?

Learned indexes have revolutionized in-memory data structures by replacing traditional B+-tree nodes with compact machine learning models that predict a key's position. However, when data spills to disk, things get messy.

Unlike a B+-tree, which points directly to a specific page, a learned index outputs an approximate position bounded by an error range ($\epsilon$). The database must then perform a "last-mile" search over a window of pages to find the actual record.

To minimize slow disk I/O, databases use a page buffer (cache) to keep frequently accessed pages in memory. This creates two tightly coupled challenges:

  1. Irregular Access: The last-mile search pattern is highly irregular and dependent on the index's internal geometry.
  2. Buffer Absorption: Many logical page requests are absorbed by the cache and never hit the disk.

Prior query optimizers either completely ignored the cache—leading to highly inaccurate cost estimations—or relied on full workload replays, which are far too slow to be useful during active query optimization or index tuning. Furthermore, under a fixed memory budget, a larger, more accurate index leaves less room for the page buffer, creating a complex optimization trade-off.

Fig. 1: I/O cost estimation methods on a disk-based PGM index (books dataset, 1 M point lookups, 128 MiB LRU buffer). LPM counts all pages touched by the last-mile search; REPLAY-100 executes the full query trace under the actual buffer; CAM-x (this work) estimates from an x% workload sample. CAM matches Replay accuracy but is 17.13× faster; LPM is up to 2.6× off.

Methods

The authors propose CAM, a cache-aware I/O cost model that decouples cost estimation into two distinct, analytical components:

  • Structural Page-Reference Distribution: CAM analyzes the index geometry (error bounds, page offsets, and fetching strategies) to determine which pages a query workload is likely to touch.
  • Policy-Pluggable Cache Models: Instead of simulating the cache step-by-step, CAM uses closed-form mathematical approximations (like Che's approximation) to estimate the hit rate for standard eviction policies, including LRU, FIFO, and LFU.

CAM supports two primary leaf-page fetching strategies: One-by-One (incremental probing) and All-at-Once (coalesced sequential reads).

Fig. 2: Illustration of model-routed learned index (e.g., RMI, left) and error-bounded learned index (e.g., PGM, right). The red dashed arrows denote the index traversal path predicted by ML models.

Using these estimates, CAM optimizes two critical database tasks:

  1. Memory-Budgeted Index Tuning: It automatically finds the optimal error bound ($\epsilon$ for PGM-indexes) or branching factor (for RMIs) that minimizes total physical I/O under a strict memory limit.
  2. CAM-Guided Hybrid Joins: For index nested-loop joins, CAM partitions the sorted probe sequence and adaptively switches between point probing (for sparse data regions to avoid fetching irrelevant pages) and range probing (for dense regions to amortize overhead).

Datasets

The model was evaluated using four standard, real-world tracking datasets containing 200 million sorted 64-bit unsigned integers each:

  • books: Highly regular, linear data.
  • fb: Facebook user IDs (highly dense).
  • osm: OpenStreetMap geospatial locations (weak local structure).
  • wiki: Wikipedia article edit timestamps.

Workloads were generated using mixtures of hotspot regions (skewed), Zipfian distributions, and uniform distributions to thoroughly test cache locality.

Key Insights and Ideas

  • The Naive Model Fails: Simply counting logical page accesses (the Logical Page Model, or LPM) mis-estimates physical I/O by up to 2.6× because it fails to account for page reuse in the buffer.
  • The U-Shaped Optimization Curve: As the index error bound ($\epsilon$) increases, the index shrinks, leaving more memory for the page buffer (raising the hit rate). However, if $\epsilon$ gets too large, the last-mile search window balloons, exploding the number of pages that must be fetched. CAM perfectly identifies the sweet spot at the bottom of this U-curve.
  • Lookup Table (LUT) Acceleration: To make CAM fast enough for real-time query optimizers, the authors precompute intra-page offsets and relative page distances into a tiny lookup table. This bypasses repetitive mathematical expansions during estimation.

Key Results

  • Replay Accuracy at a Fraction of the Time: CAM matches the accuracy of a 100% ground-truth trace replay (achieving a near-perfect ~1.04× Q-error) while running 17.13× faster.
  • Superior Throughput via Better Tuning: CAM-guided tuning improved PGM-index throughput by up to 1.17× over multicriteria tuning methods, and boosted RMI throughput by up to 1.66× compared to CDFShop.
  • Massive Join Speedups: For learned-index-based joins, the CAM-guided hybrid strategy outperformed conventional index nested-loop joins by up to 8.8× by intelligently balancing point and range probes.

Limitations and Future Work

  • LFU Steady-State Assumption: CAM's analytical model for the Least Frequently Used (LFU) policy assumes a converged, steady state. In practice, real-world workloads are finite, meaning CAM exhibits slightly higher estimation errors for LFU than for LRU or FIFO.
  • RMI Complexity: While CAM works for both PGM and RMI architectures, it is inherently more precise for PGM-indexes due to their strict, bounded error guarantees. RMI leaf-level errors depend on complex training dynamics, requiring physical index construction during the tuning phase.

Summary updated

Abstract

Learned indexes have shown attractive space-time trade-offs in main-memory settings, yet a principled I/O cost model for their disk-resident deployments is still missing, which is a prerequisite for index tuning and query optimization. The practically employed page buffer makes the problem even harder: under typical cache policies, many of the logical page references issued by the index are served by the buffer rather than reaching disk, so the effective physical I/O depends jointly on the workload, the cache policy, and the index configuration. In this paper, we propose CAM, the \textit{first} cache-aware I/O cost model for learned indexes that takes practical cache eviction policies into consideration. CAM is not tied to a particular learned index design: it estimates page access distributions without full trace replay for mainstream learned index designs, and then combines them with I/O cost models to estimate effective physical I/Os. This formulation enables principled knob tuning by explicitly modeling the trade-off between index footprint and buffer capacity. We instantiate CAM for disk-based PGM-index and RMI, and further apply the same modeling principle to learned-index-based joins through a hybrid strategy that adaptively chooses point or range probes based on local key density. Extensive experiments on real benchmarks show that CAM provides \textit{accurate and efficient} I/O estimation across diverse workloads: CAM-guided tuning improves PGM throughput by \textbf{1.17$\times$} over multicriteria PGM tuning and improves RMI throughput by \textbf{1.66$\times$} over CDFShop with I/O-related considerations. For learned-index-based joins, our hybrid strategy improves end-to-end performance by up to \textbf{8.8$\times$} over disk-based index nested-loop join.
BibTeX
@misc{shi2026cache,
  author = {Zhanwei Shi and Meng Zhang and Guangyi Zhang and Sha Hu and Jianwei Liao and Jingshu Peng and Qiyu Liu and Yingxia Shao},
  title = {{Cache-Aware I/O Cost Modeling for Disk-Based Learned Indexes}},
  year = {2026},
  eprint = {2606.21924},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.21924},
}
Figure