Pith. sign in

REVIEW 3 major objections 5 minor 53 references

Column-Oriented Datalog on the GPU

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that column-oriented storage is the right layout for Datalog on modern GPUs, backing this with FVLOG, a CUDA runtime that stores each column as raw data plus a hybrid hash and sorted index, and reports over 200x speedups…

desk verdict Novel GPU column-store Datalog engine with real speedups, but Algorithm 2's dedup test looks unsound as written and the performance claims need tightening before I'd trust the results. read the letter →

arxiv 2501.13051 v1 pith:EDSA4W5Q submitted 2025-01-22 cs.DB

Yihao Sun , Sidharth Kumar , Thomas Gilray , Kristopher Micinski This is my paper · ORCID
classification cs.DB
keywords DatalogGPUcolumn-orientedstoragedecomposedmodelrelationalalgebrasemi-naiveevaluationknowledgerepresentationandreasoningCUDA
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that the long-standing debate over row- versus column-oriented storage for Datalog should be resolved in favor of columns on modern datacenter GPUs. It presents FVLOG, a CUDA runtime library that stores each relation in decomposed columns, with a hybrid index combining a sorted offset array and a run-length-encoded hash map per column. The engine departs from CPU column-oriented systems like VLog by eagerly merging each iteration's delta into a contiguous full relation and refusing to compress raw data, betting that GPU bandwidth makes these writes cheap. On benchmarks it reports over 200x speedups over CPU column engines (VLog, Nemo) and a 2.5x average speedup over GPU row-oriented engines (GDLOG, GPUJoin). If correct, this shifts the design point for high-performance Datalog toward column-layout GPU runtimes and suggests that prior CPU-tuned fragmentation strategies should be revisited.

What carries the argument

The central object is the per-column hybrid index used for every column of every decomposed relation. Each column holds an uncompressed 32-bit raw array in insertion order; an array of sorted indices (offsets into raw data ordered by value); and a unique hash map whose keys are distinct column values and whose values are (start offset, run length) pairs into the sorted indices. This trio implements the relational algebra primitives: hash lookups give the matched value ranges for joins, the sorted indices give range scans, and the raw array gives coalesced 32-bit accesses. The join kernel is two-phase — first count and prefix-sum the matched ranges, then have threads write a balanced number of output tuples — which avoids lock contention and warp divergence.

What would settle it

Run the Same Generation and transitive closure workloads on a GPU with substantially lower memory bandwidth than the H100 (for example a consumer card at a fraction of the 3.3 TB/s), and compare FVLOG against a variant that delays merging delta into full; if the delayed variant wins, the claim that bandwidth makes eager merging the right choice fails. Separately, feed a relation whose values exceed 32 bits and check whether per-tuple processing time grows discontinuously.

Watch

Extended reading notes

Core claim

The paper claims to present the first column-oriented Datalog engine tailored to modern GPUs, named FVLOG. It stores every relation in the Decomposed Storage Model, with each column kept as an uncompressed array of 32-bit values in insertion order plus a hybrid index: a sorted array of offsets into the raw data and a run-length-encoded hash map from each distinct value to a (start, length) pair. Its design deliberately inverts VLog's strategy: rather than keeping each iteration's delta in its own fragment and concatenating on demand during joins, FVLOG eagerly merges delta tuples into the contiguous full relation every iteration, on the ground that GPU memory bandwidth makes write-heavy insertion cheap. It also schedules all rules that produce the same relation in a single iteration and adds a difference operator for deduplication to handle cyclic joins without leapfrog tries. On Same Generation, transitive closure, and LUBM TGD workloads, it reports over 200x speedups over CPU column-oriented engines VLog and Nemo, a 2.5x average speedup over GPU row-oriented engines GDLOG and GPUJoin, and up to ~300x speedup on the largest LUBM dataset.

Load-bearing premise

The load-bearing premise is that on a modern GPU, with its high memory bandwidth, the cost of eagerly copying each iteration's delta tuples into one contiguous full relation is lower than the cost of leaving the relation fragmented and concatenating pieces on demand during joins.

