# SOSD: A Benchmark for Learned Indexes

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2019.

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

- [NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes](https://mlsanity.com/paper/2312.14890/) (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)
- [Online List Labeling with Predictions](https://mlsanity.com/paper/2305.10536/) (2023)
- [Learned Sorted Table Search and Static Indexes in Small Model Space](https://mlsanity.com/paper/2107.09480/) (2021)
- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)
- [Towards Practical Learned Indexing](https://mlsanity.com/paper/2108.05117/) (2021)
- [NFL: Robust Learned Index via Distribution Transformation](https://mlsanity.com/paper/2205.11807/) (2022)
- [LeCo: Lightweight Compression via Learning Serial Correlations](https://mlsanity.com/paper/2306.15374/) (2023)
- [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)
- [Learned-Database Systems Security](https://mlsanity.com/paper/2212.10318/) (2022)
- [A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach](https://mlsanity.com/paper/2502.05001/) (2025)
- [LSI: A Learned Secondary Index Structure](https://mlsanity.com/paper/2205.05769/) (2022)
- [UpLIF: An Updatable Self-Tuning Learned Index Framework](https://mlsanity.com/paper/2408.04113/) (2024)
- [Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees](https://mlsanity.com/paper/2304.07652/) (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)
- [LearnedKV: Integrating LSM and Learned Index for Superior Performance on Storage](https://mlsanity.com/paper/2406.18892/) (2024)
- [P-MOSS: Scheduling Main-Memory Indexes Over NUMA Servers Using Next Token Prediction](https://mlsanity.com/paper/2411.02933/) (2024)
- [Sig2Model: A Boosting-Driven Model for Updatable Learned Indexes](https://mlsanity.com/paper/2509.20781/) (2025)

## Abstract (arXiv)

A groundswell of recent work has focused on improving data management systems with learned components. Specifically, work on learned index structures has proposed replacing traditional index structures, such as B-trees, with learned models. Given the decades of research committed to improving index structures, there is significant skepticism about whether learned indexes actually outperform state-of-the-art implementations of traditional structures on real-world data. To answer this question, we propose a new benchmarking framework that comes with a variety of real-world datasets and baseline implementations to compare against. We also show preliminary results for selected index structures, and find that learned models indeed often outperform state-of-the-art implementations, and are therefore a promising direction for future research.