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: hc44390d0793f7486
Venue: PODS
Year: 2025
Pagerank: 5.7428578e-05
Overall Rank: 6,576 | 55.81%
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 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,420	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1802184e-05
10,368	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.9769913e-05
10,375	Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries	2026	PODS	4.9769913e-05
10,377	Size Bound-Adorned Datalog	2026	PODS	4.9769913e-05
10,519	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	4.9769913e-05
10,723	Robust Predicate Transfer with Dynamic Execution	2026	VLDB	4.9769913e-05
10,812	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9769913e-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.00059813669
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021236408
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020013731
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019095982
521	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016923519
813	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013722638
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012068611
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020376
2,216	The Input/Output Complexity of Triangle Enumeration	2014	PODS	8.8152513e-05
2,302	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.6687541e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4221003e-05
2,517	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.3550625e-05
2,584	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	8.2555687e-05
3,154	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	7.5849549e-05
4,371	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6284915e-05
4,510	Conjunctive Queries with Comparisons	2022	SIGMOD	6.5673056e-05
4,945	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.3418058e-05
5,061	Change Propagation Without Joins	2023	VLDB	6.2897936e-05
5,491	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.1067499e-05
5,500	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.1020763e-05
5,596	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0698953e-05
6,469	Output-sensitive Conjunctive Query Evaluation	2024	PODS	5.7719911e-05
6,533	Query Evaluation by Circuits	2022	PODS	5.7519838e-05
6,569	Fast Matrix Multiplication for Query Processing	2024	PODS	5.7442578e-05
6,811	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	5.6754603e-05
7,294	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5616228e-05
9,952	On Efficient Large Sparse Matrix Chain Multiplication	2024	SIGMOD	5.101836e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,147	Conjunctive Queries with Inequalities Under Updates	2018	VLDB
2	6,811	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB
3	3,994	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
4	10,399	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS
5	3,661	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
6	11,036	Instance-Optimal Acyclic Joins: From Theory to Systems	2026	VLDB
7	10,398	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
8	4,466	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS
9	4,477	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS
10	6,469	Output-sensitive Conjunctive Query Evaluation	2024	PODS