智能数据库学习型索引研究综述

**建立高效的索引结构是提升数据库存取性能的关键技术之一. **在数据呈爆发式增长、海量聚集、高维复 杂的大数据环境下，传统索引结构（例如 B+ 树）处理海量数据时面临空间代价高、查询效率低、存取开销大等难 题. 学习型索引技术通过对底层数据分布、查询负载等特征进行建模和学习，有效的提升了索引性能，并减少了 访存空间开销. 本文从学习型索引技术的基础模型入手，对 RMI 基础模型实现原理、构造和查询过程进行了分析， 并总结了基础模型的优点和存在的问题；以此为基础，按照索引结构特点对学习型索引技术进行分类，从索引创 建方式和更新策略两方面对学习型索引技术进行了系统梳理，并对比分析了典型学习型索引技术的优点及不足之 处. 另外，本文总结了学习型索引技术的扩展研究. 最后，对学习型索引的未来研究方向进行了展望.索引技术对于数据库系统实现数据的高效访问 至关重要[1]，一直以来都是数据库领域的研究热点 之一. 自上世纪 70 年代以来，工业界和学术界开展 了大量的索引技术研究[2-5]，用于提高内存利用率、 缓存命中率或 CPU 效率. 典型索引技术有面向范围 查询的 B 树索引、面向点查询的哈希索引，以及面 向存在性查询的布隆过滤器等. 然而，大数据时代 的到来，数据呈爆发式增长、海量聚集，数据库需 要处理 PB 级，甚至 ZB 级的数据，致使传统索引结 构在处理海量数据时，面临空间代价高（例如，B+ 树索引需要借助 O(n)规模的额外空间来索引大规模 的数据集）、查询效率低（例如，B+ 树每次查询时需 要遍历根节点到叶节点路径上的所有节点，导致在 大规模数据集中查询性能下降）的问题. 其主要原 因有两方面：第一，传统索引结构是通用数据结构， 没有利用底层数据的分布规律，不能够灵活处理特 定的数据集或者查询负载；第二，传统索引结构的 查询操作往往是顺序扫描，未充分利用现代加速器 的高并行处理能力来提升查询效率. 针对上述传统 索引结构的问题，研究人员将目光投向人工智能技 术和机器学习方法，研究了学习型索引技术. 学习型索引技术的思想来源于智能数据库系统 的研究. 近些年，将人工智能技术和机器学习应用 到传统数据库系统，通过捕获底层数据的分布规律 或者查询负载的特征等，建立深度学习模型或者强 化学习模型来加强或替换数据库的核心组件（参数 调优、查询优化、索引结构等），使得传统数据库系 统拥有智能，成为了数据库领域的研究热点[6]. 在2018 年的 SIGMOD 会议上，Kraska 等人[7]首次采用 机器学习模型替换传统索引结构，学习底层数据的 分布规律，建立键与位置之间的映射关系，提出了 学习型索引的概念. 学习型索引技术因其自身的显 著优势（例如，学习型索引通过数学计算替代树遍 历操作有效减少了存储开销，提高了查询效率），引 起了数据库领域研究人员的广泛关注，在 Kraska 等 人提出的学习型索引技术的基础上，开展了大量的 研究工作. 本文从基础问题-扩展问题这两个层次 对学习型索引技术进行梳理、总结和分析. 具体 地，针对基础问题，本文首先系统概述学习型索引 技术的基础模型 RMI 模型，分析了其原理、构造 和查询过程，并总结了 RMI 模型的优点和存在的 问题. 然后，以 RMI 模型为线索，依据索引（模型） 组织方式和优化策略对学习型索引技术进行分类 和总结. 对每一类技术，从索引创建方式、更新策略 等方面展开详细阐述. 并从多个角度对比分析了不 同学习型索引技术之间的优缺点. 针对扩展问题，本 文总结了 6 个研究方向. 最后，总结分析了学习型索 引技术存在的问题并对未来的研究方向进行展望. 相关工作：由于学习型索引技术研究尚处于起 步阶段，关于这方面的综述性文章不多. 文献[6, 8-10]介绍了学习型索引技术，但是它们的侧重点是 机器学习改进的数据库系统. 文献[11]和[12]是已知 的仅针对学习型索引技术进行综述的文章. 文献 [11]是国外首篇综述学习型索引技术的文章，但是文 章侧重于技术罗列且较早期，后续涌现的许多新成 果未纳入其中. 文献[12]是国内首篇综述学习型索 引技术的文章，文章以查询类型、测试基准为分类 框架，总结了学习型索引技术. 文献[11]和[12]均侧 重于一维学习型索引的更新策略，缺乏对一维和多 维学习型索引技术细致的分类和对比分析. 本文提 出了一个新的研究框架：基本问题-扩展问题，并以 索引（模型）组织方式、优化策略来划分和总结不 同的学习型索引技术，比上述文献更加综合全面.

http://cjc.ict.ac.cn/online/onlinepaper/cp-2023112105313.pdf