Benchmarking Learned Indexes

Abstract

Recent advancements in learned index structures propose replacing existing index structures, like B-Trees, with approximate learned models. In this work, we present a unified benchmark that compares well-tuned implementations of three learned index structures against several state-of-the-art "traditional" baselines. Using four real-world datasets, we demonstrate that learned index structures can indeed outperform non-learned indexes in read-only in-memory workloads over a dense array. We also investigate the impact of caching, pipelining, dataset size, and key size. We study the performance profile of learned index structures, and build an explanation for why learned models achieve such good performance. Finally, we investigate other important properties of learned index structures, such as their performance in multi-threaded systems and their build times.

References in corpus (1)

• The PGM-index: a multicriteria, compressed and learned approach to data indexing

Cited by in corpus (4)

• Federated Learning on Non-IID Data Silos: An Experimental Study
• APEX: A High-Performance Learned Index on Persistent Memory
• Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform
• There is No Such Thing as an "Index"! or: The next 500 Indexing Papers