多核处理器中并行自适应索引算法优化  

Optimizing the parallel adaptive indexing algorithm on multi-core CPUs

作　　者：袁通[1] 刘志镜[1] 刘慧[1] YUAN Tong LIU Zhijing LIU Hui(School of Computer Science and Technology, Xidian Univ., Xi＇an 710071, China)

机构地区：[1]西安电子科技大学计算机学院,陕西西安710071

出　　处：《西安电子科技大学学报》2016年第5期57-62,共6页Journal of Xidian University

基　　金：国家自然科学基金资助项目(61202177)

摘　　要：针对现有的多核并行自适应索引算法不能高效地利用多核处理器的并行资源，且不能较好处理顺序查询的问题，提出了一种改进的多核并行自适应索引算法．该算法在优化现有Refined Partition Merge算法的基础上，将加锁并行方法与Refined Partition Merge算法相结合，在索引中数据块较少时，使用优化的Refined Partition Merge算法，降低线程之间冲突的概率，减少线程等待时间，提高线程利用率．当索引中数据块较多时，使用加锁并行方法，充分利用了多核处理器的并行资源．除此之外，还提出了一种提升自适应索引鲁棒性的优化方法，使多核并行自适应索引算法能够适应两种常用查询样式．实验结果表明，该算法使多核并行自适应索引在查询时间上明显降低，使查询速度提升25．7％～33．2％，并且能够适应多种常用查询样式．An improved parallel adaptive indexing algorithm on multi-core CPUs is proposed to solve the problems that the parallel adaptive indexing algorithms cannot take full advantage of the CMP＇s parallel execution resource, and properly process the sequential query pattern. Based on the optimization of the Refined Partition Merge algorithm, our improved parallel adaptive indexing algorithm combines the Parallel Database Cracking method with the Refined Partition Merge algorithm. In our algorithm, when fewer data chunks are in the index, we use the optimized Refined Partition Merge algorithm so as to reduce the probability of conflict between threads, decrease the waiting time, and increase the utilization of the threads, and when more data chunks are in the index, we use the Parallel Database Cracking method so as to take full advantage of the CMP＇s parallel execution resources. Besides, we propose an optimization for the robustness, which makes our algorithm suitable for two common query patterns. Experiments show that our method can reduce the query time by 25.7%-33.2%, and suit with common query patterns.

关 键 词：自适应索引 多核处理器 DATABASE Cracking算法 数据库系统 

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