DBScholar

Back to papers

Sampling-Based Query Re-Optimization

Summary: Sampling-based, low-cost post-processing detects likely cardinality-estimation errors in an optimizer’s plan and iteratively re-optimizes it with targeted sampling. Minimal integration burden—no changes to optimizer or evaluator—and low overhead demonstrated on PostgreSQL and two commercial systems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h36a13e9d959671ea
Venue
SIGMOD
Year
2016
Pagerank
0.00011289724
Overall Rank
1,261 | 91.55%
DOI
10.1145/2882903.2882914

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{wu_sigmod16,
        title = {{Sampling-Based Query Re-Optimization}},
        author = {Wu, Wentao and Naughton, Jeffrey F. and Singh, Harneet},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2882914},
        url = {https://dl.acm.org/doi/10.1145/2882903.2882914},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank Citing Paper Year Venue Pagerank
84 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035920657
453 An End-to-End Learning-based Cost Estimator 2020 VLDB 0.0001801482
689 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014725904
793 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013903938
1,064 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012181459
1,282 AI Meets AI: Leveraging Query Executions to Improve Index Recommendations 2019 SIGMOD 0.00011197535
1,609 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.0001007196
1,803 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.5987229e-05
2,523 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 8.3316032e-05
2,987 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.767043e-05
3,717 Logical and Physical Optimizations for SQL Query Execution over Large Language Models 2025 SIGMOD 7.05392e-05
4,202 Kepler: Robust Learning for Faster Parametric Query Optimization 2023 SIGMOD 6.7258607e-05
4,252 Adaptive Statistics in Oracle 12c 2017 VLDB 6.6894038e-05
4,329 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.64569e-05
4,726 Learned Index Benefits: Machine Learning Based Index Performance Estimation 2022 VLDB 6.4329878e-05
5,153 Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach 2020 SIGMOD 6.2375324e-05
5,223 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 6.210331e-05
5,713 PilotScope: Steering Databases with Machine Learning Drivers 2024 VLDB 6.0090633e-05
5,841 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.9569427e-05
5,911 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9338021e-05
6,672 Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation 2023 SIGMOD 5.6975871e-05
6,812 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6597129e-05
7,094 Plan Stitch: Harnessing the Best of Many Plans 2018 VLDB 5.5863735e-05
7,975 Robust Query Processing: Mission Possible 2020 VLDB 5.3985544e-05
8,064 Efficiently Computing Join Orders with Heuristic Search 2023 SIGMOD 5.3813708e-05
8,188 Efficient Query Re-optimization with Judicious Subquery Selections 2023 SIGMOD 5.3649397e-05
8,297 Consistent and Flexible Selectivity Estimation for High-Dimensional Data 2021 SIGMOD 5.3438874e-05
8,361 MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates 2020 SIGMOD 5.3310744e-05
8,550 ROME: Robust Query Optimization via Parallel Multi-Plan Execution 2024 SIGMOD 5.3030089e-05
8,872 SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms 2023 VLDB 5.2459616e-05
9,829 Wii: Dynamic Budget Reallocation In Index Tuning 2024 SIGMOD 5.1066866e-05
10,676 Understanding and Detecting Query Performance Regression in Practical Index Tuning: [Experiments & Analysis] 2026 SIGMOD 4.9605343e-05
10,988 Evaluating the Practical Effectiveness of LLM-Driven Index Tuning on Microsoft SQL Server 2026 VLDB 4.9605343e-05
11,288 Esc: An Early-Stopping Checker for Budget-aware Index Tuning 2025 VLDB 4.9605343e-05
11,501 LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison 2025 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 28 of 28 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
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036394222
98 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034050614
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00031291457
149 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00028910892
160 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00027775994
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
259 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022881075
287 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00022060616
291 Optimization of Dynamic Query Evaluation Plans 1994 SIGMOD 0.00021898776
296 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021874894
372 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019768921
432 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018400309
471 Robust Query Processing through Progressive Optimization 2004 SIGMOD 0.00017691682
479 Dynamic Query Evaluation Plans 1989 SIGMOD 0.00017595584
568 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016221103
646 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.00015166402
752 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014234789
792 Parametric Query Optimization 1992 VLDB 0.00013903954
996 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB 0.00012595827
1,061 Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions 2011 VLDB 0.00012207625
1,987 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.2323722e-05
2,381 To Tune or not to Tune? A Lightweight Physical Design Alerter 2006 VLDB 8.5299827e-05
3,384 Towards Predicting Query Execution Time for Concurrent and Dynamic Database Workloads 2013 VLDB 7.3392425e-05
4,088 Dynamically Optimizing Queries over Large Scale Data Platforms 2014 SIGMOD 6.7973616e-05
5,490 A Pay-As-You-Go Framework for Query Execution Feedback 2008 VLDB 6.0970166e-05
5,670 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 6.0266818e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,387 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD
2 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
3 2,438 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD
4 471 Robust Query Processing through Progressive Optimization 2004 SIGMOD
5 149 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD
6 8,188 Efficient Query Re-optimization with Judicious Subquery Selections 2023 SIGMOD
7 689 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR
8 381 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB
9 568 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD
10 9,667 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD