Source-linked AI summary
The Case for Learned Index Structures
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, Neoklis Polyzotis
TL;DR
Traditional indexes are general-purpose structures that do not exploit recurring data patterns, while specialized alternatives can require too much engineering effort. This paper explores learned models, including neural networks, as components or replacements for traditional indexes, reporting significant benefits and identifying learned indexes as a fruitful research direction.
Problem
Traditional indexes assume nothing about data distribution, while manually building specialized structures for recurring patterns usually requires too much engineering effort.
Method
The paper explores learned models that reflect data patterns to automatically synthesize specialized indexes, including hierarchical regression models and neural-network-based existence indexes.
Results
Up to 80% storage was saved with only a 13ns latency increase compared to random hashing in the reported hash-index result.
Takeaways & Limitations
Learned indexes can provide significant benefits over state-of-the-art indexes and represent a fruitful direction for future research.
Takeaways & Limitations
The learned Bloom-filter setup assumes future queries follow the same distribution as observable historical queries.
Abstract
from arXiv · showhide
Indexes are models: a B-Tree-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 learned indexes. The key idea is that a model can learn the sort order or structure of lookup keys and use this signal to effectively predict the position or existence of records. 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 by using neural nets we are able to outperform cache-optimized B-Trees by up to 70% in speed while saving an order-of-magnitude in memory over several real-world data sets. More importantly though, 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 just provides a glimpse of what might be possible.
1 Introduction
The paper proposes learned indexes as models that exploit data distributions to automatically synthesize specialized structures, while complementing rather than completely replacing traditional indexes. It explores neural and other ML models across index types and reports promising results for read-only analytical workloads, alongside substantial open challenges.
- Motivation: Traditional indexes remain general-purpose structures that do not exploit common data-distribution patterns.For continuous integer keys, using the key as an offset can reduce lookup from O(log n) to O(1) and index memory from O(n) to O(1).
- Motivation: Learned indexes use machine learning to reflect data patterns and automatically synthesize specialized index structures with low engineering cost.The motivation is that real-world data rarely follow perfectly known patterns, while manually engineering specialized solutions is expensive.
- Research Direction: The proposal targets index structures from B-Trees to Bloom filters and argues that neural-network obstacles in guarantees and computation may be manageable, especially on future hardware.The paper points to SIMD, GPUs, and TPUs as possible ways to reduce the practical cost of neural computation.
- Indexes as Models: The paper frames B-Trees as position-prediction models and Bloom filters as binary classifiers, making ML-based replacements or enhancements conceptually possible.These models must still address subtle semantic differences, such as Bloom filters allowing false positives but not false negatives.
- Scope: The authors explicitly position learned indexes as complementary to traditional indexes rather than advocating their complete replacement.The paper evaluates the approach on synthetic and real-world read-only analytical workloads but identifies write-heavy workloads as an open challenge.
2 Range Index
The range-index section interprets B-Trees as models that predict positions in sorted arrays and develops learned alternatives based on data distributions. These alternatives can offer constant-time behavior in favorable cases, but must address accuracy, caching, updates, and deployment assumptions.
- 2 Range Index: B-Trees map lookup keys to positions in sorted arrays, preserving efficient range requests and providing a model-based view of range indexing.The predicted position identifies the first record whose key is equal to or greater than the lookup key.
- 2 Range Index: A sorted array permits prediction errors to be corrected by local search, allowing regression models, including neural networks, to replace B-Trees.The authors note that strong min- and max-error guarantees are not required when local search can correct the prediction.
- 2 Range Index: A simple linear model can transform B-Tree lookup cost from O(log n) into a constant operation when the key distribution permits exact position prediction.The example uses 1M unique keys whose values range from 1M to 2M.
- Scope and Challenges: The approach is mainly evaluated under simplified assumptions of sorted, dense, in-memory arrays, leaving broader storage and update settings as challenges.B-Trees additionally offer bounded insert and lookup costs, cache efficiency, and support for non-contiguous pages.
- 2.2 Range Index Models are CDF Models: The learned-index formulation approximates the cumulative distribution function: p = F(Key) * N, where F(Key) estimates the probability that a key is at most the lookup key.N denotes the total number of keys, and p is the predicted position.
- 2.3 A First, Naïve Learned Index: Neural models can approximate a CDF efficiently at a coarse level but may incur high CPU and space costs for precise individual-record localization.Standard neural networks also require all weights for each prediction, unlike cache-efficient B-Trees.
3 The RM-Index
The RM-Index combines recursive models, automated index synthesis, and error-aware search or hybrid fallback to approximate learned index structures. Evaluations report strong speed, memory, and training results, while emphasizing that learned indexes are not universally optimal.
- Framework: The framework develops LIF, recursive-model indexes, and standard-error-based search strategies to explore learned replacements or optimizations for traditional indexes.LIF automatically generates, optimizes, and tests index configurations, while avoiding TensorFlow during inference.
- Recursive Model Index: Recursive-model indexes hierarchically route each key through stages of models until a final model predicts its position.Each stage narrows the relevant key-space region, reducing the accuracy burden on later models.
- Recursive Model Index: The staged architecture separates model size from execution cost and divides the data into sub-ranges to improve last-mile accuracy with fewer operations.It also avoids a search process between stages by directly using one model's output to select the next model.
- Hybrid Indexes: Hybrid indexes replace models whose maximum absolute error exceeds a threshold with B-Trees, bounding worst-case performance by B-Tree performance.This fallback can produce an almost entirely B-Tree index for extremely difficult data distributions.
- Evaluation: Learned indexes are up to 1.5 −3× faster and up to two orders-of-magnitude smaller than B-Trees in the reported configurations.The comparison uses lookup time, index size, and model or traversal execution time as primary metrics.
- Limitations: The paper cautions that learned indexes will not always be best in size or speed, and that string-key optimization requires substantial future research.Suggested directions include improved tokenization, suffix-tree combinations, and more complex model architectures.
- Evaluation: For strings, learned-index speedups over B-Trees are less prominent because model execution and string searching are comparatively expensive.Biased quaternary search reduces one reported neural-network search time from 1102ns to 658ns, and hybrid indexes can improve performance.
4 Point Index
The paper applies learned models to Hash-maps by learning key-distribution structure to reduce conflicts, while emphasizing architecture-dependent trade-offs in latency, storage, and performance.
- Learned Hash-map: Learned hash functions use the empirical CDF to map keys into Hash-map slots, potentially eliminating conflicts when the CDF is learned perfectly.The mapping scales the CDF by the target table size M: h(K) = F(K) ∗ M.
- Learned Hash-map: Hash-map benefits depend on how accurately the model represents the observed CDF and how inserts, look-ups, and conflicts are handled.The paper identifies Hash-map architecture and model accuracy as key determinants of the benefit over uniformly distributing hash functions.
- Results: 77% fewer conflicts were achieved across the evaluated integer datasets at an execution cost of approximately 25–40ns.The comparison used 2-stage RMI models against a MurmurHash3-like baseline with equal slots and records.
- Trade-offs: For very small payloads, Cuckoo-hashing with standard Hash-maps probably remains preferable, whereas larger payloads and distributed settings favor learned hash functions.In distributed RDMA look-ups, each conflict can require an additional microsecond-scale request, making model execution comparatively negligible.
5 Existence Index
Learned existence indexes combine a probabilistic classifier with an overflow Bloom filter to reduce memory while preserving zero false negatives under the paper’s evaluation assumptions.
- Design: Existence indexes must distinguish keys from non-keys, unlike point indexes, whose hash functions primarily seek few collisions among keys.For existence indexes, the desired function creates many within-class collisions but few key/non-key collisions.
- Assumptions: The evaluation assumes future non-key queries follow the distribution of observable historical queries.The paper notes alternatives for distribution shift, including random non-keys, generated negatives, importance weighting, and adversarial training.
- Design: The learned Bloom filter trains a sigmoid-output classifier to estimate whether an input is a database key.The model is trained on positive keys and negative non-keys using binary classification and log loss.
- Design: An overflow Bloom filter stores classifier false negatives, so queries accepted by the model pass while rejected queries are checked for guaranteed membership coverage.The threshold τ determines the model decision; keys below it populate the overflow filter.
- Results: 36% less memory was used at a 1% FPR, while a 0.1% overall FPR reduced memory by 15% in the phishing-URL experiment.The 1% configuration used 1.31MB versus 2.04MB; the 0.1% configuration used 2.59MB versus 3.06MB.
- Results: More accurate learned models improve Bloom-filter savings, and additional application features can improve accuracy while retaining zero false negatives.The paper illustrates this possibility with WHOIS and IP information for phishing-page prediction.
6 Related Work
Related work spans traditional index optimization, learned hashing, succinct structures, and model architectures, while learned indexes distinguish themselves by learning data distributions and replacing entire index structures.
- Traditional indexes: Hardware-conscious B-Tree variants and compression methods optimize existing indexes but do not learn from data distributions.The paper presents learned indexes as potentially complementary to these approaches.
- Closest precedents: A-Trees, BF-Trees, and interpolation search are closer precedents, but learned indexes propose replacing the entire index structure with learned models.The cited approaches reduce or reorganize parts of tree indexes rather than fully replacing them.
- Bloom filters: Learned existence indexes build on Bloom filters while adding classification models or models used as hash functions with different optimization goals.This perspective targets distribution-sensitive existence indexing rather than conventional Bloom-filter construction alone.
- Succinct structures: Learned indexes connect to succinct data structures but aim to predict element positions from underlying distributions rather than primarily encode entropy.The paper identifies this distinction as a potential source of higher compression.
- Open questions: Modeling the cumulative distribution function remains an open question for both range and point learned indexes.The paper identifies more effective CDF modeling as a direction for further investigation.
- Model architectures: The recursive model architecture separates model size from model computation, enabling more complex models without increasing execution cost.This connects the paper’s approach to mixture-of-experts architectures.
7 Conclusion and Future Work
The paper concludes that learned models can provide significant benefits over state-of-the-art indexes and identifies several directions for extending the approach.
- The paper treats learned indexes as a fruitful direction for future research rather than a complete replacement for traditional indexes.
- Future Work: Other model types and combinations with traditional data structures remain worth exploring beyond linear models and neural nets with mixture of experts.
- Future Work: Multi-dimensional learned indexes are proposed as a research direction because neural networks can capture complex high-dimensional relationships.
- Beyond Indexing: Learned models may also speed up sorting and joins, extending their use beyond indexing.
- GPU/TPUs: GPU/TPU invocation latency remains a challenge, although better CPU integration and request batching may amortize its 2-3 micro-seconds cost.
- Learned models have the potential to provide significant benefits over state-of-the-art indexes.
A Theoretical Analysis of Scaling Learned Range Indexes
The analysis frames learned range indexing as modeling the data’s cumulative distribution function and studies how prediction error scales with dataset size. Under this framing, constant-sized learned models have sub-linear position-error scaling, improving on constant-sized B-Trees.
- The analysis models the empirical cumulative distribution function ˆF_N(x) using a learned distribution model F(x).
- The theoretical setting assumes i.i.d. samples from a known distribution and analyzes error between the sampled empirical distribution and the model.
- Look-up time is tied to the position error between the model prediction NF(x) and the key position N ˆF_N(x).
- For a constant-sized model, average predicted-position error grows sub-linearly as O(N), improving over the linear scaling of a constant-sized B-Tree.
B Separated Chaining Hash-map
This experiment evaluates learned hash functions in a separate-chaining hash map against a MurmurHash3-like baseline across varying slot capacities. The model hash function achieves similar performance while using memory more efficiently on the reported map dataset.
- The experiment uses separate chaining, storing records directly in an array and linking only records involved in conflicts.
- The baseline is a MurmurHash3-like hash function, while the model-based hash map uses a two-stage RMI with 100k second-stage models and no hidden layers.
- The evaluation varies available hash-map slots from 75% to 125% of the number of data records.
- Figure 11 reports average lookup time, empty-slot space in GB, and space improvement relative to a randomized hash function.
- The model hash function has overall similar performance while using memory more efficiently than the random hash function.
- On the map dataset, the model hash function wastes 0.18GB in slots, an almost 80% reduction compared with a random hash function.
C Hash-Map Comparison Against Alternative Baselines
The paper compares learned hash functions with four alternative hash-map architectures and configurations. For 20-Byte records, learned in-place chaining provides better lookup performance than the evaluated cuckoo hash-map baseline.
- The comparison includes four alternative hash-map architectures and configurations.
- The baselines include an AVX-optimized Cuckoo Hash-map and a commercially used Cuckoo Hash-map.
- Learned in-place chaining: The learned in-place chained hash map uses a two-pass algorithm that places items with the learned function before separately chaining skipped conflicts.
- Learned in-place chaining: The learned hash function can affect performance through the number of conflicts, while utilization can reach 100% when inserts are not considered.
- For AVX Cuckoo Hash-maps, increasing payload size from 8 Byte to 20 Byte decreases performance by almost 40%.
- For the evaluated 20-Byte records, learned hash functions with in-place chaining provide better lookup performance than the Cuckoo Hash-map.
D Future Directions for Learned B-Trees
The paper focuses primarily on read-only, in-memory database indexes and sketches how learned index structures could be extended in future work.
- The main discussion assumes read-only, in-memory database systems.
D.1 Inserts and Updates
The paper examines how learned indexes might handle appends and middle inserts, while identifying generalization, distribution shifts, and guarantees as open issues.
- Inserts are divided into appends and middle inserts, such as updating a secondary customer-id index.
- Under future-pattern generalization, appending timestamped records updates the index in O(1) time without changing the model.
- Better last-mile predictions may trade off against generalization because they can indicate greater overfitting.
- Distribution changes and matching B-Tree O(log n) guarantees remain beyond the paper’s scope, although online learning is identified as a possible adaptation.
- A delta-index offers a simpler alternative by buffering inserts and periodically merging them, potentially with model retraining.
D.2 Paging
The paging discussion addresses the failure of continuous-block assumptions for disk-based indexes and outlines several ways to adapt learned indexes, while leaving further investigation necessary.
- Partitioning data into separate disk pages violates the continuous-block assumption underlying the learned CDF position formula.
- The RMI can be modified to partition regions with less overlap, potentially duplicating records accessed by multiple models.
- A translation table mapping first keys to disk positions can preserve the rest of the index structure, especially with very large pages.
- Predicted positions and minimum-maximum errors can reduce bytes read from large pages, potentially limiting page-size impact.
- More complex models might learn page pointers when filesystem block numbering is systematic.
- Disk-based learned indexes require more investigation despite reported space and speed benefits making them a promising future-work direction.
E Further Bloom filter Results
The paper evaluates a discretized learned Bloom-filter output used as an additional hash function and reports improved memory reductions at two target false-positive rates.
- The alternative learned Bloom filter discretizes classifier outputs and uses them as an additional hash function in a traditional Bloom filter.
- The construction maps each key through f(x) into one of m bitmap positions and combines the bitmap with a traditional Bloom filter.
- The overall false-positive rate is FPRm × FPRB, allowing the traditional Bloom filter size to be selected from the desired system rate.
- At p*=0.1%, m=1000000 yields a 2.21MB total size and a 27.4% memory reduction, versus 15% for the earlier approach.
- At p*=1%, the method yields a 1.19MB total size and a 41% memory reduction, versus 36% previously reported.
- Further analysis is needed because standard accuracy and calibration measures do not align with suitability as a hash function.