基于路径预取的树型索引查询优化  

Tree-based in-memory index query optimization based on path prefetching

作　　者：来逸瑞 李永坤 许胤龙[1] Lai Yirui;Li Yongkun;Xu Yinlong(School of Computer Science&Technology,University of Science&Technology of China,Hefei 230027,China)

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230027

出　　处：《计算机应用研究》2024年第10期3093-3099,共7页Application Research of Computers

摘　　要：在树型内存索引的研究过程中,由于传统的片上预取不能适应索引的局部性,导致访存成为该类型内存索引的性能瓶颈。提出了一种基于软件层面的路径预取算法,使用预取加速内存索引的访问,并使得该算法可以快速部署到现实机器上。该算法基于对树型索引访存流程的分析,通过预取表保存键与索引访问路径的关系,通过基于键切片哈希的匹配算法对预取表中的数据进行匹配,显著提高了索引性能。在当前较为先进的树型内存索引上实现了该算法并进行了实验评估,结果表明该算法在不同数据量和读写混合负载下提升了索引器的访问性能。因此,基于路径预取的算法可以有效加速树型内存索引的访存速度,提升索引器性能。In the process of researching tree-based in-memory indexes,traditional on-chip prefetching cannot adapt to the locality of index accesses,resulting in memory accesses becoming a performance bottleneck of this type of memory index.This paper proposed a path prefetching scheme at the software level to accelerate memory index accesses by prefetching,and enabled the algorithm to be quickly deployed on real machines.Based on the analysis of the tree-based indexes memory access process,this algorithm used a prefetch table to save the relationship between keys and index access paths,and matched data in the prefetch table through a matching algorithm based on key slice hashing.This paper implemented and evaluated the algorithm on current advanced tree-based memory indexes.The results indicate that it maintains stable performance improvement under different data scale and read-write-mixed workloads.Therefore,the algorithm based on path prefetching can effectively accelerate the memory access speed of tree-based in-memory index and improve index performance.

关 键 词：内存索引 预取 缓存 内存层次结构 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]