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: 3690
Venue: SIGMOD
Year: 2005
Pagerank: 0.00013769838
Overall Rank: 829 | 94.32%
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
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014911698
1,499	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010564536
1,712	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.9492299e-05
1,804	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD	9.7171985e-05
1,815	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.6894541e-05
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.3517129e-05
2,161	DIFF: A Relational Interface for Large-Scale Data Explanation	2019	VLDB	9.0606664e-05
2,540	Multi-Objective Parametric Query Optimization	2015	VLDB	8.45187e-05
3,506	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.3581509e-05
3,571	Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads	2017	VLDB	7.2991953e-05
3,605	Computation Reuse in Analytics Job Service at Microsoft	2018	SIGMOD	7.2640711e-05
4,383	Content-Based Routing: Different Plans for Different Data	2005	VLDB	6.7329787e-05
4,444	Xplus: A SQL-Tuning-Aware Query Optimizer	2010	VLDB	6.6999439e-05
4,481	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD	6.6754521e-05
5,000	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	6.4069917e-05
5,124	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.3567981e-05
5,137	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.3507372e-05
5,514	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.1901666e-05
5,529	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.18591e-05
5,898	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB	6.0471908e-05
6,019	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	6.0060149e-05
6,046	Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra	2021	SIGMOD	5.9956597e-05
6,117	Proactive Re-optimization with Rio	2005	SIGMOD	5.9706217e-05
6,349	Grizzly: Efficient Stream Processing Through Adaptive Query Compilation	2020	SIGMOD	5.9049304e-05
6,626	Tempura: A General Cost-Based Optimizer Framework for Incremental Data Processing	2021	VLDB	5.8198723e-05
6,663	Cheap Data Analytics using Cold Storage Devices	2016	VLDB	5.8091195e-05
7,066	Aero: Adaptive Query Processing of ML Queries	2025	SIGMOD	5.712204e-05
7,103	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	5.7023779e-05
7,244	Stop-and-Restart Style Execution for Long Running Decision Support Queries	2007	VLDB	5.6638746e-05
7,366	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB	5.6322753e-05
7,495	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.6041473e-05
7,829	Robust Query Processing: Mission Possible	2020	VLDB	5.5360082e-05
7,891	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.5211516e-05
8,004	A Concave Path to Low-overhead Robust Query Processing	2018	VLDB	5.5082745e-05
8,064	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD	5.4949524e-05
8,211	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.4658735e-05
8,305	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.4568571e-05
8,494	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.4142129e-05
8,698	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.3830073e-05
8,984	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.3395569e-05
9,154	On-Demand State Separation for Cloud Data Warehousing	2022	VLDB	5.3123022e-05
9,796	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.21848e-05
10,081	Rethink Query Optimization in HTAP Databases	2023	SIGMOD	5.158939e-05
10,151	Coresets for Robust Query Optimization	2026	PODS	5.093636e-05
10,881	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	5.093636e-05
10,986	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.093636e-05
11,466	Anser: Adaptive Information Sharing Framework of AnalyticDB	2023	VLDB	5.093636e-05
11,902	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	5.093636e-05
12,486	Visualizing the robustness of query execution	2009	CIDR	5.093636e-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.0024089429
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00029161879
328	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00021081317
419	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.0001879684
474	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017894953
492	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001756877
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
770	Parametric Query Optimization	1992	VLDB	0.00014166811
1,104	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00012157634
1,645	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	0.00010129244
2,230	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.9026958e-05
2,997	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.8745158e-05
3,988	Adaptive Query Processing in the Looking Glass	2005	CIDR	6.9720123e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,762	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB
2	664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
3	2,944	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD
4	289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD
5	151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD
6	1,256	Sampling-Based Query Re-Optimization	2016	SIGMOD
7	10,881	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB
8	5,552	Enabling Incremental Query Re-Optimization	2016	SIGMOD
9	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
10	6,117	Proactive Re-optimization with Rio	2005	SIGMOD