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:
- Irregular Access: The last-mile search pattern is highly irregular and dependent on the index's internal geometry.
- 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.
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).
Using these estimates, CAM optimizes two critical database tasks:
- 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.
- 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