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: 3068
Venue: SIGMOD
Year: 1998
Pagerank: 0.00029161879
Overall Rank: 151 | 98.97%
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 30 of 80 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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,462	PilotScope: Steering Databases with Machine Learning Drivers	2024	VLDB	5.8717744e-05
6,543	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.8461929e-05
6,593	Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis	2023	VLDB	5.8297039e-05
6,663	Cheap Data Analytics using Cold Storage Devices	2016	VLDB	5.8091195e-05
6,688	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.8015211e-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,223	Dynamic Plan Generation for Parameterized Queries	2009	SIGMOD	5.6676987e-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,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	5.5237338e-05
7,891	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.5211516e-05
7,915	Krypton: Real-time Serving and Analytical SQL Engine at ByteDance	2023	VLDB	5.5181056e-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,494	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.4142129e-05
8,636	Adaptive Code Generation for Data-Intensive Analytics	2021	VLDB	5.3954959e-05
8,961	Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet	2015	CIDR	5.3438458e-05
9,449	MCC-DB: Minimizing Cache Conflicts in Multi-core Processors for Databases	2009	VLDB	5.2665098e-05
9,756	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	5.2258278e-05
10,081	Rethink Query Optimization in HTAP Databases	2023	SIGMOD	5.158939e-05
10,096	Out-of-order Execution of Database Queries	2020	VLDB	5.1523392e-05
11,466	Anser: Adaptive Information Sharing Framework of AnalyticDB	2023	VLDB	5.093636e-05
12,486	Visualizing the robustness of query execution	2009	CIDR	5.093636e-05
12,616	The Data Ring: Community Content Sharing	2007	CIDR	5.093636e-05
12,829	Adaptive Distributed Query Processing	2003	VLDB	5.093636e-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.0024089429
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.00022278876
474	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017894953
770	Parametric Query Optimization	1992	VLDB	0.00014166811
1,517	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010520118
1,720	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	9.9265634e-05
2,360	Dynamic Memory Allocation for Multiple-Query Workloads	1993	VLDB	8.6956893e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	770	Parametric Query Optimization	1992	VLDB
2	1,256	Sampling-Based Query Re-Optimization	2016	SIGMOD
3	9,756	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
4	984	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
5	3,003	Configuration-Parametric Query Optimization for Physical Design Tuning	2008	SIGMOD
6	664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
7	7,495	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
8	290	An Overview of Query Optimization in Relational Systems	1998	PODS
9	2,104	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
10	434	Query Optimization for Parallel Execution	1992	SIGMOD