Plan Bouquets: Query Processing without Selectivity Estimation

Summary: Plan Bouquets replace selectivity estimation with a compact bouquet covering the error space. Runtime discerns selectivities via bouquet runs, with bounded overhead and guaranteed worst-case performance; compatible with existing optimizers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h39f86a061dec1215
Venue: SIGMOD
Year: 2014
Pagerank: 9.250242e-05
Overall Rank: 1,987 | 86.65%
DOI: 10.1145/2558555.2558566

Incoming Non-self Citations Over Time

Authors

1. Anshuman Dutt (Indian Institute of Science)
2. Jayant R. Haritsa (Indian Institute of Science)

BibTeX Citation

@inproceedings{dutt_sigmod14,
        title = {{Plan Bouquets: Query Processing without Selectivity Estimation}},
        author = {Dutt, Anshuman and Haritsa, Jayant R.},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2558555.2558566},
        url = {https://dl.acm.org/doi/10.1145/2558555.2558566},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014753664
1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011310561
1,603	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	0.00010097649
1,800	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.6093317e-05
4,793	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	6.4127583e-05
5,199	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.2327836e-05
5,667	Enabling Incremental Query Re-Optimization	2016	SIGMOD	6.0458446e-05
6,113	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	5.8823242e-05
6,393	QUEST: An Exploratory Approach to Robust Query Processing	2014	VLDB	5.8002013e-05
6,441	Grizzly: Efficient Stream Processing Through Adaptive Query Compilation	2020	SIGMOD	5.7834762e-05
6,660	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.7178404e-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
8,159	A Concave Path to Low-overhead Robust Query Processing	2018	VLDB	5.3873068e-05
8,345	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.3511996e-05
8,389	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3413016e-05
8,524	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.3231221e-05
8,673	Adaptive Code Generation for Data-Intensive Analytics	2021	VLDB	5.2913671e-05
9,301	Rethink Query Optimization in HTAP Databases	2023	SIGMOD	5.1987909e-05
9,730	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.1349531e-05
10,368	Coresets for Robust Query Optimization	2026	PODS	4.9793485e-05
10,679	Reqo: A Comprehensive Learning-Based Cost Model for Robust and Explainable Query Optimization	2026	SIGMOD	4.9793485e-05
13,904	CODD: A Dataless Approach to Big Data Testing	2015	VLDB	-

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 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
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040860054
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.0003475226
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028981723
289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.0002196543
386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019444411
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017962189
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016245271
836	Proactive Re-Optimization	2005	SIGMOD	0.00013557047
1,821	Least Expected Cost Query Optimization: What Can We Expect?	2002	PODS	9.5687882e-05
3,396	Variance Aware Optimization of Parameterized Queries	2010	SIGMOD	7.3418098e-05
3,527	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.2310714e-05
4,657	On the Production of Anorexic Plan Diagrams	2007	VLDB	6.4824233e-05
5,470	A Pay-As-You-Go Framework for Query Execution Feedback	2008	VLDB	6.1182634e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD
2	1,060	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB
3	4,855	Efficiently Approximating Query Optimizer Plan Diagrams	2008	VLDB
4	14,240	PLASTIC: Reducing Query Optimization Overheads through Plan Recycling	2003	SIGMOD
5	3,527	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB
6	996	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
7	1,789	Plan Selection based on Query Clustering	2002	VLDB
8	6,393	QUEST: An Exploratory Approach to Robust Query Processing	2014	VLDB
9	5,988	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB
10	8,159	A Concave Path to Low-overhead Robust Query Processing	2018	VLDB