Terascale Query Processing in the Browser: Rethinking GPU Acceleration

Source: arXiv:2607.17571 · Published 2026-07-20 · By Jiaxin Lu, Landon Dyken, Yihao Sun, Kristopher Micinski, Thomas Gilray, Sidharth Kumar

TL;DR

This paper addresses the challenge of efficiently processing recursive database queries—such as transitive closure and same-generation relations—in web browsers by leveraging GPU acceleration via WebGPU, an emerging cross-platform web GPU API. Existing GPU-accelerated recursive query engines rely on native CUDA-based approaches that cannot run in browsers due to driver and API constraints. WGLog is the first fully browser-native GPU engine for compute-bound recursive queries, designed from the ground up to overcome the limitations of prior work in browser contexts. Its core innovations include replacing traditional hash-table joins with contention-free sorted-array joins and eliminating costly per-iteration GPU-host synchronization through an asynchronous indirect-dispatch pipeline. WGLog achieves substantial speedups (1.48–4.68×) over state-of-the-art native GPU Datalog engines (mnmgJOIN and GPULog) on large graph workloads executed on a GeForce RTX 3060 Laptop GPU, while vastly outperforming CPU and WebAssembly alternatives not leveraging GPUs. This work thus pioneers practical terascale-scale GPU-accelerated recursive query processing within browsers, democratizing performant graph and relational computation without platform-specific dependencies.

Key findings

• WGLog delivers a 1.48–4.68× speedup over native GPU Datalog engines mnmgJOIN and GPULog on representative recursive query workloads including transitive closure and same-generation queries.
• WGLog reduces non-compute overhead (host–GPU synchronizations and kernel launch latency) to 2–4% of end-to-end execution time compared with 68–70% overhead in mnmgJOIN.
• Replacing hash-table joins with atomic-free sorted-array joins improves count-and-join time by 4.4× on ego-Facebook graph (largest vertex out-degree 1,043) by eliminating serialization bottlenecks from high-degree hubs.
• The asynchronous batched indirect-dispatch engine allows grouping multiple iterations into a single command buffer submission, reducing up to 3,700 host–GPU round-trips to as few as 10 per query on large fixpoints with hundreds of iterations.
• Fusing deduplication and set-difference kernels into one stage yields a 5.4% cumulative end-to-end speedup by reducing global memory roundtrips and dispatch overhead.
• Ping-pong buffer management with parity-aware radix routing obeys WebGPU’s no-read-write aliasing rules without expensive copy-back overhead.
• WGLog consistently outperforms three WebAssembly ports of popular database engines (SQLite, DuckDB, and Ascent), confirming the large performance impact of native GPU acceleration in browsers.
• On an NVIDIA RTX 3060 Laptop GPU, WGLog achieves 2.38× speedup over mnmgJOIN, 3.05× over GPULog, and 25.32× over CPU-based Soufflé on 12 transitive closure and 4 same-generation datasets.

Threat model

The adversary is any user or application requiring efficient execution of recursive queries on large graph-structured data within web browsers without native GPU support or CUDA driver dependencies. The capabilities include availability of a WebGPU-compatible GPU device, but the adversary cannot access or modify the underlying GPU drivers or native system software. The system assumes a benign environment focused on performance constraints rather than hostile adversarial tampering or side-channel attacks.

Methodology — deep read

1. Threat Model & Assumptions: WGLog targets an adversary scenario where recursive queries operate on large graph-structured datasets within untrusted web environments, with no assumptions of special driver support or native CUDA binaries. The threat model centers on overcoming inherent computational bottlenecks and environment constraints rather than adversarial attackers. The adversary is any user wanting to perform complex recursive graph queries in-browser without native GPU infrastructure. WGLog assumes WebGPU compatibility and stable GPU hardware.

2. Data: The evaluation benchmarks include 12 transitive closure (TC) and 4 same-generation (SG) graph query datasets drawn from popular graph benchmarks, including ego-Facebook with skewed degree distributions (largest degree 1,043). Datasets contain up to 80 million tuples in closures, representing real-world scale recursive workloads. The data is normalized into lexicographically sorted arrays of 32-bit keys and values at load time.

3. Architecture / Algorithm: WGLog replaces traditional hash-table joins (which suffer from serialization due to atomic compare-and-swap (CAS) retries on hot keys in skewed graphs) with a sorted-array join pipeline. This uses binary-search to find join key ranges in the base relation, followed by scanning contiguous matching tuples, avoiding atomic bottlenecks. The pipeline consists of five stages: binary-search join (split into count and emit phases), radix sort to restore lexicographic ordering, a fused kernel performing deduplication and set difference in one pass via tiled parallelism and decoupled lookback prefix scans, and a disjoint merge that merges new delta tuples into the full relation without duplicate outputs. Platforms support only split arrays of 32-bit keys/values, with no pack/unpack overhead.

To avoid costly host–GPU synchronizations inherent in WebGPU’s record-submit-fence command model (where GPU-host readback costs ~2.5 ms), WGLog batches fixpoint iterations with indirect dispatch: all dispatch parameters are stored and updated in GPU buffers, and dependent kernels launch via indirect dispatch reading parameters from GPU memory. Multiple iterations (default K=30) are recorded into a single command buffer submitted once, reducing host–GPU round-trips drastically and amortizing overhead.

Buffer management uses a ping-pong scheme with two buffers alternated across stages to obey WebGPU’s no-aliasing policy forbidding simultaneous read and write binding of the same buffer range, avoiding expensive copy-back of intermediate results. Parity-aware radix routing enables sorting without contention.