Editorial extensions

If this is right

  • If the claimed speedups hold, Datalog workloads on datacenter GPUs should be built around column-oriented storage rather than the row-oriented tries and B-trees used by CPU engines like Soufflé.
  • The eager-merge, uncompressed-column design implies that future GPUs with even higher memory bandwidth will strengthen FVLOG's advantage, while memory capacity, not core count, becomes the main scaling limit.
  • The extension of relational algebra with an explicit difference operator for deduplication gives a lock-free path to set semantics on GPU, applicable beyond Datalog to other fixpoint computations.
  • On knowledge graph reasoning (LUBM), the reported up-to-300x speedup suggests ontology materialization can move to GPU runtimes without changing rule languages.
  • The CPU version of the same data structures being roughly 9.6x faster than VLog and Nemo implies that the column design itself, not just GPU bandwidth, is responsible for a substantial share of the gain.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The 32-bit value width and 80 GB HBM residency are preconditions; if real KRR workloads need 64-bit entity ids or exceed GPU memory, the reported speedups may not transfer without a cluster extension the paper only sketches.
  • The hybrid hash-and-sorted-index design could be lifted out of Datalog into general GPU join engines, where point lookups on repeated values are common.
  • A testable extension is to run the same engine on a mid-range GPU with lower memory bandwidth against VLog's on-demand concatenation; the paper's own bandwidth argument predicts eager merge would lose there.
  • The deduplication-by-difference trick for triangle joins suggests a GPU-friendly alternative to worst-case-optimal join algorithms, worth benchmarking against Leapfrog or free join on skewed data.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes FVLog, a CUDA-based Datalog runtime whose relations are stored in a decomposed storage model (DSM) on the GPU. Each column is represented as a raw 32-bit integer array, a per-column sorted-indices array, and a hash map that maps each distinct value to an interval of sorted-index positions. The paper describes a join algorithm, an eager delta-merge strategy to keep full relations contiguous, and a deduplication algorithm used during semi-naive evaluation. It evaluates FVLog against VLog, Nemo, Souffle, and RDFox on CPU, and against GPUJoin and GDLOG on the H100, using same-generation, transitive closure, and LUBM/ChaseBench workloads, reporting large speedups. The central claim is that column-oriented storage, with the specific hybrid index and eager merging, is the right layout for Datalog on modern datacenter GPUs.

Significance. If the correctness issues are resolved, this paper would be a meaningful systems contribution: it directly attacks the storage-layout question for GPU Datalog, provides a concrete columnar data structure, and evaluates it on public datasets against several existing engines. The use of SuiteSparse matrices and LUBM/ChaseBench, and the inclusion of both CPU and GPU baselines, is a strength. However, the paper's central correctness argument is undermined by the deduplication algorithm as written, the abstract's quantitative claim is contradicted by one of the paper's own tables, and the evaluation lacks variance reporting and output validation. These issues are all fixable but require substantive revision.

major comments (3)
  1. [Abstract; Table 1, 'Column-Oriented Datalog Comparison'] The deduplication test is not sound. The ranges returned by S.hashmap[a] and T.hashmap[b] are intervals into two independently sorted index arrays, so positional overlap of these intervals does not imply that some surrogate id appears in both ranges, and a shared id can occur at non-overlapping positions. For example, for the relation R(x,y) = {(1,2), (1,3), (2,2)}, the value x=2 occupies positions [2,3) in the S sorted index and y=3 occupies positions [2,3) in the T sorted index, so the genuinely new fact (2,3) would be marked as a duplicate and dropped; conversely, an existing duplicate whose column occurrences sit at positions 0 and 1 would be retained. Because this logic underpins semi-naive evaluation, FVLog may both miss derivable facts and fail to eliminate duplicates, so the central claim of a correct fixed-point engine is not supported as written. A correct test must intersect the sets of surrogate ids, not the positional ranges, and the paper should include a correctness proof or machine-checked verification of the fixpoint.
  2. [Abstract; Table 1, 'Column-Oriented Datalog Comparison'] The abstract states 'over 200x performance gains over SOTA CPU-based column-oriented Datalog engines,' but Table 1 contains a counterexample within the paper's own numbers: on fe_body, VLog runs 169.7 s and FVLog 1.85 s, a 91.7x ratio. The text's claim that 'at least more than 150 times faster than VLog and Nemo' is likewise not supported by that row. The authors should either qualify the claim (e.g., 'up to 500x' or 'over 90x in all tested cases') or report corrected measurements.
  3. [Evaluation, Tables 1-3] Every reported runtime is a single point estimate: no repetitions, no variance or confidence intervals, and no reported output sizes or correctness checks (e.g., comparing materialized relations against independently computed fixed points). Two of the six transitive-closure runs for GPUJoin are missing due to crashes. Without these, the magnitude of the claimed speedups and the 2.5x average comparison cannot be assessed robustly. Please add multiple runs with standard deviations and at least a light-weight validation (e.g., relation cardinalities or hashes) for each benchmark.
