PaperlayerView exact revision on arXiv

Source-linked AI summary

ALEX: An Updatable Adaptive Learned Index

Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David Lomet, Tim Kraska

arXiv:1905.08898v2cs.DBcs.DScs.LG

TL;DR

The original Learned Index improves lookup performance and memory footprint but is limited to static, read-only data, leaving dynamic workloads insufficiently supported. ALEX combines learned-index models with adaptive storage and indexing techniques for updates and changing distributions. It beats the Learned Index on read-only workloads and B+Trees across read-write workloads while using substantially smaller indexes.

  • Problem

    The Learned Index cannot support modifications such as inserts, updates, or deletes, despite dynamic read-write workloads being common in practice.

  • Method

    ALEX combines Gapped Arrays, model-based insertion, exponential search, and an adaptive RMI driven by workload-aware cost models.

  • Results

    ALEX beats B+Trees across the read-write workload spectrum and beats the Learned Index by up to 2.2× on read-only workloads.

  • Takeaways & Limitations

    ALEX extends learned-index ideas to dynamic workloads while maintaining high performance and low memory footprint.

  • Takeaways & Limitations

    Out-of-bounds inserts can cause poor performance because the affected boundary data node cannot split the out-of-bounds key space directly.

Abstract

from arXiv · show

Recent work on "learned indexes" has changed the way we look at the decades-old field of DBMS indexing. The key idea is that indexes can be thought of as "models" that predict the position of a key in a dataset. Indexes can, thus, be learned. The original work by Kraska et al. shows that a learned index beats a B+Tree by a factor of up to three in search time and by an order of magnitude in memory footprint. However, it is limited to static, read-only workloads. In this paper, we present a new learned index called ALEX which addresses practical issues that arise when implementing learned indexes for workloads that contain a mix of point lookups, short range queries, inserts, updates, and deletes. ALEX effectively combines the core insights from learned indexes with proven storage and indexing techniques to achieve high performance and low memory footprint. On read-only workloads, ALEX beats the learned index from Kraska et al. by up to 2.2X on performance with up to 15X smaller index size. Across the spectrum of read-write workloads, ALEX beats B+Trees by up to 4.1X while never performing worse, with up to 2000X smaller index size. We believe ALEX presents a key step towards making learned indexes practical for a broader class of database workloads with dynamic updates.

1 INTRODUCTION

Learned indexes replace conventional index navigation with models that predict key locations, but the original Learned Index supports only static, read-only data. ALEX addresses dynamic workloads by combining learned-index ideas with adaptive storage, search, and retraining strategies.

  • Learned indexes: The Learned Index uses a hierarchy of machine-learning models to predict child models and key locations in a densely packed array.Models are trained from the data and exploit its distribution to make sufficiently accurate location predictions.
  • ALEX’s scope: Dynamic workloads require support for point lookups, short range queries, inserts, updates, deletes, and bulk loading.These operations are common in OLTP workloads and are supported by B+Trees.
  • Motivation: Sorted densely packed arrays make writes expensive because insertions can shift records, while changing distributions can degrade model accuracy and require retraining.These limitations motivate a different storage layout and adaptive model maintenance.
  • ALEX’s approach: ALEX combines model-optimized tree storage, Gapped Arrays, model-based inserts, exponential search, adaptive expansion, node splitting, and selective retraining.Its retraining policies use workload-aware cost models and avoid hand-tuning parameters for each dataset or workload.
  • Results: On read-only workloads, ALEX beats the Learned Index by up to 2.2× in performance and uses up to 15× smaller index size.Across read-write workloads, it beats B+Trees by up to 4.1× while never performing worse, with up to 2000× smaller index size.

2 BACKGROUND

Learned indexes use data-trained models to predict positions in sorted data, improving lookup speed and memory use over B+Trees on static workloads. Their central limitation is the lack of efficient modifications, which ALEX is designed to address.

  • B+Trees: B+Trees are height-balanced range indexes that store sorted data or data pointers at the leaf level.They support range queries and dynamic operations across varied data sizes and distributions.
  • B+Tree lookup: B+Tree lookups traverse internal nodes and then search within a leaf, potentially causing many comparisons and cache misses.The leaf search is typically binary search.
  • Learned Index: Learned indexes replace index components with models that learn the cumulative distribution function of the input data.A recursive model index uses higher-level models to select lower-level models, whose leaf models predict key positions.
  • Learned Index: A leaf model’s predicted position can be corrected by local search, which the original Learned Index performs within stored error bounds.This local search can be faster than searching the entire array when predictions are accurate.
  • Learned Index: Learned Index models trade accuracy against complexity, using potentially different model types at different RMI levels.Linear regression is favored at non-root levels for its simplicity and computation speed.
  • Comparison: The Learned Index can use an order of magnitude less memory than internal B+Tree nodes while improving lookup performance by up to three times.Its compact models replace many internal keys and pointers.
  • Limitation: The Learned Index does not support modifications; a naive insertion strategy has linear time complexity because it rebuilds and shifts the array and updates models.Delta-indexes are suggested as a separate way to handle inserts, while ALEX presents an alternative data structure.

3 ALEX OVERVIEW

ALEX is an in-memory, updatable learned index that combines model-based prediction with flexible storage and runtime adaptation. Its design uses Gapped Arrays, exponential search, model-based insertion, and a dynamically adjusted RMI to support changing workloads.

  • Design overview: ALEX uses Gapped Array leaf layouts and adaptive RMI structures to support dynamic updates while targeting efficient lookup and insert performance.Its cost models use simple workload statistics to initialize and adapt the RMI at runtime.
  • Design goals: ALEX is an in-memory, updatable learned index with goals of competitive insert time, faster lookups, and smaller index storage than B+Trees and Learned Indexes.Its leaf-level data storage is intended to remain comparable to a dynamic B+Tree.
  • Data nodes: ALEX stores each leaf in a data node, allowing nodes to expand and split flexibly and limiting shifts during insertion.Strategically placed gaps support faster insertion and lookup than concentrating free space at the array end.
  • Search: ALEX uses exponential search from the model’s predicted position to correct leaf-level mispredictions.The paper reports that this is faster than binary search within model-provided error bounds and removes the need to store those bounds.
  • Insertion: Model-based insertion places keys where models predict they belong, reducing prediction errors during later searches.This differs from the Learned Index, which builds an RMI over records without changing their array positions.
  • Adaptation: ALEX dynamically adjusts the RMI’s shape and height according to workload conditions rather than using a fixed structure.The structure is automatically bulk-loaded and adjusted with a cost model, without per-workload parameter retuning.
  • Gapped Arrays: Gapped Arrays distribute extra space between elements, while a bitmap tracks occupied locations and gaps with low space overhead.Gaps are filled with nearby keys to help preserve exponential-search performance.
  • Internal nodes: ALEX internal nodes use models to compute which child pointer to follow, unlike B+Tree internal nodes that navigate through stored keys and pointers.They provide flexible key-space partitioning rather than simply producing equally sized data nodes.

4 ALEX ALGORITHMS

ALEX handles lookups, inserts, deletes, and structural adaptation through model-guided data nodes, density limits, cost models, and multiple expansion or split mechanisms.

  • Lookup and insertion: ALEX traverses the RMI to a data node, predicts key positions with its model, and uses exponential search when prediction is inaccurate.
  • Lookup and insertion: Model-based insertion places new keys near predicted positions, using gaps directly or shifting elements toward the closest gap when necessary.The Gapped Array achieves O(logn) insertion time with high probability.
  • Node growth: When nodes need more space, ALEX chooses expansion or splitting through cost models based on exponential-search iterations and insertion shifts.Splitting can occur sideways or downward; splitting down creates two child data nodes from one data node.
  • Node growth: ALEX triggers structural changes before 100% fullness using lower and upper density limits, defaulting to dl = 0.6 and du = 0.8.These settings target average data storage utilization of 0.7, similar to B+Tree.
  • Cost models: ALEX compares empirical and expected node costs; if empirical cost exceeds expected cost by more than 50%, it retrains, expands, or splits using the lowest expected-cost action.Otherwise, it expands when possible and scales the model instead of retraining.
  • Cost deviation: Changing insertion distributions can make models inaccurate, create contiguous gap-free regions, and cause worst-case O(n) shifting during insertion.Performance may also degrade from random noise as nodes grow or from changing lookup access patterns.
  • Out-of-bounds inserts: Out-of-bounds inserts initially target an extreme data node, so repeated append-like inserts can perform poorly because that node cannot split the out-of-bounds key space.

5 ANALYSIS OF ALEX

ALEX’s analysis bounds RMI depth by key-distribution density and characterizes lookup and insertion costs under its node-size and density constraints. The analysis also distinguishes performance-oriented depth bounds from worst-case guarantees and identifies a space-time trade-off for search.

  • RMI depth: ⌈log_m p⌉ bounds RMI depth, and maximal depth can be maintained under inserts.Here, p is the minimum number of equal-width key-space partitions whose densest partition contains no more than m d_u keys.
  • RMI depth: RMI depth is bounded by the density of the densest key-space subregion, unlike B+Tree depth, which depends on the number of keys.The same bound can apply to a subspace corresponding to an RMI subtree.
  • Lookup and insertion complexity: Lookups and inserts reach a leaf in ⌈log_m p⌉ time; lookup then ranges from O(1) with perfect prediction to worst-case O(log m) exponential search.Exponential-search cost can be reduced through a space-time trade-off.
  • Lookup and insertion complexity: O(log m) shifts per insert are expected with high probability in a non-full Gapped Array, although the worst case is O(m).A correct predicted position that is already a gap yields O(1) insertion and enables a later direct-hit model-based lookup in O(1).
  • Lookup and insertion complexity: O(m⌈log_m p⌉) is the worst-case cost of inserting into a full node when sideways splitting propagates through ancestors.Expansion and downward splitting each cost O(m), while propagated sideways splitting can involve every internal node on the path.

6 EVALUATION

ALEX consistently outperforms established indexes across read-only, read-write, range, scaling, and distribution-shift workloads, while retaining a substantially smaller index footprint. Its advantages arise from combining adaptive modeling with Gapped Arrays, though write-heavy and very long-range scans narrow the gap.

  • 6.2 Overall Results: 4.0× higher throughput and 2000× smaller index size than B+Tree are achieved by ALEX on read-write workloads.ALEX also reaches 2.7× higher throughput and 475× smaller index size than Model B+Tree, and 36,000× smaller index size than ART.
  • 6.2 Overall Results: 4.1× higher throughput and 800× smaller index size than B+Tree are achieved by ALEX on read-only workloads.Against the Learned Index, ALEX reaches 2.2× higher throughput and 15× smaller index size.
  • 6.2.1 Read-only Workloads: ALEX’s index size depends on modeling difficulty, using fewer adaptively allocated models than the Learned Index while maintaining smaller index size at similar throughput.Model-based inserts improve predictive accuracy, while adaptive allocation avoids redundant models.
  • 6.2.2 Read-Write Workloads: ALEX’s relative advantage decreases as workloads become more write-heavy because node splitting and expansion require copying records.This cost is especially important for large payloads; unclustered payloads could reduce copying but would hurt scan performance.
  • 6.2.2 Read-Write Workloads: 2.27× higher throughput and 1000× smaller index size than B+Tree are achieved by ALEX on short-range workloads.The throughput advantage decreases as scanning dominates query time, but ALEX remains faster than the compared B+Tree configurations in the reported workload.
  • 6.2.2 Read-Write Workloads: ALEX scales to larger datasets and distribution shifts, maintaining up to 3.2× higher throughput than B+Tree under disjoint-key inserts.The evaluation also reports robustness to sequential sorted inserts and efficient bulk loading, reaching lower total time than other indexes after 3 million inserts in one workload.
  • 6.3 Drilldown into ALEX Design Trade-offs: ALEX maintains low prediction errors after initialization and after 20 million inserts, supporting efficient local search around predicted positions.Model-based inserts often produce no prediction error and remove the Learned Index’s long error tail.

7 RELATED WORK

