Beyond Traditional Search: SIMD-Optimized Correction for Learned Index

Yeojin Oh, Nakyeong Kim, Jongmoo Choi, Seehwan Yoo

http://doi.org/10.5626/JOK.2025.52.5.363

To address the limitations of traditional indexing techniques, this study examines the search performance of machine learning-based Learned Indexes, focusing on the read-only RMI and the modifiable ALEX We propose a SIMD-based optimization technique to minimize the overhead incurred during the correction phase, which accounts for over 80% of the total search time. Learned Indexes operate in two phases: prediction and correction. In our experiments with RMI, we found that when the error range is large, the SIMD Branchless Binary Search capable of quickly narrowing down the search range outperforms other methods. In contrast. when the error range is small, the model prediction-based SIMD Linear Search demonstrates superior performance. For ALEX, which maintains a relatively constant error range, the straightforward SIMD Linear Search proved to be the most efficient compared to more complex search techniques. These results underscore the importance of choosing the right search algorithm based on the dataset’s error range, index size, and density to achieve optimal performance.