Terascale Query Processing in the Browser: Rethinking GPU Acceleration

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, yihao.sun@usu.edu ‡ Syracuse University, Syracuse, NY, USA, kkmicins@syr.edu

arXiv:2607.17571v1 [cs.DB] 20 Jul 2026

§ Washington State University, Pullman, WA, USA, thomas.gilray@wsu.edu

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

D

E

F

G

i

i 1

   

VHHGIURPE

(a, b), (b, c), (c, d)

(a, c), (b, d)

(a, c), (b, d)

(a, d)

E

QHZ i

(a, d)

|T|    

Fig. 1. Transitive Closure on the running-example chain a → b → c → d. Top: the input graph contains only the blue edges E; orange paths (length 2) are derived in iteration 1 and the green path (length 3) in iteration 2. Bottom: semi-naïve evaluation joins only the new delta ∆i−1 against E at each iteration, producing ∆i until it becomes empty.

T , including (a, b) and (b, c). Because E has not changed between iterations, joining T (a, b) ∧ E(b, c) a second time produces (a, c) again, and T (b, c) ∧ E(c, d) produces (b, d) again—these are duplicates of facts already in T . Only one derivation is genuinely new: (a, d), obtained by joining the freshly-added pair T (a, c) with E(c, d). Because T is a set, the re-derivations of (a, c) and (b, d) contribute nothing. The engine performs the join, finds the result already in T , and discards it. Iteration 3 produces only such discarded rederivations, and T has reached its fixpoint of six pairs. The source of redundancy is structural. Once a pair (x, y) enters T , every subsequent iteration re-applies the rule to (x, y) and re-derives every output it can produce. On real graphs with millions of pairs in T and hundreds of iterations, this re-work dominates the cost. a) Semi-Naïve Evaluation: Semi-naïve evaluation exploits a key observation to eliminate redundancy. Each pair needs to join with E only once, immediately after it is first derived. No subsequent iterations gain new information from re-joining existing pairs, as later iterations would only rederive outputs that are already in T . The algorithm therefore maintains two disjoint relations. A full relation holding facts that have already been used as join input in earlier iterations, and a small delta ∆i holding the facts newly derived in iteration i (waiting to be used as input in the next iteration). The algorithm proceeds as follows: 1) The base rule seeds ∆0 with the input edges. 2) Iteration i joins ∆i−1 against E, producing candidate tuples. 3) From those candidates, the engine removes duplicates and subtracts those already in the full relation (set difference). 4) The surviving candidates become ∆i and are merged into the full relation. 5) Evaluation terminates when ∆i is empty. Figure 1 (bottom) traces this process on the runningexample chain. The base rule seeds ∆0 with the three input edges (a, b), (b, c), (c, d), giving |T | = 3. Iteration 1 joins ∆0 against E to produce (a, c) and (b, d); both are new, so

A. GPU Parallelism in Recursive Evaluation Each iteration of the semi-naïve loop comprises five stages: join, sort, deduplicate, set difference, and merge. All five stages are data-parallel, making them well-suited to GPU acceleration. State-of-the-art GPU systems mnmgJOIN [21] and GPULog [24], both built on NVIDIA CUDA, implement each stage as a distinct kernel. The join phase is the most compute-intensive and has become the focus of optimization. Both mnmgJOIN and GPULog implement the join using hash tables, following the classical hash join approach [21]. The base relation is inserted into a GPU-resident hash table, and each delta tuple probes it to find matching edges. Between iterations, the host reads back the delta size to decide whether fixed-point has reached or not. This readback is inexpensive under CUDA; a single cudaMemcpy of four bytes takes ∼9 µs in our measurements (§VII). Thus, per-iteration host coordination is essentially free, and the bottleneck is instead the hash join itself, which serialises on hub vertices in skewed graphs (§III). WebGPU, the portable alternative we target, departs from CUDA precisely on this assumption. B. WebGPU Compute WebGPU [26] provides a portable GPU compute API that runs in browsers and native runtimes, with shaders written in WGSL [27]. Implementations map WebGPU commands to platform backends such as Vulkan [11], Direct3D 12 [17], and Metal [2]. For recursive query evaluation, four aspects of WebGPU’s execution model are relevant to our work. Dispatch and workgroups. The basic unit of work is a compute dispatch, which launches a grid of workgroups (analogous to CUDA blocks). Each workgroup contains a fixed number of invocations (analogous to CUDA threads) that share on-chip memory and synchronise through barriers. Invocations within a workgroup are further grouped into subgroups (analogous to CUDA warps) that execute in lockstep and exchange values through intrinsics such as ballot (which gathers one bit from each invocation into a single mask) and broadcast (which propagates one invocation’s value to all others). Indirect dispatch. In a standard dispatch, the host specifies the grid dimensions. In an indirect dispatch, the GPU reads them from a buffer that a prior kernel has written. This mechanism is critical when the output size of one pipeline stage determines the grid size of the next, which is exactly the situation in each semi-naïve iteration. Command model. WebGPU follows a record–submit–fence model, where the host records dispatches into a command

'HJUHHGLVWULEXWLRQ

v1 

N

2XWGHJUHH

∆1 = {(a, c), (b, d)} and |T | = 5. Iteration 2 joins ∆1 against E: only (a, c) extends through E(c, d) to yield (a, d), since (b, d) has no outgoing edge from d; thus ∆2 = {(a, d)} and |T | = 6. Iteration 3 finds no extension for (a, d) (which also dead-ends at d), so ∆3 = ∅ and the evaluation terminates. Each iteration joins only the latest delta against E rather than the whole of T , so the per-iteration work scales as |∆i−1 | · |E| rather than |T |2 .



ORZGHJUHH YHUWLFHV

 



