Design and Optimization of Query Operator on GPU

doi:10.3778/j.issn.1002-8331.2208-0292

Abstract

Abstract: Selection, connection, projection and aggregation are the basic operations in traditional relational database. In order to realize the query optimization of relational database on GPU, the corresponding GPU algorithm must be used to realize the corresponding relational operator. Referring to the hierarchical design idea of divide and conquer of GDB, relational algebra is divided into operator layer and primitive layer. There are some difficult problems in the process of data query processing, such as data transmission delay, excessive use of shared memory, reduction of the number of active threads and communication delay caused by data communication between threads. To solve these problems, the query optimization algorithm is implemented based on the relatively new Pascal architecture. Based on the principle of the original connection, aggregation and condition selection algorithm, the corresponding algorithm is designed and optimized. The workload of each working thread is increased, the delay hiding between kernel computing and data transmission is realized, and the problem of data skew in connection operation is solved.

Key words: graphics processing unit（GPU）, Pascal architecture, query operator, primitive operation

摘要： 选择、连接、投影和聚集等是传统关系型数据库中的基本操作。为了实现关系型数据库在GPU上的查询优化，必须使用相应的GPU算法实现对应的关系算子。借鉴GDB分而治之的分层设计思想将关系代数拆分成算子层和原语层。数据查询处理过程中存在着一些难点问题，如数据传输时延、过度使用共享内存、活跃线程数减少和线程之间数据通信产生的通信时延。针对这些问题，基于较新的Pascal架构实现了查询优化算法，在原有的连接、聚集和条件选择算法原理基础上，对相应的算法进行了设计与优化。提高了每个工作线程的工作负载，实现了内核计算与数据传输之间的延迟隐藏，解决了连接操作中的数据倾斜问题。

关键词: 图形处理器（GPU）, Pascal架构, 查询算子, 原语操作

LENG Fangling, LIU Jun, WU Yingying, BAO Yubin. Design and Optimization of Query Operator on GPU[J]. Computer Engineering and Applications, 2023, 59(8): 81-88.

冷芳玲, 刘军, 吴莹莹, 鲍玉斌. GPU上的查询算子的设计与优化[J]. 计算机工程与应用, 2023, 59(8): 81-88.

References

[1] 裴威，李战怀，潘巍.GPU数据库核心技术综述[J].软件学报，2021，32（3）：859-885.
PEI W，LI Z H，PAN W.Survey of key technologies in GPU database system[J].Journal of Software，2021，32（3）：859-885.
[2] PAUL J，HE J，HE B.GPL：a GPU-based pipelined query processing engine[C]//Proceedings of the 2016 International Conference on Management of Data，2016：1935-1950.
[3] STEHLE E，JACOBSEN H A.A memory bandwidth-efficient hybrid radix sort on GPUs[C]//Proceedings of the 2017 ACM International Conference on Management of Data，2017：417-432.
[4] HE J，LU M，HE B.Revisiting co-processing for hash joins on the coupled CPU-GPU architecture[J].arXiv：1307.1955，2013.
[5] BRE? S，K?CHER B，HEIMEL M，et al.Ocelot/HyPE：optimized data processing on heterogeneous hardware[J].Proceedings of the VLDB Endowment，2014，7（13）：1609-1612.
[6] ZHANG S，HE J，HE B，et al.OmniDB：towards portable and efficient query processing on parallel CPU/GPU architectures[J].Proceedings of the VLDB Endowment，2013，6（12）：1374-1377.
[7] DOJCHINOVSKI D，GUSEV M，ZDRAVESKI V.Efficiently running SQL queries on GPU[C]//2018 26th Telecommunications Forum（TELFOR），2018：1-4.
[8] SHANBHAG A，PIRK H，MADDEN S.Efficient top-k query processing on massively parallel hardware[C]//Proceedings of the 2018 International Conference on Management of Data，2018：1557-1570.
[9] SHEHAB E，ALGERGAWY A，SARHAN A.Accelerating relational database operations using both CPU and GPU co-processor[J].Computers & Electrical Engineering，2017，57：69-80.
[10] HE B，YANG K，FANG R，et al.Relational joins on graphics processors[C]//2008 ACM SIGMOD International Conference on Management of Data，2008.
[11] SIOULAS P，CHRYSOGELOS P，KARPATHIOTAKIS M，et al.Hardware-conscious hash-joins on GPUs[C]//2019 IEEE 35th International Conference on Data Engineering（ICDE），2019：698-709.
[12] DING J，MINHAS U F，YU J，et al.ALEX：an updatable adaptive learned index[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data，2020：969-984.
[13] KARNAGEL T，MüLLER R，LOHMAN G M.Optimizing GPU-accelerated group-by and aggregation[C]//International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures，2015：13-24.
[14] DING X，LI Z.Column-stored system join optimization on coupled CPU-GPU architecture[C]//2015 4th International Conference on Computer Science and Network Technology（ICCSNT），2015：184-191.
[15] SATISH N，KIM C，CHHUGANI J，et al.Fast sort on CPUs and GPUs：a case for bandwidth oblivious SIMD sort[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data，2010：351-362.