Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees

Summary: Yannakakis+ provides a practical, constant-factor-efficient acyclic CQ evaluator with theoretical guarantees. It emits a conventional DAG plan for integration with SQL engines (DuckDB, PostgreSQL, SparkSQL, AnalyticDB), delivering 2x-5x speedups (avg 2.41x) on most queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7310
Venue: SIGMOD
Year: 2025
Pagerank: 4.7186055e-05
Overall Rank: 7,465 | 48.12%
DOI: 10.1145/3725423

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,122	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8199209e-05
7,887	SQLStorm: Taking Database Benchmarking into the LLM Era	2025	VLDB	4.6218382e-05
9,987	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.1905499e-05
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1905499e-05
10,241	Robust Predicate Transfer with Dynamic Execution	2026	VLDB	4.1905499e-05
13,141	Query running too slow? Rewrite it with Quorion!	2025	VLDB	-

Outgoing Citations (Sorted by Pagerank)

Showing 46 of 46 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
237	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00031727601
329	Neo: A Learned Query Optimizer	2019	VLDB	0.00027301488
341	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026850764
424	Amazon Redshift and the Case for Simpler Data Warehouses	2015	SIGMOD	0.00023604384
542	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00020522627
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
606	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019251186
623	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018976192
1,017	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014627121
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
1,194	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00013411666
1,344	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012477274
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
1,756	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010659753
1,825	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00010392367
1,856	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00010319105
2,053	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.682841e-05
2,080	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	9.5954034e-05
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
2,173	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3767985e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
2,369	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9462051e-05
2,778	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1345892e-05
2,781	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1282042e-05
2,804	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1039107e-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,611	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	6.9178844e-05
3,623	Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings	2020	SIGMOD	6.9017341e-05
4,157	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	6.3935343e-05
4,413	Robust Query Driven Cardinality Estimation under Changing Workloads	2023	VLDB	6.1989918e-05
4,466	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	6.1545841e-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,832	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.3085972e-05
5,973	Change Propagation Without Joins	2023	VLDB	5.2459364e-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
7,725	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.6621296e-05
8,035	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	4.5967078e-05
10,973	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,728	Conjunctive Queries with Comparisons	2022	SIGMOD	5.350072e-05
8,195	DunceCap: Compiling Worst-Case Optimal Query Plans	2015	SIGMOD	4.5573236e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
10,973	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1905499e-05
3,022	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	7.6942462e-05
8,587	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4853975e-05
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
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587