Supersonic-based parallel group-by aggregation

doi:10.11772/j.issn.1001-9081.2016.01.0013

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (1): 13-20.DOI: 10.11772/j.issn.1001-9081.2016.01.0013

Previous Articles Next Articles

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

基于Supersonic的并行分组聚集

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

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

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

Abstract

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

摘要： 针对在分析型联机分析处理(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友好

CLC Number:

TP311

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.

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

References

[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-based parallel group-by aggregation

基于Supersonic的并行分组聚集

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	. Research advances in blockchain consensus mechanisms and improvement algorithms [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	. Blockchain-based identity management system for internet of things [J]. Journal of Computer Applications, 0, (): 0-0.
[3]	Bo LI, Jianqiang HUANG, Dongqiang HUANG, Xiaoying WANG. Adaptive computing optimization of sparse matrix-vector multiplication based on heterogeneous platforms [J]. Journal of Computer Applications, 2024, 44(12): 3867-3875.
[4]	Ziqian CHEN, Kedi NIU, Zhongyuan YAO, Xueming SI. Review of blockchain lightweight technology applied to internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3688-3698.
[5]	Tingting GAO, Zhongyuan YAO, Miao JIA, Xueming SI. Overview of on-chain and off-chain consistency protection technologies [J]. Journal of Computer Applications, 2024, 44(12): 3658-3668.
[6]	Miao JIA, Zhongyuan YAO, Weihua ZHU, Tingting GAO, Xueming SI, Xiang DENG. Progress and prospect of zero-knowledge proof enabling blockchain [J]. Journal of Computer Applications, 2024, 44(12): 3669-3677.
[7]	Kedi NIU, Min LI, Zhongyuan YAO, Xueming SI. Review of blockchain consensus algorithms for internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3678-3687.
[8]	Jinhui CAI, Zhongxu YIN, Guoxiao ZONG, Junru LI. Integrated method of inference and taint analysis for nested branch breakthrough [J]. Journal of Computer Applications, 2024, 44(12): 3823-3830.
[9]	. Heterogeneous Environment Aware Streaming Graph Partitioning for Power-Law Graphs [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Source code vulnerability detection method based on Transformer-GCN [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. Partial label regression algorithm integrating feature attention and residual connection [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	. Cloud-edge collaborative data storage and retrieval architecture for industrial scenarios [J]. Journal of Computer Applications, 0, (): 0-0.
[13]	Jinxing TU, Zhixiong LI, Jianqiang HUANG. Dynamic partition algorithm for diagonal sparse matrix vector multiplication based on GPU [J]. Journal of Computer Applications, 2024, 44(11): 3521-3529.
[14]	Li ZENG, Jingru YANG, Gang HUANG, Xiang JING, Chaoran LUO. Survey on hypergraph application methods： issues， advances， and challenges [J]. Journal of Computer Applications, 2024, 44(11): 3315-3326.
[15]	. Two-stage data selection method for classifier with high performance and low energy consumption [J]. Journal of Computer Applications, 0, (): 0-0.