# Why Are Learned Indexes So Effective but Sometimes Ineffective?

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2024.

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

- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2506.20139/) (2025)
- [Poisoning Attacks on the PGM-index](https://mlsanity.com/paper/2609.02328/) (2026)

## Abstract (arXiv)

Learned indexes have attracted significant research interest due to their ability to offer better space-time trade-offs compared to traditional B+-tree variants. Among various learned indexes, the PGM-Index based on error-bounded piecewise linear approximation is an elegant data structure that has demonstrated provably superior performance over conventional B+-tree indexes. In this paper, we explore two interesting research questions regarding the PGM-Index: (a) Why are PGM-Indexes theoretically effective? and (b) Why do PGM-Indexes underperform in practice? For question~(a), we first prove that, for a set of N sorted keys, the PGM-Index can, with high probability, achieve a lookup time of O(loglog N) while using O(N) space. To the best of our knowledge, this is the tightest bound for learned indexes to date. For question~(b), we identify that querying PGM-Indexes is highly memory-bound, where the internal error-bounded search operations often become the bottleneck. To fill the performance gap, we propose PGM++, a simple yet effective extension to the original PGM-Index that employs a mixture of different search strategies, with hyper-parameters automatically tuned through a calibrated cost model. Extensive experiments on real workloads demonstrate that PGM++ establishes a new Pareto frontier. At comparable space costs, PGM++ speeds up index lookup queries by up to 2.31× and 1.56× when compared to the original PGM-Index and state-of-the-art learned indexes.