# Towards Practical Learned Indexing

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 13 references that are in the map.
- First posted on arXiv 11 Aug 2021.

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

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [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)

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

- [Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training](https://mlsanity.com/paper/2403.11472/) (2024)
- [A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach](https://mlsanity.com/paper/2502.05001/) (2025)
- [LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization](https://mlsanity.com/paper/2307.08637/) (2023)

## Abstract (arXiv)

Latest research proposes to replace existing index structures with learned models. However, current learned indexes tend to have many hyperparameters, often do not provide any error guarantees, and are expensive to build. We introduce Practical Learned Index (PLEX). PLEX only has a single hyperparameter ε (maximum prediction error) and offers a better trade-off between build and lookup time than state-of-the-art approaches. Similar to RadixSpline, PLEX consists of a spline and a (multi-level) radix layer. It first builds a spline satisfying the given ε and then performs an ad-hoc analysis of the distribution of spline points to quickly tune the radix layer.