Research map / Large language models / Agents, code and math
Column-Oriented Datalog on the GPU
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Presents FVlog, a CUDA-based column-oriented (decomposed storage model) Datalog runtime for GPUs with hybrid sorted-index/hashmap indexing and eager merging, reporting large speedups over CPU column-oriented engines and GPU row-oriented engines.
Problem
Whether column-oriented or row-oriented tuple storage is more effective for Datalog evaluation on modern datacenter GPUs, since prior column-oriented Datalog engines were CPU-only and GPU Datalog engines used row layouts.
Approach
Stores each relation as decomposed columns with surrogate IDs, a raw data array, sorted indices and a run-length-encoded unique hashmap per column; joins return only matched surrogate columns, deduplication uses a GPU-friendly hash-plus-overlap check instead of tries, and delta tuples are eagerly merged into the full relation for memory continuity.
Key results
- On vsp_finan Same Generation, FVlog runs in 7.52 s versus 4403 s for VLog and 2172 s for Nemo, and is about 20x faster than Souffle (151.5 s) on the same dataset.
- On transitive closure, FVlog is on average 2.5x faster than GDlog and 5.7x faster than GPUJoin on H100 GPU.
- On LUBM 01K TGD reasoning, FVlog on GPU takes 0.16 s versus 165.8 s for VLog and 62.32 s for Nemo; the GPU version is at least 15x faster than the authors' CPU variant.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Column-oriented GPU layout (FVlog) vs CPU column-oriented engines (VLog, Nemo) | FVlog on H100 · Same Generation query, SparseSuite graphs | running time (s): at least 150x faster than VLog and Nemo in all cases; 584x vs VLog on vsp_finan | Helped |
| Column-oriented GPU layout vs row-oriented GPU engines (GDlog, GPUJoin) | FVlog on H100 · Transitive closure, six graphs | running time (s): on average 2.5x faster than GDlog and 5.7x faster than GPUJoin | Helped |
| GPU execution vs CPU execution of same FVlog data structures (ablation) | FVlog · LUBM TGD reasoning | running time (s): GPU at least 15x faster than CPU version | Helped |
| Eagerly merging delta into full relation and using uncompressed raw data (vs VLog-style on-demand concatenation) | FVlog · Transitive closure / SG | running time (s) | No clear effect |
| Hybrid indexing (sorted indices plus unique hashmap) vs pure hashmap indexing (GPUJoin) | Datalog joins on GPU · Transitive closure benchmarks | running time (s): GPUJoin 5.7x slower on average | Helped |
| Paper's claim that CPU variant speedup vs Nemo/VLog reflects data structures (ablation) | FVlog CPU variant · LUBM 01K | running time (s): CPU FVlog ~9.6x faster than Nemo/VLog on largest dataset; paper attributes about half of gain to data structures | Mixed |
Surprising findings
- The authors' CPU variant of FVlog is only about 9.6x faster than Nemo and VLog on the largest LUBM set, suggesting that data structures explain only about half of the gain while GPU memory bandwidth explains the rest.
- Row-oriented engines Souffle and RDFox saturate at 32 cores and decline at 64 cores on the authors' benchmarks.
Limitations
- Uncompressed raw data and persistent surrogate columns lead to higher memory usage, limiting dataset size to GPU memory.
- Deduplication via auxiliary buffers equal in size to the new relation adds memory cost.
- Evaluated on a single GPU only; cluster version left as future work.
Experimental setup
Datasets: SuiteSparse graphs LUBM (ChaseBench)
Benchmarks: Same Generation query on SuiteSparse graphs Transitive closure on SuiteSparse graphs LUBM TGD reasoning (ChaseBench)
Metrics: running time (seconds) speedup
Baselines: VLog Nemo Souffle RDFox GPUJoin GDlog
Builds on: VLog semi-naive evaluation GPUJoin Souffle Leapfrog Triejoin
Closest papers by meaning
- Column-Oriented Datalog Materialization for Large Knowledge Graphs (AAAI 2016 · similarity 0.88)
- Optimised Storage for Datalog Reasoning (AAAI 2024 · similarity 0.83)
- CUDABench: Benchmarking LLMs for Text-to-CUDA Generation (NeurIPS 2026 · similarity 0.81)
- Optimised Maintenance of Datalog Materialisations (AAAI 2018 · similarity 0.81)
- KernelBench: Can LLMs Write Efficient GPU Kernels? (ICML 2025 · similarity 0.79)
- Practical Offloading for Fine-Tuning LLM on Commodity GPU via Learned Sparse Projectors (AAAI 2025 · similarity 0.79)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.