Optimizing Datalog for the GPU

Yihao Sun, Ahmedur Rahman Shovon, Thomas Gilray, Sidharth Kumar and Kristopher K. Micinski

Datalog is a logic language that powers program-analysis tools by grinding through huge recursive database joins, and running it fast has always meant CPUs with intricate pointer-based data structures that a GPU cannot handle; this work from Syracuse and Alabama redesigns the core data structure as a dense, sorted array with a hash index on top — GPU-friendly instead of pointer-chasing — so the whole computation runs as massively parallel GPU kernels, becoming the first GPU Datalog engine to actually beat a CPU one, by up to 45 times, while using less memory than earlier GPU approaches.

The argument in one glance

Problem

Datalog is fast on CPUs, but its data structures fight the GPU

Datalog computes recursive deductions by repeatedly joining relations until a fixpoint, powering program analysis and graph mining. Fast CPU engines use carefully-tuned linked data structures (B-trees, tries). GPUs offer huge parallel throughput for the joins, but those pointer-chasing structures cause control divergence and scattered memory access on a GPU.
What people did

Port Datalog, or a GPU join, straight to the GPU

Run Datalog on the GPU with the usual linked, indexed data structures, or lean on existing GPU join implementations to do the heavy relational work.
Why it fell short

Prior GPU Datalog was slower than CPU, or memory-hungry

The linked structures are hostile to a GPU, so previous GPU Datalog engines were actually slower than CPU engines — net-negative. And existing GPU join implementations that could do the work consumed enormous amounts of memory, limiting the data sizes they could handle.
This paper's idea

A dense, GPU-friendly relation structure (GPUlog and HISA)

GPUlog runs Datalog as iterated relational-algebra kernels over a new data structure, the Hash-Indexed Sorted Array (HISA): tuples packed densely for coalesced GPU access, a sorted index array over them for fast range queries, and a hash table built on that index (not the raw tuples) for fast lock-free deduplication at low memory. With semi-naive evaluation and two GPU-specific strategies, it is the first GPU Datalog engine to beat a CPU engine — up to 45 times faster than Souffle — with a favorable memory footprint.

Why this problem is worth solving

Datalog quietly powers a lot of serious infrastructure, precisely because it lets people describe what to compute and leave the how to the engine.

Datalog is a declarative logic language. Instead of writing an algorithm, you write high-level logical rules — for example, that two nodes are reachable if there is a direct edge between them, or if there is an edge from the first to some intermediate node that in turn reaches the second — and the engine computes every fact that follows from those rules and the input data. It works by starting from an explicit set of input facts (the extensional database) and repeatedly applying the rules to derive new facts (the intensional database), continuing until a round produces nothing new, a state called a fixpoint. When a rule’s condition mentions the same variable in two places, the engine must find all combinations that agree on it — exactly a join, as in a relational database — and Datalog’s distinctive power is that rules can be recursive, so a relation can be defined in terms of itself, as reachability is. This combination of declarative rules, joins, and recursion makes Datalog the backbone of real high-throughput systems: static program analysis (such as points-to analysis, which asks what each pointer in a program can point to), network monitoring, social-media mining, and business analytics. Modern engines like Souffle and LogicBlox let a user write the rules and handle the heavy lifting.

The heavy lifting, however, has always been tuned for CPUs, and the GPU’s raw power has stayed out of reach.

Under the hood, running a Datalog program is iterated relational algebra: performing many large join operations, over and over, until the fixpoint. Modern engines make this efficient with semi-naive evaluation, which avoids re-deriving facts it already has. It keeps each relation in three versions — the full set of all facts so far, the delta of facts newly discovered in the previous iteration, and the new facts produced this iteration — and joins only against the delta, the frontier of fresh facts, rather than the whole relation every round. This requires fast range queries (to find all tuples matching a join key), deduplication (to keep the delta unique and disjoint from the full set), and parallel iteration. CPU engines meet these needs with carefully-tuned, minimally-locking linked data structures such as B-trees and tries. Those structures are excellent on a CPU but hostile to a GPU: a GPU delivers its enormous throughput only when thousands of threads follow the same control flow and read contiguous, coalesced memory, whereas pointer-chasing through a linked tree makes threads diverge and scatters their memory accesses. As a result, earlier attempts to run Datalog on the GPU ended up slower than CPU engines, and GPU join implementations that could do the relational work consumed enormous amounts of memory.

What people did before, and where it broke

