HackerPapers

arXiv:2012.12501cs.DB

Learned Indexes for a Google-scale Disk-based Database

Hussam Abu-Libdeh, Deniz Altınbüken, Alex Beutel, Ed H. Chi, Lyric Doshi, Tim Kraska, Xiaozhou, Li, Andy Ly, Christopher Olston

Abstract

There is great excitement about learned index structures, but understandable skepticism about the practicality of a new method uprooting decades of research on B-Trees. In this paper, we work to remove some of that uncertainty by demonstrating how a learned index can be integrated in a distributed, disk-based database system: Google's Bigtable. We detail several design decisions we made to integrate learned indexes in Bigtable. Our results show that integrating learned index significantly improves the end-to-end read latency and throughput for Bigtable.

arXiv comments
4 pages, Presented at Workshop on ML for Systems at NeurIPS 2020
Journal reference
DOI
Subjects
cs.DBDatabases cs.DCDistributed, Parallel, and Cluster Computing cs.LGMachine Learning

On Hacker News

Linked by 4 identifiable commenters in 4 comments across 4 threads, from Jan 2021 to Jun 2025. Found in 1 HN submission from Oct 2024 to Oct 2024. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. The probability of a hash collision (2022) 1 comment

    • In theory, you can treat the objects as i.i.d. giving them a uniform prior. In practice, of course only the inputs are inputs and if you were to take that into account then you could avoid collisions, but as you say, you can't really know that ahead of time. Unless you can, such…

      kevindammView on HNParent context

  2. Ask HN: What are some cool but obscure data structures you know about? 1 comment

    • Also, Learned Indexes Structures: The Case for Learned Index Structures: https://arxiv.org/abs/1712.01208 Learned Indexes for a Google-scale Disk-based Database: https://arxiv.org/abs/2012.12501 And Noms/Dolt Prolly Trees: How to Chunk Your Database into a Merkle Tree…

      robertsdionneView on HNParent context

  3. Transformer Memory as a Differentiable Search Index 1 comment

    • > It seems wildly impracticable to productionize at the moment (excepting Google, perhaps). There were a couple related papers [1, 2] from Google on learning to index a few years ago. In fact, I'm a little surprised they weren't cited. [1]…

      bmc7505View on HNParent context

  4. PGM Indexes: Learned indexes that match B-tree performance with 83x less space 1 comment

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.