关于Learned Indexes的思考

Learned Indexes 论文前两周被发表在arXiv上,引起了业界的广泛关注。作为一种全新的索引模型,Learned Indexes 或将有希望取代目前DBMS的传统索引。其核心思想是将数据查找视为以key为输入的数据地址预测问题,从而可以利用机器学习在预测问题上的研究沉淀来优化数据查找。简单来说,Learned Indexes 是一种结合机器学习的索引模型,能根据数据分布来优化索引结构和查找效率。

Learned Indexes本身尚且处于萌芽的阶段,只通过简单实验初步证明了可行性,不像Spanner或GFS等有成熟应用的论文(这也是为什么发表在arXiv上),但其中将索引视为算法模型的思想可以说是打开了新世界的大门。首先,索引作为计算机最早研究的领域之一,其中许多算法已被数学证明为最优解。因此即使是各种NN应用层出不穷的今日,绝大多数人也不会想到将NN应用到索引上。更重要的是,传统算法和机器学习算法一直有一条鸿沟:传统算法的输出一般是确定的和易于解释的,机器学习算法的输出则和习得模型相关,是基于概率的和较难解释甚至无法解释的。计算机底层的系统要求有清晰的逻辑和准确的输出,所以一直是传统算法的天下(当然也和机器学习出现时间较晚有关)。而Learned Indexes的出现,更多是传统算法和机器学习算法的融合,比如Hybrid Indexes遇到难以学习的数据分布时会将部分或全部模型替换为传统的B-Tree以保证效率不会低于B-Tree。传统算法和机器学习算法的互补,很有可能会让现代算法再上一个台阶。

从用户的角度来说,对于经常与数据存储打交道的大数据工程师,索引优化是必不可少的一项技能(即便大数据领域的索引并不像传统数据库一样完善)。利用各种数据结构建立一套可以覆盖多数查询的索引是一项很有成就感的工作。但是不得不承认的是面对越来越多样化的数据、指数级别增长的数据和越发复杂的查询模式,设计可以满足查询效率的索引变得复杂甚至难以完成。因此分布式领域的NoSQL和NewSQL多多少少需要对数据分布或查询模式的灵活性作出妥协并针对设计常见提供特定索引。然而这只是将问题抛给了用户,比如HBase的数据热点问题、Hive的非分区字段索引问题,针对这些问题工程师需要进行大量ad-hoc处理,并不是优雅的解决方案。而Learned Indexes的出现将有可能改变这种现状。例如Learned Indexes由于了解存储数据的分布,可能在写入时便将热点key的数据打散分布到各个物理节点,从而避免数据热点问题(当然检索的性能可能受影响)。

总而言之,Learned Indexes将赋予索引根据数据分布自动调整的能力,未来或许还会将数据访问分布纳入考虑。如果被广泛应用这将会大大减少工程师花费在索引设计和优化的时间和精力。同时它很可能是传统算法与机器学习结合的开始,更多的计算机底层系统和模块会变得更加智能和高效。

本文是原创文章,转载请注明:时间与精神的小屋 - 关于Learned Indexes的思考