intechnguВестник НГУ. Серия: Информационные технологииVestnik NSU. Series: Information Technologies1818-79002410-0420НГУ10.25205/1818-7900-2025-23-3-67-78intechngu-326Research ArticleСтатьиАнализ и тестирование индекса RadixSplineAnalysis and testing of the RadixSpline Learned indexСтецкийИ. М.StetskiiI. M.

Стецкий Илья Максимович, магистрант

Новосибирск

 

Ilya M. Stetsky, Master’s Student

Novosibirsk

i.stetskii@g.nsu.ruПищикБ. Н.PischikB. N.

Пищик Борис Николаевич, доцент

Новосибирск

 

Boris N. Pishik, Associate Professor

Novosibirsk

b.pishchik@g.nsu.ruНовосибирский государственный университетРоссияNovosibirsk State UniversityRussian Federation2025101120252336778Copyright © Стецкий И.М., Пищик Б.Н., 20252025Стецкий И.М., Пищик Б.Н.Stetskii I.M., Pischik B.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://intechngu.elpub.ru/jour/article/view/326

Статья посвящена тестовой реализации индекса RadixSpline и исследованию его производительности при различных параметрах настойки. Индекс RadixSpline относится к категории обученного индекса и предназначен для эффективного поиска в отсортированных данных в структуре ключ – значение. Индекс строится за один проход по данным и состоит из сплайн-аппроксимации с ограниченной погрешностью (GreedySpline) и разреженного индекса (RadixTable). В работе перечислены известные обученные индексы и сравнение их с исследуемым RadixSpline, который выгодно отличается от других тем, что имеет простую структуру и малое количество параметров настройки. Проведен анализ работы RadixSpline и его частей, а также влияние параметров на производительность и объем затрачиваемой памяти. Тестирование реализации показало, что RadixSpline способен значительно сократить время поиска по сравнению с бинарным поиском. Кроме того, при других настройках можно сократить используемую память. В работе предлагаются уточнения в алгоритме RadixSpline и исследование возможности его интеграции в промышленные продукты для работы с большими данными.

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.

