# Benchmarking Learned Indexes

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2020.

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

- [Federated Learning on Non-IID Data Silos: An Experimental Study](https://mlsanity.com/paper/2102.02079/) (2021)
- [Data-centric Artificial Intelligence: A Survey](https://mlsanity.com/paper/2303.10158/) (2023)
- [CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm](https://mlsanity.com/paper/2103.00858/) (2021)
- [Bounding the Last Mile: Efficient Learned String Indexing](https://mlsanity.com/paper/2111.14905/) (2021)
- [WISK: A Workload-aware Learned Index for Spatial Keyword Queries](https://mlsanity.com/paper/2302.14287/) (2023)
- [On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing](https://mlsanity.com/paper/2306.10651/) (2023)
- [Learned Sorted Table Search and Static Indexes in Small Model Space](https://mlsanity.com/paper/2107.09480/) (2021)
- [On the Choice of General Purpose Classifiers in Learned Bloom Filters: An Initial Analysis Within Basic Filters](https://mlsanity.com/paper/2112.06563/) (2021)
- [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)
- [Towards Practical Learned Indexing](https://mlsanity.com/paper/2108.05117/) (2021)
- [On the Suitability of Neural Networks as Building Blocks for The Design of Efficient Learned Indexes](https://mlsanity.com/paper/2203.14777/) (2022)
- [Micro-architectural Analysis of a Learned Index](https://mlsanity.com/paper/2109.08495/) (2021)
- [Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform](https://mlsanity.com/paper/2201.01554/) (2022)
- [Proteus: A Self-Designing Range Filter](https://mlsanity.com/paper/2207.01503/) (2022)
- [LSI: A Learned Secondary Index Structure](https://mlsanity.com/paper/2205.05769/) (2022)
- [DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees](https://mlsanity.com/paper/2502.05369/) (2025)
- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [Multi-agent Databases via Independent Learning](https://mlsanity.com/paper/2205.14323/) (2022)
- [Learned k-NN Distance Estimation](https://mlsanity.com/paper/2208.14210/) (2022)
- [A Critical Analysis of Classifier Selection in Learned Bloom Filters](https://mlsanity.com/paper/2211.15565/) (2022)
- [Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees](https://mlsanity.com/paper/2304.07652/) (2023)
- [LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization](https://mlsanity.com/paper/2307.08637/) (2023)
- [From Specific to Generic Learned Sorted Set Dictionaries: A Theoretically Sound Paradigm Yelding Competitive Data Structural Boosters in Practice](https://mlsanity.com/paper/2309.00946/) (2023)
- [Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2506.20139/) (2025)
- [Lower Bounds for the Algorithmic Complexity of Learned Indexes](https://mlsanity.com/paper/2601.06629/) (2026)
- [Adversarial Query Synthesis via Bayesian Optimization](https://mlsanity.com/paper/2603.01570/) (2026)

## Abstract (arXiv)

Recent advancements in learned index structures propose replacing existing index structures, like B-Trees, with approximate learned models. In this work, we present a unified benchmark that compares well-tuned implementations of three learned index structures against several state-of-the-art "traditional" baselines. Using four real-world datasets, we demonstrate that learned index structures can indeed outperform non-learned indexes in read-only in-memory workloads over a dense array. We also investigate the impact of caching, pipelining, dataset size, and key size. We study the performance profile of learned index structures, and build an explanation for why learned models achieve such good performance. Finally, we investigate other important properties of learned index structures, such as their performance in multi-threaded systems and their build times.