Cardinality Estimation Using Sample Views with Quality Assurance

Summary: Proposes a general cardinality estimator that blends random sampling with materialized views for complex predicates, correlations, and UDFs. Uses execution feedback with data-change controls to keep estimates valid, demonstrated on a SQL Server prototype. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3911
Venue: SIGMOD
Year: 2007
Pagerank: 8.6225576e-05
Overall Rank: 2,404 | 83.51%
DOI: 10.1145/1247480.1247502

Incoming Non-self Citations Over Time

Authors

1. Per-Ake Larson (Microsoft)
2. Wolfgang Lehner (Microsoft; Technical University of Dresden)
3. Jingren Zhou (Microsoft)
4. Peter Zabback (Microsoft)

BibTeX Citation

@inproceedings{larson_sigmod07,
        title = {{Cardinality Estimation Using Sample Views with Quality Assurance}},
        author = {Larson, Per-Ake and Lehner, Wolfgang and Zhou, Jingren and Zabback, Peter},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247502},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247502},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
563	Plan-Structured Deep Neural Network Models for Query Performance Prediction	2019	VLDB	0.0001650812
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,503	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.000105564
2,069	Generating Targeted Queries for Database Testing	2008	SIGMOD	9.2293717e-05
2,203	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	8.9610447e-05
2,213	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.9410226e-05
3,215	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.6324234e-05
4,409	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.7178579e-05
4,945	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.4321265e-05
5,137	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.3507372e-05
5,514	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.1901666e-05
7,554	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.6001388e-05
7,655	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	5.5741093e-05
8,183	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.4714466e-05
8,608	One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees	2022	SIGMOD	5.4024561e-05
8,714	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	5.3778009e-05
9,455	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.2653318e-05
9,997	HyperBlocker: Accelerating Rule-based Blocking in Entity Resolution using GPUs	2025	VLDB	5.1814573e-05
10,016	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.1764556e-05
11,539	Juggler: Autonomous Cost Optimization and Performance Prediction of Big Data Applications	2022	SIGMOD	5.093636e-05
13,796	Exploiting Self-Monitoring Sample Views for Cardinality Estimation	2007	SIGMOD	-

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
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
492	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001756877
508	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00017275873
3,093	Statistics on Views	2003	VLDB	7.7664764e-05
3,803	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	7.1114677e-05
5,733	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	6.1062071e-05
8,125	Learning Table Access Cardinalities with LEO	2002	SIGMOD	5.4829273e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,309	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD
2	7,256	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD
3	12,502	Filtered Statistics	2009	SIGMOD
4	3,426	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB
5	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
6	9,455	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD
7	694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
8	3,093	Statistics on Views	2003	VLDB
9	5,010	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB
10	13,796	Exploiting Self-Monitoring Sample Views for Cardinality Estimation	2007	SIGMOD