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: h05e914733160e7d1
Venue: SIGMOD
Year: 2000
Pagerank: 6.8389401e-05
Overall Rank: 4,038 | 72.86%
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
996	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB	0.00012634603
1,276	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	0.00011239266
4,113	A genetic approach for random testing of database systems	2007	VLDB	6.7985257e-05
4,415	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.6094699e-05
6,136	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.8759799e-05
6,290	Incorporating Super-Operators in Big-Data Query Optimizers	2020	VLDB	5.8223076e-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
118	The EXODUS Optimizer Generator	1987	SIGMOD	0.00031392616
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021088704
383	Massive Stochastic Testing of SQL	1998	VLDB	0.00019484034
725	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014465736
1,376	Experiences Building the Open OODB Query Optimizer	1993	SIGMOD	0.00010874518
2,660	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1611913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	996	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,855	Efficiently Approximating Query Optimizer Plan Diagrams	2008	VLDB
4	57	On Random Sampling over Joins	1999	SIGMOD
5	4,415	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD
6	3,367	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB
7	646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
8	1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD
9	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
10	1,890	Generating Targeted Queries for Database Testing	2008	SIGMOD