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.4853975e-05
- Overall Rank
- 8,587 | 40.33%
- 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.00078516827 |
| 503 |
Worst-case Optimal Join Algorithms |
2012 |
PODS |
0.00021517145 |
| 564 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00020002796 |
| 832 |
Learning Linear Regression Models over Factorized Joins |
2016 |
SIGMOD |
0.00016089705 |
| 1,054 |
The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates |
2017 |
SIGMOD |
0.00014397587 |
| 1,452 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011922523 |
| 2,173 |
AJAR: Aggregations and Joins over Annotated Relations |
2016 |
PODS |
9.3767985e-05 |
| 2,219 |
The Input/Output Complexity of Triangle Enumeration |
2014 |
PODS |
9.2653868e-05 |
| 3,009 |
On Functional Aggregate Queries with Additive Inequalities |
2019 |
PODS |
7.7230513e-05 |
| 3,022 |
Secure Yannakakis: Join-Aggregate Queries over Private Data |
2021 |
SIGMOD |
7.6942462e-05 |
| 3,374 |
On the Enumeration Complexity of Unions of Conjunctive Queries |
2019 |
PODS |
7.1631303e-05 |
| 3,831 |
Output-optimal Parallel Algorithms for Similarity Joins |
2017 |
PODS |
6.7146681e-05 |
| 3,886 |
Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations |
2022 |
VLDB |
6.6610704e-05 |
| 4,466 |
Robust Join Processing with Diamond Hardened Joins |
2024 |
VLDB |
6.1545841e-05 |
| 5,650 |
Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins |
2021 |
PODS |
5.3887172e-05 |
| 5,728 |
Conjunctive Queries with Comparisons |
2022 |
SIGMOD |
5.350072e-05 |
| 5,772 |
Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries |
2024 |
CIDR |
5.3313794e-05 |
| 5,973 |
Change Propagation Without Joins |
2023 |
VLDB |
5.2459364e-05 |
| 6,647 |
Fast Join Project Query Evaluation using Matrix Multiplication |
2020 |
SIGMOD |
4.9729424e-05 |
| 7,017 |
Query Evaluation by Circuits |
2022 |
PODS |
4.8556471e-05 |
| 7,060 |
Fast Matrix Multiplication for Query Processing |
2024 |
PODS |
4.8401037e-05 |
| 7,122 |
Debunking the Myth of Join Ordering: Toward Robust SQL Analytics |
2025 |
SIGMOD |
4.8199209e-05 |
| 7,161 |
Computing the Difference of Conjunctive Queries Efficiently |
2023 |
SIGMOD |
4.8086254e-05 |
| 8,035 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.5967078e-05 |
| 8,972 |
Output-sensitive Conjunctive Query Evaluation |
2024 |
PODS |
4.4150824e-05 |
| 9,670 |
On Efficient Large Sparse Matrix Chain Multiplication |
2024 |
SIGMOD |
4.3024878e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 5,963 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2485815e-05 |
| 4,926 |
On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms |
2023 |
PODS |
5.8184457e-05 |
| 1,054 |
The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates |
2017 |
SIGMOD |
0.00014397587 |
| 5,582 |
Conjunctive Queries with Inequalities Under Updates |
2018 |
VLDB |
5.4211286e-05 |
| 8,035 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.5967078e-05 |
| 5,085 |
Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins |
2023 |
PODS |
5.7040225e-05 |
| 3,519 |
Scalable Computation of Acyclic Joins (Extended Abstract) |
2006 |
PODS |
7.0181381e-05 |
| 4,709 |
Instance and Output Optimal Parallel Algorithms for Acyclic Joins |
2019 |
PODS |
5.9744219e-05 |
| 4,430 |
Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins |
2016 |
PODS |
6.1879319e-05 |
| 8,972 |
Output-sensitive Conjunctive Query Evaluation |
2024 |
PODS |
4.4150824e-05 |