# Optimizing Datalog for the GPU

arXiv: https://arxiv.org/abs/2311.02206 · HTML: https://mlsanity.com/paper/2311.02206/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2023.

## Built on by (most cited first, 2 of 2)

- [Boolean Matrix Logic Programming on the GPU](https://mlsanity.com/paper/2408.10369/) (2024)
- [XLOG: A CUDA-Native Engine for Neurosymbolic Integration](https://mlsanity.com/paper/2609.27203/) (2026)

## Abstract (arXiv)

Modern Datalog engines (e.g., LogicBlox, Souffl'e, ddlog) enable their users to write declarative queries which compute recursive deductions over extensional facts, leaving high-performance operationalization (query planning, semi-na"ive evaluation, and parallelization) to the engine. Such engines form the backbone of modern high-throughput applications in static analysis, network monitoring, and social-media mining. In this paper, we present a methodology for implementing a modern in-memory Datalog engine on data center GPUs, allowing us to achieve significant (up to 45x) gains compared to Souffl'e (a modern CPU-based engine) on context-sensitive points-to analysis of httpd. We present GPUlog, a Datalog engine backend that implements iterated relational algebra kernels over a novel range-indexed data structure we call the hash-indexed sorted array (HISA). HISA combines the algorithmic benefits of incremental range-indexed relations with the raw computation throughput of operations over dense data structures. Our experiments show that GPUlog is significantly faster than CPU-based Datalog engines while achieving a favorable memory footprint compared to contemporary GPU-based joins.