4. Training / Execution Regime: The evaluation runs on a GeForce RTX 3060 Laptop GPU using CUDA baseline engines (mnmgJOIN, GPULog) recompiled for comparison, WebAssembly baselines, and CPU engines (Soufflé). Fixpoint iterations vary per dataset (tens to hundreds), with batch sizing adaptively halved near convergence to reduce overshoot wasted computation. Batch submission and asynchronous host recording hide latency.

5. Evaluation Protocol: Metrics include runtime, kernel-specific timing, GPU-host synchronization overhead, and stage-specific speedups. Ablations isolate the benefit of sorted joins vs. hash joins, batch indirect dispatch vs. host-driven loops, and fused dedup-setdiff kernels. Overheads are profiled for the largest datasets (e.g., ego-Facebook) with up to 80 million tuples. Comparisons against mnmgJOIN, GPULog, Soufflé (CPU), and WebAssembly variants (SQLite, DuckDB, Ascent) establish baselines.

6. Reproducibility: The paper does not explicitly mention public code release or frozen weights; datasets are standard graph benchmarks used in prior works [21,24]. The approach depends on WebGPU availability in browsers and standard GPUs.

Example: In transitive closure on ego-Facebook, WGLog loads sorted edge arrays, performs iterative fixpoint evaluation over hundreds of iterations within the GPU via batch indirect dispatch commands. Each iteration’s join uses binary search to locate matching edge ranges per delta tuple, emits candidates contiguously, merges results, and continues until no new tuples are produced. Non-compute reads from GPU to host happen only after each K-iteration batch completes to check fixpoint termination, dramatically reducing synchronization overhead from thousands to a handful of GPU-host fences.

Technical innovations

• Replacing hash-table-based joins with atomic-free binary-search sorted-array joins to eliminate serialization bottlenecks on skewed graphs with hub vertices.
• Designing an asynchronous fixpoint evaluation loop on WebGPU using indirect GPU dispatch arguments to batch multiple query iterations into a single host submission, removing costly per-stage host–GPU synchronizations.
• Fusing deduplication and set-difference operations into a single GPU kernel that operates on sorted candidates, reducing memory traffic and kernel launches.
• Implementing a ping-pong buffer system combined with parity-aware radix sorts to work within WebGPU’s buffer aliasing restrictions without additional costly copy-backs.

Datasets

• ego-Facebook — millions of edges with skewed degree distribution — public graph benchmark
• 12 transitive closure datasets — up to 80 million tuples in closures — from prior works [21,24]
• 4 same-generation query datasets — various sizes — prior workloads used in related GPU Datalog literature

Baselines vs proposed

• mnmgJOIN: end-to-end runtime vs WGLog: WGLog 2.38× faster
• GPULog: end-to-end runtime vs WGLog: WGLog 3.05× faster
• Soufflé (CPU): end-to-end runtime vs WGLog: WGLog 25.32× faster
• WebAssembly SQLite/DuckDB/Ascent: runtime one to orders of magnitude slower than WGLog (no GPU acceleration)

Limitations

• WGLog currently targets only compute-bound recursive queries and does not evaluate IO-bound or mixed workloads with large disk usage.
• No adversarial robustness evaluation against maliciously crafted skewed data or GPU denial-of-service attacks.
• Evaluation limited to a single GPU (NVIDIA RTX 3060) and lacks testing on integrated GPUs, mobile GPUs, or non-NVIDIA vendor hardware with WebGPU support.
• No explicit discussion of memory consumption and VRAM footprint, which could constrain deployment for very large graphs.
• Implementation adapted for WebGPU’s current API constraints; future changes in WebGPU specification or browser support could affect performance or require redesign.
• Fixpoint batch size adaptation heuristics may not generalize to all recursive workloads with different iteration count distributions.

Open questions / follow-ons

• How well does WGLog scale or adapt to heterogeneous or integrated GPUs common on mobile and low-power devices with limited compute and memory resources?
• Could the sorted-array join and asynchronous indirect dispatch pipeline generalize to non-recursive SQL workloads or other domains such as real-time graph analytics?
• What are the energy consumption and power-efficiency tradeoffs of in-browser GPU-accelerated recursive queries compared to native applications?
• Can the approach be extended to incorporate fault tolerance, partial query re-execution, or incremental incremental updates within long-running browser sessions?

Why it matters for bot defense

Bot-defense and CAPTCHA practitioners can glean two main takeaways from WGLog’s approach. First, the performance bottlenecks caused by data skew and iterative synchronization in GPU-accelerated graph computations, analogous to some graph- or session-based bot detection signals, can be substantially mitigated using sorted-array, contention-free joins combined with batched asynchronous execution pipelines. This insight emphasizes the need to reconsider hash-based structures and host-driven orchestration when seeking GPU acceleration in constrained or sandboxed environments such as browsers. Second, WGLog’s demonstration that fully browser-native GPU engines are now feasible via WebGPU opens new avenues for on-device, privacy-preserving bot analytics and feature extraction directly within the browser context. CAPTCHA systems that embed graph or relational computations client-side could leverage these design principles for scalable, latency-sensitive defenses without backend round trips or native code dependencies. However, the practicality of this approach will hinge on balancing GPU resource utilization, cross-platform browser support, and predictable latency under adversarial load.

Cite

@article{arxiv2607_17571,
  title={ Terascale Query Processing in the Browser: Rethinking GPU Acceleration },
  author={ Jiaxin Lu and Landon Dyken and Yihao Sun and Kristopher Micinski and Thomas Gilray and Sidharth Kumar },
  journal={arXiv preprint arXiv:2607.17571},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.17571}
}

Read the full paper

• arXiv:2607.17571 (abstract)
• arXiv:2607.17571 (PDF)