ALEX: An Updatable Adaptive Learned Index

Abstract

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.

References in corpus (4)

• Neo: A Learned Query Optimizer
• FITing-Tree: A Data-aware Index Structure
• Learning Multi-dimensional Indexes
• Qd-tree: Learning Data Layouts for Big Data Analytics

Cited by in corpus (11)

• Benchmarking Learned Indexes
• Qd-tree: Learning Data Layouts for Big Data Analytics
• The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning
• APEX: A High-Performance Learned Index on Persistent Memory
• LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves
• LearnedFTL: A Learning-Based Page-Level FTL for Reducing Double Reads in Flash-Based SSDs
• Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training
• Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform
• AirIndex: Versatile Index Tuning Through Data and Storage
• DeepMapping: Learned Data Mapping for Lossless Compression and Efficient Lookup
• LES3: Learning-based Exact Set Similarity Search