Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server

Summary: Empirical study of cardinality-estimation effects on plan quality in Microsoft SQL Server using complex real-world queries (aggregates, outer joins, subqueries) and both row- and column-oriented layouts. Introduces a sensitivity analysis that selectively supplies accurate subexpression cardinalities while injecting graded errors, and evaluates runtime mitigations (bitmap filtering, adaptive joins). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h50ec9f42e8ce6c2c
Venue: VLDB
Year: 2023
Pagerank: 6.3100988e-05
Overall Rank: 5,022 | 66.24%
DOI: 10.14778/3611479.3611494

Incoming Non-self Citations Over Time

Authors

1. Kukjin Lee (Microsoft)
2. Anshuman Dutt (Microsoft)
3. Vivek Narasayya (Microsoft)
4. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@article{lee_vldb23,
        title = {{Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server}},
        author = {Lee, Kukjin and Dutt, Anshuman and Narasayya, Vivek and Chaudhuri, Surajit},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {11},
        pages = {2871--2883},
        doi = {10.14778/3611479.3611494},
        url = {https://doi.org/10.14778/3611479.3611494},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,132	SQLStorm: Taking Database Benchmarking into the LLM Era	2025	VLDB	6.7885553e-05
4,852	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	6.3806134e-05
6,576	Towards Query Optimizer as a Service (QOaaS) in a Unified LakeHouse Ecosystem: Can One QO Rule Them All?	2025	CIDR	5.7448779e-05
7,410	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.5342768e-05
7,977	The Holon Approach for Simultaneously Tuning Multiple Components in a Self-Driving Database Management System with Machine Learning via Synthesized Proto-Actions	2024	VLDB	5.4142519e-05
8,389	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3413016e-05
9,012	ByteCard: Enhancing ByteDance’s Data Warehouse with Learned Cardinality Estimation	2024	SIGMOD	5.2375369e-05
9,478	LpBound in Action: Cardinality Estimation with One-Sided Guarantees	2025	SIGMOD	5.1708619e-05
10,103	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	5.0789354e-05
10,290	This is Going to Sound Crazy, But What If We Used Large Language Models to Boost Automatic Database Tuning Algorithms By Leveraging Prior History? We Will Find Better Configurations More Quickly Than Retraining From Scratch!	2026	SIGMOD	5.0431863e-05
10,336	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.0200193e-05
10,604	Understanding and Detecting Query Performance Regression in Practical Index Tuning: [Experiments & Analysis]	2026	SIGMOD	4.9793485e-05
11,333	The Accuracy of Cardinality Estimators: Unraveling the Evaluation Result Conundrum	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035864347
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.0003475226
272	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022509573
386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019444411
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
692	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014741011
944	Enhancements to SQL Server Column Stores	2013	SIGMOD	0.00012939697
982	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012714044
1,515	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	0.00010417728
1,542	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010308631
1,734	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7545773e-05
2,891	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.9021718e-05
3,367	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	7.3719456e-05
4,260	Query Optimization in Oracle 12c Database In-Memory	2015	VLDB	6.6992663e-05
4,391	Bitvector-aware Query Optimization for Decision Support Queries	2020	SIGMOD	6.6214093e-05
5,199	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.2327836e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,470	A Pay-As-You-Go Framework for Query Execution Feedback	2008	VLDB
2	15	How Good Are Query Optimizers, Really?	2016	VLDB
3	3,133	Statistics on Views	2003	VLDB
4	7,597	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
5	688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
6	14,107	Exploiting Self-Monitoring Sample Views for Cardinality Estimation	2007	SIGMOD
7	386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB
8	982	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB
9	2,433	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD
10	3,367	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB