Source-linked AI summary
RadixSpline: A Single-Pass Learned Index
Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, Thomas Neumann
TL;DR
Existing learned indexes can deliver strong size and lookup performance but are often difficult to build efficiently. RadixSpline combines an error-bounded spline with a radix table for single-pass construction over sorted data. Experiments report competitive performance and size relative to RMI, while the method uses two hyperparameters and remains efficient to build.
Problem
Some learned indexes lack insert support and cannot be constructed in a single pass, limiting their applications.
Method
RadixSpline builds an error-bounded spline and a radix table in a single pass over sorted data.
Results
RS is competitive with RMI in size and lookup performance, is almost as efficient to build as ART or BTree, and offers memory-performance trade-offs across configurations.
Takeaways & Limitations
RS is a practical learned index for write-once/read-many settings such as LSM-trees, with two hyperparameters that are relatively easy to tune.
Takeaways & Limitations
RS can be less effective with large outliers or heavy skew, and its current implementation does not use multithreading.
Abstract
from arXiv · showhide
Recent research has shown that learned models can outperform state-of-the-art index structures in size and lookup performance. While this is a very promising result, existing learned structures are often cumbersome to implement and are slow to build. In fact, most approaches that we are aware of require multiple training passes over the data. We introduce RadixSpline (RS), a learned index that can be built in a single pass over the data and is competitive with state-of-the-art learned index models, like RMI, in size and lookup performance. We evaluate RS using the SOSD benchmark and show that it achieves competitive results on all datasets, despite the fact that it only has two parameters.
1 INTRODUCTION
RadixSpline addresses the costly construction of learned indexes by enabling single-pass building over sorted data. It targets write-once/read-many settings such as LSM-trees while retaining competitive size and lookup performance.
- Learned indexes use models of sorted data’s CDF to predict lookup-key positions and can compete with state-of-the-art indexes in size and lookup performance.
- RMIs lack insert support and cannot be constructed in a single pass, limiting their applications.
- LSM-tree file merges produce sorted data that can be passed through a single-pass training algorithm, potentially adding only negligible constant overhead.
- RadixSpline is a learned index built in a single pass over sorted data with constant work per new element.
- RS fits an error-bounded linear spline to the data CDF, then builds a radix table that indexes the resulting spline points.
- RS is competitive with RMI in size and lookup performance, uses roughly one hundred lines of C++ and two hyperparameters, and can be affected by heavy skew.
2 RADIXSPLINE
RadixSpline combines an error-bounded spline with a radix table to map sorted lookup keys to approximate positions. Its single-pass construction and bounded search make lookups efficient while controlling index size.
- An RS index contains spline points, a subset of keys chosen so interpolation predicts lookup positions within a preset error bound, and a radix table.
- The spline model S satisfies S(k_i) = p_i ± e, guaranteeing that predicted data locations remain within constant error e.
- The radix table maps fixed-length key prefixes to spline-point offsets, narrowing the spline-point range examined for a lookup.
- The radix table has 2^r entries, so increasing radix bits exponentially increases table size while potentially narrowing the spline-point search range.
- RS builds the spline and radix table bottom-up in a single pass over sorted data, unlike indexes requiring multiple passes.
- Lookup extracts a radix prefix, retrieves two table pointers, binary-searches the bounded spline range, interpolates a position, and searches within p ± e.
3 EVALUATION
The evaluation compares RadixSpline with traditional and learned indexes on build time, lookup latency, size, configuration trade-offs, and LSM-tree performance. RS builds nearly as efficiently as traditional indexes, offers learned-index lookup performance with distribution sensitivity, and can trade performance for substantially lower memory use.
- Benchmark setup: RS is evaluated on six 64-bit datasets containing 200 M key/value pairs each, using SOSD end-to-end lookup measurements.The evaluation reports average latency for 10M single-threaded lookups after producing a search range and performing binary search.
- Compared indexes: RS is compared with ART, BTree, binary search, and the recursive model index (RMI).The traditional indexes use a stride of 32, while RMI is a top-down learned index using multiple model types.
- Build time: RS is significantly faster to build than RMI and almost as efficient to build as ART or BTree.The difference is attributed to RS’s single-pass build process versus RMI’s multiple training passes over sorted datapoints.
- Lookup latency: Both learned approaches are significantly faster than traditional indexes but are more affected by data distribution.The learned approaches were tuned for minimum lookup latency; binary search takes around 850ns and BTree around 600ns per lookup.
- Index size: Except for binary search and a few outliers, indexes use around 100 MiB, or 6.6% of the uncompressed key size; RS exceeds 600 MiB on face.The face configuration uses approximately 650 MiB for best performance, motivating configuration analysis.
- Configuration space: On face, spline error 16 with 20 radix bits reduces space by 99.9% while reducing performance by 11.5% relative to the best configuration.This configuration builds within 2s and requires less than 200 MiB.
- LSM-tree performance: In a preliminary RocksDB experiment, RS reduced total execution time from 712 seconds to 521 seconds and used approximately 45% less memory.Average write time increased by approximately 4%, while average read time decreased by over 20% in the 50%-read, 50%-write workload.
4 CONCLUSIONS
The paper concludes that RadixSpline is a compact, tunable learned index with a single-pass build and competitive size and lookup performance. It also identifies limits and future work around scaling, outliers, automatic tuning, and multithreading.
- 4 CONCLUSIONS: RS is a learned index built in a single pass over sorted data with two hyperparameters that are easy to tune to a dataset and memory budget.The hyperparameters control spline error and radix table size.
- 4 CONCLUSIONS: Experiments on real-world data show that RS is competitive with a state-of-the-art learned index in size and lookup performance while building as efficiently as traditional indexes.
- 4 CONCLUSIONS: The constant-size radix table may become less useful as dataset size grows or under large outliers.
- 4 CONCLUSIONS: Future work targets automatic tuning with minimal user interaction and balancing memory footprint against performance.The proposed tuning could use metrics extracted from the data.
- 4 CONCLUSIONS: RS currently does not use multithreading, leaving performance improvements as another future-work direction.