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.9536872e-05
Overall Rank
5,902 | 60.32%
DOI
10.1145/3725423

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.0023947656
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061066921
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036828234
145 Neo: A Learned Query Optimizer 2019 VLDB 0.0002908188
151 An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server 1997 VLDB 0.00028672526
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024884544
233 Amazon Redshift and the Case for Simpler Data Warehouses 2015 SIGMOD 0.00023783585
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021246
318 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021167555
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020020639
379 Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources 2018 SIGMOD 0.00019514689
682 Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques 2012 VLDB 0.0001481781
684 Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants 2007 PODS 0.00014798237
750 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014265196
812 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013729015
884 Dynamic Programming Strikes Back 2008 SIGMOD 0.00013267935
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012074152
1,257 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011310561
1,279 AI Meets AI: Leveraging Query Executions to Improve Index Recommendations 2019 SIGMOD 0.00011226878
1,301 Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products 2006 VLDB 0.00011112842
1,433 Towards a Learning Optimizer for Shared Clouds 2019 VLDB 0.00010677711
1,465 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010576304
1,570 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.0001020855
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010127607
1,678 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.9088372e-05
1,726 Optimal Top-Down Join Enumeration 2007 SIGMOD 9.788916e-05
1,734 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7545773e-05
1,891 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4184294e-05
2,251 Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs 2013 VLDB 8.7511987e-05
2,365 Hypertree Decompositions and Tractable Queries 1999 PODS 8.5654557e-05
2,517 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.3589894e-05
2,582 Secure Yannakakis: Join-Aggregate Queries over Private Data 2021 SIGMOD 8.2594787e-05
2,834 Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings 2020 SIGMOD 7.9560627e-05
2,952 Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation 2018 SIGMOD 7.8153507e-05
3,153 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.5883271e-05
3,285 Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput 2019 VLDB 7.4559907e-05
3,327 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 7.4207879e-05
4,369 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 6.6315141e-05
4,509 Conjunctive Queries with Comparisons 2022 SIGMOD 6.570408e-05
4,950 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3421691e-05
5,057 Change Propagation Without Joins 2023 VLDB 6.2927647e-05
5,534 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.0923159e-05
6,805 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6780394e-05
7,292 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 5.5642569e-05
7,633 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4792473e-05
11,526 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Semantically Similar Papers