The Case for Learned Index Structures Revisited

This episode revisits "The Case for Learned Index Structures" by Tim Kraska and coauthors from MIT and Google, which proposes replacing classic data structures like B-Trees, hash maps, and Bloom filters with small trained neural networks. The discussion covers how a B-Tree traversal is mathematically equivalent to estimating a cumulative distribution function, and how a tiny two-layer model can predict a key's position directly, turning a branchy O(log N) search into near-constant-time arithmetic suited to SIMD and GPU hardware. It also digs into how the same idea extends to hash functions tuned to real key distributions and to Bloom filters reframed as classifiers, complete with a backup filter to catch the model's false negatives. The hosts push back on each other over the paper's headline claims of 70% faster lookups and order-of-magnitude memory savings, debating whether results measured on static, read-only, in-memory workloads generalize or overstate the case. Listeners interested in database internals, the intersection of machine learning and systems design, or the tradeoffs between hand-engineered and learned structures will find the back-and-forth a useful gut check on a widely cited but contested idea.

Interactive Visualization: The Case for Learned Index Structures Revisited

Sources:
1. The Case for Learned Index Structures — Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, Neoklis Polyzotis, 2017
http://arxiv.org/abs/1712.01208
2. SOSD: A Benchmark for Learned Indexes — Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, Thomas Neumann, 2019
https://scholar.google.com/scholar?q=SOSD%3A+A+Benchmark+for+Learned+Indexes
3. 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, 2020
https://scholar.google.com/scholar?q=ALEX%3A+An+Updatable+Adaptive+Learned+Index
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. 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
6. Organization and Maintenance of Large Ordered Indexes — Rudolf Bayer, Edward M. McCreight, 1972
https://scholar.google.com/scholar?q=Organization+and+Maintenance+of+Large+Ordered+Indexes
7. The Ubiquitous B-Tree — Douglas Comer, 1979
https://scholar.google.com/scholar?q=The+Ubiquitous+B-Tree
8. Making B+-Trees Cache Conscious in Main Memory — Jun Rao, Kenneth A. Ross, 2000
https://scholar.google.com/scholar?q=Making+B%2B-Trees+Cache+Conscious+in+Main+Memory
9. Space/Time Trade-offs in Hash Coding with Allowable Errors — Burton H. Bloom, 1970
https://scholar.google.com/scholar?q=Space%2FTime+Trade-offs+in+Hash+Coding+with+Allowable+Errors
10. Network Applications of Bloom Filters: A Survey — Andrei Broder, Michael Mitzenmacher, 2004
https://scholar.google.com/scholar?q=Network+Applications+of+Bloom+Filters%3A+A+Survey
11. A Model for Learned Bloom Filters and Optimizing by Sandwiching — Michael Mitzenmacher, 2018
https://scholar.google.com/scholar?q=A+Model+for+Learned+Bloom+Filters+and+Optimizing+by+Sandwiching
12. Cuckoo Filter: Practically Better Than Bloom — Bin Fan, Dave G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, 2014
https://scholar.google.com/scholar?q=Cuckoo+Filter%3A+Practically+Better+Than+Bloom
13. A model for learned bloom filters and related structures — M. Mitzenmacher, 2018
https://scholar.google.com/scholar?q=A+model+for+learned+bloom+filters+and+related+structures
14. A-Tree: A Bounded Approximate Index Structure — A. Galakatos, M. Markovitch, C. Binnig, R. Fonseca, T. Kraska, 2018
https://scholar.google.com/scholar?q=A-Tree%3A+A+Bounded+Approximate+Index+Structure
15. FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs — C. Kim, J. Chhugani, N. Satish, et al., 2010
https://scholar.google.com/scholar?q=FAST%3A+Fast+Architecture+Sensitive+Tree+Search+on+Modern+CPUs+and+GPUs
16. Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer — N. Shazeer, A. Mirhoseini, K. Maziarz, et al., 2017
https://scholar.google.com/scholar?q=Outrageously+Large+Neural+Networks%3A+The+Sparsely-Gated+Mixture-of-Experts+Layer
Interactive Visualization: The Case for Learned Index Structures Revisited