A Compiler for Fused Relational Operations on Multisets
summary
A compiler lowers physical query plans into an abstract loop IR that fuses inner joins, left/right/full outer joins, non‑equi joins, set ops and multiset (bag) semantics, then emits C++ that co‑iterates over provided data structures via generalized iteration machines. Built code is portable across tries, row/column stores and hash tables; index‑build time is excluded from reported runs. Evaluation shows a 3.8x geometric mean speedup (0.8–12.1x) vs Hyper on selected LSQB and worst‑case triangle queries, with TPC‑H sequential parity (~1.0x) and parallel ~0.6x.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:05Fusing relational operators
- 2:29Worst-case optimal joins
- 3:33Fusion limitations
- 4:14Compiler architecture
- 5:17Relational vs tensor algebra
- 6:41Complex operations handling
- 7:24Coordinate trees
- 8:06Outer joins in IR
- 9:57Lowering query plans
- 11:20Query plan lowering example
- 12:45Performance evaluation
- 13:48Benchmark results
- 14:09Conclusion
- 14:30Q&A
related talks
17mTowards Iterative Relational Algebra on the GPU
23mDeep Fusion for Efficient Nested Recursive Computations
05mRelational Programming
27mFunctional Programming on Top of SQL Engines
19mCompiling Recurrences over Dense and Sparse Arrays
16mIndexed Streams: A Formal Intermediate Representation for Fused Contraction Programs
41mHow types can turn a SQL interpreter into a SQL compiler
18mCompilation of Shape Operators on Sparse Arrays