Back to papers
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
- 1975
- Venue
- PODS
- Year
- 2025
- Pagerank
- 4.4897014e-05
- Overall Rank
- 8,589 | 40.25%
- DOI
-
10.1145/3725241
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 26 of 26 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 31 |
Provenance Semirings |
2007 |
PODS |
0.0007857786 |
| 502 |
Worst-case Optimal Join Algorithms |
2012 |
PODS |
0.00021526612 |
| 583 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00019717214 |
| 834 |
Learning Linear Regression Models over Factorized Joins |
2016 |
SIGMOD |
0.00016135159 |
| 1,056 |
The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates |
2017 |
SIGMOD |
0.0001441128 |
| 1,442 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011956109 |
| 2,169 |
AJAR: Aggregations and Joins over Annotated Relations |
2016 |
PODS |
9.3845975e-05 |
| 2,215 |
The Input/Output Complexity of Triangle Enumeration |
2014 |
PODS |
9.2717602e-05 |
| 3,006 |
On Functional Aggregate Queries with Additive Inequalities |
2019 |
PODS |
7.7299363e-05 |
| 3,024 |
Secure Yannakakis: Join-Aggregate Queries over Private Data |
2021 |
SIGMOD |
7.692511e-05 |
| 3,371 |
On the Enumeration Complexity of Unions of Conjunctive Queries |
2019 |
PODS |
7.1696145e-05 |
| 3,833 |
Output-optimal Parallel Algorithms for Similarity Joins |
2017 |
PODS |
6.7173578e-05 |
| 3,885 |
Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations |
2022 |
VLDB |
6.6674822e-05 |
| 4,465 |
Robust Join Processing with Diamond Hardened Joins |
2024 |
VLDB |
6.1604282e-05 |
| 5,639 |
Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins |
2021 |
PODS |
5.393897e-05 |
| 5,718 |
Conjunctive Queries with Comparisons |
2022 |
SIGMOD |
5.3552123e-05 |
| 5,765 |
Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries |
2024 |
CIDR |
5.336442e-05 |
| 5,967 |
Change Propagation Without Joins |
2023 |
VLDB |
5.250976e-05 |
| 6,647 |
Fast Join Project Query Evaluation using Matrix Multiplication |
2020 |
SIGMOD |
4.9772122e-05 |
| 7,017 |
Query Evaluation by Circuits |
2022 |
PODS |
4.8603097e-05 |
| 7,065 |
Fast Matrix Multiplication for Query Processing |
2024 |
PODS |
4.8447515e-05 |
| 7,126 |
Debunking the Myth of Join Ordering: Toward Robust SQL Analytics |
2025 |
SIGMOD |
4.8232367e-05 |
| 7,162 |
Computing the Difference of Conjunctive Queries Efficiently |
2023 |
SIGMOD |
4.8132423e-05 |
| 8,034 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.6010599e-05 |
| 8,966 |
Output-sensitive Conjunctive Query Evaluation |
2024 |
PODS |
4.4193184e-05 |
| 9,670 |
On Efficient Large Sparse Matrix Chain Multiplication |
2024 |
SIGMOD |
4.3066148e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 5,962 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2536266e-05 |
| 4,953 |
On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms |
2023 |
PODS |
5.8085795e-05 |
| 1,056 |
The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates |
2017 |
SIGMOD |
0.0001441128 |
| 5,576 |
Conjunctive Queries with Inequalities Under Updates |
2018 |
VLDB |
5.426344e-05 |
| 8,034 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.6010599e-05 |
| 5,104 |
Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins |
2023 |
PODS |
5.6946113e-05 |
| 3,515 |
Scalable Computation of Acyclic Joins (Extended Abstract) |
2006 |
PODS |
7.0220813e-05 |
| 4,708 |
Instance and Output Optimal Parallel Algorithms for Acyclic Joins |
2019 |
PODS |
5.980172e-05 |
| 4,432 |
Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins |
2016 |
PODS |
6.1938383e-05 |
| 8,966 |
Output-sensitive Conjunctive Query Evaluation |
2024 |
PODS |
4.4193184e-05 |