Accelerating Iterative Relational Algebra Operations with WebGPU (poster)

Lu, J.,Kumar, S.

Location: 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

Citation: Lu, J., Kumar, S., Accelerating Iterative Relational Algebra Operations with WebGPU (poster), The 12th Greater Chicago Area Systems Research Workshop (GCASR), Chicago, IL, 2025-05-08. https://gcasr.org/2025/posters