NestGPU: Nested Query Processing on GPU
NestGPU: Nested Query Processing on GPU
复制标题
DOI：
10.1109/icde51399.2021.00092
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Sofoklis Floratos;Mengbai Xiao;Hao Wang-;Chengxin Guo;Yuan Yuan-Yuan;Rubao Lee;Xiaodong Zhang
中科院分区：
文献类型：
--
作者：
Sofoklis Floratos;Mengbai Xiao;Hao Wang-;Chengxin Guo;Yuan Yuan-Yuan;Rubao Lee;Xiaodong Zhang
嵌套查询通常用于表达复杂的用例，方法是将子查询的输出作为输入连接到外部查询块。然而，它们的执行非常耗时。研究人员提出了各种算法和技术，解开子查询，以提高性能。由于这是一个定制的方法，需要高的算法和工程努力，它在很大程度上不是一个开放的功能，在大多数现有的数据库系统。我们的方法是通用的和GPU加速的基础上，旨在以最小的开发成本高性能。我们研究嵌套和非嵌套查询结构之间的主要区别，以确定其优点和GPU处理的限制。此外，我们专注于嵌套的方法，算法简单，丰富的并行，在相对较低的空间复杂度，通用的程序结构。我们创建了一个新的代码生成框架，最适合嵌套方法的GPU。我们还进行了一些关键的系统优化，包括大规模并行扫描与索引，有效的向量化优化连接操作，利用缓存局部循环和高效的GPU内存管理。我们已经在NestGPU中实现了所提出的解决方案，NestGPU是一种基于GPU的列存储数据库系统，与GPU设备无关。我们已经广泛的评估和测试系统，以显示我们提出的方法的有效性。
Nested queries are commonly used to express complex use-cases by connecting the output of a subquery as an input to the outer query block. However, their execution is highly time-consuming. Researchers have proposed various algorithms and techniques that unnest subqueries to improve performance. Since this is a customized approach that needs high algorithmic and engineering efforts, it is largely not an open feature in most existing database systems.Our approach is general-purpose and GPU-acceleration based, aiming for high performance at a minimum development cost. We look into the major differences between nested and unnested query structures to identify their merits and limits for GPU processing. Furthermore, we focus on the nested approach that is algorithmically simple and rich in parallels, in relatively low space complexity, and generic in program structure. We create a new code generation framework that best fits GPU for the nested method. We also make several critical system optimizations including massive parallel scanning with indexing, effective vectorization to optimize join operations, exploiting cache locality for loops and efficient GPU memory management. We have implemented the proposed solutions in NestGPU, a GPU-based column-store database system that is GPU device independent. We have extensively evaluated and tested the system to show the effectiveness of our proposed methods.