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.4532693e-05
Overall Rank: 2,438 | 83.66%
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
545	Plan-Structured Deep Neural Network Models for Query Performance Prediction	2019	VLDB	0.0001657599
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
1,511	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.00010408003
1,901	Generating Targeted Queries for Database Testing	2008	SIGMOD	9.3902763e-05
2,228	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	8.7912743e-05
2,249	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7479608e-05
3,136	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.5902303e-05
4,329	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.64569e-05
5,056	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.282339e-05
5,223	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.210331e-05
5,611	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.0498181e-05
7,094	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	5.5863735e-05
7,654	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.4588598e-05
8,363	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.3305234e-05
8,790	One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees	2022	SIGMOD	5.2633515e-05
8,894	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	5.2415191e-05
9,475	HyperBlocker: Accelerating Rule-based Blocking in Entity Resolution using GPUs	2025	VLDB	5.157794e-05
9,667	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.1278365e-05
10,249	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.0412674e-05
11,898	Juggler: Autonomous Cost Optimization and Performance Prediction of Big Data Applications	2022	SIGMOD	4.9605343e-05
14,152	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.0003999751
78	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036725074
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029532435
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027775994
171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027063233
296	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021874894
337	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020593498
346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020265363
471	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017691682
518	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016918797
3,142	Statistics on Views	2003	VLDB	7.5858292e-05
3,884	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.9285249e-05
5,864	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9498215e-05
8,309	Learning Table Access Cardinalities with LEO	2002	SIGMOD	5.3415206e-05

Semantically Similar Papers

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