选择语言
< 返回主菜单

​使内存中的学习型索引在磁盘上高效

2024-06-03

Innovation Highlights

       提出了一套通用的转换和优化准则 (SGACRU),并将其应用于现有的内存型学习型索引。这一通用转换方法能够有效将内存中的学习型索引转化为适用于磁盘场景的索引,同时获得比之前更快的查询速度和更少的内存占用。

Achievements Summary

使内存中的学习型索引在磁盘上高效

       近年来,学习型索引已成为数据库管理系统的研究热点。然而,目前最先进的学习型索引主要针对内存场景设计,与基于磁盘的数据库管理系统并不完全匹配。为解决这一问题,张焕晨团队提出了一套通用的转换和优化准则(SGACRU),并将其应用于现有的内存型学习型索引。这一通用转换方法能够有效将内存中的学习型索引转化为适用于磁盘场景的索引,同时获得比之前更快的查询速度和更少的内存占用。

8.png

8.png

图1. SGACRU架构

SGACRU准则包括:

G1: (Search) 根据磁盘和工作负载特征,在“最后一英里”搜索期间确定叶页获取策略。

G2: (Granularity) 确定学习模型的预测粒度(例如,项与页)。

G3: (Alignment) 利用页面对齐扩展索引训练的错误界限,以减少模型数量,同时保持相同的预期I/O页面。

G4: (Compression) 通过压缩模型参数减少内存使用,接受与主导I/O时间相比微不足道的CPU开销增加。

G5: (Robustness) 对于CDF难以学习的数据集,回退到高效压缩的区域映射索引。

G6: (Update) 使用混合索引进行高效更新。

9.png

图2. CPU时间与I/O时间对比

这一套通用的转换和优化准则在提升索引结构的速度、空间利用、鲁棒性、智能化水平等方面具有显著优势,同时减轻了研究人员设计磁盘场景下学习型索引的负担。具体包括:

(1)结合磁盘特性和学习型索引的特点,提出了内存和磁盘交互、模型预测的粒度两方面的优化策略,以加速基于磁盘的学习型索引的响应速度。

(2)总结了多种学习型索引的构建算法,并提出通用的优化,可以显著减少索引的内存占用,同时保持高效的查询性能。

(3)从功能性和鲁棒性的角度分别提供相应的优化策略,有助于研究人员更好地理解和高效使用学习型索引。

(4)这一通用转换方法可应用于现有的内存中的学习型索引,使研究人员无需为磁盘场景重新设计索引结构,从而有效提高了开发效率。

10.png

图3. 在Facebook数据集上与FILM的吞吐量和空间成本比较


       该工作提升了学习索引在磁盘上的性能和效率,推动了人工智能与数据库融合的学习型索引的发展,具有重要的理论和应用价值。本论文一作为上海期智研究院实习生、清华大学交叉信息学院博士生张缴怡。



更多信息请阅读论文:

1. GRF:A Global Range Filter for LSM-Trees with Shape Encoding, Hengrui Wang, Te Guo, Junzhao Yang, Huanchen Zhang*, SIGMOD 2024.

2. LeCo: Lightweight Compression Via Learning Serial Correlations, Yihao Liu, Xinyu Zeng, Huanchen Zhang*, SIGMOD 2024.

3. Making In-Memory Learned Indexes Efficient on Disk, Jiaoyi Zhang, Kai Su, Huanchen Zhang*, SIGMOD 2024.

4. SALI: A Scalable Adaptive Learned Index Framework based on Probability Models, Jiake Ge, Huanchen Zhang, Boyu Shi, Yuanhui Luo, Yunda Guo, Yunpeng Chai, Yuxing Chen, and Anqun Pan*, SIGMOD 2024.

5. PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware, Shuangyu Cai, Boyu Tian, Huanchen Zhang, and Mingyu Gao*, SIGMOD 2024.

分享到