Skip to content
The methodOpen data
Back to the collection

Optimizing Datalog for the GPU

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

2023 · arXiv

AlgorithmsDatabasesMathematics
Read the paper
HN score
0
Mentions
4
Readers
4
Months
4
What’s in a score?

From the abstract

Modern Datalog engines (e.g., LogicBlox, Soufflé, ddlog) enable their users to write declarative queries which compute recursive deductions over extensional facts, leaving high-performance operationalization (query planning, semi-naïve 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é (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.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

4 selected excerpts · 4 total mentions

lmeyerov
Neutral mention · rule
arxiv: https://arxiv.org/html/2311.02206v5 I've been a fan of this series! The work by this team, as well as kuzudb (acquired by apple) and relational.ai, have similar vibes. One area that has been especially interesting to me is identifying cases where new kinds of vector-friendly join operators are helpful . We've been doing a very different kind of oss gpu graph query language & engine (gfql), where we're solving how to turn declarative cypher property graph queries on big parquets / sql db results / etc -> query plans over scalable cpu/gpu dataframe operations that trounce neo4j etc at a fraction of the time & cost and without needing a DB, and these join algorithm results carry over quite enticingly despite not being datalog.
Original comment Optimizing Datalog for the GPU
cmrdporcupine
Neutral mention · rule
So much of the "magic" with Prolog and similar relational languages necessarily happens with dynamic data at runtime (especially in a game engine where entities move around, etc so the state of relations changes significantly) I'm not sure how much static you could get with it. That said, there's plenty of research in the DB world on precompiled and JITted query execution plans. All of that would apply to a Prolog or Datalog engine as well. Also, a personal interest of mine I keep wanting to come back to is how much one can make use of GPU and TPU hardware to accelerate the joins that go on in these systems. There are people working in this space already:…
Read the full comment
https://arxiv.org/html/2311.02206v3 but I believe their emphasis is on large scale data sets (e.g. big data graphs) whereas I'm curious to see if there's a way that an approach using HW acceleration could make low latency "OLTP" type applications possible for applications like robotics/vehicle autonomy/games, using complex rule sets. I watch my son play Dwarf Fortress and I'm like... it needs a Prolog.
Original comment Game Programming in Prolog
westurner
Neutral mention · rule
"GDlog: A GPU-Accelerated Deductive Engine" (2023) https://arxiv.org/abs/2311.02206 : > Abstract: Modern deductive database engines (e.g., LogicBlox and Soufflé) enable their users to write declarative queries which compute recursive deductions over extensional data, leaving their high-performance operationalization (query planning, semi-naïve evaluation, and parallelization) to the engine. Such engines form the backbone of modern high-throughput applications in static analysis, security auditing, social-media mining, and business analytics. State-of-the-art engines are built upon nested loop joins over explicit representations (e.g., BTrees and tries) and ubiquitously…
Read the full comment
employ range indexing to accelerate iterated joins. In this work, we present GDlog: a GPU-based deductive analytics engine (implemented as a CUDA library) which achieves significant performance improvements (5--10x or more) versus prior systems. GDlog is powered by a novel range-indexed SIMD datastructure: the hash-indexed sorted array (HISA). We perform extensive evaluation on GDlog, comparing it against both CPU and GPU-based hash tables and Datalog engines, and using it to support a range of large-scale deductive queries including reachability, same generation, and context-sensitive program analysis . Our experiments show that GDlog achieves performance competitive with modern SIMD hash tables and beats prior work by an order of magnitude in runtime while offering more favorable memory footprint.
Original comment GDlog: A GPU-Accelerated Deductive Engine

Keep following the thread.

More in Algorithms

More from the same topics.

1994arXiv

On proof and progress in mathematics

William P. Thurston

In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.

Mathematics
29 mentions21 months
9HN score
2017arXiv

The Case for Learned Index Structures

Tim Kraska, Alex Beutel, Ed H. Chi +2

Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not.

Databases
19 mentions14 months
5HN score