A Compiler for Operations on Relations with Bag Semantics

Fredrik Kjolstad; James Dong

REVIEW 4 major objections 4 minor 23 references

A Compiler for Operations on Relations with Bag Semantics

T0 review · 4 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read This paper claims that a loop-based intermediate representation with deterministic-finite-automaton iteration machines can compile the full relational algebra—outer joins, non-equi joins, differences included—into fused C++ code that…

desk verdict Strong systems idea for fusing bag-semantics relational algebra, but the iteration-machine correctness proofs have real gaps and the 'compiler' is more of a hand-tuned generator. read the letter →

arxiv 2502.06988 v1 pith:6BIXNXC5 submitted 2025-02-10 cs.PL cs.DB

James Dong , Fredrik Kjolstad This is my paper · ORCID

classification cs.PLcs.DB

keywords relationalalgebrabagsemanticsmultisetquerycompilationoperatorfusionintermediaterepresentationco-iterationcodegeneration

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 claims that the full relational algebra can be compiled to fused, loop-based code without dropping bag (multiset) semantics. The authors introduce an abstract loop intermediate representation (ALIR) whose loop domains are multiset expressions over coordinate trees, and deterministic-finite-automaton iteration machines that drive co-iteration as relations run out of values. They report coverage of inner joins, outer and left/right joins, differences, non-equi joins, projections, and filters, with correctness under multiset semantics and portability across storage layouts. If the claim holds, query engines could fuse entire operator graphs instead of chaining hand-written operator implementations, with the reported 3.87x average speedup on selected graph queries and worst-case optimal triangle-query performance following as consequences. The main caveat is that converting SQL to ALIR is currently semi-automatic and manually tuned, so the general-compiler claim depends on automating that step.

What carries the argument

The load-bearing object is the iteration machine: a deterministic finite automaton constructed by a product construction for each multiset operator, with states labeled by the sets of inputs that must still be co-iterated and node labels choosing producer, omitter, or 'not ready' behavior. The 'not ready' label is what makes multiset difference correct: it fast-forwards only the inputs involved in the difference when duplicate counts do not line up. Around it sit the coordinate-tree data model (relations broken into per-attribute levels abstracted from storage), the ALIR grammar of nested loops over multiset expressions, index-only relations for outer joins, and a galloping rule that advances iterators by skipto so fusion can also produce worst-case optimal join behavior.

What would settle it

Run the compiler on a bag-semantics query whose correctness depends on the not-ready mechanism, for example (A−B)∩C with A={{1,1}}, B={{1}}, C={{1}}, and compare against reference multiset semantics; if the generated code produces anything other than {{1}}, the central correctness claim fails. Separately, remove all manual ALIR tuning from the decision-support pipeline and check whether the automatic planner alone generates correct code for all 22 queries; if it cannot, the generality claim is qualified to hand-crafted plans.

Watch

Extended reading notes

Core claim

The central discovery is a code-generation path from relational algebra to fused loops that preserves multiset semantics for the operators real database systems need. The path goes: relations are viewed as coordinate trees, one level per attribute; loops are written over multiset expressions over these trees; each loop domain is converted into an iteration machine, a DFA whose states list which inputs must still be co-iterated and whose node labels say whether the current value produces output, is omitted, or must wait because a multiset difference left a gap; and the machine is lowered to C++ loops that advance iterators exactly as the multiset expression demands. The paper claims this is the first approach to fuse outer joins, non-equi joins, and differences under bag semantics while remaining portable across data structures, and validates it by generating code that matches a leading in-memory database on standard decision-support queries sequentially (1.00x geomean) while outperforming database baselines on fused graph queries (3.87x geomean).

Load-bearing premise

The load-bearing premise is that a relational algebra expression can be converted into an efficient ALIR automatically; the paper only converts semi-automatically and hand-tunes 13 of 22 decision-support queries, so if that conversion cannot be automated the system becomes a generator for manually written loop plans rather than a general fused query compiler.

Editorial extensions

If this is right

