Lune

ICDE2021Top-tier venue

NestGPU: Nested Query Processing on GPU

Sofoklis Floratos, Mengbai Xiao, Hao Wang, Chengxin Guo, Yuan Yuan, Rubao Lee, Xiaodong Zhang

Abstract

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 timeconsuming. 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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • FaScalSQL: A Fast and Scalable GPU-Accelerated SQL Query Engine for Out-of-Memory Tables cites GPU Database Systems Characterization and Optimization
  • FaScalSQL: A Fast and Scalable GPU-Accelerated SQL Query Engine for Out-of-Memory Tables cites Data-Parallel Query Processing on Non-Uniform Data
  • GPU Database Systems Characterization and Optimization cites Data-Parallel Query Processing on Non-Uniform Data
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. GPU Database Systems Characterization and OptimizationJiashen Cao, Rathijit Sen, Matteo Interlandi, Joy Arulraj et al.VLDB 2024 · 36 citations
  2. X-TED: Massive Parallelization of Tree Edit DistanceDayi Fan, Rubao Lee, Xiaodong ZhangVLDB 2024 · 2 citations
  3. FaScalSQL: A Fast and Scalable GPU-Accelerated SQL Query Engine for Out-of-Memory TablesChaemin Lim, Suhyun Lee, Jinwoo Choi, Kwanghyun Park et al.ICDE 2026

Builds on1

  1. Data-Parallel Query Processing on Non-Uniform DataHenning Funke, Jens TeubnerVLDB 2020 · 34 citations

Related papers

  1. A Case for Graphics-driven Query ProcessingHarish Doraiswamy, Vikas Kalagi, Karthik Ramachandra, Jayant R. HaritsaVLDB 2023 · 4 citations
  2. Nested Parquet Is Flat, Why Not Use It? How To Scan Nested Data With On-the-Fly Key Generation and JoinsAlice Rey, Maximilian Rieger, Thomas NeumannSIGMOD 2025 · 1 citation
  3. Efficient Join Algorithms For Large Database Tables in a Multi-GPU EnvironmentRan Rui, Hao Li, Yi-Cheng TuVLDB 2021 · 43 citations
  4. RayDB: Building Databases with Ray Tracing CoresXuri Shi, Kai Zhang, X. Sean Wang, Xiaodong Zhang et al.VLDB 2026 · 3 citations
  5. Efficiently Processing Joins and Grouped Aggregations on GPUsBowen Wu, Dimitrios Koutsoukos, Gustavo AlonsoSIGMOD 2025 · 15 citations
Dusk over the sea between two cliffs drawn in fine vertical lines