Source-linked AI summary
SOSD: A Benchmark for Learned Indexes
Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, Thomas Neumann
TL;DR
Whether learned indexes can outperform optimized traditional structures on real-world data remains contested. SOSD introduces an open benchmark with datasets and optimized baselines, and preliminary experiments find that learned indexes can outperform traditional indexes in many scenarios.
Problem
Whether learned indexes outperform optimized traditional structures on real-world data remains contested, and prior work lacked an open-source implementation.
Source: §1 · p. 1Method
SOSD is an open-source benchmark for comparing in-memory search algorithms on sorted data, with diverse datasets and efficient baseline implementations.
Source: §3 · p. 2Results
Learned index structures can outperform traditional index structures in many scenarios in the preliminary SOSD experiments.
Source: §1 · p. 1Takeaways & Limitations
Index choice depends on whether users can afford dataset-specific CDF-model tuning; the authors recommend RMI or RadixSpline when they can.
Source: §4 · p. 4Learned indexes lack support for efficient updates, although several benchmarked methods also lack them.
Source: §4 · p. 4
Abstract
from arXiv · showhide
A groundswell of recent work has focused on improving data management systems with learned components. Specifically, work on learned index structures has proposed replacing traditional index structures, such as B-trees, with learned models. Given the decades of research committed to improving index structures, there is significant skepticism about whether learned indexes actually outperform state-of-the-art implementations of traditional structures on real-world data. To answer this question, we propose a new benchmarking framework that comes with a variety of real-world datasets and baseline implementations to compare against. We also show preliminary results for selected index structures, and find that learned models indeed often outperform state-of-the-art implementations, and are therefore a promising direction for future research.
1 Introduction
Learned indexes [14] attracted interest as alternatives to traditional structures, but skepticism persisted about their ability to beat optimized in-memory data structures. SOSD provides an open-source benchmark, and preliminary results show learned indexes can outperform traditional indexes in many scenarios.
1 Introduction
- Learned indexes [14] replace structures such as B-trees with models that predict a sought key’s position in a sorted array by approximating its CDF.The CDF is the cumulative distribution function of the data.Source: §1 · p. 1
- SOSD enables comparisons of learned index structures on synthetic and real-world datasets through open-source code, diverse datasets, and optimized baselines.The authors describe their RMI implementation as the first performant, publicly available implementation of the approach proposed in [14].Source: §1 · p. 1
- Learned index structures can outperform traditional index structures in many scenarios, according to preliminary experiments using SOSD.The study reports end-to-end latency and uses performance counters such as cache misses and branch mispredictions to explain results; it also includes a bottom-up spline-based approach.Source: §1 · p. 1
- The SOSD RMI is a novel implementation, not the implementation used in [14].This qualification applies to the implementation presented by the authors.Source: §1 · p. 1
2 Techniques
The techniques compare in-memory secondary indexes on sorted data, spanning on-the-fly search, auxiliary structures, CDF-approximating learned indexes, and traditional indexes. The learned approaches estimate key positions, while traditional baselines reorganize the data into specialized structures.
2 Techniques
- Each technique acts as an in-memory secondary index associating keys with 64-bit TIDs and must find qualifying keys and their TIDs for a query.The studied approaches include on-the-fly algorithms, auxiliary indexes, CDF approximators, and traditional indexes.Source: §2 · p. 2
- RadixBinarySearch narrows a lookup to a key range using a radix structure, then binary-searches that smaller range.Its radix structure maps fixed-length key prefixes to their first occurrences in the sorted array.Source: §2 · p. 2
- RMI approximates the CDF with a typically two-level model tree built top-down, while RadixSpline fits a linear spline bottom-up and indexes its segments in a radix structure.RadixSpline locates the relevant segment at lookup time and linearly interpolates between its spline points.Source: §2 · p. 2
- Traditional baselines include ART radix trees, the STX v0.9 B+-tree implementation, and FAST, a cache-optimized binary search tree.These structures reorganize the data into specialized structures.Source: §2 · p. 2
3 Search on Sorted Data Benchmark
SOSD provides an open-source framework, datasets, and efficient baselines for comparing in-memory search algorithms on sorted data. Preliminary experiments examine lookup performance, build times, and performance counters.
Search on Sorted Data Benchmark
- SOSD is open-source C++ code with diverse datasets and efficient baselines, adding eight instructions and one cache miss per lookup.The benchmark also supports performance-counter analysis.Source: §3 · p. 2
Results
- RMI and RadixSpline have very low lookup latencies; ART leads on face32, while interpolation search excels on dense data but is sensitive to skew.Table 2 reports lookup latencies in nanoseconds per lookup for each technique.Source: Table 2 · p. 3, §3 · p. 3
Datasets
- SOSD includes eight datasets of 200 million 64-bit unsigned keys, with 32-bit versions for all except osmc and wiki.The datasets span real-world data and synthetic distributions.Source: §3 · p. 3
Queries and results
- Experiments use 10 million uniformly selected equality lookups, run one at a time on a single thread, on AWS c5.4xlarge.The measured DRAM latency for an LLC miss was 90 ns.Source: §3 · p. 3
Results
- RS has the highest build times because it fits a fine-grained linear spline; build phases are unoptimized, yet CDF-approximator build times may suit many applications.BS, IS, and TIP only copy the data vector; RBS scans the data to build its auxiliary structure.Source: Figure 2 · p. 3, §3 · p. 4
- On amzn32 and amzn64, FAST incurs fewer than five cache misses per lookup, while RMI and RS incur around ten but have similar or better search times.The passage cautions that cache misses, instructions, and branch mispredictions alone do not fully explain search-time differences.Source: §3 · p. 4, Figure 3 · p. 4
4 Takeaways
CDF approximators can outperform baseline implementations, but choosing an index depends on the workload and whether dataset-specific model tuning is affordable.
4 Takeaways
- CDF approximators RMI and RS can outperform baseline implementations, and simple models suffice for efficient learned indexes on the tested datasets.RMI is trained top-down, whereas RS is built bottom-up by fitting linear splines.Source: §4 · p. 4
- When users can afford dataset-specific tuning, the paper recommends RMI or RS; otherwise, it recommends ART or FAST for 32-bit keys and ART or RBS for 64-bit keys.For uniform dense integers, IS is the clear winner; RMI and RS consume little space, and RBS has low space overhead compared with ART.Source: §4 · p. 4
- Efficient updates are a current drawback of learned indexes, although several recent works address updates and RBS and FAST also lack efficient updates.The paper describes update support as an important feature for index structures.Source: §4 · p. 4
- Planned SOSD extensions include multi-threaded and vectorized lookups, updates, and integration into real database systems to measure effects on SQL queries.The authors also plan comparisons with recent learned-index variants and exploration of multidimensional indexes, accelerators, and query-specific compiled structures.Source: §4 · p. 4