Run Datalog on the CPU with linked data structures. Use B-trees and tries, carefully tuned and minimally locking, as CPU engines like Souffle do. Where it broke. These are excellent on a CPU but leave the GPU’s massive parallel throughput entirely unused.
Port the linked structures to the GPU. Move the same pointer-chasing indexed structures onto the GPU. Where it broke. Pointer chasing causes control divergence and scattered, uncoalesced memory access, so earlier GPU Datalog engines were actually slower than CPU ones.
Use existing GPU join implementations. Lean on state-of-the-art GPU joins to do the heavy relational work. Where it broke. They consumed enormous amounts of memory, limiting the data sizes they could handle and not delivering an end-to-end Datalog win.
The gap. No design combined a dense, GPU-friendly data layout with the range queries, deduplication, and incremental evaluation Datalog needs, at a reasonable memory footprint. Providing that with the Hash-Indexed Sorted Array is what GPUlog does.

How GPUlog works

From pointer-chasing trees to a dense, index-backed GPU relation

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Give relations a dense layout the GPU can actually run fast. GPUlog’s foundation is the Hash-Indexed Sorted Array, whose bottom layer stores the relation’s tuples in a dense, contiguous array so that a GPU’s thousands of threads read coalesced memory at full throughput, instead of the pointer-chasing B-trees and tries that make CPU engines fast but cripple a GPU. Choosing a dense, hardware-friendly data representation so the accelerator runs at its native throughput, rather than porting a structure designed for a different machine, is the same move the graph-network compiler work covered elsewhere on this site makes, replacing memory-hostile access patterns with a layout the GPU can stream through efficiently so the hardware’s parallelism is actually used.

Do only the new work each round. GPUlog keeps Datalog’s incremental heart — semi-naive evaluation — joining each iteration only against the delta, the frontier of facts newly discovered in the previous round, rather than re-deriving the entire relation every time, so the engine never repeats deductions it has already made. Refusing to redo work whose result is already known, and confining each step to what is genuinely new, is the same discipline the redundant-writeback work covered elsewhere on this site follows, recognizing when an operation would only reproduce a value that already exists and skipping it so effort is spent only where something actually changes.

Index the index, not the data. The cleverness of HISA is that its hash table and its range-query ordering are built on a sorted index array of references into the dense tuples, rather than on the tuples themselves, so lookups and lock-free deduplication are fast while only unique keys need references, keeping the memory footprint small. Introducing a compact layer of indirection between the lookups and the underlying data, so a capability like ordered range access is gained without duplicating or bloating the data it points at, is the same design the handle-based memory work covered elsewhere on this site is built around, routing access through a lean level of indirection so the structure gains flexibility and efficiency the raw data alone could not provide.

Following a recursive query through GPUlog

Running a recursive analysis to a fixpoint on the GPU

A trace of GPUlog evaluating a recursive Datalog query, following the paper's HISA and semi-naive design.

Step 1 of 5

A recursive rule set over input facts

A program analysis is written in Datalog as recursive rules over an input relation, and the engine must repeatedly join relations until no new facts appear — a heavy, iterated workload.

Reachability and points-to analysis are exactly this shape.

Why it works

Datalog’s core is repeated joins to a fixpoint. Because a Datalog program derives facts by joining relations and re-applying rules until nothing new appears → the computation is dominated by many large join operations → so making joins fast and parallel is what makes Datalog fast.
CPU-style linked structures fight the GPU. Because engines traditionally use pointer-chasing B-trees and tries → those cause control divergence and uncoalesced memory that cripple a GPU → so a dense, array-backed structure is needed to exploit GPU throughput.
A sorted index gives range queries without moving data. Because joins need to find all tuples matching a key → a sorted index array over the dense tuples exposes each match as a contiguous range → so range queries are fast and the tuples stay densely packed.
Indexing the index saves memory. Because the hash table is built on the sorted index array rather than the raw tuples, storing references only for unique keys → lookups and deduplication are fast while the footprint stays small → so GPUlog uses far less memory than prior GPU joins.
Only the new frontier is recomputed. Because semi-naive evaluation joins solely against the delta of freshly-discovered facts → the engine never re-derives facts it already knows → so each iteration does only the necessary new work.

What it costs (trade-offs and scope)

Temporary materialization trades memory for time. GPUlog’s multi-way joins temporarily materialize intermediate results — a deliberate space-for-time trade the authors found crucial to scale to high data loads. It speeds the joins but uses extra memory during the computation.
It targets in-memory, GPU-resident relations. GPUlog is an in-memory engine holding relations in GPU memory. Datasets far larger than a GPU’s memory would require partitioning or multi-GPU or host-memory strategies beyond this design.
The dense structure suits Datalog’s access pattern. HISA is designed around Datalog’s needs — range queries, deduplication, delta merges. Its advantages come from matching that pattern; a workload with very different access needs would not benefit the same way.
The speedups depend on the workload and hardware. The up-to 45 times gain is on a specific comparison (an NVIDIA H100 GPU running GPUlog versus an EPYC CPU running Souffle) on a particular analysis; the reported range is 5 to 45 times, so smaller and larger gains occur, and other hardware would shift the figures.
It is a backend, given the rules. GPUlog is a Datalog engine backend implemented in CUDA; it accelerates the evaluation of Datalog programs but assumes the rules and the relational-algebra plan, rather than replacing the whole query-language front end.
Some operations still have room to improve. The paper notes areas like hash-table merging as current implementation points rather than fully optimized, so the design is a strong foundation with further engineering possible.

