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

doi:10.3969/j.issn.1001-2400.2016.05.011

Abstract

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

YUAN Tong;LIU Zhijing;LIU Hui. Optimizing the parallel adaptive indexing algorithm on multi-core CPUs[J].Journal of Xidian University, 2016, 43(5): 57-62.

References

［1］马艳萍, 姬光荣, 邹海林, 等. 数据依赖的多索引哈希算法［J］. 西安电子科技大学学报, 2015, 42(4): 159-164.
MA Yanping, JI Guangrong, ZOU Hailin, et al. Data-oriented Multi-index Hashing ［J］. Journal of Xidian University, 2015, 42(4): 159-164.
［2］ LEIS V, KEMPER A, NEUMANN T. The Adaptive Radix Tree: Artful Indexing for Main-memory Databases ［C］//Proceedings of the 29th International Conference on Data Engineering. Washington: IEEE Computer Society, 2013: 38-49.
［3］ IDREOS S, KERSTEN M L, MANEGOLD S. Database Cracking ［C］//3rd Biennial Conference on Innovative Data Systems Research. Asilomar: CIDR, 2007: 68-78.
［4］ GRAEFE G, HALIM F, IDREOS S, et al. Concurrency Control for Adaptive Indexing ［J］. Proceedings of the VLDB Endowment, 2012, 5(7): 656-667.
［5］ PIRK H, PETRAKI E, IDREOS S, et al. Database Cracking: Fancy Scan, Not Poor Man's Sort ［C］//10th International Workshop on Data Management on New Hardware. New York: ACM, 2014: 25-32.
［6］ IDREOS S, MANEGOLD S, KUNO H, et al. Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-memory Column-stores ［J］. Proceedings of the VLDB Endowment, 2011, 4(9): 585-597.
［7］ GRAEFE G, KUNO H. Self-selecting, Self-tuning, Incrementally Optimized Indexes ［C］//13th International Conference on Extending Database Technology. New York: ACM, 2010: 371-381.
［8］ IDREOS S, KERSTEN M, MANEGOLD S. Updating a Cracked Database ［C］//2007 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2007: 416-424.
［9］ SCHUHKNECHT F, JINDAL A, DITTRICH J. The Uncracked Pieces in Database Cracking ［J］. Proceedings of the VLDB Endowment, 2014, 7(2): 97-108.
［10］ HALIM F, IDREOS S, KARRAS P, et al. Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-memory Column-stores ［J］. Proceedings of the VLDB Endowment, 2012, 5(6): 502-513.

Optimizing the parallel adaptive indexing algorithm on multi-core CPUs

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Metrics

Comments

Recommended 10