minor comments (5)
  1. [Table 1 caption and text] The dataset collection is called 'SuiteSparse' in the reference, but the text and Table 1 caption use 'SparseSuite'; please correct the name.
  2. [Throughout] The engine name is written inconsistently as 'FVLOG', 'FV LOG', and 'FVLog'; choose one spelling and use it consistently.
  3. [Algorithm 1, line 21] The pseudocode refers to 'RB.sorted id' while the data structure is described as 'sorted indices'; align the notation.
  4. [Table 3 caption and surrounding text] The CPU model is given as 'EPYC 9534' earlier but 'EPYC 9543' in the Table 3 discussion; also, 'an 64 cores' should be 'a 64-core'.
  5. [Evaluation] No source code or artifact link is provided, which limits independent verification; please make the implementation available or state where it can be obtained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all central claims are empirical comparisons against external engines and public datasets, with no fitted parameters or derivation-by-construction.

full rationale

The paper's central claims are performance claims: that a column-oriented DSM layout with eager delta merging, uncompressed raw columns, and hybrid hash/sorted indexing outperforms CPU column-oriented engines and GPU row-oriented prototypes. These claims are established by direct timing measurements on public datasets (SuiteSparse, LUBM/ChaseBench) against external engines (VLog, Nemo, Soufflé, RDFox) and two GPU prototypes. No parameter is fitted to the target outcome, and no result is derived from the outcome it is supposed to predict. The two GPU baselines (GDLOG and GPUJoin) come from overlapping author groups, but they are used as implemented benchmark rivals, not as sources of unverified theorems or as justification for the design's correctness. The design decisions, such as eagerly merging delta tuples into a full relation, are argued from hardware properties (GPU memory bandwidth, parallelism) and then tested indirectly through the benchmarks; this is a normal empirical validation, not circular reasoning. The paper does cite prior work by the same authors for GDLOG, but that citation supports the existence and behavior of a baseline system, and the comparison is independently reproducible in principle. The only notable concern is the correctness of Algorithm 2's deduplication check, which appears to compare positional overlaps of sorted-index ranges rather than actual row ids; this is a soundness/correctness issue, not a circularity issue, and therefore does not affect the circularity score. Overall, the derivation chain is not circular: the paper measures its proposed system against external ground truth and public workloads, and its claims stand or fall on those measurements.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard relational algebra over DSM, on the semi-naive evaluation model, and on hardware assumptions about GPU bandwidth and memory capacity. No fitted constants or invented entities appear; the main unproven inputs are representativeness of the benchmarks and the GPU-specific performance tradeoffs.

