# CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm

arXiv: https://arxiv.org/abs/2103.00858 · HTML: https://mlsanity.com/paper/2103.00858/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 63 references that are in the map.
- First posted on arXiv 1 Mar 2021.

## Builds on (most cited first, 17 of 17)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [Learning to Optimize Join Queries With Deep Reinforcement Learning](https://mlsanity.com/paper/1808.03196/) (2018)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [FITing-Tree: A Data-aware Index Structure](https://mlsanity.com/paper/1801.10207/) (2018)
- [Database Meets Deep Learning: Challenges and Opportunities](https://mlsanity.com/paper/1906.08986/) (2019)
- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads](https://mlsanity.com/paper/2006.13282/) (2020)
- [SOSD: A Benchmark for Learned Indexes](https://mlsanity.com/paper/1911.13014/) (2019)
- [The PGM-index: a multicriteria, compressed and learned approach to data indexing](https://mlsanity.com/paper/1910.06169/) (2019)
- [Learning State Representations for Query Optimization with Deep Reinforcement Learning](https://mlsanity.com/paper/1803.08604/) (2018)
- [The Case for Learned Spatial Indexes](https://mlsanity.com/paper/2008.10349/) (2020)
- [Towards a Hands-Free Query Optimizer through Deep Learning](https://mlsanity.com/paper/1809.10212/) (2018)
- [Database Learning: Toward a Database that Becomes Smarter Every Time](https://mlsanity.com/paper/1703.05468/) (2017)
- [A Model for Learned Bloom Filters and Related Structures](https://mlsanity.com/paper/1802.00884/) (2018)

## Built on by (most cited first, 8 of 8)

- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)
- [Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training](https://mlsanity.com/paper/2403.11472/) (2024)
- [LeCo: Lightweight Compression via Learning Serial Correlations](https://mlsanity.com/paper/2306.15374/) (2023)
- [A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach](https://mlsanity.com/paper/2502.05001/) (2025)
- [UpLIF: An Updatable Self-Tuning Learned Index Framework](https://mlsanity.com/paper/2408.04113/) (2024)
- [DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees](https://mlsanity.com/paper/2502.05369/) (2025)
- [Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2506.20139/) (2025)
- [Sig2Model: A Boosting-Driven Model for Updatable Learned Indexes](https://mlsanity.com/paper/2509.20781/) (2025)

## Abstract (arXiv)

Learned indexes, which use machine learning models to replace traditional index structures, have shown promising results in recent studies. However, existing learned indexes exhibit a performance gap between synthetic and real-world datasets, making them far from practical indexes. In this paper, we identify that ignoring the importance of data partitioning during model training is the main reason for this problem. Thus, we explicitly apply data partitioning to index construction and propose a new efficient and updatable cache-aware RMI framework, called CARMI. Specifically, we introduce entropy as a metric to quantify and characterize the effectiveness of data partitioning of tree nodes in learned indexes and propose a novel cost model, laying a new theoretical foundation for future research. Then, based on our novel cost model, CARMI can automatically determine tree structures and model types under various datasets and workloads by a hybrid construction algorithm without any manual tuning. Furthermore, since memory accesses limit the performance of RMIs, a new cache-aware design is also applied in CARMI, which makes full use of the characteristics of the CPU cache to effectively reduce the number of memory accesses. Our experimental study shows that CARMI performs better than baselines, achieving an average of 2.2x/1.9x speedup compared to B+ Tree/ALEX, while using only about 0.77x memory space of B+ Tree. On the SOSD platform, CARMI outperforms all baselines, with an average speedup of 1.2x over the nearest competitor RMI, which has been carefully tuned for each dataset in advance.