"Accelerating Iterative Relational Algebra Operations with WebGPU (poster)"

Accelerating Iterative Relational Algebra Operations with WebGPU (poster)

Lu, J., Kumar, S.

• Publication: Chicago, IL
• Link: https://gcasr.org/2025/posters
• PDF: jiaxin.pdf

Bottom‐up logic programming (e.g., Datalog) runs via repeated relational‐algebra kernels - selection, projection, join, and reorder - until no new facts emerge. While GPUs promise massive parallelism for these primitives, existing engines remain CPU-bound (8–16 threads) and struggle with deduplication and growing result sets.

We introduce a WebGPU-based hash-join pipeline that:

• Maps each RA primitive (hash‐join, GPU radix sort, deduplication, set difference, insertion into the full relation) to its own WGSL compute shader
  
• Uses dynamic, growable GPU buffers and load-factor-tuned hash tables for memory management
  
• Drives a delta-only fixed-point loop, processing only newly discovered tuples each iteration