Terascale Query Processing in the Browser: Rethinking GPU acceleration Jiaxin Lu∗ , Landon Dyken∗ , Yihao Sun† , Kristopher Micinski‡ , Thomas Gilray§ , and Sidharth Kumar∗ ∗ University of Illinois Chicago, Chicago, IL, USA, {jlu73, ldyke, sidharth}@uic.edu † Utah State University, Logan, UT, USA, [email protected] ‡ Syracuse University, Syracuse, NY, USA, [email protected]
arXiv:2607.17571v1 [cs.DB] 20 Jul 2026
§ Washington State University, Pullman, WA, USA, [email protected]
Abstract—Recursive query computation, central to graph algorithms and relational databases, demands GPU acceleration due to inherent computational intensity. While substantial prior work addresses GPU implementations of recursive queries, requiring fixed-point evaluation, existing systems are restricted to native execution environments. We introduce WGLog, the first web-browser-native GPU engine for compute-bound recursive database queries. WGLog is built entirely on WebGPU compute shaders, a cross-platform API that enables GPU acceleration in web browsers. WGLog leverages two key technical innovations. First, we replace hash-table-based joins with atomicfree sorted-array joins, eliminating the serialization bottleneck that hash tables suffer on skewed graphs. Second, we develop an asynchronous execution pipeline using WebGPU’s indirect dispatch capability, which eliminates GPU-host synchronizations that would otherwise dominate per-iteration overhead. On representative workloads, WGLog delivers 1.48–4.68× speedup over native GPU systems and orders of magnitude improvement over CPU and webAssembly implementations.
I. I NTRODUCTION Relational query processing with SQL excels at singlepass analytical workloads but struggles with recursion. SQL was designed for flat, acyclic computations, making recursive queries such as graph closure and transitive reachability cumbersome to express and inefficient to evaluate. Datalog [9], [10], by contrast, is a simple but expressive declarative language purpose-built for recursive queries. It powers state-ofthe-art systems across program analysis [4], [23], network and graph analytics [7], [20], and knowledge-graph reasoning [25]. These applications rely on recursive queries, a common computational pattern in which new facts are iteratively derived from existing data until saturating at a fixed point, a state where further rule application produces no new tuples. At scale, recursive queries become bandwidth-bound as iterations repeatedly stream through millions of tuples [13]. Mainstream engines such as Soufflé [23] and DDlog [18] run on CPUs and are limited by CPU memory bandwidth when closures reach tens of millions of tuples (80 million in the largest graph we evaluate [21], [24]). GPUs are a natural alternative because their high-bandwidth memory and massive parallelism match this access pattern. Recent CUDA systems confirm this potential. State-of-the-art datalog engines, mnmgJOIN [21] and GPUlog [24] accelerate TC and SG fixpoints, achieving order-of-magnitude speedups over Soufflé on large graphs.
Deploying portable implementations of Datalog outside CUDA environments remains an open problem. Both mnmgJOIN and GPUlog require NVIDIA-specific toolchains and produce native binaries, restricting deployment to systems with a CUDA driver installed. This limitation is increasingly costly as analytics shift toward on-device processing for privacy and compliance. Medical, financial, and personal-data workloads cannot upload to remote servers and must process locally. GPU computing has evolved dramatically. Once confined to specialized systems, GPUs are now ubiquitous [12]. Nearly all modern laptops contain powerful GPUs. Yet no infrastructure exists to exploit these GPUs within the portable web environment. The web browser remains disconnected from GPU acceleration despite serving billions of users daily. A GPU-accelerated database engine in the browser would close this gap, democratizing high-performance analytics and enabling users to process large datasets locally on their existing hardware without specialized toolchains or expertise. We address this gap with WGLog, the first GPU-accelerated database engine designed for browser execution, built entirely on WebGPU compute shaders. WebGPU [26] provides a portable GPU compute API that runs in browsers without driver installation. Instead of being a port of CUDA implementation WGLog is designed from scratch. A direct port of existing CUDA pipelines to WebGPU fails for two fundamental reasons. First, a naive port would inherit the hash-join serialization bottleneck at hub vertices (highdegree) that already constrains CUDA baselines on skewed graphs [21], [24]. Second, WebGPU’s record-submit-fence command model makes per-stage host synchronization expensive when repeated across hundreds of fixpoint iterations, unlike CUDA’s approach. To address both problems, WGLog redesigns the recursive evaluation pipeline entirely. Rather than using hash tables, it replaces the hash-based pipeline with a sorted-array pipeline that avoids contention at hub vertices. Additionally, it exploits the observation that Datalog’s fixpoint semantics require only a termination signal, not per-stage intermediate sizes [1]. WGLog batches multiple iterations into a single WebGPU command submission using indirect dispatch, a mechanism that lets the GPU compute its own dispatch parameters so the host never needs to read back intermediate sizes. We validate WGLog on three representative compute-bound workloads: transitive closure, same-generation
queries, and triangle counting. This paper makes the following contributions: • A sorted-array pipeline that replaces hash join with binary-search join and ordered set operations, eliminating data-skew-induced serialization (§IV). • A batched indirect-dispatch fixpoint loop that reduces GPU-host synchronization across iteration, reducing noncompute overhead to 2–4% of end-to-end time, compared with 68–70% in CUDA baselines (§V). • An implementation and evaluation of WGLog on 12 TC and 4 SG datasets, demonstrating 2.38× cumulative speedup over mnmgJOIN, 3.05× over GPULog, and 25.32× over Soufflé on the same NVIDIA GeForce RTX 3060 Laptop GPU (§VII). To our knowledge, this is the first GPU-accelerated implementation of recursive database queries for the web browser. We compare against three WebAssembly ports of popular database engines (SQLite, DuckDB, and Ascent). As expected, WGLog significantly outperforms these baselines because WebAssembly does not leverage GPU acceleration. II. BACKGROUND Datalog is a declarative logic language, where users specify what facts to derive, not how to derive them. A program consists of rules of the form: H(x̄) ← B1 (x̄1 ), . . . , Bk (x̄k ). The head H is the fact to derive; the body Bi are conditions that must hold; shared variables express joins. Each rule body represents a relational-algebra expression where the conjunction of body atoms forms a join with equality conditions on shared variables. Datalog extends relational algebra with a fixpoint operator that gives recursive rules their iterative semantics. A rule whose body references the relation it defines is recursive. Datalog’s semantics are based on fixpoint computation, where rules are repeatedly applied to the database until no new fact is derived, reaching the fixpoint [1]. An important property of these semantics is that derived relations are sets, so re-deriving an existing fact does not change the database. We illustrate fixpoint computation with Transitive Closure (TC), the running example used throughout the paper. Given a directed graph with edge relation E, TC computes the reachability relation T (x, y) using one base rule (left) and one recursive rule (right): T (x, y) ← E(x, y).
T (x, z) ← T (x, y), E(y, z).
The base rule copies each edge into T ; the recursive rule extends a known path by one hop. Consider the four-vertex chain in Figure 1 (top). The base rule seeds T with the three input edges (a, b), (b, c), (c, d). A naïve evaluator then reapplies the recursive rule to every pair in T at every iteration. Iteration 1 derives two new pairs: (a, c) from T (a, b)∧E(b, c), and (b, d) from T (b, c) ∧ E(c, d). Both are added to T . Iteration 2 again applies the rule to every pair currently in
E=
0