Any supported relational algebra operator combination can be fused, so no intermediate relation is materialized unless the user deliberately precomputes, as needed for aggregation and non-equi joins.
Generated code honors multiset semantics, so duplicate counts from joins, intersections, unions, and differences are exact rather than set-approximated.
The same ALIR can be lowered to sorted lists, hash tables, columns, tries, or native containers by choosing per-layer storage capabilities, giving portability across data structures.
Fusion gives worst-case optimal asymptotic scaling for multi-way inner joins: the triangle query runs in roughly linear time versus quadratic for baseline engines.
On standard decision-support queries, generated code is on par with a leading in-memory database sequentially (geomean 1.00x) and competitive in parallel (0.61x), while on selected graph queries it is faster by a geomean 3.87x and up to 12.23x.

Reading between the lines

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

If ALIR generation becomes fully automatic, the practical barrier to fused query execution shifts from operator implementations to query-to-IR planning, so compilers could fuse whole query graphs rather than operator pipelines.
The not-ready iterator mechanism for multiset difference is a general alignment technique; it could be reused in streaming and incremental-maintenance settings where multiplicity mismatches arise.
The storage-description interface makes portability measurable: each new data structure requires only lookup and iteration primitives, so one could test generality by counting adapter lines per structure, as the paper does with a six-line hash-map adapter.
Because the decision-support numbers relied on manual tuning of 13 of 22 queries, whether an automated planner can match them is an open, testable question rather than an established result.

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.

Desk Editor's Note

read the letter

Jim, this is a serious systems paper tackling the right problem: fusing relational operators under bag semantics without dropping outer joins, differences, or non-equi joins. The ALIR idea and the iteration-machine DFA are a genuine generalization of indexed streams/TACO, and the "not ready" states for multiset difference are a clever fix. The evaluation is broad: TPC-H, LSQB, a worst-case-optimal triangle query, and storage-format portability. The triangle scaling (linear vs quadratic) is a concrete, reproducible-looking win.

That said, the central soundness story is not fully delivered. Lemma 5.3's proof uses a dominance claim that is false in a simple IM for A∩B∩C: {A,B} does not dominate {A} because one can reach {A} via {A,C}. The lemma may be salvageable, but the proof as written does not establish it. Algorithm 2's minimization rule is also unproven: removing a node when its immediate predecessor has the same interpretation is not shown to preserve the floor mapping for all subsets, and the "guaranteed to minimize" claim has no proof. These are load-bearing, since every generated loop inherits correctness from these machines.

The paper is also upfront about being semi-automatic: the ALIR conversion is manually fine-tuned, and 13 of 22 TPC-H queries were manually modified. That is acceptable for a prototype, but it weakens the "compiler for any expression" headline. No artifact is provided, so the numbers cannot be independently checked.

Proportionately: none of this looks like a fatal flaw. The ideas are plausible and the gap is in proof rather than an obvious counterexample to the overall approach. A serious referee should push for a rigorous proof of Lemma 5.3 and the minimization invariant, and for an artifact. I would bring this to a reading group and cite it as prior work, but I would not build on it until those proof gaps are closed.

Referee Report

4 major / 4 minor

Summary. The paper presents ALIR, a nested-loop intermediate representation for relational algebra expressions over multisets, and an iteration-machine construction that lowers ALIR loop domains to co-iteration code over abstract layer storages. The claimed contributions are: a data model based on coordinate trees for set and bag semantics; an IR that expresses fused inner joins, outer joins, differences, non-equi joins, and Cartesian products; a DFA-based iteration-machine construction with a minimization step; and a code generator to C++. The evaluation reports LSQB speedups, TPC-H parity with Hyper, and data-structure portability experiments. The formal core is Section 5, which defines iteration machines, product construction, minimization, and legality, and Section 6, which lowers them to loops.

Significance. If the central construction is correct, this would be a substantial advance: it would be the first system to fuse the full relational algebra on bag semantics while remaining portable across data structures, and the iteration-machine formulation is a clean generalization of prior iteration-lattice work. The paper is also commendably explicit about the boundary of automatic query planning: Section 2 states that ALIR conversion is semi-automatic and manually fine-tuned, and Appendix C discloses that 13 of 22 TPC-H queries were manually modified. However, the formal guarantees that the generated code matches relational-algebra semantics are not established: the proof of the key uniqueness lemma is invalid, the minimization criterion is unsupported, and there is no end-to-end correctness theorem connecting ALIR and code generation to multiset semantics. The experimental evidence is suggestive but cannot fill those gaps.

major comments (4)

[Section 5.3, Lemma 5.3] The proof of Lemma 5.3 rests on the assertion that u1∪v1 dominates u1 and v1 in the iteration-machine DFA, but this assertion is false. In the iteration machine for A∩B∩C generated by Algorithm 1, the node {A,C} is reachable from the initial state {A,B,C} by the transition that removes B, and {A} is reachable from {A,C} by the transition that removes C. Thus the path {A,B,C}→{A,C}→{A} reaches {A} without passing through {A,B}. Taking u1={A} and v1={A,B}, the node u1∪v1={A,B} does not dominate u1. Since this domination claim is the only argument given for why no distinct reachable product states are merged under the label u1∪u2, the product construction is not proven to preserve distinct reachable states. A correct replacement proof, or a modified construction, is needed before the paper's claim of correct code for multiset difference and Cartesian product expressions is supported.
[Section 5.4, Algorithm 2] The minimization algorithm is load-bearing because it is applied automatically to every generated iteration machine, but its soundness is not established. The algorithm removes a node v when I(ip(v)) = I(v), yet no lemma shows that for every subset p with floor(p) = v, the new floor′(p) satisfies I′(floor′(p)) = I(floor(p)). Removing v also changes the join-semilattice (closure property 5) and therefore the floor of many subsets, not just of v. The notation ip(v) is ambiguous: the text calls ip(v) the immediate predecessor and equates it with floor′(v), but the algorithm accumulates ip(u) as a set of successors v of u. Finally, the assertion that "removability only flows upwards" is stated without proof, and the claim that the algorithm "is guaranteed to minimize the complexity of the generated loops" has no formal definition of the minimized quantity. Because an unsound merge could change which inputs are advanced in a loop and hence output multiplicities, this step needs a rigorous correctness argument.
[Sections 4–6, especially Algorithm 3] The paper never states or proves an end-to-end correctness theorem relating generated C++ code to relational-algebra semantics. There are local lemmas about floors and transitions (Lemma 5.1, Lemma 5.2) and about loop ordering (Lemma 6.1), but no theorem of the form: for every ALIR program P and every input satisfying the storage description, the C++ generated by Algorithm 3 produces exactly the multiset denoted by P. Given the subtle multiset-difference example in Section 5.2, where an apparently natural iteration machine produces the wrong result, this is not a mere formality. The correctness of the product rules (Section 5.3), the not-ready behavior ∅(®N), multiple cursors, and the index-only-relation re-introduction in Section 5.5 all need to be tied together in one theorem for the abstract's strong claim to hold.
[Section 2 and Appendix C] The paper's central claim is that the approach "can be used to generate a fused implementation for any set of relational algebra operators," but the path from a relational algebra expression to ALIR is not automatic: Section 2 says "we perform this conversion semi-automatically and manually fine-tune it to optimize performance on the benchmark data," and Appendix C reports that 13 of 22 TPC-H queries were manually modified. The paper demonstrates compilation from ALIR to C++, not compilation from relational algebra to ALIR. The manuscript should either provide a specification and correctness argument for an automatic RA-to-ALIR translation, or explicitly scope the contribution to ALIR-to-code generation and adjust the abstract and introduction accordingly.

minor comments (4)

[Figure 1] Figure 1 shows an arrow from "Relational Algebra" to "ALIR," which may mislead readers given that Section 2 states the conversion is semi-automatic and manually fine-tuned; the figure should be annotated to show that the RA-to-ALIR step is not fully automatic.
[Section 5.2] The labels ⊤(®N), ∅(®N), and the multiple-cursor mechanism are introduced in prose but are not given formal definitions in the grammar or in the interpretation function ⟦M⟧; adding a precise definition of these labels and their product rules would make the construction easier to verify.
[Section 5.4] The phrase "guaranteed to minimize the complexity of the generated loops" is used without defining the cost model; even if a correctness proof is supplied, the optimality claim needs a separate statement and proof.
[Appendix C] The manual modifications to the 13 TPC-H queries are listed by query number but not described; a table of the specific modifications (e.g., loop reorderings, subquery precomputation, parallel tiling changes) would make the evaluation more reproducible.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the iteration-machine construction is defined from operator semantics and benchmark tuning is disclosed, not disguised as prediction.

