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

Abstract:

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.

Key words: adaptive indexing, multicore processors, database cracking algorithm, database system