RadixSplineLearned Indexсплайн-аппроксимацияразреженный индексоптимизация поискапроизводительность СУБДмашинное обучение в индексацииRadixSplineLearned Indexspline approximationsparse indexsearch optimizationDBMS performancemachine learning in indexingИсследование выполнено при поддержке благотворительного фонда содействия образованию и становления молодых специалистов «Высшая лига».The work was supported by the charitable foundation for the promotion of education and formation of young specialists «Высшая лига».ReferencesKraska T., Beutel A., Chi E.H., Dean J., Polyzotis N. The Case for Learned Index Structures // arXiv:1712.01208 [cs.DB]. 2017. DOI: 10.48550/arXiv.1712.01208Kraska T., Beutel A., Chi E.H., Dean J., Polyzotis N. The Case for Learned Index Structures // arXiv:1712.01208 [cs.DB]. 2017. DOI: 10.48550/arXiv.1712.01208Kipf A., Marcus R., van Renen A., Stoian M., Kemper A., Kraska T., Neumann T. RadixSpline: A Single-Pass Learned Index // Proceedings of the Third International Workshop on Exploiting Artifi cial Intelligence Techniques for Data Management (aiDM ‘20). 2020. Art. No. 5. P. 1–5. DOI: 10.1145/3401071.3401659.Kipf A., Marcus R., van Renen A., Stoian M., Kemper A., Kraska T., Neumann T. RadixSpline: A Single-Pass Learned Index // Proceedings of the Third International Workshop on Exploiting Artifi cial Intelligence Techniques for Data Management (aiDM ‘20). 2020. Art. No. 5. P. 1–5. DOI: 10.1145/3401071.3401659.Neumann T., Michel S. Smooth Interpolating Histograms with Error Guarantees // Proceedings of the 11th International Conference on Extending Database Technology (EDBT ‘08). Cardiff , UK, 2008. P. 42–53. DOI: 10.1007/978-3-540-70504-8-12.Neumann T., Michel S. Smooth Interpolating Histograms with Error Guarantees // Proceedings of the 11th International Conference on Extending Database Technology (EDBT ‘08). Cardiff , UK, 2008. P. 42–53. DOI: 10.1007/978-3-540-70504-8-12.MovieLens32M Dataset [Электронный ресурс] / URL: GroupLens Research (дата обращения: 10.12.2024).MovieLens32M Dataset [Электронный ресурс] / URL: GroupLens Research (дата обращения: 10.12.2024).Index Block Format [Электронный ресурс] // RocksDB Wiki. – URL: https://github.com/facebook/rocksdb/wiki/Index-Block-Format (дата обращения: 10.08.2024).Index Block Format [Электронный ресурс] // RocksDB Wiki. – URL: https://github.com/facebook/rocksdb/wiki/Index-Block-Format (дата обращения: 10.08.2024).RocksDB: A Persistent Key-Value Store [Электронный ресурс] / Meta Open Source. URL: https://github.com/facebook/rocksdb (дата обращения: 10.08.2024).RocksDB: A Persistent Key-Value Store [Электронный ресурс] / Meta Open Source. URL: https://github.com/facebook/rocksdb (дата обращения: 10.08.2024).O’Neil P. The Log-Structured Merge-Tree (LSM-Tree) // Acta Informatica. 1996. Vol. 33. No. 4. P. 351–385. DOI: 10.1007/s002360050048.O’Neil P. The Log-Structured Merge-Tree (LSM-Tree) // Acta Informatica. 1996. Vol. 33. No. 4. P. 351–385. DOI: 10.1007/s002360050048.Marcus R., Kipf A., van Renen A., Stoian M., Misra S., Kemper A., Neumann T., Kraska T. Benchmarking Learned Indexes // Proceedings of the VLDB Endowment (PVLDB). 2021. Vol. 14. No. 1. P. 1–13. DOI: 10.14778/3421424.3421425.Marcus R., Kipf A., van Renen A., Stoian M., Misra S., Kemper A., Neumann T., Kraska T. Benchmarking Learned Indexes // Proceedings of the VLDB Endowment (PVLDB). 2021. Vol. 14. No. 1. P. 1–13. DOI: 10.14778/3421424.3421425.Li Z., Chan T. N., Yiu M. L., Jensen C. S. A Survey of Learned Indexes for the Multi-dimensional Space // arXiv:2403.06456 [cs.DB]. 2024. DOI: 10.48550/arXiv.2403.06456Li Z., Chan T. N., Yiu M. L., Jensen C. S. A Survey of Learned Indexes for the Multi-dimensional Space // arXiv:2403.06456 [cs.DB]. 2024. DOI: 10.48550/arXiv.2403.06456Ferragina P., Vinciguerra G. A Critical Analysis of Recursive Model Indexes // arXiv:2106.16166 [cs.DB]. 2021. DOI: 10.48550/arXiv.2106.16166Ferragina P., Vinciguerra G. A Critical Analysis of Recursive Model Indexes // arXiv:2106.16166 [cs.DB]. 2021. DOI: 10.48550/arXiv.2106.16166Ding J., Minhas U. F., Yu J., Wang C., Li Y., Zhang H., Chandramouli B., Gehrke J., Kossmann D., Lomet D., Kraska T. Towards Practical Learned Indexing (Extended Abstracts) // arXiv:2108.05117 [cs.DB]. 2021. DOI: 10.48550/arXiv.2108.05117Ding J., Minhas U. F., Yu J., Wang C., Li Y., Zhang H., Chandramouli B., Gehrke J., Kossmann D., Lomet D., Kraska T. Towards Practical Learned Indexing (Extended Abstracts) // arXiv:2108.05117 [cs.DB]. 2021. DOI: 10.48550/arXiv.2108.05117Wu J., Zhang Y., Chen S., Wang J., Chen Y., Xing C. LSI: A Learned Secondary Index Structure // arXiv:2205.05769 [cs.DB]. 2022. DOI: 10.48550/arXiv.2205.05769Wu J., Zhang Y., Chen S., Wang J., Chen Y., Xing C. LSI: A Learned Secondary Index Structure // arXiv:2205.05769 [cs.DB]. 2022. DOI: 10.48550/arXiv.2205.05769Hadian A., Heinis T. Shift-Table: A Low-Latency Learned Index for Range Queries using Model Correction // arXiv:2103.13160 [cs.DB]. 2021. DOI: 10.48550/arXiv.2103.13160Hadian A., Heinis T. Shift-Table: A Low-Latency Learned Index for Range Queries using Model Correction // arXiv:2103.13160 [cs.DB]. 2021. DOI: 10.48550/arXiv.2103.13160Vaidya K., Kraska T. Partitioned Learned Bloom Filter // Proceedings of the VLDB Endowment. 2020. Vol. 13. No. 12. P. 3298–3311. DOI: 10.14778/3415478.3415545Vaidya K., Kraska T. Partitioned Learned Bloom Filter // Proceedings of the VLDB Endowment. 2020. Vol. 13. No. 12. P. 3298–3311. DOI: 10.14778/3415478.3415545Spector B., Marcus R., van Renen A., Stoian M., Kemper A., Kraska T., Neumann T. Bounding the Last Mile: Effi cient Learned String Indexing // arXiv:2111.14905 [cs.DB]. 2021. DOI: 10.48550/arXiv.2111.14905Spector B., Marcus R., van Renen A., Stoian M., Kemper A., Kraska T., Neumann T. Bounding the Last Mile: Effi cient Learned String Indexing // arXiv:2111.14905 [cs.DB]. 2021. DOI: 10.48550/arXiv.2111.14905Crotty A. Hist-Tree: Those Who Ignore It Are Doomed to Learn [Электронный ресурс] // CIDR 2021. URL: https://cs.brown.edu/people/acrotty/pubs/cidr2021-paper20.pdf (дата обращения: 02.02.2025).Crotty A. Hist-Tree: Those Who Ignore It Are Doomed to Learn [Электронный ресурс] // CIDR 2021. URL: https://cs.brown.edu/people/acrotty/pubs/cidr2021-paper20.pdf (дата обращения: 02.02.2025).

The authors declare that there are no conflicts of interest present.