Proactive Re-Optimization

Summary: Proactive re-optimization computes bounding boxes around statistics to bound estimate errors, selects plans robust to deviations for skewed/correlated data, and enables rapid online statistics collection during execution. Rio prototype shows up to 3× gains over traditional re-optimizers on complex queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4119affa7ed4a478
Venue: SIGMOD
Year: 2005
Pagerank: 0.00013551072
Overall Rank: 837 | 94.38%
DOI: 10.1145/1066157.1066171

Incoming Non-self Citations Over Time

Authors

1. Shivnath Babu (Stanford University)
2. Pedro Bizarro (University of Wisconsin)
3. David DeWitt (University of Wisconsin)

BibTeX Citation

@inproceedings{babu_sigmod05,
        title = {{Proactive Re-Optimization}},
        author = {Babu, Shivnath and Bizarro, Pedro and DeWitt, David},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066171},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066171},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 51 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019095982
688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014749318
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010572023
1,605	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	0.00010095581
1,800	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.6082185e-05
1,835	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD	9.53331e-05
1,989	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.2469024e-05
2,162	DIFF: A Relational Interface for Large-Scale Data Explanation	2019	VLDB	8.9344773e-05
2,524	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3400278e-05
3,527	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.2283486e-05
3,544	Computation Reuse in Analytics Job Service at Microsoft	2018	SIGMOD	7.2108612e-05
3,593	Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads	2017	VLDB	7.1803217e-05
4,069	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD	6.8184364e-05
4,108	Content-Based Routing: Different Plans for Different Data	2005	VLDB	6.8000756e-05
4,508	Xplus: A SQL-Tuning-Aware Query Optimizer	2010	VLDB	6.5696141e-05
4,796	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	6.409726e-05
4,945	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.3418058e-05
5,200	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.2303304e-05
5,227	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.2183387e-05
5,553	Aero: Adaptive Query Processing of ML Queries	2025	SIGMOD	6.0843382e-05
5,598	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.0690976e-05
5,988	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB	5.9229752e-05
6,024	Proactive Re-optimization with Rio	2005	SIGMOD	5.9096276e-05
6,114	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	5.8796178e-05
6,171	Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra	2021	SIGMOD	5.8597104e-05
6,444	Grizzly: Efficient Stream Processing Through Adaptive Query Compilation	2020	SIGMOD	5.7807677e-05
6,710	Tempura: A General Cost-Based Optimizer Framework for Incremental Data Processing	2021	VLDB	5.7022785e-05
6,776	Cheap Data Analytics using Cold Storage Devices	2016	VLDB	5.6834455e-05
7,251	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	5.5719214e-05
7,378	Stop-and-Restart Style Execution for Long Running Decision Support Queries	2007	VLDB	5.537392e-05
7,413	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.5316834e-05
7,492	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB	5.5094171e-05
7,603	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.4846849e-05
7,958	Robust Query Processing: Mission Possible	2020	VLDB	5.4164639e-05
8,049	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.3988942e-05
8,165	A Concave Path to Low-overhead Robust Query Processing	2018	VLDB	5.3847569e-05
8,192	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD	5.379021e-05
8,348	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.3486679e-05
8,393	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3387995e-05
8,531	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.3206021e-05
8,860	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.2620362e-05
9,134	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.2223611e-05
9,310	Rethink Query Optimization in HTAP Databases	2023	SIGMOD	5.1963298e-05
9,325	On-Demand State Separation for Cloud Data Warehousing	2022	VLDB	5.1933808e-05
9,735	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.1325223e-05
10,380	Coresets for Robust Query Optimization	2026	PODS	4.9769913e-05
11,291	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.9769913e-05
11,783	Anser: Adaptive Information Sharing Framework of AnalyticDB	2023	VLDB	4.9769913e-05
12,208	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	4.9769913e-05
12,783	Visualizing the robustness of query execution	2009	CIDR	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 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.0023943337
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.0004772731
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.000408505
57	On Random Sampling over Joins	1999	SIGMOD	0.00040095727
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034748721
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029618887
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028977821
334	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00020682536
423	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.00018487497
471	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017744392
477	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017640718
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016244162
792	Parametric Query Optimization	1992	VLDB	0.00013938197
1,122	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00011933634
1,612	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	0.00010068388
2,268	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.7182371e-05
2,989	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.7736772e-05
4,046	Adaptive Query Processing in the Looking Glass	2005	CIDR	6.8297725e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,686	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB
2	644	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
3	2,890	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD
4	288	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD
5	149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD
6	1,258	Sampling-Based Query Re-Optimization	2016	SIGMOD
7	11,291	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB
8	5,663	Enabling Incremental Query Re-Optimization	2016	SIGMOD
9	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
10	6,024	Proactive Re-optimization with Rio	2005	SIGMOD