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: he1eb7f30bcdc709b
Venue: VLDB
Year: 2009
Pagerank: 7.3719456e-05
Overall Rank: 3,367 | 77.37%
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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
982	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012714044
3,645	UDO: Universal Database Optimization using Reinforcement Learning	2021	VLDB	7.1397796e-05
4,132	SQLStorm: Taking Database Benchmarking into the LLM Era	2025	VLDB	6.7885553e-05
4,202	Kepler: Robust Learning for Faster Parametric Query Optimization	2023	SIGMOD	6.7374091e-05
5,022	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	6.3100988e-05
5,199	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.2327836e-05
8,389	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3413016e-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
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
88	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035351639
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
129	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.0003040756
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028981723
187	DB2 Design Advisor: Integrated Automatic Physical Database Design	2004	VLDB	0.0002592488
232	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023792809
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
491	Database Tuning Advisor for Microsoft SQL Server 2005	2004	VLDB	0.00017413042
646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.0001520859
831	Pipelining in Multi-Query Optimization	2001	PODS	0.00013589597
4,659	Automated Statistics Collection in DB2 UDB	2004	VLDB	6.4822228e-05

Semantically Similar Papers

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