DunceCap: Compiling Worst-Case Optimal Query Plans

Summary: DunceCap is a query compiler that combines Yannakakis' acyclic-join algorithm with a universal worst-case optimal planner to produce end-to-end optimal plans. It yields order-of-magnitude gains over standard RDBMS and simple WCO baselines on diverse multiway-join workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5155
Venue: SIGMOD
Year: 2015
Pagerank: 5.4743814e-05
Overall Rank: 8,168 | 43.97%
DOI: 10.1145/2723372.2764945

Incoming Non-self Citations Over Time

Authors

1. Adam Perelman (Stanford University)
2. Christopher Ré (Stanford University)

BibTeX Citation

@inproceedings{perelman_sigmod15,
        title = {{DunceCap: Compiling Worst-Case Optimal Query Plans}},
        author = {Perelman, Adam and Ré, Christopher},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2764945},
        url = {https://dl.acm.org/doi/10.1145/2723372.2764945},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,549	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010390168
5,461	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.2090515e-05
8,374	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	5.4399097e-05
9,720	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	5.2319816e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS
2	1,759	Rank-aware Query Optimization	2004	SIGMOD
3	7,207	A Scalable and Generic Approach to Range Joins	2022	VLDB
4	6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD
5	136	Join Synopses for Approximate Query Answering	1999	SIGMOD
6	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
7	4,346	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD
8	8,636	Adaptive Code Generation for Data-Intensive Analytics	2021	VLDB
9	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
10	3,841	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD