DBScholar

Back to papers

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
h30293d3960aa9d5d
Venue
SIGMOD
Year
2025
Pagerank
5.9338021e-05
Overall Rank
5,911 | 60.38%
DOI
10.1145/3725423
PDF
Download (CC BY-NC-SA 4.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{wang_sigmod25,
        title = {{Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees}},
        author = {Wang, Qichen and Chen, Bingnan and Dai, Binyang and Yi, Ke and Li, Feifei and Lin, Liang},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3725423},
        url = {https://dl.acm.org/doi/10.1145/3725423},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 47 of 47 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.0023948467
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061463175
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
78 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036725074
142 Neo: A Learned Query Optimizer 2019 VLDB 0.00029114937
151 An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server 1997 VLDB 0.00028611216
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024929198
226 Amazon Redshift and the Case for Simpler Data Warehouses 2015 SIGMOD 0.0002389883
318 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021178303
320 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021128745
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020048899
382 Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources 2018 SIGMOD 0.0001946654
676 Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques 2012 VLDB 0.00014838681
685 Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants 2007 PODS 0.00014747128
752 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014234789
815 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013682594
881 Dynamic Programming Strikes Back 2008 SIGMOD 0.0001324243
1,096 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012035761
1,261 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011289724
1,282 AI Meets AI: Leveraging Query Executions to Improve Index Recommendations 2019 SIGMOD 0.00011197535
1,293 Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products 2006 VLDB 0.00011143846
1,436 Towards a Learning Optimizer for Shared Clouds 2019 VLDB 0.00010658836
1,444 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010616242
1,568 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.00010178045
1,603 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010090639
1,681 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.8821344e-05
1,732 Optimal Top-Down Join Enumeration 2007 SIGMOD 9.7561649e-05
1,740 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7289523e-05
1,896 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4010932e-05
2,261 Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs 2013 VLDB 8.7351549e-05
2,376 Hypertree Decompositions and Tractable Queries 1999 PODS 8.5345413e-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
2,828 Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings 2020 SIGMOD 7.9476509e-05
2,965 Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation 2018 SIGMOD 7.7894987e-05
3,165 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.5598778e-05
3,269 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 7.463682e-05
3,297 Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput 2019 VLDB 7.4280812e-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,552 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.0707348e-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
7,654 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4588598e-05
11,581 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

Semantically Similar Papers