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.7238683e-05
Overall Rank: 6,585 | 55.87%
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,445	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1630894e-05
10,435	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.9605343e-05
10,441	Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries	2026	PODS	4.9605343e-05
10,443	Size Bound-Adorned Datalog	2026	PODS	4.9605343e-05
10,585	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	4.9605343e-05
10,784	Robust Predicate Transfer with Dynamic Execution	2026	VLDB	4.9605343e-05
10,873	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9605343e-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.00059660827
318	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021178303
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020048899
397	Worst-case Optimal Join Algorithms	2012	PODS	0.0001911958
522	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016893112
815	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013682594
1,096	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012035761
1,568	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010178045
2,229	The Input/Output Complexity of Triangle Enumeration	2014	PODS	8.7890942e-05
2,316	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.6404062e-05
2,475	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.3947133e-05
2,526	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.3274934e-05
2,593	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	8.2282707e-05
3,165	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	7.5598778e-05
4,396	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6072577e-05
4,527	Conjunctive Queries with Comparisons	2022	SIGMOD	6.5466033e-05
4,971	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.3209003e-05
5,080	Change Propagation Without Joins	2023	VLDB	6.2689958e-05
5,514	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.0866191e-05
5,522	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.0818991e-05
5,610	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0498245e-05
6,482	Output-sensitive Conjunctive Query Evaluation	2024	PODS	5.7529053e-05
6,545	Query Evaluation by Circuits	2022	PODS	5.7329641e-05
6,579	Fast Matrix Multiplication for Query Processing	2024	PODS	5.7252637e-05
6,826	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	5.6566963e-05
7,311	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5432326e-05
9,985	On Efficient Large Sparse Matrix Chain Multiplication	2024	SIGMOD	5.0849662e-05

Semantically Similar Papers

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