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 Zhuan1,2, HAN Ruichen1,2, ZHANG Yansong1,2,3, CHEN Yueguo1,2, ZHANG Yu4   

  1. 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, 张宇4   

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

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: