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.00028981723
Overall Rank: 149 | 99.00%
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,922	Inspector Joins	2005	VLDB	5.9469659e-05
5,988	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB	5.9257426e-05
6,029	Proactive Re-optimization with Rio	2005	SIGMOD	5.9105715e-05
6,169	Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra	2021	SIGMOD	5.8624857e-05
6,660	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.7178404e-05
6,710	Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis	2023	VLDB	5.7019157e-05
6,772	Cheap Data Analytics using Cold Storage Devices	2016	VLDB	5.6861277e-05
6,800	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6792071e-05
7,249	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	5.5745603e-05
7,304	Dynamic Plan Generation for Parameterized Queries	2009	SIGMOD	5.5593451e-05
7,376	Stop-and-Restart Style Execution for Long Running Decision Support Queries	2007	VLDB	5.540013e-05
7,410	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.5342768e-05
7,487	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB	5.5119239e-05
7,597	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.4872821e-05
7,954	Robust Query Processing: Mission Possible	2020	VLDB	5.4190023e-05
8,039	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	5.4017809e-05
8,042	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.4014499e-05
8,082	Krypton: Real-time Serving and Analytical SQL Engine at ByteDance	2023	VLDB	5.3942942e-05
8,164	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	5.3852872e-05
8,185	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD	5.381532e-05
8,345	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.3511996e-05
8,673	Adaptive Code Generation for Data-Intensive Analytics	2021	VLDB	5.2913671e-05
9,125	Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet	2015	CIDR	5.2239819e-05
9,301	Rethink Query Optimization in HTAP Databases	2023	SIGMOD	5.1987909e-05
9,617	MCC-DB: Minimizing Cache Conflicts in Multi-core Processors for Databases	2009	VLDB	5.1507816e-05
10,318	Out-of-order Execution of Database Queries	2020	VLDB	5.0367346e-05
10,982	A Portable Middleware for Plan-Based Adaptive Query Processing	2026	VLDB	4.9793485e-05
11,777	Anser: Adaptive Information Sharing Framework of AnalyticDB	2023	VLDB	4.9793485e-05
12,777	Visualizing the robustness of query execution	2009	CIDR	4.9793485e-05
12,906	The Data Ring: Community Content Sharing	2007	CIDR	4.9793485e-05
13,119	Adaptive Distributed Query Processing	2003	VLDB	4.9793485e-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.0023947656
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.0003475226
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.0002196543
476	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017640534
792	Parametric Query Optimization	1992	VLDB	0.00013942753
1,546	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010294163
1,736	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	9.7507905e-05
2,385	Dynamic Memory Allocation for Multiple-Query Workloads	1993	VLDB	8.5394982e-05

Semantically Similar Papers

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