Exact Cardinality Query Optimization for Optimizer Testing

Summary: Makes exact-cardinality optimization practical for optimizer testing, despite the prohibitive cost of evaluating all subexpressions. Techniques implemented in SQL Server yield ideal-plan baselines across substantially more TPC-H queries. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10060
Venue: VLDB
Year: 2009
Pagerank: 7.4218997e-05
Overall Rank: 3,426 | 76.50%
DOI: 10.14778/1687627.1687739

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Microsoft)
2. Vivek Narasayya (Microsoft)
3. Ravi Ramamurthy (Microsoft)

BibTeX Citation

@article{chaudhuri_vldb09,
        title = {{Exact Cardinality Query Optimization for Optimizer Testing}},
        author = {Chaudhuri, Surajit and Narasayya, Vivek and Ramamurthy, Ravi},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687739},
        url = {https://doi.org/10.14778/1687627.1687739},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
1,122	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.0001209124
3,926	UDO: Universal Database Optimization using Reinforcement Learning	2021	VLDB	7.0128068e-05
4,470	Kepler: Robust Learning for Faster Parametric Query Optimization	2023	SIGMOD	6.6817353e-05
5,010	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	6.4023732e-05
5,137	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.3507372e-05
5,744	SQLStorm: Taking Database Benchmarking into the LLM Era	2025	VLDB	6.1019672e-05
8,305	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.4568571e-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
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
87	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035281619
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
128	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.0003072825
151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00029161879
184	DB2 Design Advisor: Integrated Automatic Physical Database Design	2004	VLDB	0.00026256101
222	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00024193708
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
492	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001756877
501	Database Tuning Advisor for Microsoft SQL Server 2005	2004	VLDB	0.0001738508
664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015167825
822	Pipelining in Multi-Query Optimization	2001	PODS	0.00013807229
4,591	Automated Statistics Collection in DB2 UDB	2004	VLDB	6.614318e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
2	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
3	1,122	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB
4	388	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB
5	18	How Good Are Query Optimizers, Really?	2016	VLDB
6	13,796	Exploiting Self-Monitoring Sample Views for Cardinality Estimation	2007	SIGMOD
7	2,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD
8	5,137	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD
9	7,495	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
10	5,010	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB