Output-Optimal Algorithms for Join-Aggregate Queries

Summary: Output-optimal algorithms for acyclic join-aggregate queries over commutative semirings; runtime Theta(N * OUT^(1-1/fn-fhtw) + OUT), with fn-fhtw the free-connex fractional hypertree width. First polynomial improvement over Yannakakis in four decades; resolves the open question and yields output-sensitive results for cyclic queries via tree decompositions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2007
Venue: PODS
Year: 2025
Pagerank: 5.8774519e-05
Overall Rank: 6,444 | 55.79%
DOI: 10.1145/3725241

Incoming Non-self Citations Over Time

Authors

1. Xiao Hu (University of Waterloo)

BibTeX Citation

@inproceedings{hu_pods25,
        address = {New York, NY, USA},
        series = {{PODS} '25},
        title = {{Output-Optimal Algorithms for Join-Aggregate Queries}},
        url = {https://dl.acm.org/doi/10.1145/3725241},
        doi = {10.1145/3725241},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hu, Xiao},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,235	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.3016261e-05
10,135	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	5.093636e-05
10,146	Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries	2026	PODS	5.093636e-05
10,148	Size Bound-Adorned Datalog	2026	PODS	5.093636e-05
10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	5.093636e-05
10,529	Robust Predicate Transfer with Dynamic Execution	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 27 of 27 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059843817
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
816	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013827772
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,549	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010390168
2,183	The Input/Output Complexity of Triangle Enumeration	2014	PODS	9.0066814e-05
2,266	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.8391372e-05
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
2,468	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.5358494e-05
2,573	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	8.4015654e-05
3,622	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	7.2465862e-05
4,553	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6346951e-05
4,575	Conjunctive Queries with Comparisons	2022	SIGMOD	6.6223692e-05
4,985	Change Propagation Without Joins	2023	VLDB	6.412102e-05
5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.2472125e-05
5,368	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.2448114e-05
5,463	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.2086169e-05
5,529	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.18591e-05
6,398	Query Evaluation by Circuits	2022	PODS	5.8867918e-05
6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS	5.8053953e-05
6,885	Fast Matrix Multiplication for Query Processing	2024	PODS	5.7464502e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.6852987e-05
7,386	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	5.6273882e-05
9,766	On Efficient Large Sparse Matrix Chain Multiplication	2024	SIGMOD	5.2214067e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	816	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD
2	5,066	Conjunctive Queries with Inequalities Under Updates	2018	VLDB
3	7,386	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB
4	3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
5	10,170	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS
6	3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
7	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
8	4,371	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS
9	4,401	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS
10	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS