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: 7309
Venue: SIGMOD
Year: 2025
Pagerank: 4.7218691e-05
Overall Rank: 7,467 | 48.06%
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,126	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8232367e-05
8,207	SQLStorm: Taking Database Benchmarking into the LLM Era	2025	VLDB	4.5583637e-05
9,988	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.1945683e-05
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1945683e-05
10,241	Robust Predicate Transfer with Dynamic Execution	2026	VLDB	4.1945683e-05
13,127	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.0040449103
59	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064501896
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
237	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00031726304
333	Neo: A Learned Query Optimizer	2019	VLDB	0.00027206884
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
426	Amazon Redshift and the Case for Simpler Data Warehouses	2015	SIGMOD	0.00023594359
544	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00020521965
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
608	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019235898
626	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018973823
1,019	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014625603
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
1,193	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00013414989
1,341	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012486285
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
1,758	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010655546
1,826	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00010400425
1,855	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00010315245
2,050	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.6886663e-05
2,083	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	9.5834572e-05
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
2,169	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3845975e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1897043e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
2,377	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9402115e-05
2,783	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1293383e-05
2,785	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1286814e-05
2,796	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1112658e-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,608	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	6.924272e-05
3,625	Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings	2020	SIGMOD	6.9055212e-05
4,158	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	6.3994318e-05
4,417	Robust Query Driven Cardinality Estimation under Changing Workloads	2023	VLDB	6.2037371e-05
4,465	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	6.1604282e-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,879	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.2908101e-05
5,967	Change Propagation Without Joins	2023	VLDB	5.250976e-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
7,728	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.666214e-05
8,034	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	4.6010599e-05
10,970	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,718	Conjunctive Queries with Comparisons	2022	SIGMOD	5.3552123e-05
8,195	DunceCap: Compiling Worst-Case Optimal Query Plans	2015	SIGMOD	4.561696e-05
4,432	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1938383e-05
10,970	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1945683e-05
3,024	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	7.692511e-05
8,589	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4897014e-05
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
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128