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.7455776e-05
Overall Rank: 6,573 | 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,410	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1826718e-05
10,356	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.9793485e-05
10,363	Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries	2026	PODS	4.9793485e-05
10,365	Size Bound-Adorned Datalog	2026	PODS	4.9793485e-05
10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	4.9793485e-05
10,713	Robust Predicate Transfer with Dynamic Execution	2026	VLDB	4.9793485e-05
10,802	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9793485e-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.00059752575
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021246
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020020639
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
521	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016929744
812	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013729015
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012074152
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020855
2,215	The Input/Output Complexity of Triangle Enumeration	2014	PODS	8.8194236e-05
2,299	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.6727773e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4260608e-05
2,517	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.3589894e-05
2,582	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	8.2594787e-05
3,153	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	7.5883271e-05
4,369	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6315141e-05
4,509	Conjunctive Queries with Comparisons	2022	SIGMOD	6.570408e-05
4,950	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.3421691e-05
5,057	Change Propagation Without Joins	2023	VLDB	6.2927647e-05
5,487	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.1096421e-05
5,496	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.1049663e-05
5,595	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0727701e-05
6,467	Output-sensitive Conjunctive Query Evaluation	2024	PODS	5.7747248e-05
6,531	Query Evaluation by Circuits	2022	PODS	5.754708e-05
6,567	Fast Matrix Multiplication for Query Processing	2024	PODS	5.7469783e-05
6,805	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	5.6780394e-05
7,292	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5642569e-05
9,944	On Efficient Large Sparse Matrix Chain Multiplication	2024	SIGMOD	5.1042523e-05

Semantically Similar Papers

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