Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans

Summary: Mid-query re-optimization detects sub-optimal plans during execution via targeted statistics collection. These stats guide resource tuning or plan changes for the remainder, with low overhead; demonstrated in Paradise with gains on complex queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h52a03c6bdfb031c4
Venue: SIGMOD
Year: 1998
Pagerank: 0.00028910892
Overall Rank: 149 | 99.01%
DOI: 10.1145/276304.276315

Incoming Non-self Citations Over Time

Authors

1. Navin Kabra (University of Wisconsin)
2. David J. DeWitt (University of Wisconsin)

BibTeX Citation

@inproceedings{kabra_sigmod98,
        title = {{Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans}},
        author = {Kabra, Navin and DeWitt, David J.},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276315},
        url = {https://dl.acm.org/doi/10.1145/276304.276315},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 81 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,713	PilotScope: Steering Databases with Machine Learning Drivers	2024	VLDB	6.0090633e-05
5,927	Inspector Joins	2005	VLDB	5.9281216e-05
5,999	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB	5.9034324e-05
6,038	Proactive Re-optimization with Rio	2005	SIGMOD	5.8901698e-05
6,672	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.6975871e-05
6,725	Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis	2023	VLDB	5.6826988e-05
6,759	Cheap Data Analytics using Cold Storage Devices	2016	VLDB	5.6710776e-05
6,816	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6593309e-05
7,269	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	5.5534971e-05
7,325	Dynamic Plan Generation for Parameterized Queries	2009	SIGMOD	5.5383706e-05
7,397	Stop-and-Restart Style Execution for Long Running Decision Support Queries	2007	VLDB	5.5190903e-05
7,432	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.5133928e-05
7,509	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB	5.4916369e-05
7,619	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.4665491e-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,067	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.3810658e-05
8,107	Krypton: Real-time Serving and Analytical SQL Engine at ByteDance	2023	VLDB	5.3739121e-05
8,188	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	5.3649397e-05
8,208	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD	5.3612833e-05
8,361	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.3310744e-05
8,701	Adaptive Code Generation for Data-Intensive Analytics	2021	VLDB	5.2714222e-05
9,157	Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet	2015	CIDR	5.2042524e-05
9,335	Rethink Query Optimization in HTAP Databases	2023	SIGMOD	5.1791475e-05
9,640	MCC-DB: Minimizing Cache Conflicts in Multi-core Processors for Databases	2009	VLDB	5.134315e-05
10,351	Out-of-order Execution of Database Queries	2020	VLDB	5.0177035e-05
11,052	A Portable Middleware for Plan-Based Adaptive Query Processing	2026	VLDB	4.9605343e-05
11,827	Anser: Adaptive Information Sharing Framework of AnalyticDB	2023	VLDB	4.9605343e-05
12,826	Visualizing the robustness of query execution	2009	CIDR	4.9605343e-05
12,954	The Data Ring: Community Content Sharing	2007	CIDR	4.9605343e-05
13,166	Adaptive Distributed Query Processing	2003	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034691614
285	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022143946
291	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.00021898776
479	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017595584
792	Parametric Query Optimization	1992	VLDB	0.00013903954
1,549	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010257684
1,746	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	9.718559e-05
2,385	Dynamic Memory Allocation for Multiple-Query Workloads	1993	VLDB	8.5255503e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	792	Parametric Query Optimization	1992	VLDB
2	1,261	Sampling-Based Query Re-Optimization	2016	SIGMOD
3	8,188	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
4	996	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
5	3,050	Configuration-Parametric Query Optimization for Physical Design Tuning	2008	SIGMOD
6	646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
7	7,619	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
8	259	An Overview of Query Optimization in Relational Systems	1998	PODS
9	2,151	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
10	448	Query Optimization for Parallel Execution	1992	SIGMOD