full rationale

The paper's central derivation—ALIR loop domains lowered to DFA iteration machines via Algorithm 1, minimized by Algorithm 2, and emitted as C++ co-iteration loops—is defined directly from standard multiset operator semantics (union, intersection, difference, product, plus outer/non-equi join encodings). The product construction's interpretation rules and the floor/transition lemmas are internal definitions; no parameter is fitted to benchmark data and then renamed a prediction. The performance comparisons are honest engineering evaluations with disclosed manual tuning: Section 2 states 'we perform this conversion semi-automatically and manually fine-tune it to optimize performance on the benchmark data' and Appendix C lists 13 of 22 TPC-H queries modified by hand; this is a disclosed limitation on the automation claim, not a circular derivation. Citations to the authors' prior TACO, indexed streams, and iteration lattices work situate the approach, but the paper redefines the necessary structures (coordinate trees, iterator interfaces, iteration machines) in place, so the citations are not load-bearing for the correctness argument. The skeptic's concerns about Algorithm 2's removal criterion and Lemma 5.3's proof are real proof gaps about whether generated code is correct, but an invalid or missing proof is not circularity: the target result is not assumed as an input. Accordingly no step reduces to its own inputs.

Assumptions & free parameters 1 free parameters · 5 assumptions · 2 invented entities

The central claim depends on the standard axioms of multiset algebra, the coordinate-tree data model, and the assumption that storage layers expose exactly the lookup/iteration primitives. It also depends on a hand-set parameter: the per-benchmark manual choice of ALIR loop structure, which is not produced automatically. No physical entities are introduced; the iteration machine and index-only relations are formal constructs of the paper, so they are the only 'invented entities' to list.

free parameters (1)

Manual ALIR query plan (loop order, index-only tags, storage choices) = Per-query hand written; 13 of 22 TPC-H queries manually modified
Section 2 states the conversion to ALIR is semi-automatic and manually fine-tuned for performance; Appendix C lists specific queries that were modified by hand. The reported speedups depend on these hand-chosen plans rather than on a fully automatic planner.

assumptions (5)

standard math Multiset algebra operators (union, intersection, difference, plus, times) follow the standard semantics of Syropoulos (2001)
Used throughout Section 4.1 and in the interpretation rules of Section 5.3.
domain assumption Every relation can be represented as a coordinate tree with one level per attribute in a fixed order
Section 3.1; ALIR loops iterate over coordinate-tree levels, and the allowed loop orderings are constrained by this representation.
domain assumption Storage layers provide exactly lookup/iteration capabilities and iterator layers must be sorted
Section 3.2; the co-iteration algorithm requires iterators to be sorted and relies on the presence of the listed primitives (init, curval, advance, present, skipto, reset).
domain assumption A universal set U exists and is iterable when complement of a set expression is needed
Section 5.6 legality: complement (set negation) is only supported when the universal set can be iterated, such as a finite range of integers; for unbounded domains the expression is illegal.
ad hoc to paper The ALIR loop structure is manually chosen (semi-automatically) and fine-tuned per benchmark
Section 2: 'we perform this conversion semi-automatically and manually fine-tune it to optimize performance on the benchmark data'; Appendix C: 13 of 22 TPC-H queries manually modified.

invented entities (2)

Iteration machine
purpose: DFA-based representation of co-iteration over multisets, including 'not ready' states for differences; used for loop and case generation in the compiler
Defined and validated only through the paper's own code generator; no external benchmark or formal proof connects the iteration machine to relational-algebra semantics in full.
Index-only relation
purpose: Relation included in an iteration machine only for branching (presence checks), enabling outer joins and differences without iterating over the relation's values
Internal IR device introduced in Section 4.5; correctness is argued informally with an example, not proven formally.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Compiler for Operations on Relations with Bag Semantics." pith.science (2026). https://pith.science/paper/6BIXNXC5

