如何计算结构体大小 谷歌用ML模型替代组件，或彻底改变数据系统开发

“如果这项研究取得更多的成果，将来有一天我们很可能回过头看然后说，索引是最先倒下的，接着是其他的组件(排序算法、查询优化、连接)，它们都逐渐被神经网络取代。”纽约州立大学布法罗分校的计算机科学和工程教授Murat Demirbas这样说。

文章描述了一个非常有前景且十分有趣的方向，题目读来也颇有小说的感觉——“The Case for Learned Index Structures”。

这篇论文旨在证明“机器学习模型有潜力大幅超越当前较先进的索引，提供好很多的性能”。

用神经网络学习数据分布，让索引“data-aware”

索引(Index)，就是一种对表中一列或多列的值进行排序的结构，使用索引可以快速访问表中的特定信息。的索引好比图书的目录，目录能让你在看书时不把整本书看完就快速找到需要的信息，索引也能让程序迅速地找到表中的数据，而不必将整个扫描完。

但是，在应用索引时，对数据本身并不了解，数据相当于一个黑盒，而不了解数据的分布，造成了很大的浪费。

举例来说，如果键的范围在0到500m之间，比起用哈希，直接把键当索引速度可能更快。如果知道了数据的累积分布函数(CDF)，“CDF*键*记录大小”可能约等于要查找的记录的位置，这一点也适用于其他数据分布的情况。

数据的累积分布函数(CDF)可以作为索引

作者在论文中表示，较精确了解数据分布，可以大幅优化当前系统使用的几乎所有索引结构。

但是，较精确了解数据分布，就成了“白盒”，失去了可重用性。这样一来就需要检查数据，每次都从头开始设计索引。

于是，谷歌研究人员想到了机器学习方法，并使用其中最强的一种——神经网络，去学习数据分布，并用学到的知识预测数据的分布。

这样一种折中的方法，让数据索引变得“data-aware”，由此获得性能的提升。

如果成功，开发方式可能彻底改变

他们将神经网络应用于三种索引类型：B树，用于处理范围查询;哈希映射(Hash-map)，用于点查找查询;以及Bloom-filter，用于设置包含检查。下面着重介绍一下作者如何用神经网络替代B树。

B树提供了一种有效的分层索引。从概念上讲，B-tree将一个键映射到一个页面。因此，我们可以用一个模型，也进行键的位置映射，而对于错误范围，我们可以做一个二进制搜索(或扩展环搜索)的变体来定位页面。

要知道min_error和max-error，就用拥有的数据来训练模型。数据是静态的，神经网络进行预测，然后从这些错误中学习。即使简单的逻辑回归也可以用于简单的分布。

在测试时，作者将机器学习索引与B树进行比较，他们使用了3个真实世界数据集，其中网络日志数据集(Weblogs)对索引而言极具挑战性，包含了200多万个日志条目，是很多年的大学网站的请求，而且每个请求都有单一的时间戳，数据中含有非常复杂的时间模式，包括课程安排、周末、假期、午餐休息、部门活动、学期休息，这些都是非常难以学习的。

从上图可见，对于网络日志数据，机器学习索引带来的速度提升较高达到了53%，对应的体积也有76%的缩小，相比之下误差范围稍有加大。

用机器学习模型替换B树的好处是：

索引结构更小：更少的主内存或L1缓存

查找速度更快：因为索引变小了

更强的并行性(TPU)，而不是B-树中的分层if语句

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-72494-1.html