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: hb4e7c1a4679e41ae
Venue: SIGMOD
Year: 2007
Pagerank: 8.4766785e-05
Overall Rank: 2,433 | 83.65%
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
560	Plan-Structured Deep Neural Network Models for Query Performance Prediction	2019	VLDB	0.00016403151
1,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
1,508	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.00010440205
1,890	Generating Targeted Queries for Database Testing	2008	SIGMOD	9.4193315e-05
2,216	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	8.8177753e-05
2,238	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7751619e-05
3,131	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.6141006e-05
4,330	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.6595681e-05
5,044	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.30014e-05
5,199	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.2327836e-05
5,597	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.0718206e-05
7,072	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	5.6074688e-05
7,633	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.4792473e-05
8,347	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.350539e-05
8,770	One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees	2022	SIGMOD	5.2812395e-05
8,870	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	5.2601766e-05
9,458	HyperBlocker: Accelerating Rule-based Blocking in Entity Resolution using GPUs	2025	VLDB	5.173446e-05
9,632	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.1472849e-05
10,205	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.0603873e-05
11,848	Juggler: Autonomous Cost Optimization and Performance Prediction of Big Data Applications	2022	SIGMOD	4.9793485e-05
14,107	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
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027837289
169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027134723
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021914399
336	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020657819
346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020329113
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
519	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016942879
3,133	Statistics on Views	2003	VLDB	7.6127492e-05
3,871	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.9543581e-05
5,851	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9718136e-05
8,288	Learning Table Access Cardinalities with LEO	2002	SIGMOD	5.3614914e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,361	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD
2	7,364	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD
3	12,792	Filtered Statistics	2009	SIGMOD
4	3,367	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB
5	9,632	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD
6	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
7	688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
8	3,133	Statistics on Views	2003	VLDB
9	5,022	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB
10	14,107	Exploiting Self-Monitoring Sample Views for Cardinality Estimation	2007	SIGMOD