Towards Iterative Relational Algebra on the GPU
summary
Implements a CUDA GPU backend that runs iterative relational algebra for Datalog via a custom open-addressing hash table and fused join+projection operators, with two deduplication variants and explicit pinned-memory management. On a single NVIDIA 800 GPU the hash table inserts about 400M keys/sec (up to ~4B on string graphs), powers a transitive-closure kernel, and beats cuDF and Souffl'e by as much as 10.8× vs cuDF and 3.9× vs Souffl'e on many datasets, but hits OOM on the largest graphs.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:26Data log for graph problems
- 2:32Relational algebra primitives
- 4:42Parallel join algorithms
- 6:28Transitive closure on GPU
- 7:56GPU hash table design
- 10:04Join and deduplication optimization
- 11:52Performance evaluation
- 13:40Comparison with Soufflé and cuDF
- 15:31Limitations and future work
- 16:56Conclusion
related talks
32mDeep Learning and the Relational Algebra
16mA Compiler for Fused Relational Operations on Multisets
36mOptimizing Relational Programs II
01h 06mDesign and Implementation of the RelationalAI Knowledge Graph Management System
01h 04mQuery Optimization and Acceleration at Dremio
14mDeductive Optimization of Relational Data Storage
51mPl/cuda the fusion of HPC grade power
46mKeynote: When Hardware and Databases Collide