Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer

Summary: Counts, exhaustively enumerates, and uniformly samples the complete plan search space of a cost-based optimizer. Applied in SQL Server for validation and testing, these methods expose plan/execution mismatches and sustain unbiased testing when exhaustive search is impractical. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3272
Venue: SIGMOD
Year: 2000
Pagerank: 6.9835426e-05
Overall Rank: 3,970 | 72.77%
DOI: 10.1145/342009.335451

Incoming Non-self Citations Over Time

Authors

1. Florian Waas (Centrum Wiskunde & Informatica; Microsoft)
2. César Galindo-Legaria (Microsoft)

BibTeX Citation

@inproceedings{waas_sigmod00,
        title = {{Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer}},
        author = {Waas, Florian and Galindo-Legaria, César},
        series = {{SIGMOD} '00},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/342009.335451},
        url = {https://dl.acm.org/doi/10.1145/342009.335451},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
984	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB	0.00012825643
1,621	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	0.00010203114
4,111	A genetic approach for random testing of database systems	2007	VLDB	6.8945321e-05
4,346	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.7510183e-05
6,026	Parallelizing Extensible Query Optimizers	2009	SIGMOD	6.0024042e-05
6,194	Incorporating Super-Operators in Big-Data Query Optimizers	2020	VLDB	5.9470844e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
119	The EXODUS Optimizer Generator	1987	SIGMOD	0.0003183602
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
392	Massive Stochastic Testing of SQL	1998	VLDB	0.00019342814
708	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014727576
1,341	Experiences Building the Open OODB Query Optimizer	1993	SIGMOD	0.00011108876
2,627	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.3284491e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	984	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
2	682	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB
3	4,817	Efficiently Approximating Query Optimizer Plan Diagrams	2008	VLDB
4	54	On Random Sampling over Joins	1999	SIGMOD
5	4,346	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD
6	3,426	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB
7	1,256	Sampling-Based Query Re-Optimization	2016	SIGMOD
8	664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
9	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
10	2,069	Generating Targeted Queries for Database Testing	2008	SIGMOD