Robust Query Processing through Progressive Optimization

Summary: Progressive query optimization (POP) detects cardinality errors during execution and re-optimizes plans in a commercial DBMS. CHECK operators compute a validity range via a sensitivity analysis; when violated, re-optimization uses partial results. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hafc60422fa7a7261
Venue: SIGMOD
Year: 2004
Pagerank: 0.00017691682
Overall Rank: 471 | 96.85%
DOI: 10.1145/1007568.1007642

Incoming Non-self Citations Over Time

Authors

1. Volker Markl (IBM)
2. Vijayshankar Raman (IBM)
3. David Simmen (IBM)
4. Guy Lohman (IBM)
5. Hamid Pirahesh (IBM)
6. Miso Cilimdzic (IBM)

BibTeX Citation

@inproceedings{markl_sigmod04,
        title = {{Robust Query Processing through Progressive Optimization}},
        author = {Markl, Volker and Raman, Vijayshankar and Simmen, David and Lohman, Guy and Pirahesh, Hamid and Cilimdzic, Miso},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007642},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007642},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 65 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,067	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.3810658e-05
8,182	A Concave Path to Low-overhead Robust Query Processing	2018	VLDB	5.3669522e-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
9,179	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	5.1992749e-05
9,350	On-Demand State Separation for Cloud Data Warehousing	2022	VLDB	5.1762083e-05
9,691	BladeDISC: Optimizing Dynamic Shape Machine Learning Workloads via Compiler Approach	2023	SIGMOD	5.1258854e-05
9,822	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR	5.1092136e-05
10,420	Rethinking Query Optimization for Multi-Agent Systems	2027	VLDB	4.9605343e-05
10,580	SmartRabbit: An Interactive Query Processor	2026	SIGMOD	4.9605343e-05
10,903	ReSequel: Robust LLM-assisted Query Rewriting and Optimization using Templatization and Sampling	2026	VLDB	4.9605343e-05
11,052	A Portable Middleware for Plan-Based Adaptive Query Processing	2026	VLDB	4.9605343e-05
11,347	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.9605343e-05
12,826	Visualizing the robustness of query execution	2009	CIDR	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
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
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034050614
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028910892
291	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.00021898776
426	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.00018432573
479	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017595584
646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015166402
1,304	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.00011088983
3,009	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.7439468e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,361	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB
2	5,223	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD
3	7,619	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
4	10,446	Coresets for Robust Query Optimization	2026	PODS
5	6,128	Robustness Metrics for Relational Query Execution Plans	2018	VLDB
6	1,261	Sampling-Based Query Re-Optimization	2016	SIGMOD
7	7,509	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
8	568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
9	8,208	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD
10	14,258	Progressive Optimization in Action	2004	VLDB