基于Supersonic的并行分组聚集

doi:10.11772/j.issn.1001-9081.2016.01.0013

计算机应用 ›› 2016, Vol. 36 ›› Issue (1): 13-20.DOI: 10.11772/j.issn.1001-9081.2016.01.0013

• 第32届中国数据库学术会议(NDBC 2015) • 上一篇下一篇

基于Supersonic的并行分组聚集

张兵^1,2, 孙辉^1,2, 范旭^1,2, 李翠平^1,2, 陈红^1,2, 王雯^1,2

1. 数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;
2. 中国人民大学信息学院, 北京 100872

收稿日期:2015-09-15 修回日期:2015-10-12 发布日期:2016-01-09 出版日期:2016-01-10
通讯作者: 孙辉(1977-),女,山东青岛人,讲师,博士,主要研究方向:高性能数据库、数据挖掘
作者简介:张兵(1989-),男,湖北随州人,硕士研究生,主要研究方向:面向协处理器的数据库存储和查询处理、基于多核的数据库性能;范旭(1990-),男,河北邯郸人,硕士研究生,主要研究方向:基于OLAP系统的数据查询方法、装置及系统。

Supersonic-based parallel group-by aggregation

ZHANG Bing^1,2, SUN Hui^1,2, FAN Xu^1,2, LI Cuiping^1,2, CHEN Hong^1,2, WANG Wen^1,2

1. Key Laboratory of Data Engineering and Knowledge Engineering, Ministry of Education (Renmin University of China), Beijing 100872, China;
2. School of Information, Renmin University of China, Beijing 100872, China

Received:2015-09-15 Revised:2015-10-12 Online:2016-01-09 Published:2016-01-10

摘要/Abstract

摘要： 针对在分析型联机分析处理(OLAP)应用中频繁出现的数据密集型操作符——分组聚集耗时较多的问题,提出Cache友好的分组聚集算法对该操作进行性能优化。首先,为充分发挥列存储在数据密集型计算方面的优势,采用基于开源的列存储查询执行引擎Supersonic,并在此之上设计Cache友好的分组聚集算法;其次,为加速查询的执行,使用并行技术,将单线程的分组聚集算法改为多线程并行的分组聚集算法。基于Supersonic设计并实现4种并行分组聚集算法:无共享Hash表并行分组聚集(NSHPGA)算法、表锁共享Hash表并行分组聚集(TLSHPGA)算法、桶锁共享Hash表并行分组聚集(BLSHPGA)算法、节点锁共享Hash表并行分组聚集(NLSHPGA)算法,且在不同的分组势集、不同的线程数的情况下,针对上述4种算法做了多组实验。通过对比3种不同粒度的共享Hash表并行分组聚集算法的加速比,得出NLSHPGA算法在加速比和并发度两方面表现最好,部分查询可达到10倍加速比;通过比较NSHPGA算法和NLSHPGA算法的加速比、Cache miss内存使用等情况,得出NLSHPGA算法在分组势集大于8时,加速比超过NSHPGA算法,并且Cache miss更低,使用的内存更少。

关键词: 并行分组聚集, Supersonic, 节点锁, 列存储, cache友好

Abstract: To solve the time-consuming problem of group-by aggregation operation in case of data-intense computation, a cache-friendly group-by aggregation method was proposed. In this paper, the group-by aggregation operation was optimized in two aspects. Firstly, designing cache-friendly group-by aggregation algorithm on Supersonic, an open-source and column-oriented query execution engine, to take the full advantage of column-storage on in-memory computation. Secondly, rewriting the algorithm with multi-threads to speed up the query. In this paper, four different parallel aggregation algorithms were put forward, respectively named Shared-Nothing Parallel Group-by Aggregation (NSHPGA) algorithm, Table-Lock Shared-Hash Parallel Group-by Aggregation (TLSHPGA) algorithm, Bucket-Lock Shared-Hash Parallel Group-by Aggregation (BLSHPGA) algorithm and Node-Lock Shared-Hash Parallel Group-by Aggregation (NLSHPGA) algorithm. Through a series of comparison experiment on different group power set and different number of worker threads, NLSHPGA algorithm was proved to have the best performance both on speed-up ratio and concurrency, which achieved 10x speedups on part of queries. Besides, considering Cache miss and memory utilization, the results shows that NSHPGA algorithm is suitable for smaller group power set, which was 8 in the experiment, and when getting larger, NLSHPGA algorithm performs better than NSHPGA algorithm.

Key words: parallel group-by aggregation, Supersonic, node-lock, column storage, cache-friendly

中图分类号:

TP311

张兵, 孙辉, 范旭, 李翠平, 陈红, 王雯. 基于Supersonic的并行分组聚集[J]. 计算机应用, 2016, 36(1): 13-20.

ZHANG Bing, SUN Hui, FAN Xu, LI Cuiping, CHEN Hong, WANG Wen. Supersonic-based parallel group-by aggregation[J]. Journal of Computer Applications, 2016, 36(1): 13-20.

参考文献

[1] 王珊,张延松.面向并发OLAP的数据库查询处理方法:201210113665.4 [P].2012-04-17.(WANG S, ZHANG Y S. Processing method of paralleled OLAP database: 201210113665.4 [P]. 2012-04-17.)
[2] LUDÄSCHER B, ALTINTAS I, BOWERS S, et al. Scientific process automation and workflow management [M]// SHOSHANI A, ROTEM D. Scientific Data Management: Challenges, Existing Technology, and Deployment, Computational Science Series. London: Chapman & Hall, 2009: 467-508.
[3] DIFALLAH D E, PAVLO A, CURINO C, et al. OLTP-Bench: an extensible testbed for benchmarking relational databases [J]. Proceedings of the VLDB endowment, 2013, 7(4): 277-288.
[4] BONCZ P A, ZUKOWSKI M, NES N J. MonetDB/X100: hyper-pipelining query execution [C]// CIDR 2005: Proceedings of the Second Biennial Conference on Innovative Data Systems Research. Asilomar, CA: [s.n.], 2005: 225-237.
[5] GRAEFE G. Volcano-an extensible and parallel query evaluation system [J]. IEEE transactions on knowledge & data engineering, 1994, 6(1): 120-135.
[6] WANG L, ZHOU M, ZHANG Z, et al. NUMA-aware scalable and efficient in-memory aggregation on large domains [J]. IEEE transactions on knowledge & data engineering, 2015, 27(4): 1071-1084.
[7] SHATDAL A, NAUGHTON J F. Adaptive parallel aggregation algorithms [C]// SIGMOD'95: Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data: New York: ACM, 1995: 104-114.
[8] CIESLEWICZ J, ROSS K A. Adaptive aggregation on chip multiprocessors [C]// Proceedings of the 33rd International Conference on Very Large Data Bases. [S.l.]: VLDB Endowment, 2007: 339-350.
[9] KU C, LIU Y, MORTAZAVI M, et al. Optimization strategies for column materialization in parallel execution of queries [C]// DEXA 2014: Proceedings of the 25th International Conference on Database and Expert Systems Applications. Berlin: Springer, 2014: 191-198.
[10] MACH W, SCHIKUTA E. Parallel database sort and join opera-tions revisited on grids [C]// HPCC 2007: Proceedings of the Third International Conference on High Performance Computing and Communications. Berlin: Springer, 2007: 216-227.
[11] MASSIE M L, CHUN B N, CULLER D E. The ganglia distributed monitoring system: design, implementation, and experience [J]. Parallel computing, 2004, 30(7): 817-840.
[12] CHOU J, WU K, RUBEL O, et al. Parallel index and query for large scale data analysis [C]// Proceedings of the 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. Piscataway, NJ: IEEE, 2011: 1-11.
[13] D'ANGELO G, RAMPONE S. Towards a HPC-oriented parallel implementation of a learning algorithm for bioinformatics applications [J]. BMC bioinformatics, 2014, 15(s-5): S2.
[14] OSTROVSKY I, DUFFY J, LIDDELL M, et al. Data parallel query analysis: US8266172 B2 [P]. 2012-09-11.
[15] 蒋蜀,陈佩佩,谢立.并行数据库的研究[J].计算机研究与发展,1994,31(1):1-10.(JIANG S, CHEN P P, XIE L. Research on paralleled database [J]. Journal of computer research and development, 1994, 31(1): 1-10.)

基于Supersonic的并行分组聚集

Supersonic-based parallel group-by aggregation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	高威刘丽华和斌涛邓方安. 区块链共识机制与改进算法研究进展[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	翟社平朱鹏举杨锐刘佳一腾. 基于区块链的物联网身份管理系统[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[3]	李博, 黄建强, 黄东强, 王晓英. 基于异构平台的稀疏矩阵向量乘自适应计算优化[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3867-3875.
[4]	陈姿芊, 牛科迪, 姚中原, 斯雪明. 适用于物联网的区块链轻量化技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3688-3698.
[5]	高婷婷, 姚中原, 贾淼, 斯雪明. 链上链下一致性保护技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3658-3668.
[6]	贾淼, 姚中原, 祝卫华, 高婷婷, 斯雪明, 邓翔. 零知识证明赋能区块链的进展与展望[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3669-3677.
[7]	牛科迪, 李敏, 姚中原, 斯雪明. 面向物联网的区块链共识算法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3678-3687.
[8]	蔡锦辉, 尹中旭, 宗国笑, 李俊儒. 面向嵌套分支突破的推断与污点分析融合的方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3823-3830.
[9]	杨巍白璐宁俊义董建军单春海信俊昌. 异构环境感知的幂律图流划分方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	梁辰王奕森魏强杜江. 基于Transformer-GCN的源代码漏洞检测方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	吴海峰陶丽青程玉胜. 集成特征注意力和残差连接的偏标签回归算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	秦学程刘春颜李宝赵蕴龙. 面向工业场景的云边协同数据存储与检索架构[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[13]	涂进兴, 李志雄, 黄建强. 基于GPU对角稀疏矩阵向量乘法的动态划分算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3521-3529.
[14]	曾蠡, 杨婧如, 黄罡, 景翔, 罗超然. 超图应用方法综述：问题、进展与挑战[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3315-3326.
[15]	崔双双王宏志朱加昊吴昊. 面向低能耗高性能的分类器两阶段数据选择方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.