你清楚AI、数据库与计算机体系

你清楚AI、数据库与计算机体系

• ✨博主介绍

✨博主介绍

💂 个人主页:苏州程序大白 💂 个人社区:CSDN全国各地程序猿 🤟作者介绍：中国DBA联盟(ACDU)成员，CSDN全国各地程序猿（媛）聚集地管理员。目前从事工业自动化软件开发工作。擅长C#、Java、机器视觉、底层算法等语言。2019年成立柒月软件工作室，2021年注册苏州凯捷智能科技有限公司 💅 有任何问题欢迎私信，看到会及时回复

在这里插入图片描述

2018年在数据库顶会SIGMOD上，MIT的Tim Kraska发表了一篇论文题为《The Case for Learned Index Structures》（下简称“Learned Index论文”），提出了“Learned Index（学习索引）”的概念，这篇论文引发了业界高度关注的原因不仅是“Learned Index”概念新颖，更在于Google AI负责人Jeff Dean也位列此论文作者。在AI领域，凡是有Jeff Dean名字出现的论文，都带有超越论文本身的技术方向意义。

索引是数据库系统中用于提升数据存取性能的核心技术，自20世纪70年代以来，数据库领域的研究人员提出了各种各样的索引结构，用于满足不同类型的存取性能需求，比如针对范围查询的B-tree、B+tree与LSM-tree、针对点查询的哈希索引、针对存在查询的布隆过滤器。

这些传统索引技术在TB单位的数据量下运行良好，但当前数据量进入PB乃至更高单位的情况下，传统索引技术引发了三方面的问题：第一，空间代价过高，例如平衡树索引需要借助O(n)规模的额外空间来索引原始的数据，大数据条件下索引代价过大；第二，传统索引技术是用索引深度支撑索引规模，当数据量很大时每次查询均需多次间接搜索，例如B+tree中的每次查询都需要访问从树根到叶节点路径上的所有节点，这使得B+tree的查找性能在大规模数据集上将变得较差；第三，对于哈希函数，大规模数据带来较高冲突概率，哈希函数在较高冲突概率条件下性能急剧恶化。

算法工程一般认为，已经充分算法化的问题不是AI技术的对象，也没有必要使用AI技术，这里举一个例子，GPT-3模型公布后有一些人用对话的方式测试模型做较大数字的相乘，结果发现GPT-3乘法出错，于是认为是GPT-3模型的缺陷，这种认识一定程度上是对AI的误解，“乘法”这样明确的演绎性算法本来就应该通过规则直接计算，AI本来就不是来处理这类问题的。计算机技术中的数据结构及其算法，比如平衡树算法与哈希算法，一般认为都是典型的已经充分算法化的领域，研究者一般不会想到在数据结构问题领域里还有AI发挥的空间。

对于上述问题，“Learned Index论文”提出了有深度和有启发性的新思路：数据库的索引技术实际上都是模型（论文第一句话就是“Indexes are models”），比如范围查询，该模型输入是所要查询的键（key），输出是其值（value）所在的存储位置，误差范围最小为0（目标数据刚好在改页起始位置）、最大为一页的长度（目标数据刚好在改页的末尾）。如果以更算法化的语言描述这个模型，这个模型实际上是在预测数据的累积分布函数（cumulative distribution function，CDF），但传统索引技术都是通用性数据结构（general purpose data structures）——模型目的是预测数据的累积分布函数、模型却完全不考虑现实应用中数据的具体分布——这就是影响传统索引技术效率提高的原因。举一个简单的例子，如果某部分数据的key是固定长度的连续正整数，那么对于这部分数据就完全没必要用B-tree索引，而是可以直接记录下第一个key的存储地址，然后所查询的key乘以某个固定长度就是偏移量，这样就可以用O(1)复杂度完成查询，而不是B-tree索引的O(log n)复杂度，同时，索引的存储代价也从O(n)降低到O(1)。

通过上述分析，问题就非常清晰了，“Learned Index论文”提出，如果用深度学习模型来替换掉传统索引模型，让模型自己去学习拟合实际数据，进而自动化生成索引，就有可能获得比传统索引更高的效率，这就是“Learned Index”的概念。

“Learned Index论文”给出了初步的学习索引框架(learning index framework，LIF)和递归模型索引(recursive model index，RMI)。LIF是一个索引合成系统，用于生成索引配置、自动地优化和测试索引，LIF能够学习简单的模型(例如线性回归模型)，并依赖 Tensorflow训练复杂的模型(例如神经网络模型)。但是，LIF在执行模型时不使用Tensorflow，而是自动提取模型的权重并生成高效的C++索引代码。LIF的代码生成是专为小模型设计的，它消除了Tensorflow中管理大模型的所有不必要的开销和工具。RMI旨在解决学习索引的精度问题，它受到了混合专家模型的启发，RMI的结构是由多个模型组成的分层模型结构，RMI中的每一个模型都以键作为输入并返回一个位置，上层模型的输出结果用于选择下一层的模型，最后一层模型的输出作为RMI的输出。

“Learned Index论文”所做的实验结果令人印象深刻：经过多个数据集的测试，“Learned Index”的查找性能比B+tree快1.5倍~3倍，并且所需的存储空间比B+树低了2个数量级。

点查询的哈希索引，本身就是一组函数模型且具有O(1)的查找性能，所以AI优化的思路与范围查询不同，“Learned Index论文”提出了通过学习键的分布可以得到更好的哈希函数（“Learned Hash-map”），即能够减少哈希冲突。

在这里插入图片描述

对于存在查询的布隆过滤器，“Learned Index论文”则提出了“学习布隆过滤器（Learned Bloom fifilters）”，通过学习数据分布降低哈希冲突的概率，这里需要注意的是，“Learned Hash-map”与“Learned Bloom fifilters”不同，“Learned Hash-map”的目标是降低存在的键之间的冲突概率，而“Learned Bloom fifilters”的目标是降低存在的键与不存在的键之间的冲突概率。“Learned Index论文”提出的“Learned Bloom fifilters”将存在索引视为一个二元概率分类任务，并训练了一个RNN模型预测键存在的概率。

在这里插入图片描述

“Learned Index论文”是“Learned Index”研究的开端之作，解决方案远非完善，比如论文完全没有提到如何支持数据插入操作，这实际上是索引技术非常关键的问题，类似于数据插入会引起B-tree、B+tree与LSM-tree的重新调整，大量插入新数据后会改变键的分布，会使得学习模型需要重新学习，因此，“Learned Index论文”所实现的技术离实用还有较远的距离。

“Learned Index论文”最重要的价值是提供了一种启发性的分析思路——只要一个问题存在“预测性”，那么就有可能以AI的角度重新考虑该问题，并获得新的更好的结果。经历了数十年发展的数据库索引技术，似乎已经被研究得非常充分了，但在“Learned Index论文”提示大家之前，似乎大家都没有发现数据库索引技术实际上是个典型的“预测性”问题并且存在“索引模型目的是预测数据的累积分布函数，但索引模型却完全不考虑现实应用中数据的具体分布”这个明显的问题。

如果从“预测性”这个角度进一步分析，计算机科学中其实有大量问题都是“预测性”的，比如计算机体系中广泛采用的Prefetching就是典型的“预测性”机制、在分布式大数据领域“预测性”的问题则更多，这些“预测性”问题的存在为AI研究开辟了一个新的空间，Google AI负责人Jeff Dean在《The Case for Learned Index Structures》作者中出现，所反映出来的正是这个背景。