VORWLQGH[ FRQWHQW





9HUWH[UDQNVRUWHGE\RXWGHJUHH 



 v1

 v1

 v1

 v1

 v1

N

N





 v1

VORWV Fig. 2. Data skew in ego-Facebook. Top: log-log plot of out-degree by vertex rank (sorted high-to-low); the highest-ranked vertex has 1,043 outgoing edges. Bottom: those 1,043 edges all share the same hash key (v1 ) and occupy 1,043 consecutive slots in the hash table.

buffer, submits the buffer, and cannot observe any result until the entire buffer completes. Reading a value back requires two additional steps: copying it to a CPU-mappable staging buffer, and issuing an asynchronous mapAsync call that yields the host thread until the GPU finishes. The resulting round-trip costs ∼2.5 ms in our measurements (§VII), roughly 285× more than the equivalent CUDA cudaMemcpy. Buffer aliasing. WebGPU forbids a single buffer from appearing in two binding slots of the same compute pass when one slot is writable. Algorithms that update data in place under CUDA must instead alternate between two buffers, using a ping-pong pattern. These constraints mean that porting a CUDA-style recursive engine to WebGPU by replacing API calls one-for-one would inherit two distinct bottlenecks. The first is the hash-join bottleneck from the algorithmic design, and second being the read-back bottleneck from the command model. Together, these set the cost floor that WGLog’s redesign must beat. III. M OTIVATION Existing GPU Datalog engines [21], [24] execute semi-naïve evaluation as a host-orchestrated pipeline of joins, sorting, duplicate removal, set difference, and merge. This design assumes that hash-table accesses are close to uniform, that the host can cheaply sequence dependent GPU work, and that buffers can be updated in place. Recursive graph workloads and WebGPU violate all three assumptions. Data skew turns hash-based joins into serialized probe and retry chains (§III-A); data-dependent stage sizes force repeated host–GPU synchronization in a host-driven loop (§III-B); and WebGPU’s no-aliasing rule rejects in-place buffer updates that CUDA pipelines rely on (§III-C). The fixpoint loop repeats these costs across many iterations, so the performance problem is structural rather than an isolated slow kernel. A. Data Skew in Hash-Based Join The first issue is an algorithmic cost within the join kernel itself. Hash-based GPU joins are attractive because each delta tuple can probe the hash table independently. The assumption

+RVWGULYHQIL[SRLQWLWHUDWLRQRQHLWHUDWLRQ

D&RQVWUXFWLRQFDVFDGLQJ&$6UHWULHV KDVK WDEOH

VDPHKXEKDVKUHJLRQ 





(h, a)

(h, b)

(h, c)









T0 T1

×

T2

×

D LGOH R D MRLQ

R D VRUW

R D GHGXS

D KRVWGLVSDWFK *38NHUQHO

R D VHWGLII

R PHUJH

R UHDGEDFN

Fig. 4. Host-driven fixpoint pipeline of existing GPU Datalog engines: ∼10 host–GPU synchronisation points per iteration in both mnmgJOIN and GPULog.

×

E/RRNXSORQJOLQHDUSUREHFKDLQ VWRS

ORRNXSh KDVK WDEOH

+RVW *38 WLPH

addresses this issue with a hash-free sorted-array pipeline (addressed in §IV and evaluated in §VII-C). B. Stage-Wise Synchronization in Host-Driven Fixpoints

RWKHU

(h, * )

(h, * )

(h, * )



(h, * )

HPSW\















d = 1,043RFFXSLHGVORWV Fig. 3. Two serialisation mechanisms at a hub vertex of out-degree d. Top (construction): d concurrent threads insert edges that share the same hash key; each thread fails CAS on every already-claimed slot and retries the next, so the nth thread does n−1 retries before succeeding, producing a cascade with O(d2 ) total CAS attempts. Bottom (lookup): a probe for the hub key must walk all d consecutive occupied slots one at a time, because each slot’s load address depends on whether the previous slot matched the target key, blocking the GPU from issuing concurrent memory requests.

behind this design is that join keys distribute evenly enough for linear probing to remain close to constant time. Real graph inputs often violate that assumption: degree distributions are skewed, and a small number of vertices have out-degrees orders of magnitude larger than the median (Figure 2). In TC, all outgoing edges of a high-degree vertex share the same join key, so lookup and insertion requests for that key concentrate in the same hash-table region. This concentration creates two serialization mechanisms (Figure 3), one during hash-table construction, and one during lookup. During hash-table construction, threads inserting keys that map to the same neighborhood race to claim overlapping slots with atomic compare-and-swap (CAS). Each failed CAS advances a thread to the next slot, producing a retry chain whose length grows with the local cluster size (number of keys hashed to the same slot). During lookup, even a readonly probe must walk the same cluster through a chain of dependent memory loads. Each slot access reveals whether the target key has been found or the probe must continue to the next slot, so the address of each load depends on the result of the previous one. The GPU can therefore issue only one outstanding memory request per thread in the skewed region, rather than the many concurrent requests it would issue under uniform keys. On ego-Facebook [14], one vertex has out-degree 1,043, making the worst-case probe path scale with the largest degree rather than the average degree. GPULog rebuilds its hash index every iteration and pays both construction and lookup costs repeatedly. mnmgJOIN builds the hash table once and avoids repeated construction, but every probe of the hub vertex still walks the long lookup chain in every iteration. WGLog

The second issue is a system-level cost between kernels rather than within them. Each semi-naïve iteration contains several dependent phases, and each phase produces an output size needed by the next phase (Figure 4). In a host-driven implementation, the host must observe these device-produced sizes before it can allocate the next buffer, call a library primitive, or launch the next grid with the correct dimensions. These observations are synchronization points, where the host waits for the GPU, reads a size value, and then issues the next dependent operation. The cost is significant because recursive queries repeat the phase sequence many times. A source-level audit gives approximately 13 synchronization points per iteration for mnmgJOIN and 10–14 for GPULog. On three graphs requiring 188–426 iterations to converge, mnmgJOIN’s GPU kernels account for only 30–32% of end-to-end time. The remaining 68–70% is non-compute overhead: kernel launch latency, host– GPU synchronization, and implicit buffer allocations within Thrust [3] and CUB [15] library calls. GPULog’s non-compute fraction is lower, 21–34%, because its per-iteration GPU work is heavier, but the absolute overhead remains substantial. On SF.cedge [5], which takes 287 iterations and produces an 80M-tuple closure, thousands of host-mediated stage transitions occur in one query. WebGPU makes this issue central because its command model is record–submit–fence rather than a stream of cheap host-visible kernel launches. However, Datalog’s declarative semantics do not require the host to observe every intermediate stage size. Within one iteration, and even across several iterations, the only value the host ultimately needs for control flow is whether the delta becomes empty. WGLog addresses this issue with a batched indirect-dispatch engine that keeps intermediate sizes in GPU buffers and chains dependent stages without per-stage host readback (addressed in §V and evaluated in §VII-D). C. WebGPU Binding Rules Constrain In-Place Updates The third issue is WebGPU’s buffer binding model. CUDA implementations can often read and write the same globalmemory allocation inside one kernel or across tightly coupled library calls. WebGPU is stricter, where the same buffer range cannot serve as both the input binding and the output binding

of a single compute pass [26]. For a recursive Datalog pipeline, this rule affects every stage that transforms a relation in place, including filtering, radix-sort passes, and merge. A direct copy-back design would preserve the single-buffer abstraction, where each stage writes a temporary output and then copies it back into the input buffer expected by the next stage. That design is simple but bandwidth-expensive, and recursive queries repeat the cost across many iterations. The alternative is a ping-pong design that alternates between two physical buffers. Ping-pong avoids the extra copy but consumes more memory and forces every stage to track which side currently holds the valid relation. WGLog adopts pingpong split arrays, parity-aware radix routing, and adaptive radix width as engine-level optimizations that make the sorted pipeline practical under WebGPU’s binding rules (addressed in §V and evaluated in §VII-E). D. Implication for Design Taken together, the above three issues make clear that a browser-native Datalog engine cannot simply port the CUDA hash-based recipe. The join path should avoid mutable hashtable state under skewed keys, the fixpoint loop should avoid host observation between dependent stages, and buffer management should respect WebGPU’s no-aliasing rule without adding copy-back traffic. WGLog therefore makes three design choices. First, it represents recursive relations as sorted arrays and implements the recursive join through binary-search range lookup and ordered set operations (§IV). Second, it records batches of dependent WebGPU dispatches using indirect dispatch arguments stored in GPU buffers, so the host checks termination only at batch boundaries (§V). Third, it uses pingpong split arrays and parity-aware sort routing to avoid illegal read-write aliasing without a copy-back stage (§V). §VII-C and §VII-D evaluate the algorithmic choices in isolation, while §VII-E measures the buffer-management tradeoff directly. IV. A S ORTED -A RRAY P IPELINE WITHIN WGL OG FOR DATA -S KEW-R ESISTANT J OINS As introduced in §II, Semi-naïve evaluation iterates over a five-stage loop, which includes, join, sort, deduplicate, set difference and merge, until the delta becomes empty (fixed point reached). This section presents three sorted-array primitives that together implement the algorithmic stages without hash-table mutation, (a) a binary-search join for the join stage (§IV-A), (b) a fused kernel combining deduplication and set difference (§IV-B), and (c) a disjoint merge that incorporates the new delta into Full (§IV-C). A. Binary-Search Join §III-A showed that skewed graph degrees turn hash-based joins into CAS retry chains during construction and long dependent probe chains during lookups. WGLog gets rid of this bottleneck entirely by replacing hash-table lookup with sorted-array range queries. The key invariant is simple. The base, delta, and full relations are lexicographically sorted at every stage boundary. Sorting groups all tuples with the same

D&RXQWSKDVH

E(PLWSKDVH

OLQHDUVFDQPDWFKHV R        

T





lower_bound(3)

(a, 3)







atomicAdd(count, 4)

2QHDWRPLFXSGDWHSHUPDWFKLQJTWXSOH QRWSHUHPLWWHGWXSOH

R       





T





lower_bound(3)









(a, 3)

QHZ7  (a, 1) (a, 4) (a, 7) (a, 9)  FRQWLJXRXVVODEQRSHUPDWFKDWRPLF

Fig. 5. Binary-search join for delta tuple (a, 3): count phase locates the matching range in E; emit phase reserves one contiguous output slab and writes the matches without per-match atomics.

join key into one contiguous range, so a lookup becomes a binary search followed by a sequential scan over the exact matches rather than a walk through a hash-table collision cluster. Looking at the TC query, the recursive join pairs each newly discovered tuple (a, b) in the delta with every base edge (b, c) in E, producing candidates (a, c). WGLog sorts E once at dataset load and never modifies it, so all edges whose source is b occupy one contiguous range. For each delta tuple, the join binary-searches for the start of that range and scans forward through the matches. Two-phase algorithm. A delta tuple matching a vertex of out-degree d emits d candidates, so the total output size is unknown until the join runs. WGLog therefore splits the join into a count phase and an emit phase (Figure 5). In the count phase, each thread handles one delta tuple, finds its matching range in E, and contributes the range length to a global candidate count. In the emit phase, the thread repeats the same range lookup, reserves one contiguous output slab, and writes all candidates into that slab. The repeated search is the tradeoff for avoiding per-output coordination, where the number of coarse reservations depends on the number of delta tuples, not on the number of emitted matches. Binary search avoids the hub-vertex bottleneck. A skewed vertex with out-degree d creates a hash probe region whose cost grows with d (§III-A); on ego-Facebook [14], the largest such vertex has d = 1,043. By contrast, binary search reaches the matching range in at most ⌈log2 |E|⌉ ≤ 18 steps on our largest dataset (|E| = 223,001), after which the scan touches the d matching edges contiguously. The tradeoff is that low-degree vertices still pay the logarithmic search cost. WGLog accepts the low-degree overhead because power-law graphs concentrate much of the join work at high-degree vertices; in our ablation, replacing hash lookup with binary search improves count-and-join time by 4.4× on ego-Facebook (§VII-C). B. Fused Deduplication and Set Difference After the binary-search join, the resulting candidates are sorted before becoming the next delta. Sorting creates two useful properties: duplicate candidates become adjacent, and the full relation becomes searchable because it is also sorted by invariant. The two filters required by semi-naïve evaluation therefore become local predicates over the candidate stream:

)XVHG'HGXS6HW'LII.HUQHO &ODVVLI\

VRUWHGFDQGLGDWHWLOH

keep = unique

Full



(1, 2)

(1, 2)

(1, 4)

(2, 3)

(2, 3)

(3, 5)

(4, 1)

NHHS

GXS

LQ)XOO

NHHS

GXS

LQ)XOO

NHHS

6FDQ YDOLG VFDQ

VKDUHGPHPRU\LQFOXVLYHVFDQ  

 

 

 

 

 

 

 

thread_offset = scan[tid 1]

/RRNEDFN GHFRXSOHGORRNEDFN FURVV:*SUHIL[ :*

:*

:*

,

,

3

VWDWHEXIIHU

 3 + 3 + 9 = 15

6FDWWHU 

:*

3 

WG3 : P 3 I 15, wg_offset = 12

ZULWHVXUYLYRUVWRRXWSXW (1, 2)

pos = 12 + 1 = 13



(2, 3)

(4, 1)







The disjointness guarantee makes the merge simple. The output size is exactly |∆|+|Full |, and each workgroup’s output range is determined by its merge partition rather than by a data-dependent survivor count. The merge therefore needs no per-tuple atomics and no cross-workgroup synchronization. Disjoint inputs eliminate the post-merge cleanup pass. Semi-naïve evaluation guarantees that ∆i contains only tuples absent from the full relation before iteration i. Because the fused kernel enforces that guarantee, the merge inputs are disjoint, and the output remains a sorted set without a cleanup pass. The WebGPU buffer-routing needed to implement this merge without read-write aliasing is part of the engine design in §V.

pos = wg_offset + scan[tid 1]

FRQWLJXRXVVODE QRSHUPDWFKDWRPLF Fig. 6. The fused deduplication and set-difference kernel: classify, scan, decoupled lookback, scatter (§IV-B).

keep a tuple only if it is the first copy among adjacent equal candidates and absent from the full relation. Fusing the filters. A direct implementation materializes a deduplicated intermediate array and then reads it again for set difference. WGLog avoids that round trip by fusing both filters into one tiled kernel (Figure 6). The first dispatch computes launch parameters from the candidate count; the second dispatch streams the sorted candidates once, evaluates both predicates, and emits only survivors. Avoiding the intermediate array removes one global-memory round trip and reduces the separate-filter path from seven dispatches to two. Tiled execution. The kernel processes candidates in fixedsize tiles of 3,072 tuples (256 threads × 12 tuples per thread). Within each tile, threads classify candidates, run a workgroup prefix scan to assign local write offsets, use decoupled lookback [16] to obtain the global tile offset, and scatter survivors in input order. Because the input is sorted and each tile writes survivors in the same order, the output remains sorted for the next stage. In our ablation, this fusion cuts cumulative end-toend time by another 5.4% (§VII-E).

V. WGL OG ’ S ASYNCHRONOUS F IXPOINT E NGINE The sorted-array pipeline of §IV removes the data-skew bottleneck, but it does not by itself make the engine WebGPUnative. §III-B showed that host-driven stage transitions create repeated synchronization, and §III-C showed that WebGPU’s binding model prevents CUDA-style in-place updates. WGLog therefore follows one engine rule: the host decides when the fixpoint terminates, but the GPU decides how each stage, iteration, and buffer transition proceeds. The engine implements this rule with three mechanisms. §V-A describes the device-resident data flow of one iteration. §V-B shows how indirect dispatch removes host observation between dependent stages and batches multiple iterations into one submission. §V-C explains the ping-pong and radixrouting scheme that satisfies WebGPU’s no-aliasing rule without copy-back traffic. A. Per-Iteration Pipeline The four stages of §IV, binary-search join, radix sort, fused deduplication and set difference, and disjoint merge, compose into one fixpoint iteration (Figure 7). The join produces unsorted candidate tuples, the radix sort restores lexicographic order, and the two set-operation stages then consume sorted arrays directly. All stages operate on parallel 32-bit arrays of source and destination identifiers rather than packed 64-bit tuples, so no pack/unpack conversion is needed at stage boundaries. The important engine property is that every stage boundary is represented by buffers, not by hostvisible values. Candidate counts, filtered-delta counts, merge sizes, and indirect-dispatch arguments all remain in device memory until a batch finishes.

C. Disjoint Merge

B. Batched Indirect-Dispatch Loop

After the fused kernel produces the new delta, that delta must be merged into the full relation while preserving the sorted-set invariant. A standard Merge Path parallel merge [8] combines two sorted arrays, but it does not remove duplicates: if the same tuple appears in both inputs, both copies are emitted. WGLog avoids a post-merge deduplication pass because the fused kernel has already subtracted the full relation from the new delta. The two inputs to the merge are therefore disjoint by construction.

§III-B attributed two-thirds of mnmgJOIN’s end-to-end time to host–GPU synchronization: each stage’s output size is unknown until the stage finishes, and the host needs that size before it can dispatch the next stage. WGLog eliminates this dependency by routing every intermediate size through GPUresident buffers; the host never reads any intermediate value during a batch. Indirect dispatch. Every kernel writes its output count to a 4-byte device buffer. A lightweight kernel reads that count and

3LSHOLQHGDWDIORZLQRQHLWHUDWLRQ EDVHUHODWLRQNH\V>@YDOXHV>@

%LQDU\6HDUFK-RLQ

QH[WLWHUDWLRQ

XQVRUWHGFDQGLGDWHVNH\V>@YDOXHV>@

5DGL[6RUW

VRUWHGFDQGLGDWHVNH\V>@YDOXHV>@

)XVHG'HGXS6HW'LII

QHZ i + 1 NH\V>@YDOXHV>@

'LVMRLQW0HUJH VRUWHGXQLTXHFullNH\V>@YDOXHV>@ Fig. 7. Data flow of one fixpoint iteration: split arrays of 32-bit keys/values throughout, with no format conversion at stage boundaries. Deduplication and set difference (introduced as two separate stages are fused into a single kernel in our optimized implementation.

computes the dispatch parameters for the next stage, writing them into a second device buffer. The next stage then launches via indirect dispatch, reading its launch configuration from that buffer rather than from the host. Because both the count and the dispatch parameters live on the device, no host–GPU synchronization occurs between consecutive stages within an iteration. The same pattern carries the new delta’s size across iteration boundaries. Batched recording. Because every dispatch within and across iterations reads its parameters from device memory, the host can record K consecutive iterations into a single command buffer and submit them as one unit. The GPU executes all K iterations in sequence without returning to the host; only on completion does the host read back the per-iteration delta sizes to detect whether any reached zero (the fixpoint signal). On SF.cedge [5], which converges in 287 iterations, mnmgJOIN performs 287 × 13 ≈ 3,700 host– GPU round trips per query. With the transitive-closure default Kmax = 30, a fixed-size batch schedule would reduce the loop to ⌈287/30⌉ = 10 termination checks before any adaptive shrink adjustments. The command-model ablation in §VII-D isolates the resulting effect. Adaptive batch sizing. A larger K amortizes the per-batch submission cost over more iterations, but risks overshoot: if the fixpoint converges at iteration i, the remaining K −(i mod K) iterations dispatch on an empty delta and waste GPU time. The waste dominates on short-fixpoint datasets where K may exceed the total iteration count. For transitive closure, WGLog starts from Kmax = 30 and halves the next batch size whenever a completed batch shows strong delta decay (last-to-first size ratio below 0.1). The halving is monotonic, so near convergence the batch size shrinks to one or two iterations and limits the final empty work. For same-generation queries, whose evaluated fixpoints run for only 54–77 iterations, WGLog uses a fixed K = 10 because the adaptive policy adds little benefit on these short loops. Double-buffered submission. The host hides recording latency by building batch N +1 while the GPU executes batch N ; on batch N ’s fence, the pre-recorded batch is submitted

(if no termination is detected) or discarded. C. WebGPU Buffer Routing and Adaptive Radix Sort §III-C explained that WebGPU rejects read-write aliasing within a compute pass. The engine therefore treats every relation as a pair of physical buffers and flips roles after each stage that logically updates the relation. This ping-pong scheme turns an illegal in-place update into legal read-fromA/write-to-B or read-from-B/write-to-A passes. The cost is extra memory, but the benefit is avoiding a copy-back after every transformation. The evaluation measures this tradeoff directly in §VII-E. The fused kernel of §IV-B requires its input to be lex-sorted on (src, dst), and the disjoint merge preserves this invariant on the full relation. The join’s output, however, is unsorted, so every iteration must sort its candidate array before the fused kernel can read it. WGLog performs this sort with a GPU radix sort that processes eight bits per pass (histogram, prefix sum, scatter). Because each radix pass reads one buffer pair and writes the other, radix sort is the stage most sensitive to ping-pong routing. Adaptive bit-width selection. A 32-bit key requires four passes, a 24-bit key three, a 16-bit key two—and since each pass reads and writes the whole array, fewer passes translate directly into less memory traffic. At dataset load, WGLog scans the maximum vertex identifier and picks the narrowest width that covers it: 16 bits below 216 , 24 bits below 224 , 32 bits otherwise. In the six-dataset sort ablation, four datasets use 16-bit sorting and two use 24-bit sorting; none requires the full 32 bits. Compared with a fixed 32-bit radix, adaptive selection reduces sort time by 1.57× on average, while the end-to-end gain is smaller because sort is not the dominant stage on every dataset (§VII-E). Parity-aware buffer routing. Lexicographic sorting first orders by the destination field (the secondary key) and then by the source field (the primary key), with each field requiring two, three, or four eight-bit radix passes depending on the selected width. Each pass reads one split-array pair and writes another, so the implementation ping-pongs between an A-side and a B-side pair. Because 24-bit fields use an odd number of passes, the final output side would otherwise differ from the 16- and 32-bit cases. WGLog routes the second field’s input and output buffers according to this parity so the sorted candidates always end on the A-side pair, letting downstream stages read from fixed buffers. VI. G ENERALIZATION ACROSS DATALOG Q UERIES Datalog can express a wide range of queries beyond transitive closure, including graph reachability, ancestor relationships, social-network analyses, knowledge-graph reasoning, and triangle/clique enumeration [1], [4], [7], [20], [25]. The WGLog engine described in §IV–V is not specific to TC; the sorted-array primitives and the batched indirect-dispatch loop apply to any query expressible as a fixpoint over join, set operations, and merge over sorted relations. This section

TABLE I TC END - TO - END TIME ( MS ) ON 12 GRAPHS . |TC | IS THE CLOSURE SIZE IN TUPLES ; SPEEDUPS BELOW 1× INDICATE WGL OG IS SLOWER .

Dataset OL.cedge cal.cedge TG.cedge p2p-Gnutella09 p2p-Gnutella04 cti fe_sphere ego-Facebook luxembourg_osm wing delaunay_n16 SF.cedge

Iter. 64 195 58 20 26 53 188 17 426 11 101 287

|TC | 146,120 501,755 481,121 21,402,960 47,059,527 6,859,653 78,557,912 2,508,102 5,022,084 329,438 6,137,959 80,498,014

WGLog 68.538 155.366 55.551 239.319 537.248 127.389 1965.439 149.445 598.227 38.758 208.760 2467.678

mnmgJOIN 54.83 332.48 83.88 313.51 789.75 252.23 4972.56 164.39 1208.42 15.50 405.00 7180.45

illustrates the generality with two additional queries: samegeneration, and triangle counting. Same-Generation is a canonical bilinear recursive query, expressed as: sg(X, Y ) ← parent(X, Px ), parent(Y, Py ), sg(Px , Py ). Conceptually, this is the family-tree query. It finds pairs of nodes lying at the same generational depth, for example, siblings (one level up share a parent), cousins (two levels up share a grandparent), and so on. Each recursive step looks up two parents in the base relation rather than one base edge, and emits the cross product of the two match sets. The sortedarray pipeline, fused kernel, batched loop, and disjoint merge of §IV–V-B carry over; only two query-specific components require modification. Triangle Counting is a non-recursive three-way self-join over the edge relation: triangle(a, b, c) ← edge(a, b), edge(b, c), edge(c, a). The rule has no recursion, so the fixpoint loop reduces to a single pass. However, triangle counting stresses exactly the join bottleneck that motivated the sorted-array design: every input edge probes the edge relation by source vertex, and hub vertices serialize hash-based probes (Section III-A). Because triangle counting isolates the join from recursive scheduling, it provides the cleanest comparison between the sorted-array and hash-based approaches. Section VII-C reports head-to-head results against mnmgJOIN’s streaming hash and GPULog’s materialized hash on five SNAP graphs. VII. E VALUATION Evaluation platform. We use an NVIDIA GeForce RTX 3060 Laptop GPU with 6 GB of memory. We intentionally choose a consumer-grade laptop GPU because WGLog’s target deployment is browser-hosted analytics on personal hardware, not datacenter accelerators. The same machine runs both Chromium with WebGPU’s Dawn/D3D12 backend (subgroup and timestamp-query support enabled) and native CUDA 12.4 with the Thrust and CUB libraries. Datasets. We use two recursive query workloads, Transitive Closure (TC) and Same-Generation (SG), on graphs from

GPULog 94.78 318.50 103.32 1131.98 2654.20 401.28 5778.39 547.17 1375.92 28.29 500.34 7211.61

speedup vs. mnmgJOIN / GPULog 0.80× / 1.38× 2.14× / 2.05× 1.51× / 1.86× 1.31× / 4.73× 1.47× / 4.94× 1.98× / 3.15× 2.53× / 2.94× 1.10× / 3.66× 2.02× / 2.30× 0.40× / 0.73× 1.94× / 2.40× 2.91× / 2.92×

TABLE II SG END - TO - END TIME ( MS ) ON 4 GRAPHS . Dataset OL.cedge cal.cedge TG.cedge fe_ocean

Iter. 56 58 54 77

|SG| 285,431 23,519 608,090 65,941,441

WGLog 62.317 58.142 63.325 1998.453

mnmgJOIN 101.58 52.91 108.29 2977.80

GPULog 207.37 153.49 228.60 9614.56

vs. mnmgJOIN / GPULog 1.63× / 3.32× 0.91× / 2.64× 1.71× / 3.61× 1.49× / 4.81×

SNAP [14] and SuiteSparse [5]. The TC suite has 12 graphs spanning closure size (146K–80M tuples), iteration count (11– 426), and degree skew (ego-Facebook’s 1043-degree hub). The SG suite has 4 graphs covering the same three axes for the bilinear recursive shape (54–77 iterations, 23K–66M tuples). The triangle microbenchmark in §VII-C uses 5 SNAP graphs with maximum out-degree from 343 to 2,540. Baselines. For GPU comparison we use mnmgJOIN [21] and GPULog [24], both CUDA hash-based engines. For CPU comparison we use Soufflé as the compiled baseline and sql.js [22], Ascent WASM [19], and DuckDB-WASM [6] as browser-bound baselines. Methodology. Production runs use 10 warmup and 100 timed executions per dataset, with BATCH=30 (adaptive shrink, adaptive radix) for TC and BATCH=10 for SG. Larger ablation sweeps use 30 timed executions unless stated otherwise. End-to-end time is wall-clock query time; per-stage GPU time is measured via WebGPU timestamp queries. A. End-to-End vs. GPU SOTA We compare WGLog against the two CUDA GPU baselines on the 12 TC graphs and the 4 SG graphs. Tables I and II show end-to-end time and per-dataset speedup. WGLog runs in 6.61 s on TC and 2.18 s on SG, compared with 15.77 s and 3.23 s for mnmgJOIN, and 20.14 s and 10.21 s for GPULog. Cumulatively, WGLog is 2.38× and 1.48× faster than mnmgJOIN, and 3.05× and 4.68× faster than GPULog on TC and SG respectively. We have three observations. First, performance gains scale with closure size and iteration count. The four largest TC closures (p2p-Gnutella09 through SF.cedge, 21–80M tuples) account for ∼78% of cumulative time and yield 1.31– 2.91× wins over mnmgJOIN and 2.92–4.94× over GPULog. These workloads stress the two bottlenecks WGLog elimi-

TABLE III C UMULATIVE E2E TIME ( S ) FOR BROWSER WASM BASELINES AND A S OUFFLÉ CPU CEILING . WGL OG REFERENCE : TC 6.61, SG 2.18.

TABLE IV S ORTED - ARRAY PIPELINE ABLATIONS WITHIN WGL OG ’ S TC ENGINE . T IMES IN MS .

Baseline sql.js (browser) Ascent WASM (browser) DuckDB-WASM (browser) Soufflé (native CPU)

Design choice Sorted-array vs. hash Binary-search join

TC time 873.00 140.93 94.92 167.39

TC speedup 132.0× 21.31× 14.35× 25.32×

SG time 673.64 60.96 52.97 109.06

SG speedup 308.7× 27.94× 24.28× 50.01×

nates: hash-table contention scales with closure size and hostdriven synchronization scales with iteration count. Second, hub-skewed graphs and long-fixpoint graphs win through different mechanisms. ego-Facebook’s 1043degree hub gives WGLog a 3.66× win over GPULog by replacing hash probing with sorted range lookup. luxembourg_osm’s 426 iterations over a 5M closure give 2.02× over mnmgJOIN despite small per-iteration work, because the host loop is amortized over batches rather than paid per stage. Third, graphs with limited per-iteration work yield smaller gains. OL.cedge (146K closure) loses 0.80× to mnmgJOIN and wing (11 iterations) loses 0.40× because their useful GPU work is too small to amortize WebGPU’s fixed browser overhead. Both losses are constant overheads rather than algorithmic regressions; they are absorbed by the 9.16 s cumulative gap on the larger TC queries. SG generalization. The SG cumulative win over mnmgJOIN drops to 1.48× (from TC’s 2.38×) because SG’s bilinear cross-product fan-out gives more compute per iteration, amortizing mnmgJOIN’s hash-join overhead. Against GPULog the gap widens to 4.68× because GPULog’s materialized intermediate relations grow super-linearly with the fan-out. The single SG loss is cal.cedge, whose 23,519-tuple closure mirrors TC’s small-graph loss pattern. B. Comparison to Browser-Based Recursion Engines Browser-based deployment of recursive queries currently relies on WebAssembly CPU runtimes: database engines compiled to WASM and executed by the browser’s JavaScript engine. We compare WGLog against the three most widely-used such runtimes: sql.js [22] (a SQLite WASM port), AscentWASM [19] (a Rust Datalog port), and DuckDB-WASM [6] (an analytical-database WASM port). All three share WGLog’s zero-install deployment context but lack GPU acceleration. We additionally include Soufflé as a non-browser CPU ceiling (compiled, multi-threaded native Datalog) to bound how much of the speedup attributes to GPU acceleration versus to leaving the browser-CPU sandbox. Table III shows cumulative end-toend time and the corresponding WGLog speedup. We have two observations. First, browser-based recursive query evaluation has been CPU-only before WGLog, and the gap to every WASM runtime spans more than an order of magnitude: 14–132× on TC and 24–308× on SG. DuckDB-WASM and Ascent WASM are the most competitive browser baselines (both use specialised join engines), but neither can match a GPU at recursive scale. sql.js, the most widely-deployed browser SQL engine, lags furthest because its general-purpose recursive-CTE evaluation was not designed for the iteration counts and tuple volumes of TC/SG.

Scope 6 TC graphs ego-Facebook

Before 2153.45 42.53

After 876.94 9.69

Improvement 2.46× 4.40×

TABLE V T RIANGLE COUNTING ( END - TO - END MS ) ON FIVE SNAP GRAPHS : WGL OG SORTED - ARRAY BINARY- SEARCH VS . MNMG JOIN STREAMING HASH VS . GPUL OG MATERIALISED HASH . OOM = C U D A M A L L O C FAILURE ON THE GPUL OG T W O _ H O P INTERMEDIATE . Dataset email-Enron ca-AstroPh com-amazon soc-Slashdot0902 com-dblp

edges 367,662 396,100 1,851,744 870,161 2,099,732

max-deg 1,383 504 549 2,540 343

WGLog 37.78 17.82 26.29 152.04 38.45

mnmgJOIN 450.91 173.47 35.20 1,819.17 187.83

GPULog 45,724.4 710.7 605.9 OOM 1,235.3

Second, even Soufflé (compiled, multi-threaded, and the production native CPU Datalog standard) trails WGLog by 25.32× on TC and 50.01× on SG, showing that the speedup is not merely a consequence of escaping the browser-CPU sandbox. The widening from TC to SG reflects SG’s heavier per-iteration work, which exposes more parallelism for the GPU to exploit relative to a multi-core CPU. C. Sorted-Array Pipeline We isolate Contribution 1 in two complementary experiments. The within-pipeline ablation (Table IV) replaces sortedarray components with hash equivalents inside WGLog’s recursive engine. The triangle microbenchmark (Table V) compares the join algorithm head-to-head on a non-recursive query, removing fixpoint loop noise so the join cost is measured in isolation. We have three observations. First, replacing the hash path with sorted set operations gives the largest single gain inside the recursive pipeline, reducing six-dataset TC time from 2153.45 ms to 876.94 ms (2.46×). The improvement validates the design principle: a WebGPU engine should avoid mutable hash-table state in the recursive path. Second, the benefit concentrates on hub-skewed graphs. On ego-Facebook, replacing the hash join with a binary-search join reduces count-and-join time from 42.53 ms to 9.69 ms (4.40×) because the sorted range lookup avoids long hash probe chains at the 1043-degree hub. Third, the triangle microbenchmark confirms the gain is intrinsic to the join algorithm, not the recursive loop. WGLog is faster than mnmgJOIN on all five graphs (1.34–11.96×) and faster than GPULog on the four that complete (23.0– 1,210×). mnmgJOIN’s slowdown grows with triangle density: ca-AstroPh (20.5 triangles/edge) costs 9.74× while com-amazon (2.2 triangles/edge) only 1.34×, because each source edge triggers a longer hash-chain walk on denser graphs. GPULog incurs an additional materialisation cost: its two_hop intermediate reaches 21–51M tuples on the completed datasets, and on soc-Slashdot0902 (870K edges, hub of 2,540) it exceeds the 6 GB GPU and aborts. WGLog’s sorted-array binary-search join avoids both failure

((5XQWLPHE\6XEPLVVLRQ6WUDWHJ\ TABLE VI E NGINEERING OPTIMIZATIONS WITHIN WGL OG . T IMES IN MS .



Choice Fused dedup/diff Adaptive radix (sort) Adaptive radix (end-to-end) Ping-pong vs. copy-back

PV

 

1DLYH

%$7&+ 

PV

PV

%$7&+ 

%$7&+ 

([HFXWLRQVWUDWHJ\

Fig. 8. Effect of removing host readbacks and batching WebGPU submissions on OL.cedge. Same kernels throughout, only submission policy varies.

modes: per-hub work scales as O(d log N ) rather than O(d2 ), and there is no intermediate materialisation.

D. Batched Indirect-Dispatch Loop We isolate Contribution 2 in two experiments. The submission-policy ablation (Figure 8) varies how many readbacks per iteration the host performs while keeping all kernels identical. The batch-size sweep (Figure 9) varies the number of fixpoint iterations per command submission to find the production setting. Batch-size selection. We have three observations on the submission policy. First, host readback is the dominant cost. An empty WebGPU fence costs 0.176 ms but a 4-byte readback costs 2.503 ms, so each per-stage readback is 14.2× more expensive than a fence. A naïve port with three readbacks per iteration takes 1273.6 ms on OL.cedge; in this mode, 93.5% of end-to-end time is WebGPU synchronization rather than useful query work. Second, indirect dispatch alone gives a 4.70× speedup. Keeping each iteration in one command buffer and reading back only the termination size (BATCH=1) drops time to 271.1 ms, because indirect dispatch removes the mid-iteration readbacks used to size dependent stages. Third, multi-iteration batching gives another 3.27× on top. BATCH=10 drops time to 82.9 ms and BATCH=30 to 82.6 ms, a cumulative 15.4× reduction over the naïve port. Even one readback per iteration is too expensive, so batching multiple iterations into one submission is necessary to amortize the round trip. Batch-size selection. For TC, no single fixed batch size is best across all graphs. Short hub-heavy graphs prefer BATCH=10-30, medium graphs prefer BATCH=30-40, and long fixpoints keep improving up to BATCH=50. We select BATCH=30 as the production default because it is the largest tested setting that improves all six representative TC graphs over BATCH=20. BATCH=40 regresses three graphs and BATCH=50 regresses four graphs. Adaptive shrinking adds another 2.2% over fixed BATCH=30 on the six-graph ablation, and improves the 12-dataset cumulative time by 7.8% over the previous BATCH=10 adaptive default. For SG, BATCH=10 is best on three of four graphs because the evaluated fixpoints are only 54–77 iterations; BATCH=30 regresses by 4.8%.

Before 699.17 1353.75 4180.33 390.10

%DWFKVL]HVZHHS



Improvement 1.06× 1.57× 1.13× 1.76×

7&JUDSKVZHHS 6*JUDSKVZHHS

    

After 661.31 860.07 3686.12 221.78

7&GHIDXOW



Scope 6 TC graphs 6 TC graphs 6 TC graphs 64M-element filter

6*GHIDXOW



1RUPDOL]HG((WLPH

((WLPHPV



PV











0D[LPXPLWHUDWLRQVUHFRUGHGSHUFRPPDQGEXIIHU



Fig. 9. Batch-size ablation for TC and SG. TC needs a larger adaptive batch, while SG plateaus at BATCH=10.

E. Engineering Choices The remaining design decisions are engineering optimizations that complement the two algorithmic contributions. Table VI reports each. Fused dedup/diff. Combining deduplication and setdifference into a single kernel saves 5.4% on the six-dataset TC ablation by removing one kernel launch and one globalmemory round-trip per iteration. Adaptive radix. Auto-selecting 16/24/32-bit radix sort by maximum vertex ID reduces sort time by 1.57× but the endto-end gain is only 1.13× because sort is not the dominant stage on every dataset. 16-bit graphs save two of four passes (1.81–2.01× sort speedup), while 24-bit graphs save one pass (1.29–1.30×). Ping-pong vs. copy-back. WebGPU rejects a buffer range bound as both read-only input and writable output in the same compute pass, forcing either a copy-back fallback or a pingpong design that alternates between two buffers. At 64M elements over 100 filter passes, ping-pong takes 221.78 ms while copy-back takes 390.10 ms (extra copy adds 75.9%). WGLog chooses ping-pong because the fixpoint loop is bandwidthsensitive and repeats the same update pattern many times; the cost is 1,280 MB of additional VRAM in the production TC buffers (20.8% of the 6 GB GPU). VIII. P ORTABILITY ( AND CONCLUSION ) Thus far, we have demonstrated WGLog as a highperformance web-based database engine and the first GPUaccelerated system of its kind. Beyond raw performance, the browser platform offers portability. We demonstrate this in this section by running the identical WGLog source code on macOS without modification. Specifically, we loaded the same build that produced our Windows/D3D12 results in Chrome on an M5 Pro MacBook, validating cross-platform compatibility. We compare WGLog against other popular WebAssembly engines, sql.js [22], DuckDB-WASM [6], and Ascent [19]. On

TABLE VII TC SUITE ON BROWSER - DEPLOYABLE ENGINES , M5 P RO M AC B OOK . Engine sql.js Ascent WASM DuckDB-WASM

End-to-End (s) 463.82 78.75 50.72

vs. WGLog 112.2× 19.1× 12.3×

the 12-graph TC suite, WGLog finishes in 4.13 s; DuckDBWASM takes 50.72 s, Ascent 78.75 s, and sql.js 463.82 s, 12.3×, 19.1×, and 112.2× slower (Table VII). On the 3graph SG subset, WGLog runs in 109.89 ms vs 273.80 ms for DuckDB-WASM and 1,582.99 ms for sql.js. R EFERENCES [1] S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases. Addison-Wesley, 1995. [2] Apple, “Metal programming guide,” https://developer.apple.com/metal/, 2026. [3] N. Bell and J. Hoberock, “Thrust: A productivity-oriented library for CUDA,” in GPU Computing Gems Jade Edition, W. mei W. Hwu, Ed. Morgan Kaufmann, 2012, pp. 359–371. [4] M. Bravenboer and Y. Smaragdakis, “Strictly declarative specification of sophisticated points-to analyses,” in Proceedings of the 24th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA ’09). ACM, 2009, pp. 243–262. [5] T. A. Davis and Y. Hu, “The University of Florida sparse matrix collection,” ACM Transactions on Mathematical Software, vol. 38, no. 1, pp. 1–25, 2011. [6] DuckDB Foundation, “DuckDB-Wasm: An in-process analytical database for the browser,” https://github.com/duckdb/duckdb-wasm, 2024. [7] W. Fan, C. Hu, and C. Tian, “Incremental graph computations: Doable and undoable,” Proceedings of the ACM on Management of Data, vol. 1, no. 1, pp. 1–30, 2023. [8] O. Green, R. McColl, and D. A. Bader, “GPU merge path: A GPU merging algorithm,” in Proceedings of the 26th ACM International Conference on Supercomputing (ICS ’12). ACM, 2012, pp. 331–340. [9] T. J. Green, S. S. Huang, B. T. Loo, and W. Zhou, “Datalog and recursive query processing,” Foundations and Trends in Databases, vol. 5, no. 2, pp. 105–195, 2013. [10] S. S. Huang, T. J. Green, and B. T. Loo, “Datalog and emerging applications: an interactive tutorial,” in Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, 2011, pp. 1213–1216. [11] Khronos Group, “Vulkan specification,” https://www.khronos.org/ vulkan/, 2026. [12] D. Kirk et al., “Nvidia cuda software and gpu parallel computing architecture,” in ISMM, vol. 7, 2007, pp. 103–104. [13] S. Kumar and T. Gilray, “Distributed relational algebra at scale,” in International Conference on High Performance Computing, Data, and Analytics (HiPC). IEEE, vol. 1, 2019. [14] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014. [15] D. Merrill, “CUB: Cooperative primitives for CUDA C++,” https: //github.com/NVIDIA/cccl/tree/main/cub, 2024, NVIDIA Corporation. [16] D. Merrill and M. Garland, “Single-pass parallel prefix scan with decoupled look-back,” in GPU Technology Conference (GTC). NVIDIA, 2016. [17] Microsoft, “Direct3D 12 programming guide,” https://learn.microsoft. com/en-us/windows/win32/direct3d12/, 2026. [18] L. Ryzhyk and M. Budiu, “Differential Datalog,” in Datalog 2.0 2019, 2019, pp. 56–67. [19] A. Sahebolamri, T. Gilray, and K. Micinski, “Seamless deductive inference via macros,” in Proceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction (CC ’22). ACM, 2022, pp. 77–88. [20] J. Seo, S. Guo, and M. S. Lam, “SociaLite: Datalog extensions for efficient social network analysis,” in Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE ’13). IEEE, 2013, pp. 278–289.

[21] A. R. Shovon, T. Gilray, K. Micinski, and S. Kumar, “Towards iterative relational algebra on the GPU,” in 2023 USENIX Annual Technical Conference (USENIX ATC 23). Boston, MA: USENIX Association, Jul. 2023, pp. 1009–1016. [Online]. Available: https: //www.usenix.org/conference/atc23/presentation/shovon [22] sql.js contributors, “sql.js: A Javascript SQLite library compiled to WebAssembly,” https://github.com/sql-js/sql.js, 2024. [23] P. Subotić, H. Jordan, L. Chang, and B. Scholz, “On fast large-scale program analysis in Datalog,” in Proceedings of the 25th International Conference on Compiler Construction (CC ’16). ACM, 2016, pp. 196– 206. [24] Y. Sun, A. R. Shovon, T. Gilray, S. Kumar, and K. K. Micinski, “Optimizing Datalog for the GPU,” in Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1 (ASPLOS ’25). Rotterdam, Netherlands: ACM, Mar. 2025, pp. 762–776. [25] J. Urbani, C. J. H. Jacobs, and M. Krötzsch, “Column-oriented Datalog materialization for large knowledge graphs,” in Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI ’16). AAAI Press, 2016, pp. 258–264. [26] W3C, “WebGPU,” https://www.w3.org/TR/webgpu/, 2026, W3C Candidate Recommendation Draft. [27] W3C, “WebGPU Shading Language,” https://www.w3.org/TR/WGSL/, 2026, W3C Candidate Recommendation Draft.

Related documents

• Tailwind: A Practical Framework for Query Accelerators#155427
• UPC++: A High-Performance Communication Framework for Asynchronous Computation#814595
• WarpGuard: Towards Control-Flow Attestation for Heterogeneous CPU-GPU Execution#370276
• NUNA: Characterizing and Mitigating Non-Uniform Network Access in Multi-Die GPU Scale-Up Systems#423941
• VDCores: Resource Decoupled Programming and Execution for Asynchronous GPU#155230