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: 3619
Venue: SIGMOD
Year: 2004
Pagerank: 0.0001756877
Overall Rank: 492 | 96.63%
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 12 of 62 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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,494	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.4142129e-05
9,154	On-Demand State Separation for Cloud Data Warehousing	2022	VLDB	5.3123022e-05
9,440	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	5.2680376e-05
9,475	BladeDISC: Optimizing Dynamic Shape Machine Learning Workloads via Compiler Approach	2023	SIGMOD	5.2634238e-05
9,612	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR	5.2449175e-05
9,756	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	5.2258278e-05
10,291	SmartRabbit: An Interactive Query Processor	2026	SIGMOD	5.093636e-05
10,881	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	5.093636e-05
12,486	Visualizing the robustness of query execution	2009	CIDR	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
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
100	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034385207
151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00029161879
289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.00022278876
419	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.0001879684
474	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017894953
664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015167825
1,321	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.00011162369
2,984	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.8920597e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,426	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB
2	5,137	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD
3	7,495	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
4	10,151	Coresets for Robust Query Optimization	2026	PODS
5	6,019	Robustness Metrics for Relational Query Execution Plans	2018	VLDB
6	1,256	Sampling-Based Query Re-Optimization	2016	SIGMOD
7	7,366	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
8	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
9	8,064	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD
10	13,902	Progressive Optimization in Action	2004	VLDB