@misc{pith2026250206988,
  author       = {Pith},
  title        = {Pith review of: A Compiler for Operations on Relations with Bag Semantics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6BIXNXC5}},
  note         = {Machine review of arXiv:2502.06988}
}

read the original abstract

We describe an abstract loop-based intermediate representation that can express fused implementations of relational algebra expressions on sets and bags (multisets). The loops are abstracted away from physical data structures thus making it easier to generate, reason about, and perform optimization like fusion on. The IR supports the natural relational algebra as well as complex operators that are used in production database systems, including outer joins, non-equi joins, and differences. We then show how to compile this IR to efficient C++ code that co-iterates over the physical data structures present in the relational algebra expression. Our approach lets us express fusion across disparate operators, leading to a 3.87x speedup (0.77--12.23x) on selected LSQB benchmarks and worst-case optimal triangle queries. We also demonstrate that our compiler generates code of high quality: it has similar sequential performance to Hyper on TPC-H with a 1.00x speedup (0.38--4.34x) and competitive parallel performance with a 0.61x speedup (0.23--1.80x). Finally, our approach is portable across data structures.

Figures

Figures reproduced from arXiv: 2502.06988 by the authors.

**Figure 2.** Example coordinate tree. Nodes are labeled with their values; the tuples in each subtree is the the multiset for each node. Dotted lines represent the tuples corresponding to each leaf node. Unlike standard relational algebra, in which relations are sets, we model relations using bag or multiset semantics, like most real-world RDBMSes. In this view, a relation is taken as a multiset of tuples, or rows, of fixed len… view at source ↗

**Figure 3.** Grammar for ALIR. 𝑅 represents a relation, and 𝛼 is an attribute. intermediate results are represented as relations. A representation such as an operator graph that relies on templating can only handle optimizations with a fixed structure for each template, so such representations are too coarse-grained to model fusion across arbitrary relational expressions. Instead, we use a representation that focuses on fusion b… view at source ↗

Figures from the paper (12 more)

**Figure 4.** Figure 4: Inner join in ALIR. Consider the following inner join and relational schema, which produces a tuple for every pair of tuples in𝐴 and in 𝐵 that match on shared attributes: 𝑅 = 𝐴 Z 𝐵 𝑅(𝑥, 𝑦, 𝑧);𝐴(𝑥, 𝑦); 𝐵(𝑦, 𝑧) [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

**Figure 5.** Figure 5: ALIR for 𝜎𝑥 2+𝑦 2=𝑟 2 (𝐴) Z 𝐵 where the lefthand side is precomputed into a temporary. let 𝑇 (Σ𝑥, 𝑦) B for 𝑥 ∈ 𝐴.𝑥 for 𝑦 ∈ 𝐴.𝑦 ∩ {𝑦 | 𝑥 2 + 𝑦 2 = 𝑟 2 } 𝑇 [𝑦].Σ𝑥 += 𝐴.𝑥 in for 𝑦 ∈ 𝑇 .𝑦 ∩ 𝐵.𝑦 for 𝑧 ∈ 𝐵.𝑧 for Σ𝑥 ∈ 𝑇 .Σ𝑥 (Σ𝑥, 𝑦, 𝑧) [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]

**Figure 9.** Figure 9: Semantics of different join types. NULL is blank. [PITH_FULL_IMAGE:figures/full_fig_p007_9.png]

**Figure 12.** Figure 12: Left non-equi join for the same expression. let 𝑇 (𝑥, 𝑦1, 𝑦2, 𝑧) B 𝐴 Z𝐴.𝑦<𝐵.𝑦 𝐵 in 𝐴 Z𝐴.𝑦<𝐵.𝑦 𝐵 using 𝑇 . . . for 𝑦2 ∈ 𝐵.𝑦(𝑇 .𝑦2 ) for 𝑧 ∈ 𝐵.𝑧 − 𝑇 .𝑧 for dups ∈ 𝐵 (∅, ∅, 𝑦2, 𝑧) [PITH_FULL_IMAGE:figures/full_fig_p007_12.png]

**Figure 14.** Figure 14: Iteration machine for (𝐴 ∩ 𝐵) ∪ 𝐶. ⊥ represents the end of iteration. Self-edges are added for completeness as a DFA. The structure of how the iteration changes in this example is shown in the diagram in [PITH_FULL_IMAGE:figures/full_fig_p009_14.png]

**Figure 16.** Figure 16: Diagram showing iteration state for (left) incorrect iteration machine (right) correct iteration machine. [PITH_FULL_IMAGE:figures/full_fig_p010_16.png]

**Figure 15.** Figure 15: Venn diagram for the expression 𝐴 ∩ 𝐵 ∪𝐶; sections colored according to IM nodes. Note that due to uniqueness, the transition function for an iteration machine is uniquely determined from the set of states. In particular, 𝛿 (𝑛, 𝑥) = floor(𝑛 − {𝑥}). This follows from…

**Figure 17.** Figure 17: Two distinct IMs for 𝐴 ∩ 𝐵, with omitter nodes crossed out. Edge labels and self-loops are omitted. Consider the two iteration machines (IMs) in [PITH_FULL_IMAGE:figures/full_fig_p012_17.png]

**Figure 18.** Figure 18: Selected LSQB queries. For each query, the result is the total number of matches. Lines and arrows [PITH_FULL_IMAGE:figures/full_fig_p017_18.png]

**Figure 19.** Figure 19: LSQB results. 103 104 105 N (log scale) 10−4 10−3 10−2 10−1 100 101 102 runtime (s, log scale) Ours DuckDB Hyper [PITH_FULL_IMAGE:figures/full_fig_p018_19.png]

**Figure 22.** Figure 22: Join comparison using intersection. Error bars represent the standard deviation of each segment. Bottom chart is normalized to fastest kernel. 7.2 Fusion To demonstrate the advantages of fusion, we implemented the triangle-finding query [Ngo et al. 2014]: 𝐴(𝑎, 𝑏) Z …

**Figure 23.** Figure 23: TPC-H results. All results normalized to our sequential runtime, which is labeled in seconds. [PITH_FULL_IMAGE:figures/full_fig_p020_23.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 8 canonical work pages

[7]

In Proceedings of 1994 IEEE 10th International Conference on Data Engineering

A multi-set extended relational algebra: a formal approach to a practical issue. In Proceedings of 1994 IEEE 10th International Conference on Data Engineering . 80–88. https://doi.org/10.1109/ICDE.1994. 283002 Joseph M. Hellerstein, Michael Stonebraker, and James Hamilton

work page doi:10.1109/icde.1994 1994
[11]

Proceedings of the VLDB Endowment 11, 13 (2018), 2209–2222

Everything you always wanted to know about compiled and vectorized queries but were afraid to ask. Proceedings of the VLDB Endowment 11, 13 (2018), 2209–2222. Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe

work page 2018
[12]

The Tensor Algebra Compiler. Proc. ACM Program. Lang. 1, OOPSLA, Article 77 (oct 2017), 29 pages. https://doi.org/10.1145/3133901 Yannis Klonatos, Christoph Koch, Tiark Rompf, and Hassan Chafi

doi:10.1145/3133901 2017
[15]

Relaxed Operator Fusion for In-Memory Databases: Making Compilation, Vectorization, and Prefetching Work Together at Last. Proc. VLDB Endow. 11, 1 (sep 2017), 1–13. https: //doi.org/10.14778/3151113.3151114 Amine Mhedhbi, Matteo Lissandrini, Laurens Kuiper, Jack Waudby, and Gábor Szárnyas

arXiv 2017
[16]

LSQB: a large-scale subgraph query benchmark. In Proceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)(Virtual Event, China)(GRADES-NDA ’21). Association for Computing Machinery, New York, NY, USA, Article 8, 11 pages. https://doi.org/10.1145/3461837.3464516 ...

arXiv
[17]

SIGMOD Rec

Skew Strikes Back: New Developments in the Theory of Join Algorithms. SIGMOD Rec. 42, 4 (feb 2014), 5–16. https://doi.org/10.1145/2590989.2590991 Shoumik Palkar

arXiv 2014
[20]

arXiv:2101.03091 [cs.SI] P

Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings. arXiv:2101.03091 [cs.SI] P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price

arXiv
[1976]

ACM Trans

The Design and Implementation of INGRES. ACM Trans. Database Syst. 1, 3 (sep 1976), 189–222. https://doi.org/10.1145/320473.320476 Apostolos Syropoulos

work page arXiv 1976

Show all 23 references

[1979]

InProceedings of the 1979 ACM SIGMOD International Conference on Management of Data (Boston, Massachusetts) (SIGMOD ’79)

Access path selection in a relational database management system. InProceedings of the 1979 ACM SIGMOD International Conference on Management of Data (Boston, Massachusetts) (SIGMOD ’79). Association for Computing Machinery, New York, NY, USA, 23–34. https://doi.org/10.1145/58...

1979
[1981]

A History and Evaluation of System R. Commun. ACM 24, 10 (oct 1981), 632–646. https://doi.org/10.1145/358769.358784 Surajit Chaudhuri

1981
[1994]

IEEE Trans

Volcano— An Extensible and Parallel Query Evaluation System. IEEE Trans. on Knowl. and Data Eng. 6, 1 (feb 1994), 120–135. https://doi.org/10.1109/69.273032 P.W.P.J. Grefen and R.A. de By

1994 doi
[1998]

In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Seattle, Washington, USA) (PODS ’98)

An overview of query optimization in relational systems. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Seattle, Washington, USA) (PODS ’98). Association for Computing Machinery, New York, NY, USA, 34–43. https://doi.org...
[2007]

Architecture of a Database System. Found. Trends Databases 1, 2 (Feb. 2007), 141–259. https://doi.org/10.1561/1900000002 Rawn Henry, Olivia Hsu, Rohan Yadav, Stephen Chou, Kunle Olukotun, Saman Amarasinghe, and Fredrik Kjolstad

2007 doi
[2008]

row-stores: how different are they really?

Column-stores vs. row-stores: how different are they really?. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (Vancouver, Canada) (SIGMOD ’08). Association for Computing Machinery, New York, NY, USA, 967–980. https://doi.org/10.1145/1376616...

2008
[2010]

In Proceedings of the Ninth International Conference on Generative Programming and Component Engineering (Eindhoven, The Netherlands) (GPCE ’10)

Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs. In Proceedings of the Ninth International Conference on Generative Programming and Component Engineering (Eindhoven, The Netherlands) (GPCE ’10). Association for Computing Machinery...
[2011]

In Proceedings of the 2011 IEEE 27th International Conference on Data Engineering (ICDE ’11)

HyPer: A Hybrid OLTP&OLAP Main Memory Database System Based on Virtual Memory Snapshots. In Proceedings of the 2011 IEEE 27th International Conference on Data Engineering (ICDE ’11) . IEEE Computer Society, USA, 195–206. https://doi.org/10.1109/ICDE.2011.5767867 Timo Kersten, ...

2011
[2013]

arXiv:1210.0481 [cs.DB] A Compiler for Operations on Relations with Bag Semantics 1:23 A PROOFS Lemma 5.1 (Floor function)

Leapfrog Triejoin: a worst-case optimal join algorithm. arXiv:1210.0481 [cs.DB] A Compiler for Operations on Relations with Bag Semantics 1:23 A PROOFS Lemma 5.1 (Floor function). Given an iteration machine over input set 𝑆, for every combination of inputs 𝑝 ⊆ 𝑆, there exists ...

arXiv
[2014]

Building Efficient Query Engines in a High-Level Language. Proc. VLDB Endow. 7, 10 (jun 2014), 853–864. https://doi.org/10.14778/2732951.2732959 Scott Kovach, Praneeth Kolichala, Tiancheng Gu, and Fredrik Kjolstad

