基于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-10 发布日期:2016-01-09
通讯作者: 孙辉(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-10 Published:2016-01-09

摘要/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]. 《计算机应用》唯一官方网站, 2021, 41(11): 3394-3401.
[2]	祁祥洲邢红杰. 基于中心核对齐的多核单类支持向量机[J]. 计算机应用, 0, (): 0-0.
[3]	陈浩杰，范江亭，刘勇. 分布式强化学习解决动态旅行商问题[J]. 计算机应用, 0, (): 0-0.
[4]	郭一阳于炯杜旭升杨少智曹铭. 基于自编码器与集成学习的离群点检测算法[J]. 计算机应用, 0, (): 0-0.
[5]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[6]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[7]	张妮韩萌王乐李小娟程浩东. 基于正负效用划分的高效用模式挖掘方法综述[J]. 计算机应用, 0, (): 0-0.
[8]	武鹏, 吴尽昭. 基于线性误差断言的推理方法[J]. 计算机应用, 2021, 41(8): 2199-2204.
[9]	王梓森, 梁英, 刘政君, 谢小杰, 张伟, 史红周. 科研项目同行评议专家学术专长匹配方法[J]. 计算机应用, 2021, 41(8): 2418-2426.
[10]	赵全, 汤小春, 朱紫钰, 毛安琪, 李战怀. 大规模短时间任务的低延迟集群调度框架[J]. 计算机应用, 2021, 41(8): 2396-2405.
[11]	康军, 黄山, 段宗涛, 李宜修. 时空轨迹序列模式挖掘方法综述[J]. 计算机应用, 2021, 41(8): 2379-2385.
[12]	陈静, 毛莺池, 陈豪, 王龙宝, 王子成. 基于改进单点多盒检测器的大坝缺陷目标检测方法[J]. 计算机应用, 2021, 41(8): 2366-2372.
[13]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 计算机应用, 2021, 41(8): 2232-2241.
[14]	孙蕊, 韩萌, 张春砚, 申明尧, 杜诗语. 含负项top-k高效用项集挖掘算法[J]. 计算机应用, 2021, 41(8): 2386-2395.
[15]	李莉吴怡杨祉坤陈云鹏. 基于分区型区块链医疗电子病历共享方案[J]. , 0, (): 0-0.