Why Are Learned Indexes So Effective but Sometimes Ineffective?

Summary: Explains PGM-Index’s theoretical O(log log N) lookups with O(N) space, yet identifies memory-bound internal searches as the practical bottleneck. PGM++ mixes search strategies and cost-model tuning, improving lookup speed up to 2.31×. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h96d9cd120358a024
Venue: VLDB
Year: 2025
Pagerank: 5.255795e-05
Overall Rank: 8,882 | 40.31%
DOI: 10.14778/3746405.3746415
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Qiyu Liu (Southwest University)
2. Siyuan Han (Hong Kong University of Science and Technology)
3. Yanlin Qi (Harbin Engineering University)
4. Jingshu Peng (ByteDance)
5. Jin Li (Harvard University)
6. Longlong Lin (Southwest University)
7. Lei Chen (Hong Kong University of Science and Technology)

BibTeX Citation

@article{liu_vldb25,
        title = {{Why Are Learned Indexes So Effective but Sometimes Ineffective?}},
        author = {Liu, Qiyu and Han, Siyuan and Qi, Yanlin and Peng, Jingshu and Li, Jin and Lin, Longlong and Chen, Lei},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {9},
        pages = {2886--2898},
        doi = {10.14778/3746405.3746415},
        url = {https://doi.org/10.14778/3746405.3746415},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,485	LICO: An SIMD-Aware High-Performance Learned Inverted Index Compression Framework	2026	SIGMOD	4.9769913e-05
10,491	Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions	2026	SIGMOD	4.9769913e-05
10,500	On Self-Designing Learned Indexes	2026	SIGMOD	4.9769913e-05
10,659	HIRE: A Hybrid Learned Index for Robust and Efficient Performance under Mixed Workloads	2026	SIGMOD	4.9769913e-05
11,340	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB	4.9769913e-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
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
277	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022320139
422	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018488849
458	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017880664
768	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014107655
835	Benchmarking Learned Indexes	2021	VLDB	0.00013575971
904	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.00013170142
1,525	Updatable Learned Index with Precise Positions	2021	VLDB	0.00010355133
2,235	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.787006e-05
2,582	Are Updatable Learned Indexes Ready?	2022	VLDB	8.2641447e-05
3,198	CDFShop: Exploring and Optimizing Learned Index Structures	2020	SIGMOD	7.5422544e-05
3,621	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.1510804e-05
3,701	Stable Learned Bloom Filters for Data Streams	2020	VLDB	7.0820503e-05
3,710	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	7.0775695e-05
4,362	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	6.6357559e-05
4,366	DILI: A Distribution-Driven Learned Index	2023	VLDB	6.6330579e-05
4,635	PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery	2023	VLDB	6.4904555e-05
6,426	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.7871847e-05
6,613	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	5.7326443e-05
8,955	HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle	2022	SIGMOD	5.2508006e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,601	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD
2	1,525	Updatable Learned Index with Precise Positions	2021	VLDB
3	4,715	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR
4	8,382	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD
5	40	The Case for Learned Index Structures	2018	SIGMOD
6	6,613	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD
7	835	Benchmarking Learned Indexes	2021	VLDB
8	3,621	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB
9	5,378	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD
10	458	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB