Database star-join optimization for multicore CPU and GPU platforms

doi:10.11772/j.issn.1001-9081.2020091430

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (3): 611-617.DOI: 10.11772/j.issn.1001-9081.2020091430

Special Issue: 第37届CCF中国数据库学术会议(NDBC 2020)

• The 37th CCF National Database Conference (NDBC 2020) • Next Articles

Database star-join optimization for multicore CPU and GPU platforms

LIU Zhuan^1,2, HAN Ruichen^1,2, ZHANG Yansong^1,2,3, CHEN Yueguo^1,2, ZHANG Yu⁴

1. Key Laboratory of Data Engineering and Knowledge Engineering(Renmin University of China), Beijing 100872, China;
2. School of Information, Renmin University of China, Beijing 100872, China;
3. National Survey Research Center at Renmin University of China, Beijing 100872, China;
4. National Satellite Meteorological Center, China Meteorological Administration, Beijing 100081, China

Received:2020-09-07 Revised:2020-10-16 Online:2021-03-10 Published:2020-12-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61772533, 61732014), the Natural Science Foundation of Beijing (4192066).

面向多核CPU和GPU平台的数据库星形连接优化

刘专^1,2, 韩瑞琛^1,2, 张延松^1,2,3, 陈跃国^1,2, 张宇⁴

1. 数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;
2. 中国人民大学信息学院, 北京 100872;
3. 中国人民大学中国调查与数据中心, 北京 100872;
4. 中国气象局国家卫星气象中心, 北京 100081

通讯作者: 张延松
作者简介:刘专(1996-),男,贵州六盘水人,硕士研究生,主要研究方向:OLAP查询优化、内存数据库、异构计算平台优化、数据仓库;韩瑞琛(1997-),男,湖南常德人,硕士研究生,CCF会员,主要研究方向:内存数据库、内存OLAP、新硬件数据库;张延松(1973-),男,黑龙江牡丹江人,副教授,博士,CCF会员,主要研究方向:内存数据库、GPU数据库、新硬件数据库;陈跃国(1978-),男,辽宁盖州人,教授,博士,CCF会员,主要研究方向:大数据分析、信息检索、知识图谱;张宇(1977-),女,黑龙江绥化人,高级工程师,博士,主要研究方向:数据仓库、GPU数据库。
基金资助:
国家自然科学基金资助项目（61772533，61732014）；北京市自然科学基金资助项目（4192066）。

Abstract

Abstract: Focusing on the high execution cost of star-join between the fact table and multiple dimension tables in On-line Analytical Processing (OLAP), a star-join optimization technique was proposed for advanced multicore CPU (Central Processing Unit) and GPU (Graphics Processing Unit). Firstly, the vector index based vectorized star-join algorithm on CPU and GPU platforms was proposed for the intermediate materialization cost problem in star-join in multicore CPU and GPU platforms. Secondly, the star-join operation based on vector granularity was presented according to the vector division for CPU cache size and GPU shared memory size, so as to optimize the vector index materialization cost in star-join. Finally, the compressed vector index based star-join algorithm was proposed to compress the fixed-length vector index to the variable-length binary vector index, so as to improve the storage access efficiency of the vector index in cache under low selection rate. Experimental results show that the vectorized star-join algorithm achieves more than 40% performance improvement compared to the traditional row-wise or column-wise star-join algorithms on multicore CPU platform, and the vectorized star-join algorithm achieves more than 15% performance improvement compared to the conventional star-join algorithms on GPU platform; in the comparison with the mainstream main-memory databases and GPU databases, the optimized star-join algorithm achieves 130% performance improvement compared to the optimal main-memory database Hyper, and achieves 80% performance improvement compared to the optimal GPU database OmniSci. It can be seen that the vector index based star-join optimization technique effectively improves the multiple table join performance, and compared with the traditional optimization techniques, the vector index based vectorized processing improves the data storage access efficiency in small cache, and the compressed vector further improves the vector index access efficiency in cache.

Key words: On-Line Analytical Processing (OLAP), star-join, vectorized query processing, vector compression technique, heterogeneous computing

摘要： 针对联机分析处理（OLAP）中事实表与多个维表之间的星形连接执行代价较高的问题，提出了一种在先进的多核中央处理器（CPU）和图形处理器（GPU）上的星形连接优化方法。首先，对于多核CPU和GPU平台的星形连接中的物化代价问题，提出了基于向量索引的CPU和GPU平台上的向量化星形连接算法；然后，通过面向CPU cache和GPU shared memory大小的向量划分来提出基于向量粒度的星形连接操作，从而优化星形连接中向量索引的物化代价；最后，提出了基于压缩向量的星形连接算法，将定长向量索引压缩为变长的二元向量索引，从而在低选择率时提高cache内向量索引的存储访问效率。实验结果表明，在CPU平台上向量化星形连接算法相对于常规的行式或列式连接性能提升了40%以上，在GPU平台上向量化星形连接算法相对于常规星形连接算法性能提升超过了15%；与当前主流的内存数据库和GPU数据库相比，优化的星形连接算法性能相对于最优内存数据库Hyper性能提升了130%，相对于最优的GPU数据库OmniSci性能提升了80%。可见基于向量索引的向量化星形连接优化技术有效地提高了多表连接性能，与传统优化技术相比，基于向量索引的向量化处理提高了较小cache上的数据存储访问效率，压缩向量进一步提升了向量索引在cache内的访问效率。

关键词: 联机分析处理, 星形连接, 向量化查询处理, 向量压缩技术, 异构计算

CLC Number:

TP311

LIU Zhuan, HAN Ruichen, ZHANG Yansong, CHEN Yueguo, ZHANG Yu. Database star-join optimization for multicore CPU and GPU platforms[J]. Journal of Computer Applications, 2021, 41(3): 611-617.

刘专, 韩瑞琛, 张延松, 陈跃国, 张宇. 面向多核CPU和GPU平台的数据库星形连接优化[J]. 计算机应用, 2021, 41(3): 611-617.

References

[1] ZHANG Y,ZHOU X,ZHANG Y,et al. Virtual denormalization via array index reference for main memory OLAP[J]. IEEE Transactions on Knowledge and Data Engineering,2016,28(4):1061-1074.
[2] BALKESEN C,TEUBNER J,ALONSO G,et al. Main-memory hash joins on multi-core CPUs:tuning to the underlying hardware[C]//Proceedings of the 29th International Conference on Data Engineering. Piscataway:IEEE,2013:362-373.
[3] SHANBHAG A,MADDEN S,YU X. A study of the fundamental performance characteristics of GPUs and CPUs for database analytics[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York:ACM,2020:1617-1632.
[4] BLANAS S,LI Y,PATEL J M. Design and evaluation of main memory hash join algorithms for multi-core CPUs[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York:ACM,2011:37-48.
[5] BALKESEN C,ALONSO G,TEUBNER J,et al. Multi-core,mainmemory joins:sort vs. hash revisited[J]. Proceedings of the VLDB Endowment,2013,7(1):85-96.
[6] RICHTER S,ALVAREZ V,DITTRICH J. A seven-dimensional analysis of hashing methods and its implications on query processing[J]. Proceedings of the VLDB Endowment,2015,9(3):96-107.
[7] SCHUH S,CHEN X,DITTRICH J. An experimental comparison of thirteen relational equi-joins in main memory[C]//Proceedings of the 2016 International Conference on Management of Data. New York:ACM,2016:1961-1976.
[8] CHNEG X,HE B,DU X,et al. A study of main-memory hash joins on many-core processor:a case with Intel knights landing architecture[C]//Proceedings of the 2017 ACM Conference on Information and Knowledge Management. New York:ACM,2017:657-666.
[9] HE B,YANG K,FNAG R,et al. Relational joins on graphics processors[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. New York:ACM,2008:511-524.
[10] BREB S,HEIMEL M,SIEGMUND N,et al. GPU-accelerated database systems:survey and open challenges[M]//PALPANAS T,POKORNÝ J,VAKALI A. Transactions on Large-Scale Dataand Knowledge-Centered Systems XV:Selected Papers from ADBIS 2013 Satellite Events,LNCS 8920. Berlin:Springer, 2014:1-35.
[11] HE J,LU M,HE B. Revisiting co-processing for hash joins on the coupled CPU-GPU architecture[J]. Proceedings of the VLDB Endowment,2013,6(10):889-900.
[12] AREFYEVA I,BRONESKE D,CAMPERO G,et al. Memory management strategies in CPU/GPU database systems:a survey[C]//Proceedings of the 2018 International Conference:Beyond Databases, Architectures and Structures, CCIS 928. Cham:Springer,2018:128-142.
[13] SCHMIDT C,UFLACKER M. Workload-driven data placement for GPU-accelerated database management systems[C]//Proceedings of the 2019 Database Systems for Business, Technology and Web. Bonn,Germany:[s. n.],2019:91-94.
[14] YABUTA M,NGUYEN A,KATO S,et al. Relational joins on GPUs:a closer look[J]. IEEE Transactions on Parallel and Distributed Systems,2017,28(9):2663-2673.
[15] SIOULAS P,CHRYSOGELOS P,KARPATHIOTAKIS M,et al. Hardware-conscious hash-joins on GPUs[C]//Proceedings of the IEEE 35th International Conference on Data Engineering. Piscataway:IEEE,2019:698-709.
[16] RUI R,LI H,TU Y. Join algorithms on GPUs:a revisit after seven years[C]//Proceedings of the 2015 International Conference Big Data. Piscataway:IEEE,2015:2541-2550.
[17] HU X X,XI J Q,TANG D Y. Optimization for multi-join queries on the GPU[J]. IEEE Access,2020,8:118380-118395.
[18] SOMPOLSKI J,ZUKOWSKI M,BONCZ P. Vectorization vs. compilation in query execution[C]//Proceedings of the 7th International Workshop on Data Management on New Hardware. New York:ACM,2011:33-40.
[19] CHRYSOGELOS P,KARPATHIOTAKIS M,APPUSWAMY R, et al. HetExchange:encapsulating heterogeneous CPU-GPU parallelism in JIT compiled engines[J]. Proceedings of the VLDB Endowment,2019,12(5):544-556.
[20] 张延松, 张宇, 王珊. 一种基于向量索引的内存OLAP星型连接加速新技术[J]. 计算机学报,2019,42(8):1686-1703. (ZHANG Y S,ZHANG Y,WANG S. A novel in-memory OLAP star join acceleration technique with vector index[J]. Chinese Journal of Computers,2019,42(8):1686-1703.)

Database star-join optimization for multicore CPU and GPU platforms

面向多核CPU和GPU平台的数据库星形连接优化

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

[1]	WANG Guan, WANG Yuxin, CHEN Xin, WANG Fei, GUO He. Heterogeneous scheduling algorithm with immediate successor finish time [J]. Journal of Computer Applications, 2017, 37(1): 12-17.
[2]	LIU Xinrui, REN Fengyu, LEI Guoping. Research of domain ontology driven enterprise on-line analytical processing systems [J]. Journal of Computer Applications, 2016, 36(1): 254-259.
[3]	. Synthesized heuristic task scheduling algorithm for heterogeneous system [J]. Journal of Computer Applications, 2010, 30(05): 1316-1320.
[4]	. Independent tasks scheduling algorithm based on dynamic fit degree [J]. Journal of Computer Applications, 2006, 26(12): 3001-3003.