The evaluation

Three ways to run Datalog's recursive joins

Property	CPU Datalog (Souffle)	Prior GPU Datalog or joins
Data structure
Uses GPU parallel throughput	No, CPU only
Memory footprint	Moderate
Range queries and deduplication	Yes, via linked index	Limited
Net performance	Baseline

Three ways to run Datalog's recursive joins, as compared in the paper. CPU engines like Souffle use carefully-tuned linked structures (B-trees, tries) that are fast on a CPU but leave GPU throughput unused. Porting those structures to the GPU, or leaning on prior GPU join implementations, either ran slower than the CPU (net-negative) because pointer chasing causes control divergence and scattered memory, or used enormous memory. GPUlog runs Datalog as iterated relational-algebra kernels over the Hash-Indexed Sorted Array (HISA): a dense contiguous array of tuples for coalesced access, a sorted index array over them for fast range queries, and an open-addressing hash table built on that index (storing references only for unique keys) for fast lock-free deduplication at low memory. With semi-naive evaluation and two GPU-specific strategies (eager buffer management and temporarily-materialized multi-way joins), GPUlog is the first GPU Datalog engine to beat CPU engines net-positive, outperforming prior work by 5 to 45 times — up to 45 times faster than Souffle (an NVIDIA H100 running GPUlog versus an EPYC CPU running Souffle) on context-sensitive points-to analysis of the httpd web server — with a favorable memory footprint versus contemporary GPU joins (about 5 times better join performance).Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

GPUlog is a clean, well-motivated systems result that finally makes a stubborn workload fit the GPU. Datalog is genuinely important — it is the engine behind real static-analysis, graph-mining, and monitoring systems — and its core is iterated relational joins to a fixpoint, exactly the kind of massively parallel work a GPU should devour. The reason it did not is a data-structure mismatch: fast CPU engines rely on carefully-tuned linked structures like B-trees, and pointer chasing through them causes the control divergence and scattered memory that make a GPU crawl, so prior GPU Datalog engines were actually slower than CPU ones. The paper’s contribution is a data structure, the Hash-Indexed Sorted Array, that reconciles the two worlds: a dense contiguous array of tuples the GPU can stream through, a sorted index over it for the range queries joins need, and a hash table built on that index — not the raw tuples — for fast lock-free deduplication while keeping the memory footprint small. Combined with semi-naive evaluation, so only the frontier of new facts is joined each round, and two GPU-specific strategies for buffering and multi-way joins, this makes GPUlog the first GPU Datalog engine to be net-positive against CPU engines, up to 45 times faster than Souffle on a real points-to analysis, and with better memory behavior than prior GPU joins. Read the scope precisely. It is an in-memory, GPU-resident engine, so data far larger than GPU memory needs strategies beyond this design; its multi-way joins trade memory for speed via temporary materialization; the up-to 45 times figure is one hardware comparison within a 5-to-45-times range; and it is a backend that accelerates evaluation given the rules. The durable idea is that unlocking an accelerator for a workload is often less about a clever algorithm than about designing the data structure to the hardware’s grain — dense where the GPU wants dense, indexed where the algorithm needs indexing — so that decades of algorithmic technique like semi-naive evaluation can finally run at the accelerator’s throughput.

Background

Why the data structure, not just the algorithm, decides accelerator performance

It helps to see GPUlog within a lesson that recurs whenever a workload is moved onto an accelerator: the algorithm often ports easily, but the data structure decides whether the hardware is actually used, because accelerators reward dense, contiguous, uniform access and punish the pointer-chasing and irregularity that CPUs tolerate. Datalog’s semi-naive evaluation is the same clever algorithm on the GPU as on the CPU; what changed to make it fast was replacing linked trees with a dense, index-backed array shaped to the GPU’s appetite. The encrypted-computation acceleration work covered elsewhere on this site reflects the same principle from the arithmetic side, reshaping a workload’s representation down to how numbers are stored so that the GPU runs the operations it is built for rather than emulating ones it is not. The common thread is that on a GPU, and on accelerators generally, the memory access pattern is the performance, so the highest-leverage design decision is the layout of the data the parallel threads touch: get it dense and coalesced and the hardware flies, leave it linked and scattered and even the best algorithm stalls. As more classic CPU workloads — databases, logic engines, graph analytics — are pushed onto GPUs to exploit their throughput, the pattern GPUlog exemplifies, of co-designing a hardware-shaped data structure while preserving the algorithm’s essential techniques, is likely to be how each of them is finally made to pay off.