assumptions (4)
  • standard math Decomposed Storage Model relations with surrogate ids correctly reconstruct the original n-ary relation under join and projection.
    Section 'Decomposed Storage Model (DSM)' defines the decomposition R0(id,x0),...,Rn(id,xn) and reconstruction via joins on id; this is standard relational algebra, assumed without proof.
  • standard math Semi-naive evaluation with full, delta, and new relation versions reaches the same fixpoint as naive evaluation.
    Used throughout the 'Continuous Memory Layout' and 'Schedule multiple rules per iteration' sections; correctness of the fixpoint strategy is assumed from Datalog folklore.
  • domain assumption GPU memory bandwidth and thread parallelism make eager delta merging and uncompressed raw data faster than VLog's fragmented layout on an H100.
    Section 'Continuous Memory Layout' justifies the design by hardware bandwidth; this is an empirical assumption not proven by the paper's equations.
  • domain assumption Benchmark graphs from SuiteSparse and LUBM from ChaseBench are representative of Datalog workloads.
    The Evaluation selects six SparseSuite graphs and LUBM TGD queries; the text asserts diversity and real-world origin but does not establish representativeness for the broad class of Datalog programs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Column-Oriented Datalog on the GPU." pith.science (2026). https://pith.science/paper/EDSA4W5Q

@misc{pith2026250113051,
  author       = {Pith},
  title        = {Pith review of: Column-Oriented Datalog on the GPU},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EDSA4W5Q}},
  note         = {Machine review of arXiv:2501.13051}
}
read the original abstract

Datalog is a logic programming language widely used in knowledge representation and reasoning (KRR), program analysis, and social media mining due to its expressiveness and high performance. Traditionally, Datalog engines use either row-oriented or column-oriented storage. Engines like VLog and Nemo favor column-oriented storage for efficiency on limited-resource machines, while row-oriented engines like Souffle use advanced data structures with locking to perform better on multi-core CPUs. The advent of modern datacenter GPUs, such as the NVIDIA H100 with its ability to run over 16k threads simultaneously and high memory bandwidth, has reopened the debate on which storage layout is more effective. This paper presents the first column-oriented Datalog engines tailored to the strengths of modern GPUs. We present VFLog, a CUDA-based Datalog runtime library with a column-oriented GPU datastructure that supports all necessary relational algebra operations. Our results demonstrate over 200x performance gains over SOTA CPU-based column-oriented Datalog engines and a 2.5x speedup over GPU Datalog engines in various workloads, including KRR.

Figures

Figures reproduced from arXiv: 2501.13051 by the authors.

