【前沿】谷歌大脑Jeff Dean最新工作：用机器学习索引替代B-Trees，性能提升3倍

2017 年 12 月 12 日 专知专知内容组（编）

【导读】最近谷歌Jeffrey Dean等人发表工作《The Case for Learned Index Structures》：用机器学习来学习数据分布，从而替代B-Trees、哈希索引和布隆过滤器减少索引的大小，结果表明新方法3x性能提升和10-100x空间缩小。

▌知乎网友相关回答

摘抄自知乎网友Huijun Wu的回答

链接：https://www.zhihu.com/question/263916416/answer/27

这篇文章应当是一个引领新潮流的工作。如果将ML理解为一个建模方法，那么用其来应对复杂多变的workload其实是很吸引人的idea。杂多变的workload其实是很吸引人的idea。从近期计算机系统和数据库类的会议文章来看，人们也慢慢开始用ML来解决传统的系统设计经验带来的sub-optimal solution的问题。在索引、缓存算法还是负载均衡等问题中，高性能往往来源于算法本身对workload的假设与实际情况的高度契合。以缓存算法为例，脱离workload特性谈某种缓存策略更优都是耍流氓，那如果AI能够准确建模当前workload特性，那么对于选择甚至构造一种最优策略都大有裨益。

但用ML解决此类问题依然存在显著问题。建模复杂问题往往需要复杂模型，而复杂模型的计算存储效率依然是问题，ML community自己也在研究模型压缩等问题。如果说仅仅进行预测的计算量还不算大的话，训练开销则不可忽视。类似于这篇文章中的假设，对于负载相对不变的情况，模型是不需要重新训练，训练开销也许不是什么大事，但是个人觉得这类问题对于ML的需求其实比较弱。更多的实际情况应该是workload在变化，怎么识别concept drift并高效调整模型，从而给出更优的策略。

总的来说，ML对诸多研究领域都带来许多新机会和新挑战。有ML这个新工具，很多问题得以更精确建模和解决。ML本身的问题，比如对硬件性能的高需求，算法的可靠性可解释性也使得在真正使用之前还需要做很多工作。

▌论文

论文：The Case for Learned Index Structures

摘要：索引是模型：B-Tree-Index可以被看作是一个模型，用于将键映射到排序数组中的记录的位置，哈希索引也是一格模型，将键映射到未排序数组的记录位置，一个BitMap-Index作为模型来指示数据记录是否存在。在本文的探索性研究中，我们从这个前提出发，假设所有现有的索引结构（index structures）都可以用其他类型的模型来代替，包括深度学习模型，我们称之为索引学习（learned indexed）。关键的思想是，一个模型可以学习排序顺序或查找键的结构，并使用这个信号来有效地预测记录的位置或记录是否存在。从理论上分析了索引学习在哪些条件下表现优于传统索引结构，并描述了索引学习结构设计中的主要挑战。最初的结果表明，通过使用神经网络，我们能获得比用缓存优化（cache-optimized）的B树高出70％的速度，同时在几个真实数据集上的内存占用节省了一个数量级。更重要的是，我们相信通过学习模型取代数据管理系统核心组件的想法对未来的系统设计有着深远的影响，而且这项工作只是相关工作的冰山一角。

参考链接：

https://www.arxiv-vanity.com/papers/1712.01208v1/

https://www.zhihu.com/question/263916416/answer/275010943

-END-

专 · 知

人工智能领域主题知识资料查看获取：【专知荟萃】人工智能领域25个主题知识资料全集（入门/进阶/论文/综述/视频/专家等）

同时欢迎各位用户进行专知投稿，详情请点击：

【诚邀】专知诚挚邀请各位专业者加入AI创作者计划！了解使用专知！

请PC登录www.zhuanzhi.ai或者点击阅读原文，注册登录专知，获取更多AI知识资料！