Towards Iterative Relational Algebra on the GPU

Ahmedur Rahman Shovon, Thomas Gilray, Kristopher Micinski, Sidharth Kumar

Research output: Chapter in Book/Entry/PoemConference contribution

1 Scopus citations


Iterative relational algebra (RA kernels in a fixed-point loop) enables bottom-up logic programming languages such as Datalog. Such declarative languages are attractive targets for high-performance implementations of relational data analytics in fields such as graph mining, program analysis, and social-media analytics. Language-level constructs are implemented via high-performance relational algebra primitives (e.g., projections, reorderings, and joins). Such primitives would appear a natural target for GPUs, obtaining high throughput on large datasets. However, state-of-the-art Datalog engines are still CPU-based, scaling best between 8–16 threads. While much has explored standalone RA operations on the GPU, relatively less work focuses on iterative RA, which exposes new challenges (e.g., deduplication and memory management). In this short paper, we present a GPU-based hash-join implementation, leveraging (a) a novel open-addressing-based hash table implementation, (b) operator fusing to optimize memory access and (c) two variant implementations of deduplication. To evaluate our work, we implement transitive closure using our hash-join-based CUDA library and compared its performance against cuDF (GPU-based) and Soufflé (CPU-based). We show favorable results against both, with gains up to 10.8× against cuDF and 3.9× against Soufflé.

Original languageEnglish (US)
Title of host publicationProceedings of the 2023 USENIX Annual Technical Conference, ATC 2023
PublisherUSENIX Association
Number of pages8
ISBN (Electronic)9781939133359
StatePublished - 2023
Event2023 USENIX Annual Technical Conference, ATC 2023 - Boston, United States
Duration: Jul 10 2023Jul 12 2023

Publication series

NameProceedings of the 2023 USENIX Annual Technical Conference, ATC 2023


Conference2023 USENIX Annual Technical Conference, ATC 2023
Country/TerritoryUnited States

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Towards Iterative Relational Algebra on the GPU'. Together they form a unique fingerprint.

Cite this