【技术】如果我告诉你数据库索引是可以学习的,你会怎么做?

这篇论文是我在NIPS中看到的,在过去的几天里,在ML的圈子里得到了相当多的关注。论文中反复强调:在他们的心里,数据库索引是模型。它们可能不(通常)是有统计学意义的,但它们是提供(希望相当快的)输入(索引创建的关键)和输出(内存中的位置)之间的映射的结构。二叉树,是一种典型的有序数据结构,甚至采用了树的形式,这是机器学习工具箱中的核心工具。

论文地址:https://www.arxiv-vanity.com/papers/1712.01208/

在这一关键的直觉上,该论文提出了这样的问题:如果这些结构只是模型,那么可以通过统计模型来学习,然后利用这些模型,被索引的数据的分布比目前使用的索引更好,更小,更有效吗?剧透:答案(至少对于数值型数据类型)是肯定的。

例如,它可能的情况是,所有的元素都是一样的长度,并且每个数字键的位置都会增加5:在这种情况下,你可以很容易地学习键和位置之间的线性回归映射,其速度远远超过有序分裂的B树。B树在最坏的情况下也是有效的,在这种情况下,数字键位置的CDF密度(如果你将其排序为一行的话)是真正随机的,并且假设其是未知的。

关于B树的一个有趣的事实是,每当添加新数据时,它们都需要重新平衡,作者认为这与重新训练模型类似。因此,出于比较的目的,他们只是比较了训练集的性能,因为B树和候选统计模型只有在经过重新训练才会起作用。

作者通过训练一个基线模型开始:包含2层,32个隐藏单元,并且紧密相连的网络。这个模型有两个主要问题。

  1. 首先,它生成预测min / max的搜索位置作为关键函数的速度非常缓慢:它需要在Tensorflow中训练,这需要很高的前期成本,对于这个小模型来说不值得。
  2. 其次,它在单个键的级别上并不是很精确。虽然它在学习累积键分布的整体形状方面做得很好,但它避免了CDF函数中局部变量的过度拟合,因此当你在关键空间的小区域“放大”时,它就变得不那么准确了。正因为如此,它并没有显著地加快查找过程,而是在做一个完整的基线键扫描。按照他们设计这个问题的思路,一个简单的模型可以很容易地将预期搜索误差从1亿减少到10000,但是由于模型中固有的平滑性假设,很难将其降低到100s量级。

解决这些问题有两个关键的解决方案:一个是实现细节,一个是理论创新。第一个是相对简单的(至少在概念上是这样):构建一个框架,通过该框架,你可以在Tensorflow中训练模型,但是模型的推理阶段是在c++中进行评估的。这使得以前测试的基准模型的性能显着提高:从80,000ns降至30ns。

第二,框架作为解决“最后一英里”精度问题的解决方案,是递归模型。在这个框架中,我们从训练一个“顶层”模型开始,该模型输出对键的位置的预测。然后,我们把空间分成三个部分,然后分别学习每个子区域的模型。例如,顶层模型可以预测出,在一个10000长内存区域内,键4560将映射到位置2000。因此,他们根据顶层模型的预测,将观测结果分组,并对新模型进行特定训练,比如,预测位置在0到3500之间的键。

当这种方法——使用优化代码的层次结构模型——在带有数字键值的数据上进行尝试时,结果令人印象深刻。与B树相比,学习索引实现了有意义的提速,提高了超过60%。值得注意的是,下面的结果并不使用GPU。这表明,如果GPU在数据库硬件中变得更标准,这种改进甚至可能会增加。

它们目前只显示了对数字键建模的成果,但建议将目前用于文本(RNNs,character -level CNNs)的更复杂的方法添加到这个通用框架中。

为什么所有这些都是有趣的,除了可能导致新一代数据库索引设计的实际事实?

首先,我要承认,这篇论文在我在心里有特殊的意义。它除了介绍一些引人注目的ML概念之外,还使我更深入、更清晰地思考了索引工作背后的机制,而以前,这一直是我简单理解但没有深入研究的内容。

其次,利用机器学习模型来优化他们所运行的各种低级系统,这似乎有现实意义。这是我记得的第一批使用机器学习来优化计算过程的论文之一,但似乎不太可能是最后一个。

原文发布于微信公众号 - ATYUN订阅号(atyun_com)

原文发表时间:2017-12-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据科学与人工智能

【机器学习】机器学习背后的统计思想

要理解机器学习首先要明白他的定义,很多人给出了定义“学习是人类具有的一种重要智能行为,但究竟什么是学习,长期以来却众说纷纭。社会学家、逻辑学家和心理学家都各有其...

2248
来自专栏大数据挖掘DT机器学习

NLP中自动生产文摘(auto text summarization)

最近几年在人工智能领域中大热的工程技术deep learning,将机器对图像,语音,人类语言的认知能力都提升了不少,前前后后也涌现出不少不仅仅是很cool而且...

5175
来自专栏机器之心

学界 | 百度提出问答模型GNR:检索速度提高25倍

选自Baidu Research 作者:Jonathan Raiman & John Miller 机器之心编译 参与:刘晓坤、李泽南、蒋思源 近日,百度人工智...

29210
来自专栏机器之心

教程 | 如何用深度学习处理结构化数据?

33311
来自专栏ATYUN订阅号

亚马逊机器学习团队开发可离线工作的复杂语音识别模型

世界上最受欢迎的虚拟助手有什么共同之处?它们在云中执行大部分语音识别,他们的自然语言模型利用功能强大的服务器,具有几乎无限的处理能力。它在很大程度上是可以接受的...

692
来自专栏人工智能头条

无监督对话数据清洗利器:Data Purification Framework

1041
来自专栏AI科技大本营的专栏

AI 技术讲座精选:用Keras和Gym实现深度强化学习

综述 ? 本篇博文将向大家演示,如何在仅仅运用78行代码的情况下,利用 Keras 和 Gym 实现深度强化学习,使得 CartPole 这款游戏得以成功运行...

27412
来自专栏企鹅号快讯

结合感知和概念思维,DeepMind提出可微归纳逻辑框架∂ILP

选自DeepMind 机器之心编译 最近,DeepMind 在 JAIR 上发表论文《Learning Explanatory Rules from Noisy...

1935
来自专栏ATYUN订阅号

我的神经网络不工作了!我应该做什么? 详细解读神经网络的11种常见问题

“当你正在深入研究深度学习的下一个重大突破时,或许会遇到一个不幸的挫折:你的神经网络不起作用。你去找你的老板/主管,但他们也不知道如何去解决这个问题——他们和你...

2473
来自专栏量子位

OpenAI推新程序包:GPU适应十倍大模型仅需增加20%训练时间

安妮 编译自 Medium 量子位 出品 | 公众号 QbitAI GPU内存太小可能是神经网络训练过程中最大的拦路虎。 不怕,用这个OpenAI推出的grad...

30611

扫码关注云+社区