ALEX: An Updatable Adaptive Learned Index

By Jialin Ding, U. F. Minhas, Hantian Zhang, Yinan Li, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David B. Lomet. SIGMOD Conference, 2019

398 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/6b2cae9d709731c7ab41400c3286e37820252364

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

1. Qinbin Li
2. Bingsheng He
3. Quan Chen
4. Yiqun Diao
5. Bo Du
6. Mang Ye

In Computer Networks and Communications

1. Bingsheng He
2. Qinbin Li

In Signal Processing

1. Bingsheng He

Citations in the corpus

• Federated Learning on Non-IID Data Silos: An Experimental Study (2021, background): “In data management systems, we have witnessed some promising advancement with leveraging machine learning services, such as learned index structures [9, 46] and learned cost estimation [21, 47].”