系统与数据库2017arxiv.org编辑精选
学习型索引结构之论证
The Case for Learned Index Structures
进阶 · 约 60 分钟读完前置知识：B-tree/数据库索引基础、机器学习基础、数据分布与回归模型
导读
这篇论文提出把索引看作一种"模型"：既然 B-tree 等结构本质上是在学习数据的分布，就可以用机器学习模型（如回归模型、神经网络）来近似键到位置的映射，从而替代 B-tree、哈希索引乃至布隆过滤器。作者在只读查询等场景下与 B-tree 做了对比实验，报告了性能提升和空间占用下降。
HN 关注点：这个"用模型替代索引结构"的思路有多大颠覆性，以及论文的基线对比是否公平——评论里立刻有人指出它只拿 B-tree 作比较，而忽略了现有更先进、同样编码数据分布的 succinct 索引结构。
后来怎么样
这篇论文开创了 learned index 研究方向，后续引出 PGM-index、ALEX 等大量工作，并推动了数据库系统对数据感知索引的探索；但它并没有取代 B-tree 成为主流索引实现。
HN 评论精选
这几条评论里：支持 1 质疑 2 补充 1
质疑论文只与 B-tree 对比不公平，现有编码数据分布的 succinct 结构更紧凑、也支持高吞吐写入，应作为基线。
这是一篇很有意思的论文，很多想法我之前没见过，而且有几个点是大多数计算机科学家忽略、它却抓得很准的。但拿 B-tree 做性能对比会让结果有偏向。最先进的访问方法用的是 succinct 数据结构，它们会编码数据分布——而论文里说这种东西目前基本不存在。我在几家公司构建过也见过这类结构。公平地说，我不记得有相关文献（高端数据库领域向来如此）。关于 succinct 结构的要点：它们可以针对高吞吐混合负载自适应构建，论文也说这类结构不具备该特性——但那只限于不编码数据分布的 succinct 结构；这类结构的一大用途（除减少 B-tree 索引膨胀外）正是实时写入性能。它们极其紧凑。按我粗略估算，论文测试数据集对应的等价搜索结构可以完全放进 L2 缓存，每层只需几个（ admittedly 很巧妙）位运算即可遍历。论文里的算法比 B-tree 紧凑得多，这是有价值的结果，但仍远大于替代方案。要注意这里的 succinct 结构并不是小型 B-tree……
jandrewrogers查看英文原文
This is a very interesting paper, lots of ideas I haven't seen before and it gets a few ideas very right that most computer scientists overlook (more on that below). But comparing performance against B-trees tilts the results. State-of-the-art access methods use succinct data structures which encode the data distribution, which was called out in the paper as something that doesn't really exist currently. I've built and seen these structures at a few different companies. In fairness, I don't recall any literature on these (as is the norm for high-end database computer science). The key points on succinct structures: - They can be constructed adaptively for high-throughput mixed workloads, also called out in the paper as not being a feature of these structures -- which is true if you limit the scope to succinct structures that don't encode data distribution. One of the driving use cases, beside reducing B-tree index bloat, is real-time write performance. - These structures are extremely compact. The equivalent search structure for the test data set in the paper easily fits (per my cocktail napkin calculation) entirely in L2 cache and each level is traversed with a handful of (admittedly clever) bit-twiddling operations. While the algorithms in the paper are much more compact than B-trees, which is an interesting and valuable result, they are still much larger than alternatives. It should be noted that the succinct data structures used here are not tiny B-trees -- they operate on different principles. - Multidimensional versions of the succinct data structures already exist. The majority of the performance of my spatial databases can be attributed to the development of succinct index structures that generalize to spatial data models. The spatial algorithms allow it to scale out but the performance is due to succinctness. Which is to say, the ideas in the paper are really neat, but they are unlikely to supplant other algorithms for databases. Where the paper really gets it right is framing "indexing" as a learning/prediction problem. Most computer scientists think of indexes as a data structures to search for things but give little thought to the theoretical limits of indexing in the abstract. As in, what is the best possible indexing structure for data models generally, and how close can we get to that for practical purposes? The abstract description of optimal indexing is essentially as an algorithmic induction/prediction problem, which makes an ideal implementation intractable but when you start to think of indexes in terms of algorithmic information instead of organizing values, it leads to interesting constructs like the data structures mentioned above that are dramatically more efficient and effective than traditional top-down indexing algorithm designs. Optimal index construction is, oddly enough, closely related to the problem of AI. Consequently, it doesn't surprise me that algorithms from AI can be applied to produce efficient index representations. At the limit, you would expect the data structures for indexing and AI to converge.
支持认可这是数据库与分布式系统走向"数据感知"的自然趋势，并提供了论文摘要链接。
这里是该方法的一个简要总结：[链接]。我喜欢它。这是一个自然的趋势：数据库和分布式系统会变得越来越"数据感知"，以换取效率和性能。
mad44查看英文原文
Here is a brief summary of the approach. http://muratbuffalo.blogspot.com/2017/12/paper-summary-case-for-learned-index.html I like it. This is a natural trend: we will see databases and distributed systems become more data-aware to achieve efficiency and performance. http://muratbuffalo.blogspot.com/2015/08/new-directions-for-distributed-systems.html
补充最有价值的方向是多维索引：直接学习 kNN/相似性搜索索引可规避 K-D 树等方法的缺点。
真正酷的应用是论文结尾提到的多维索引。比如现在相似性搜索（比如推荐系统）的 kNN 通常用某种 K-D 树或投影方法，这有不少缺点，包括内存占用。如果我们能直接"学习"这个索引，那会非常惊艳。
anon1253查看英文原文
The really cool application of this, which they allude to at the end of the paper, is multi dimensional indexes. For example right now kNN for similarity search (think recommender systems) is usually done with some form of K-D tree or projection method. This has a bunch of downsides, including memory usage. If we can "learn" that index directly, that would be really fancy.
质疑质疑"数据感知索引"的新颖性：按数据分布调整索引看似理所当然，为何此前无人实现。
听起来是个有意思的方法，但我想确认自己对论文范围和影响力的理解是否正确："数据感知索引"肯定不是新颖之处吧？还是说对数据分布建模一直都很困难，以至于之前没人做成？根据常见的数据类型去调整索引看起来是很自然的做法。不过这个想法确实很酷。
Asdfbla查看英文原文
Sounds like an interesting approach, but just that I understand the scope or impact of the paper right: Surely data-aware indexing can't be the novel part, right? Or was it always so complicated to model the data distribution that no one managed to do it until now? It seems natural to try to adapt your index to the type of data you see more often than not. Very cool idea though.
历次讨论
- 2017Hacker News 讨论帖398 分 · 66 评
同领域还值得读
I/O 比 CPU 更快——让我们划分资源并消除操作系统抽象
I/O Is Faster Than CPU – Let’s Partition Resources and Eliminate OS Abstractions
指出在现代服务器硬件上 I/O 速度已接近甚至超过 CPU，传统操作系统抽象反而成为瓶颈。
系统与数据库2019 · 817 分 · 277 评进阶 · 约 30 分钟编辑精选使用 io_uring 的高效 I/O
Efficient IO with io_uring
由 Linux 内核开发者 Jens Axboe 撰写，介绍 Linux 新的异步 I/O 接口 io_uring。
系统与数据库2019 · 426 分 · 96 评进阶 · 约 45 分钟编辑精选线程对大多数用途而言是个坏主意（1995）
Threads Are a Bad Idea for Most Purposes (1995)
这篇 1995 年的文章由 John Ousterhout 撰写，讨论为什么线程对大多数用途而言是坏主意，并主张事件驱动编程通常更简单、更高效。
系统与数据库2017 · 423 分 · 382 评进阶 · 约 25 分钟编辑精选FoundationDB：一个分布式、解耦的事务型键值存储
FoundationDB: A distributed, unbundled, transactional key value store
介绍 FoundationDB：一个分布式、解耦设计的事务性键值存储。
系统与数据库2021 · 283 分 · 99 评进阶 · 约 90 分钟编辑精选SQLite：过去、现在与未来
SQLite: Past, Present, and Future
这篇 VLDB 论文梳理 SQLite 的历史、当前架构与性能表现，并展望未来方向。
系统与数据库2022 · 282 分 · 86 评进阶 · 约 40 分钟编辑精选