Figure 1
Figure 1. Converting Edge relation from NSM to DSM. Decomposed Storage Model (DSM) Database records are traditionally stored as rows of n-ary tuples in a horizon￾tal layout known as the N-ary Storage Model (NSM). Even today, most database management systems (DBMS) utilize NSM. However, some research demonstrated that storing database records via vertical columns could offer better per￾formance (Weyl et al. 1975). This approac… view at source ↗
Figure 2
Figure 2. Reach stored in column-oriented layout on GPU. This overhead is particularly problematic in Datalog, where the materialized IDB is often orders-of-magnitude larger than the input EDB. Column-Oriented Relations on the GPU In our approach, the relations are stored using the DSM, where each relation is decomposed into columns, and each column shares an identical datastructure [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. , the first matched range has a length of 3, while the second has only 1. The second method involves divid￾ing the workload based on the output result, ensuring that each thread writes the same number of tuples, thereby avoid￾ing data skew. However, this method requires extra searches within each thread to find the corresponding matched range, therefore most of CPU-based engines usually prefer the first method. Howe… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 51 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    J.; Madden, S

    Abadi, D. J.; Madden, S. R.; and Hachem, N. 2008. Column-stores vs. row-stores: how different are they really? In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 967--980

    work page 2008

  4. [4]

    Abiteboul, S.; Hull, R.; and Vianu, V. 1995. Foundations of databases, volume 8. Addison-Wesley Reading

    work page 1995

  5. [5]

    J.; Hill, M

    Ailamaki, A.; DeWitt, D. J.; Hill, M. D.; and Skounakis, M. 2001. Weaving Relations for Cache Performance. In VLDB, volume 1, 169--180

    work page 2001

  6. [6]

    J.; Hill, M

    Ailamaki, A.; DeWitt, D. J.; Hill, M. D.; and Wood, D. A. 1999. DBMSs on a modern processor: Where does time go? In VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK, 266--277

    work page 1999

  7. [7]

    Ajileye, T.; and Motik, B. 2022. Materialisation and data partitioning algorithms for distributed RDF systems. Journal of Web Semantics, 73: 100711

    work page 2022

  8. [8]

    Aref, M.; Kimelfeld, B.; Pasalic, E.; and Vasiloglou, N. 2015 a . Extending datalog with analytics in LogicBlox. In Proceedings of the 9th Alberto Mendelzon International Workshop on Foundations of Data Management

    work page 2015

Show all 53 references
  1. [9]

    J.; Kimelfeld, B.; Olteanu, D.; Pasalic, E.; Veldhuizen, T

    Aref, M.; Ten Cate, B.; Green, T. J.; Kimelfeld, B.; Olteanu, D.; Pasalic, E.; Veldhuizen, T. L.; and Washburn, G. 2015 b . Design and implementation of the LogicBlox system. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, 1371--1382

    2015

  2. [10]

    Atserias, A.; Grohe, M.; and Marx, D. 2013. Size bounds and query plans for relational joins. SIAM Journal on Computing, 42(4): 1737--1767

    2013

  3. [11]

    Benedikt, M.; Konstantinidis, G.; Mecca, G.; Motik, B.; Papotti, P.; Santoro, D.; and Tsamoura, E. 2017. Benchmarking the chase. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 37--52

    2017

  4. [12]

    A.; Zukowski, M.; and Nes, N

    Boncz, P. A.; Zukowski, M.; and Nes, N. 2005. MonetDB/X100: Hyper-Pipelining Query Execution. In Cidr, volume 5, 225--237

    2005

  5. [13]

    Bravenboer, M.; and Smaragdakis, Y. 2009. Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications, 243--262

    2009

  6. [14]

    Calimeri, F.; Fusc \`a , D.; Perri, S.; and Zangari, J. 2017. I-DLV: the new intelligent grounder of DLV. Intelligenza Artificiale, 11(1): 5--20

    2017

  7. [15]

    Ceri, S.; Gottlob, G.; and Lavazza, L. 1986. Translation and optimization of logic queries: The algebraic approach. In Proceedings of the 12th International Conference on Very Large Data Bases, 395--402

    1986

  8. [16]

    cuCollection. 2024. cuCollections (cuco), an open-source, header-only library of GPU-accelerated, concurrent data structures. https://github.com/NVIDIA/cuCollections. Accessed: 2024-08-30

    2024

  9. [17]

    A.; and Hu, Y

    Davis, T. A.; and Hu, Y. 2011. The university of Florida sparse matrix collection. ACM Trans. Math. Softw., 38(1)

    2011

  10. [18]

    Green, O. 2021. HashGraph—Scalable hash tables using a sparse graph data structure. ACM Transactions on Parallel Computing (TOPC), 8(2): 1--17

    2021

  11. [19]

    Green, O.; McColl, R.; and Bader, D. A. 2012. GPU merge path: a GPU merging algorithm. In Proceedings of the 26th ACM international conference on Supercomputing, 331--340

    2012

  12. [20]

    Hoder, K.; Bj rner, N.; and De Moura, L. 2011. Z--an efficient engine for fixed points with constraints. In Computer Aided Verification: 23rd International Conference, CAV 2011, Snowbird, UT, USA, July 14-20, 2011. Proceedings 23, 457--462. Springer

    2011

  13. [21]

    F.; Boley, H.; Tabet, S.; Grosof, B.; Dean, M.; et al

    Horrocks, I.; Patel-Schneider, P. F.; Boley, H.; Tabet, S.; Grosof, B.; Dean, M.; et al. 2004. SWRL: A semantic web rule language combining OWL and RuleML. W3C Member submission, 21(79): 1--31

    2004

  14. [22]

    Intel . 2024. oneAPI Threading Building Blocks (oneTBB) . https://github.com/oneapi-src/oneTBB. Accessed: 2024-08-30

    2024

  15. [23]

    Ivliev, A.; Ellmauthaler, S.; Gerlach, L.; Marx, M.; Mei ner, M.; Meusel, S.; and Kr \" o tzsch, M. 2023. Nemo: First Glimpse of a New Rule Engine. In Pontelli, E.; Costantini, S.; Dodaro, C.; Gaggl, S.; Calegari, R.; Garcez, A. D.; Fabiano, F.; Mileo, A.; Russo, A.; and Toni,...

    2023

  16. [24]

    JEDEC . 2021. High Bandwidth Memory (HBM) DRAM . https://www.jedec.org/document_search?search_api_views_fulltext=jesd235. Accessed: 2024-08-30

    2021

  17. [25]

    Jordan, H.; Scholz, B.; and Suboti \'c , P. 2016. Souffl \'e : On synthesis of program analyzers. In Computer Aided Verification: 28th International Conference, CAV 2016, Toronto, ON, Canada, July 17-23, 2016, Proceedings, Part II 28, 422--430. Springer

    2016

  18. [26]

    Jordan, H.; Suboti \'c , P.; Zhao, D.; and Scholz, B. 2019 a . Brie: A specialized trie for concurrent datalog. In Proceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores, 31--40

    2019

  19. [27]

    Jordan, H.; Suboti \'c , P.; Zhao, D.; and Scholz, B. 2019 b . A specialized B-tree for concurrent datalog evaluation. In Proceedings of the 24th symposium on principles and practice of parallel programming, 327--339

    2019

  20. [28]

    KBS. 2024. Nemo Examples and Benchmarks. https://github.com/knowsys/nemo-examples/blob/main/chasebench/lubm/. Accessed: 2024-08-30

    2024

  21. [29]

    Kolovski, V.; Wu, Z.; and Eadon, G. 2010. Optimizing enterprise-scale OWL 2 RL reasoning in a relational database system. In International Semantic Web Conference, 436--452. Springer

    2010

  22. [30]

    Motik, B.; Nenov, Y.; Piro, R.; and Horrocks, I. 2019. Maintenance of datalog materialisations revisited. Artificial Intelligence, 269: 76--136

    2019

  23. [31]

    Motik, B.; Nenov, Y.; Piro, R.; Horrocks, I.; and Olteanu, D. 2014. Parallel materialisation of datalog programs in centralised, main-memory RDF systems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28

    2014

  24. [32]

    Nenov, Y.; Piro, R.; Motik, B.; Horrocks, I.; Wu, Z.; and Banerjee, J. 2015. RDFox: A highly-scalable RDF store. In The Semantic Web-ISWC 2015: 14th International Semantic Web Conference, Bethlehem, PA, USA, October 11-15, 2015, Proceedings, Part II 14, 3--20. Springer

    2015

  25. [33]

    Q.; R \'e , C.; and Rudra, A

    Ngo, H. Q.; R \'e , C.; and Rudra, A. 2014. Skew strikes back: new developments in the theory of join algorithms. Acm Sigmod Record, 42(4): 5--16

    2014

  26. [34]

    NVIDIA. 2024 a . CUDA Best Practice Guide: Coalesced Access to Global Memory. https://docs.nvidia.com/cuda/cuda-c-best-practices-guide/index.html#coalesced-access-to-global-memory. Accessed: 2024-08-30

    2024

  27. [35]

    NVIDIA. 2024 b . CUDA Programming Guide: Programming Models. https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#programming-model. Accessed: 2024-08-30

    2024

  28. [36]

    J.; Hammond, S

    Pennycook, S. J.; Hammond, S. D.; Wright, S. A.; Herdman, J.; Miller, I.; and Jarvis, S. A. 2013. An investigation of the performance portability of OpenCL. Journal of Parallel and Distributed Computing, 73(11): 1439--1450

    2013

  29. [37]

    Raasveldt, M.; and M \"u hleisen, H. 2019. Duckdb: an embeddable analytical database. In Proceedings of the 2019 International Conference on Management of Data, 1981--1984

    2019

  30. [38]

    H.; and Cherry, C

    Robinson, A. H.; and Cherry, C. 1967. Results of a prototype television bandwidth compression scheme. Proceedings of the IEEE, 55(3): 356--364

    1967

  31. [39]

    S \'a enz-P \'e rez, F.; Caballero, R.; and Garc \' a-Ruiz, Y. 2011. A deductive database with datalog and sql query languages. In Programming Languages and Systems: 9th Asian Symposium, APLAS 2011, Kenting, Taiwan, December 5-7, 2011. Proceedings 9, 66--73. Springer

    2011

  32. [40]

    D.; Lee, V

    Satish, N.; Kim, C.; Chhugani, J.; Nguyen, A. D.; Lee, V. W.; Kim, D.; and Dubey, P. 2010. Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, 351--362

    2010

  33. [41]

    Shore, J. E. 1975. On the external storage fragmentation produced by first-fit and best-fit allocation strategies. Communications of the ACM, 18(8): 433--440

    1975

  34. [42]

    R.; Gilray, T.; Micinski, K.; and Kumar, S

    Shovon, A. R.; Gilray, T.; Micinski, K.; and Kumar, S. 2023. Towards iterative relational algebra on the \ GPU \ . In 2023 USENIX Annual Technical Conference (USENIX ATC 23), 1009--1016

    2023

  35. [43]

    J.; Batkin, A.; Chen, X.; Cherniack, M.; Ferreira, M.; Lau, E.; Lin, A.; Madden, S.; O'Neil, E.; et al

    Stonebraker, M.; Abadi, D. J.; Batkin, A.; Chen, X.; Cherniack, M.; Ferreira, M.; Lau, E.; Lin, A.; Madden, S.; O'Neil, E.; et al. 2018. C-store: a column-oriented DBMS. In Making Databases Work: the Pragmatic Wisdom of Michael Stonebraker, 491--518

    2018

  36. [44]

    R.; Gilray, T.; Micinski, K.; and Kumar, S

    Sun, Y.; Shovon, A. R.; Gilray, T.; Micinski, K.; and Kumar, S. 2023. GDlog: A GPU-Accelerated Deductive Engine. arXiv preprint arXiv:2311.02206

    2023 arXiv

  37. [45]

    Ullman, J. D. 1983. Principles of database systems. Galgotia publications

    1983

  38. [46]

    Urbani, J.; Jacobs, C.; and Kr \"o tzsch, M. 2016. Column-oriented datalog materialization for large knowledge graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30

    2016

  39. [47]

    Urbani, J.; Kotoulas, S.; Maassen, J.; Van Harmelen, F.; and Bal, H. 2010. OWL reasoning with WebPIE: calculating the closure of 100 billion triples. In The Semantic Web: Research and Applications: 7th Extended Semantic Web Conference, ESWC 2010, Heraklion, Crete, Greece, May ...

    2010

  40. [48]

    Veldhuizen, T. L. 2014. Leapfrog triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory

    2014

  41. [49]

    R.; Willsey, M.; and Suciu, D

    Wang, Y. R.; Willsey, M.; and Suciu, D. 2023. Free join: Unifying worst-case optimal and traditional joins. Proceedings of the ACM on Management of Data, 1(2): 1--23

    2023

  42. [50]

    Weyl, S.; Fries, J.; Wiederhold, G.; and Germano, F. 1975. A modular self-describing clinical databank system. Computers and Biomedical Research, 8(3): 279--293

    1975

  43. [51]

    Whaley, J.; and Lam, M. S. 2004. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 conference on Programming Language Design and Implementation, 131--144

    2004

  44. [52]

    Zeng, X.; Hui, Y.; Shen, J.; Pavlo, A.; McKinney, W.; and Zhang, H. 2023. An Empirical Evaluation of Columnar Storage Formats. Proc. VLDB Endow., 17(2): 148--161

    2023

  45. [53]

    Zukowski, M.; Nes, N.; and Boncz, P. 2008. DSM vs. NSM: CPU performance tradeoffs in block-oriented query processing. In Proceedings of the 4th international workshop on Data management on new hardware, 47--54

    2008

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.