Related work improves indexes through learned models, alternative node structures, and hardware-aware layouts. ALEX differs by combining model-based key-space partitioning and insertion with adaptive cost-driven restructuring for dynamic workloads.

  • Learned Index Structures: Learned Index models use the data’s cumulative distribution function to predict key locations in a sorted array.This approach optimizes the index for a specific data distribution.
  • Learned Index Structures: FITing-tree and BF-tree replace B+Tree leaf nodes with linear models or bloom filters while retaining search and update performance.These methods target index compression through alternative leaf data structures.
  • Learned Index Structures: ALEX differs by using models to split key space, accurate linear models for larger nodes, model-based insertion, and cost models that adjust to dynamic workloads.Unlike approaches requiring search through internal model levels, ALEX searches only after reaching the leaf level.
  • Memory Optimized Indexes: Memory-optimized indexes exploit CPU cache behavior, multicore execution, SIMD, and prefetching to improve in-memory tree performance.CSS-trees eliminate pointers in index nodes, while CSB+-trees extend cache-aware layouts to incremental updates.
  • ML in other DB components: Machine learning has also been applied to cardinality estimation, query optimization, workload forecasting, multidimensional indexing, and data partitioning.SageDB extends this direction by envisioning learned components throughout a database system.

8 CONCLUSION

ALEX combines learned-index insights with established storage and indexing techniques to create an updatable learned index for dynamic workloads. The paper reports consistent advantages over B+Trees across read-write workloads and over the Learned Index on read-only workloads, while identifying theoretical, storage, and concurrency-control directions for future work.

  • 8 CONCLUSION: ALEX combines Gapped Array nodes, model-based inserts, exponential search, and an adaptive RMI driven by simple cost models.The design targets high performance and low memory footprint on dynamic workloads.
  • 8 CONCLUSION: ALEX consistently beats B+Tree across the read-write workload spectrum and beats the Learned Index by up to 2.2× on read-only workloads.The conclusion presents these results as evidence for the approach’s effectiveness across dynamic and static workloads.
  • 8 CONCLUSION: Future work includes theoretical analysis of ALEX performance, secondary storage for larger-than-memory datasets, and concurrency-control techniques tailored to ALEX.These are stated as open research directions rather than resolved capabilities.

A Extended Bulk Loading Evaluation

ALEX’s bulk-loading optimizations reduce its loading overhead substantially, while their effects on subsequent workload throughput differ. AMC is broadly beneficial, whereas ACC can hurt write-heavy performance because shift costs are difficult to estimate.

  • Bulk-loading performance: ALEX with both optimizations takes 50% more time than B+Tree on average to bulk load 100 million keys, with a worst case of 2× slower.Without optimizations, ALEX takes 3.6× more time on average; AMC alone reduces this to 2.6×.
  • Post-loading throughput: AMC has negligible impact on read-heavy and write-heavy throughput after bulk loading.The optimization improves bulk loading without noticeably changing subsequent workload throughput.
  • Post-loading throughput: ACC decreases write-heavy throughput by up to 9.6% but has negligible impact on read-heavy throughput.The decrease occurs because average shifts per insert are difficult to estimate accurately.
  • Recommendations: AMC should always be used for faster bulk loading, whereas ACC should be used only when faster bulk loading justifies possible write-throughput loss.The authors attribute ACC’s write-heavy penalty to underestimated shift costs.
  • Optimization mechanisms: AMC progressively doubles systematic-sample sizes and recomputes a linear model, reusing prior samples without redundant work.In the worst case, AMC takes no more time than computing one model from all keys, ignoring minor overheads and locality effects.
  • Optimization mechanisms: ACC extrapolates node cost from progressively larger samples, unlike AMC, which directly estimates model parameters.ACC must recompute each sample’s cost because placement in the Gapped Array depends on sampled keys, and cost grows with node size.

B Extreme Distribution Shif Evaluation

ALEX remains competitive when keys arrive under radically changing distributions, though adaptation reduces throughput and the initial bulk-loaded structure affects how readily it adapts.

  • Results: ALEX continues to outperform other indexes without distribution shift and still outperforms them under four distribution-shift variants.The experiment combines four datasets into 200 million keys and varies bulk-loading and insertion order.
  • Results: Distribution shifts lower ALEX throughput because the index spends extra time restructuring itself to adapt.The workload uses 50% point lookups and 50% inserts while inserting keys from changing distributions.
  • Results: Bulk loading from a complex distribution yields throughput similar to no shift, whereas bulk loading from a simple distribution causes throughput to suffer.Complex initial structures are deeper and adapt with less overhead; simple initial structures are shallower and must add nodes later.
  • Adaptation mechanisms: ALEX checks nodes periodically for cost deviation and forces splits when shifts per insert become extremely high.These changes are intended to accelerate adaptation to radically changing key distributions.

