ALEX: Building an Updatable Learned Index for Databases

This episode unpacks ALEX, a 2020 paper from MIT, Microsoft Research, Arizona State, and Georgia Tech that reworks the "learned index" idea for real-world databases. It traces the lineage from Kraska et al.'s 2018 Learned Index, which used a hierarchy of regression models to predict a key's position in a sorted array but only worked on static, read-only data since any insert would break the model's predictions. The discussion explains how ALEX solves this with a Gapped Array that leaves deliberate empty slots for near-free inserts, plus a tree structure whose nodes can grow, shrink, split, or retrain their local models on the fly, letting it support inserts, updates, and deletes alongside lookups. The headline numbers — up to 4.1x the throughput of a B+Tree with an index up to 2000 times smaller — anchor a broader explanation of why B+Trees have dominated databases since the 1970s and what it takes for a learned alternative to finally handle OLTP-style workloads. Listeners interested in database internals or machine learning applied to systems problems will get a clear, building-block explanation of both the classic B+Tree and the model-based alternative trying to replace it.

Interactive Visualization: ALEX: Building an Updatable Learned Index for Databases

Sources:
1. 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, 2019
http://arxiv.org/abs/1905.08898
2. The Case for Learned Index Structures — Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, Neoklis Polyzotis, 2018
https://scholar.google.com/scholar?q=The+Case+for+Learned+Index+Structures
3. FITing-Tree: A Data-aware Index Structure — Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, Tim Kraska, 2019
https://scholar.google.com/scholar?q=FITing-Tree%3A+A+Data-aware+Index+Structure
4. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds — Paolo Ferragina, Giorgio Vinciguerra, 2020
https://scholar.google.com/scholar?q=The+PGM-index%3A+a+fully-dynamic+compressed+learned+index+with+provable+worst-case+bounds
5. Benchmarking Learned Indexes — Ryan Marcus, Andreas Kipf, Alexander van Renen, Mihail Stoian, Sanchit Misra, Alfons Kemper, Thomas Neumann, Tim Kraska, 2020
https://scholar.google.com/scholar?q=Benchmarking+Learned+Indexes
6. A Sparse Table Implementation of Priority Queues — Alon Itai, Alan G. Konheim, Michael Rodeh, 1981
https://scholar.google.com/scholar?q=A+Sparse+Table+Implementation+of+Priority+Queues
7. Cache-Oblivious Streaming B-trees — Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul, Jelani Nelson, 2007
https://scholar.google.com/scholar?q=Cache-Oblivious+Streaming+B-trees
8. Hekaton: SQL Server's Memory-Optimized OLTP Engine — Cristian Diaconu, Craig Freedman, Erik Ismert, Per-Åke Larson, Pravin Mittal, Ryan Stonecipher, Nitin Verma, Mike Zwilling, 2013
https://scholar.google.com/scholar?q=Hekaton%3A+SQL+Server%27s+Memory-Optimized+OLTP+Engine
9. Cache Craftiness for Fast Multicore Key-Value Storage (Masstree) — Yandong Mao, Eddie Kohler, Robert Morris, 2012
https://scholar.google.com/scholar?q=Cache+Craftiness+for+Fast+Multicore+Key-Value+Storage+%28Masstree%29
10. The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases — Viktor Leis, Alfons Kemper, Thomas Neumann, 2013
https://scholar.google.com/scholar?q=The+Adaptive+Radix+Tree%3A+ARTful+Indexing+for+Main-Memory+Databases
11. Speedy Transactions in Multicore In-Memory Databases (Silo) — Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, Samuel Madden, 2013
https://scholar.google.com/scholar?q=Speedy+Transactions+in+Multicore+In-Memory+Databases+%28Silo%29
12. An Adaptive Packed-Memory Array — Michael A. Bender, Haodong Hu, 2007
https://scholar.google.com/scholar?q=An+Adaptive+Packed-Memory+Array
13. SageDB: A Learned Database System — Tim Kraska, Mohammad Alizadeh, Alex Beutel, et al., 2019
https://scholar.google.com/scholar?q=SageDB%3A+A+Learned+Database+System
Interactive Visualization: ALEX: Building an Updatable Learned Index for Databases