The Case for Learned Index Structures

By Tim Kraska, Alex Beutel, Ed H. Chi, Joseph Dean, Neoklis Polyzotis. SIGMOD Conference, 2017

1,261 citations recorded by the source corpus.

Indexes are models: a \btree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not. In this exploratory research paper, we start from this premise and posit that all existing index structures can be replaced with other types of models, including deep-learning models, which we term \em learned indexes. We theoretically analyze under which conditions learned indexes outperform traditional index structures and describe the main challenges in designing learned index structures. Our initial results show that our learned indexes can have significant advantages over traditional indexes. More importantly, we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work provides just a glimpse of what might be possible.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/0539535989147bc7033f4a34931c7b8e17f1c650

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Transformer Memory as a Differentiable Search Index (2022, background): “Notably, there been also prior work on learned indexes (Kraska et al., 2018; Abu-Libdeh et al., 2020) that train neural networks to learn B-Tree Indexes.”
A Deep Look into Neural Ranking Models for Information Retrieval (2019, background): “[130] recently proposed to look at indexes as models.”
Neo: A Learned Query Optimizer (2019, background): “SageDB [23, 24] laid out a vision towards building a new type of data processing system that makes heavy used of learned components.”
Learning to Optimize Join Queries With Deep Reinforcement Learning (2018, background): “Application of machine learning in database internals is still the subject of signicant debate this year and will continue to be a contentious question for years to come [11, 26, 32, 37].”
Distributed Hierarchical GPU Parameter Server for Massive Scale Deep Learning Ads Systems (2020, background): “Here we have 100 total parameters in this example—there are 10 11 parameters in real-world large-scale deep learning models. function (Kraska et al., 2018) to maximize the parameter co-occurrence.”
Secretaries with Advice (2020, background): “Examples range from building better data structures [22, 28], to improved competitive and approximation ratios for several online tasks [23, 24, 26, 29–31], to cases where advice has been used to speed-up algorithms [1, 5] or to reduce their space complexity [19].”
Learned Cardinalities: Estimating Correlated Joins with Deep Learning (2018, background): “Recent research therefore investigates ML for classical database problems like parameter tuning [2], query optimization [13, 23, 27], and even indexing [12].”
An anatomy for neural search engines (2019, methodology): “Interesting work on using machine learning models to build learned indices, in place of the traditional datastructures for in-memory indices like Redis, have also been proposed [Kraska et al., 2018].”
Improving Online Algorithms via ML Predictions (2024, background): “Another recent work is that of Kraska et al. [17] that empirically shows that better indexes can be built using machine learned models; it does not provide any provable guarantees for its methods.”
FLAML: A Fast and Lightweight AutoML Library (2019, background): “For example, classification or regression models have been explored for indexing (Kraska et al., 2018; Galakatos et al., 2019), cardinality and selectivity estimation (Kipf et al.”
Recommender Systems with Generative Retrieval (2023, methodology): “Figure 2: A high-level overview of the modeling approach used in TIGER.”
Algorithms with predictions (2020, background): “In parallel Kraska et al. (2018) showed that these endeavors are not simply theoretical, building a system that used machine learning to improve retrieval speed for index data structures.”
Conformer-Kernel with Query Term Independence for Document Retrieval (2020, background): “Finally, when the relevance of items are known, or a reliable proxy metric exists, machine learned policies [Kraska et al., 2018, Oosterhuis et al., 2018, Rosset et al., 2018] can also be effective for efficient search over indexes but these methods are not directly relevant to our current…”
ALEX: An Updatable Adaptive Learned Index (2019, methodology): “This difference, combined with the fact that Learned Index uses additional space per model to store error bounds, accounts for ALEX having 3000× smaller index size.”
Secretary and Online Matching Problems with Machine Learned Advice (2020, background): “Improving the performance of classical online algorithms with the help of machine learned predictions is a relatively new area that has gained a lot of attention in the last couple of years [24, 21, 36, 27, 30, 34, 17, 33, 32].”
Bao: Making Learned Query Optimization Practical (2020, background): “In the context of data management systems, machine learning techniques have been applied to a wide variety of problems too numerous to list here, including index structures [39], data matching [23], Size Queries WL Data Schema”