Analysis and testing of the RadixSpline Learned index

Abstract

Recent advances in machine learning have introduced a novel approach to database indexing known as learned indexes. Among these, the RadixSpline index has emerged as a particularly promising solution for efficient search in sorted key-value data. This paper presents a comprehensive analysis and performance evaluation of the RadixSpline index, which combines spline approximation with bounded error (GreedySpline) and a sparse radix table structure. We investigate the index’s behavior under different parameter configurations, focusing on two key parameters: the spline approximation error (err) and the radix prefix length (r). Our experimental study, conducted on a 25 MB subset of the MovieLens32M dataset, demonstrates that RadixSpline can achieve up to 30% faster search times compared to traditional binary search while reducing memory usage by over 80 % compared to RocksDB’s sparse index implementation. The study makes several important contributions: (1) we provide a detailed analysis of parameter sensitivity, identifying optimal configurations for various use cases; (2) we address implementation challenges not covered in the original work, including handling of non-contiguous prefixes and missing keys; (3) we demonstrate the index’s suitability for real-time applications through its single-pass construction property. Our results confirm that RadixSpline offers significant advantages over conventional indexing methods, particularly in scenarios requiring fast searches with limited memory resources. The findings suggest strong potential for integrating RadixSpline into production database systems, with RocksDB being a particularly promising candidate for such integration.