Why Are Learned Indexes So Effective but Sometimes Ineffective?

Summary: The paper gives a theoretical account of PGM-Index effectiveness and pins practical slowdown to memory-bound queries and expensive internal search. Introduces PGM++—a mix-of-search-strategies with cost-model auto-tuning—achieving much faster lookups at similar space. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13929
Venue: VLDB
Year: 2025
Pagerank: 4.2856385e-05
Overall Rank: 9,745 | 32.28%
DOI: 10.14778/3746405.3746415

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,172	HIRE: A Hybrid Learned Index for Robust and Efficient Performance under Mixed Workloads	2026	SIGMOD	4.1905499e-05
10,706	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
101	The Case for Learned Index Structures	2018	SIGMOD	0.00049778866
382	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00024888997
819	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00016237497
844	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00015964123
1,085	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.00014173956
1,365	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00012379754
1,438	Benchmarking Learned Indexes	2021	VLDB	0.00011965956
2,550	Updatable Learned Index with Precise Positions	2021	VLDB	8.5569576e-05
2,734	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.2082721e-05
4,056	Are Updatable Learned Indexes Ready?	2022	VLDB	6.4905689e-05
4,069	CDFShop: Exploring and Optimizing Learned Index Structures	2020	SIGMOD	6.4744708e-05
4,448	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.1741316e-05
4,830	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	5.8884997e-05
5,072	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	5.7121108e-05
5,327	DILI: A Distribution-Driven Learned Index	2023	VLDB	5.5660777e-05
5,601	PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery	2023	VLDB	5.4158958e-05
5,655	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	5.3877506e-05
6,441	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.0546366e-05
7,389	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	4.7386163e-05
8,648	HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle	2022	SIGMOD	4.4718808e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,351	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD	4.3490308e-05
2,550	Updatable Learned Index with Precise Positions	2021	VLDB	8.5569576e-05
5,154	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR	5.6548237e-05
8,811	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD	4.4398976e-05
101	The Case for Learned Index Structures	2018	SIGMOD	0.00049778866
7,389	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	4.7386163e-05
1,438	Benchmarking Learned Indexes	2021	VLDB	0.00011965956
5,072	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	5.7121108e-05
6,442	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD	5.0541252e-05
844	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00015964123