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

这篇论文是我在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 条评论
登录 后参与评论

相关文章

来自专栏新智元

【让调参全部自动化】自动机器学习,神经网络自主编程(代码与诀窍)

【新智元导读】自动机器学习(AutoML)是近来很活跃的研究方向。KDnuggets 的主编 Matthew Mayo 写了一篇文章介绍了 AutoML 的概念...

3824
来自专栏深度学习入门与实践

【原】机器学习几个基本的问题

  从今年四月份到现在已经工作快9个月了,最开始是做推荐系统,然后做机器学习,现在是文本挖掘,每个部分研究的时间都不多,但还是遇到了很多问题,目前就把一定要总结...

1879
来自专栏Flutter入门

Android OpenGL ES(四)-为平面图添加滤镜

之前我们通过YUV数据格式的处理知道,只要保留Y的数据,就是灰度的图片。但是OpenGL中处理的是RGB格式的数据,我们要如何去取得灰度图呢? 我们可以通过公...

833
来自专栏BestSDK

深度学习 VS 深度克隆,谁才是解决聊天机器人的最佳方法?

对话式 AI (聊天机器人)涉及到三个维度的问题:(1)语言技能(2)知识获取(3)对话行为。 这三者虽然强相关,但人类大脑通过单独的实验,在不同的时间段内,可...

2935
来自专栏大数据文摘

论文Express | 自然语言十项全能:转化为问答的多任务学习

Salesforce最新论文提出了一个可处理多项自然语言处理的通用模型:decaNLP,处理机器翻译、文本分类等NLP任务统统不在话下!

992
来自专栏CDA数据分析师

R语言中的情感分析与机器学习

利用机器学习可以很方便的做情感分析。本篇文章将介绍在R语言中如何利用机器学习方法来做情感分析。在R语言中,由Timothy P.Jurka开发的情感分析以及更一...

1769
来自专栏null的专栏

CTR——人工神经网络+决策树

一、引言    这是篇论文的笔记,记录阅读该论文中的一些体会,希望与大家一起学到知识。论文题目为《Using neural networks for click...

5258
来自专栏PPV课数据科学社区

【技术】从文本挖掘和机器学习中洞悉数据

文本挖掘分析的是包含在自然语言文本中的数据。它可以帮助企业从文本型数据中获得具有潜在价值的商业洞察力,比如Word文档、邮件或Facebook、Tw...

2626
来自专栏机器之心

All In! 我学会了用强化学习打德州扑克

选自willtipton 机器之心编译 参与:Jane W、蒋思源 最近,强化学习(RL)的成功(如 AlphaGo)取得了大众的高度关注,但其基本思路相当简单...

30411
来自专栏AI科技评论

开发 | 在玩图像分类和图像分割?来挑战基于 TensorFlow 的图像注解生成!

AI科技评论按:本文刊载于 Oreilly,AI科技评论编译。 玩过图像分类的开发者不少,许多人或许对图像分割(image segmentation)也不陌生,...

3416

扫描关注云+社区