2014
[2017]

ACM Transactions on Database Systems (TODS) 42, 4 (2017), 1–44

Emptyheaded: A relational engine for graph processing. ACM Transactions on Database Systems (TODS) 42, 4 (2017), 1–44. Peter A Boncz, Marcin Zukowski, and Niels Nes

2017
[2018]

Proceedings of the ACM on Programming Languages 2, OOPSLA (2018), 1–30

Format abstraction for sparse tensor algebra compilers. Proceedings of the ACM on Programming Languages 2, OOPSLA (2018), 1–30. Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom

2018
[2019]

In Proceedings of the 2019 International Conference on Management of Data (Amsterdam, Netherlands) (SIGMOD ’19)

DuckDB: An Embeddable Analytical Database. In Proceedings of the 2019 International Conference on Management of Data (Amsterdam, Netherlands) (SIGMOD ’19). Association for Computing Machinery, New York, NY, USA, 1981–1984. https://doi.org/10.1145/3299869.3320212 Tiark Rompf an...

2019
[2021]

ACM Program

Compilation of Sparse Array Programming Models.Proc. ACM Program. Lang. 5, OOPSLA, Article 128 (oct 2021), 29 pages. https://doi.org/10.1145/3485505 Alfons Kemper and Thomas Neumann

2021 doi
[2023]

Proceedings of the ACM on Programming Languages 7, PLDI (2023), 1169–1193

Indexed Streams: A Formal Intermediate Representation for Fused Contraction Programs. Proceedings of the ACM on Programming Languages 7, PLDI (2023), 1169–1193. Gianfranco Lamperti, Michele Melchiori, and Marina Zanella

2023

Pith tools

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

[1] [7]

In Proceedings of 1994 IEEE 10th International Conference on Data Engineering

A multi-set extended relational algebra: a formal approach to a practical issue. In Proceedings of 1994 IEEE 10th International Conference on Data Engineering . 80–88. https://doi.org/10.1109/ICDE.1994. 283002 Joseph M. Hellerstein, Michael Stonebraker, and James Hamilton

work page doi:10.1109/icde.1994 1994

[2] [11]

Proceedings of the VLDB Endowment 11, 13 (2018), 2209–2222

Everything you always wanted to know about compiled and vectorized queries but were afraid to ask. Proceedings of the VLDB Endowment 11, 13 (2018), 2209–2222. Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe

work page 2018

[3] [12]

The Tensor Algebra Compiler. Proc. ACM Program. Lang. 1, OOPSLA, Article 77 (oct 2017), 29 pages. https://doi.org/10.1145/3133901 Yannis Klonatos, Christoph Koch, Tiark Rompf, and Hassan Chafi

doi:10.1145/3133901 2017

[4] [15]

Relaxed Operator Fusion for In-Memory Databases: Making Compilation, Vectorization, and Prefetching Work Together at Last. Proc. VLDB Endow. 11, 1 (sep 2017), 1–13. https: //doi.org/10.14778/3151113.3151114 Amine Mhedhbi, Matteo Lissandrini, Laurens Kuiper, Jack Waudby, and Gábor Szárnyas

arXiv 2017

[5] [16]

LSQB: a large-scale subgraph query benchmark. In Proceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)(Virtual Event, China)(GRADES-NDA ’21). Association for Computing Machinery, New York, NY, USA, Article 8, 11 pages. https://doi.org/10.1145/3461837.3464516 ...

arXiv

[6] [17]

SIGMOD Rec

Skew Strikes Back: New Developments in the Theory of Join Algorithms. SIGMOD Rec. 42, 4 (feb 2014), 5–16. https://doi.org/10.1145/2590989.2590991 Shoumik Palkar

arXiv 2014

[7] [20]

arXiv:2101.03091 [cs.SI] P

Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings. arXiv:2101.03091 [cs.SI] P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price

arXiv

[8] [1976]

ACM Trans

The Design and Implementation of INGRES. ACM Trans. Database Syst. 1, 3 (sep 1976), 189–222. https://doi.org/10.1145/320473.320476 Apostolos Syropoulos

work page arXiv 1976