Efficiently Approximating Query Optimizer Plan Diagrams

Summary: Efficiently approximates plan diagrams for parametric SQL templates via sampling and monotonicity across optimizer APIs (optimal, suboptimal, ranked). TPC-H/DS shows ~90% accuracy at <15% overhead; zero-error for optimizers with <10% overhead; Picasso. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9948
Venue: VLDB
Year: 2008
Pagerank: 6.4944225e-05
Overall Rank: 4,817 | 66.96%
DOI: 10.14778/1454159.1454173

Incoming Non-self Citations Over Time

Authors

1. Atreyee Dey (Indian Institute of Science)
2. Sourjya Bhaumik (Indian Institute of Science)
3. Harish D. (Indian Institute of Science)
4. Jayant R. Haritsa (Indian Institute of Science)

BibTeX Citation

@article{dey_vldb08,
        title = {{Efficiently Approximating Query Optimizer Plan Diagrams}},
        author = {Dey, Atreyee and Bhaumik, Sourjya and D., Harish and Haritsa, Jayant R.},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {1325--1336},
        doi = {10.14778/1454159.1454173},
        url = {https://doi.org/10.14778/1454159.1454173},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,420	Lero: A Learning-to-Rank Query Optimizer	2023	VLDB	8.605257e-05
2,540	Multi-Objective Parametric Query Optimization	2015	VLDB	8.45187e-05
3,506	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.3581509e-05
3,513	Variance Aware Optimization of Parameterized Queries	2010	SIGMOD	7.354613e-05
5,281	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	6.2842378e-05
5,394	Leveraging Query Logs and Machine Learning for Parametric Query Optimization	2022	VLDB	6.2336084e-05
8,305	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.4568571e-05
10,986	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.093636e-05
12,486	Visualizing the robustness of query execution	2009	CIDR	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00029161879
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.00022278876
492	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001756877
984	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB	0.00012825643
1,104	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00012157634
1,321	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.00011162369
1,604	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00010230973
1,645	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	0.00010129244
1,771	Plan Selection based on Query Clustering	2002	VLDB	9.7942089e-05
1,795	Least Expected Cost Query Optimization: What Can We Expect?	2002	PODS	9.738718e-05
3,506	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.3581509e-05
4,616	On the Production of Anorexic Plan Diagrams	2007	VLDB	6.6048588e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,970	Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer	2000	SIGMOD
2	5,898	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB
3	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
4	1,604	The Picasso Database Query Optimizer Visualizer	2010	VLDB
5	5,615	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS
6	4,346	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD
7	1,771	Plan Selection based on Query Clustering	2002	VLDB
8	4,616	On the Production of Anorexic Plan Diagrams	2007	VLDB
9	3,506	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB
10	984	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB