一句话：提出基于抽象循环IR的关系代数编译器，可在集合与多重集上融合算子并生成高效C++代码。
本文研究如何为集合与多重集上的关系代数提供统一的编译方法，并支持生产数据库中的复杂算子，如外连接、非等值连接和差集。作者设计了一种以循环为中心的抽象中间表示，将物理数据结构抽象掉以便优化，并给出从关系代数查询计划树到该IR的 lowering 方法。随后，该IR被编译为高效C++代码，对表达式中的物理数据结构进行共同迭代，且方法可移植于不同数据结构。由于能够跨不同算子融合，该方法在部分LSQB基准和最坏情况最优三角形查询上相比Hyper取得3.8倍加速（0.8–12.1倍）；在TPC-H上顺序性能与Hyper相当（1.0倍，0.4–4.3倍），并行性能接近Hyper（0.6倍，0.2–1.8倍），代码质量较高。
We describe a comprehensive compilation approach for relational algebra, centered on an abstract loop-based intermediate representation (IR) that can express fused implementations of relational algebra operators on both sets and multisets. The loops are abstracted away from physical data structures thus making it easier to optimize. We show how to lower relational algebra query plan trees to the IR, including the complex operators that are used in production database systems, such as 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 relational algebra expressions. Finally, we show that our approach is portable across data structures. Since our approach can fuse across disparate operators, it achieves a 3.8x speedup (0.8--12.1x) compared to Hyper on selected LSQB benchmarks and worst-case optimal triangle queries. Our compiler also generates code of high quality: it has similar sequential performance to Hyper on TPC-H with a 1.0x speedup (0.4--4.3x) and is approaching their parallel performance with a 0.6x speedup (0.2--1.8x).
@article{DongK26,
title = {A Compiler for Fused Relational Operations on Multisets},
author = {James Dong and Fredrik Kjolstad},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {PLDI},
year = {2026},
doi = {10.1145/3808283}
}