C Extended Range Qery Evaluation

ALEX maintains an advantage over fixed-page-size B+Trees for longer range scans and mixed workloads, while its cost model balances local operation costs with traversal and index-size effects.

  • Range queries: ALEX maintains its advantage over fixed-page-size B+Trees across all datasets for longer range scans.Retuning B+Tree page size can improve range queries but reduces point-lookup and insert performance.
  • Mixed workload: ALEX maintains its performance advantage in a workload with 5% inserts, 85% point lookups, and 10% short range queries.Range queries have a maximum scan length of 100; ART is excluded because its implementation lacks range-query support.
  • Cost model: Intra-node cost represents average point-lookup or insert time, while TraverseToLeaf cost represents traversal time from the root to a data node.The cost model separately captures work within a data node and pointer traversal through the RMI.
  • Cost model: Each traversal includes a fixed cost associated with total RMI size because larger RMIs worsen cache locality.The depth of a data node is measured by the number of pointer chases needed to reach it.
  • Cost model: The cost of ALEX combines intra-node operation cost and root-to-data-node traversal cost, normalized by the number of keys in each data node.The normalization uses key count as a proxy for each node’s contribution to average query time.
  • Scope: The simple cost model performed well in evaluation, but a more complex model might better reflect true runtime.The authors leave that refinement as future work.

D.2 Cost Computation Performance.

ALEX’s cost-computation overhead grows as writes become more frequent but remains a small fraction of workload time, with higher fractions for datasets whose nodes fill quickly or are larger.

  • Mechanism: ALEX computes costs when nodes become full to compare expected and empirical intra-node costs, then uses cost-based decisions when deviation is detected.Maintained statistics make the comparison low overhead, requiring three multiplications and an addition.
  • Overhead: Cost computation occupies an increasing fraction of workload time as the write fraction increases, yet remains small even on write-only workloads.Read-only workloads spend no time on cost-based decisions because nodes never become full.
  • Dataset differences: YCSB has the highest cost-computation fraction because its nodes are larger and its lookups and inserts make nodes fill quickly.Longlat has the next-highest fraction because its data nodes become full frequently.

E Comparison of Gapped Array and PMA

ALEX chooses Gapped Arrays over PMAs because strategically placed gaps preserve model-based search performance while retaining efficient dynamic insertion behavior.

  • PMA uniformly spaces gaps and rebalances local array regions when density bounds are violated.
  • Under random inserts from a static distribution, PMA inserts elements in O(logn) time, matching the Gapped Array.
  • ALEX does not use PMA storage because PMA rebalancing moves keys farther from predicted locations, worsening search performance.
  • ALEX already obtains PMA’s main benefit for non-static or complex distributions through its adaptive RMI structure.
  • ALEX data nodes built on Gapped Arrays consistently outperform those built on PMAs in the evaluation.

F Analysis of Model-based Search

The analysis characterizes how Gapped Array space expansion affects model-based direct hits, identifying bounds that connect spacing, prediction accuracy, and search time.

  • If every distinct key pair has predicted locations separated by at least one, all keys receive unique predicted locations.
  • c =1 uses optimal space, while c ≥ cmax corresponds to optimal search time when cache misses are ignored.
  • Theorem 2 bounds the number of keys placed at predicted locations from above.
  • When f(i)>1, the proof establishes that the corresponding key cannot be placed at its rounded predicted location, creating a model miss.
  • The number of direct hits is at most 2 plus the count of indices satisfying yi+2−yi >1.
  • The upper bound applies to the Learned Index with c =1 and explains why Gapped Arrays can substantially reduce search time.
  • Theorem 3 guarantees at least l +1 keys at predicted locations, where l is the longest initial run with δi ≥1.
Loading 1905.08898v2…