If you remember only three things

1. Datalog is a declarative logic language: users write high-level recursive rules and the engine computes every fact that follows by repeatedly joining relations until a fixpoint (no new facts). It powers static program analysis (like points-to analysis), graph mining, and network monitoring, and modern engines like Souffle are fast on CPUs. Their core computation is iterated relational algebra — many large joins — made efficient by semi-naive evaluation, which keeps each relation as full, delta, and new versions and joins only against the delta (the frontier of newly-discovered facts) to avoid re-deriving everything, requiring fast range queries, deduplication, and iteration. CPU engines meet these with carefully-tuned linked structures (B-trees, tries), which are hostile to a GPU because pointer chasing causes control divergence and scattered, uncoalesced memory access — so prior GPU Datalog was slower than CPU, and GPU joins used enormous memory.
2. GPUlog runs Datalog as iterated relational-algebra kernels over a new data structure, the Hash-Indexed Sorted Array (HISA), designed to fit the GPU while preserving Datalog's algorithmic benefits. HISA has three layers: a dense contiguous data array of tuples for coalesced, high-throughput GPU access; a sorted index array over the tuples that turns a join lookup into a fast contiguous range scan; and an open-addressing hash table built on that sorted index (not on the raw tuples), which stores references only for unique join keys, giving fast lock-free deduplication at low memory. Merging a deduplicated delta into the full relation is just concatenating dense arrays. GPUlog adds two GPU-specific strategies: eager buffer management (amortizing allocation) and temporarily-materialized multi-way joins (a space-for-time trade to scale to high data loads).
3. GPUlog is the first GPU Datalog engine to achieve net-positive performance versus CPU engines, outperforming prior work by 5 to 45 times — up to 45 times faster than Souffle (NVIDIA H100 versus an EPYC CPU) on context-sensitive points-to analysis of the httpd web server — with about 5 times better join performance than state-of-the-art GPU joins and a favorable memory footprint. Scope: it is an in-memory, GPU-resident engine (very large data needs other strategies), its multi-way joins trade memory for speed, the top speedup is one hardware comparison within a range, and it is a backend that accelerates evaluation given the rules. The durable lesson is that unlocking an accelerator for a workload is often less about a clever algorithm than about designing the data structure to the hardware's grain — dense where the GPU wants dense, indexed where the algorithm needs indexing — so established techniques can finally run at the accelerator's throughput.

Check yourself

Check your understanding

1. What is Datalog, and what is the core computation an engine must perform?
2. Why had running Datalog on a GPU failed to beat CPU engines before this work?
3. What is the Hash-Indexed Sorted Array (HISA), and how does its layering help?
4. What did GPUlog achieve, and what makes the result notable?

Sources

The paper is “Optimizing Datalog for the GPU” by Yihao Sun, Ahmedur Rahman Shovon, Thomas Gilray, Sidharth Kumar, and Kristopher K. Micinski, published at ASPLOS 2025, DOI 10.1145/3669940.3707274. The authors are at Syracuse University and the University of Alabama at Birmingham.

This explainer is based on the full text of the paper, obtained from the authors’ arXiv version (arXiv:2311.02206), which corresponds to the CC-BY version of record. The problem framing (Datalog as a declarative language over extensional and intensional databases, the reachability and same-generation examples, joins arising from shared variables, recursion and fixpoint computation, semi-naive evaluation with full, delta, and new relation versions to avoid re-derivation, the use of Datalog in static program analysis, graph mining, and network monitoring, and the reliance of CPU engines like Souffle on carefully-tuned linked structures such as B-trees and tries that are hostile to the GPU due to control divergence and uncoalesced memory), the GPUlog design (the Hash-Indexed Sorted Array with its dense data array, sorted index array for range queries, and open-addressing hash table built on the sorted index storing references only for unique keys; the CUDA-based engine running iterated relational-algebra kernels; and the two strategies of eager buffer management and temporarily-materialized multi-way joins), and the results (the first GPU Datalog engine to be net-positive versus CPU engines, up to 45 times faster than Souffle comparing an NVIDIA H100 to an EPYC CPU on context-sensitive points-to analysis of httpd, a 5-to-45-times improvement over prior work, about 5 times better join performance than state-of-the-art GPU joins, and a favorable memory footprint) are all drawn directly from the paper. Background explanations of Datalog, joins, semi-naive evaluation, GPUs, coalesced memory, and hash tables are standard and provided to make the paper’s contribution understandable.