Cardinality Estimation: An Experimental Survey

Summary: Comprehensively surveys and classifies cardinality (zeroth-frequency moment) estimators, detailing guarantees and design trade-offs. An expanded evaluation of 12 algorithms on synthetic and real data compares accuracy, runtime, and memory, showing workload-dependent winners. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h253f0fed14b71c81
Venue: VLDB
Year: 2018
Pagerank: 0.00010324934
Overall Rank: 1,537 | 89.68%
DOI: 10.1145/3164135.3164145

Incoming Non-self Citations Over Time

Authors

1. Hazar Harmouch (Hasso Plattner Institute; University of Potsdam)
2. Felix Naumann (Hasso Plattner Institute; University of Potsdam)

BibTeX Citation

@article{harmouch_vldb18,
        title = {{Cardinality Estimation: An Experimental Survey}},
        author = {Harmouch, Hazar and Naumann, Felix},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {4},
        pages = {499--512},
        doi = {10.1145/3164135.3164145},
        url = {https://doi.org/10.1145/3164135.3164145},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,065	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202293
1,308	Automating Large-Scale Data Quality Verification	2018	VLDB	0.00011073863
2,837	Query Performance Prediction for Concurrent Queries using Graph Embedding	2020	VLDB	7.9495917e-05
3,092	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	7.6548729e-05
3,132	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.6107287e-05
4,330	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.6564176e-05
4,347	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.6457039e-05
6,796	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6784895e-05
7,426	Learning to be a Statistician: Learned Estimator for Number of Distinct Values	2022	VLDB	5.5295692e-05
7,476	Fast Detection of Denial Constraint Violations	2022	VLDB	5.5150385e-05
7,958	Robust Query Processing: Mission Possible	2020	VLDB	5.4164639e-05
8,210	Grep: A Graph Learning Based Database Partitioning System	2023	SIGMOD	5.3761621e-05
8,336	LAQy: Efficient and Reusable Query Approximations via Lazy Sampling	2023	SIGMOD	5.3508072e-05
9,380	An Effective and Differentially Private Protocol for Secure Distributed Cardinality Estimation	2023	SIGMOD	5.1843659e-05
9,381	Efficient and Effective Cardinality Estimation for Skyline Family	2023	SIGMOD	5.1843659e-05
9,520	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.1683226e-05
10,187	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	5.0628015e-05
10,306	AdaNDV: Adaptive Number of Distinct Value Estimation via Learning to Select and Fuse Estimators	2025	VLDB	5.0392037e-05
10,532	A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables	2026	SIGMOD	4.9769913e-05
10,710	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.9769913e-05
11,057	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	4.9769913e-05
11,192	Efficient and Accurate Differentially Private Cardinality Continual Releases	2025	SIGMOD	4.9769913e-05
11,201	PLM4NDV: Minimizing Data Access for Number of Distinct Values Estimation with Pre-trained Language Models	2025	SIGMOD	4.9769913e-05
11,225	SPECIAL: SynoPsis AssistEd Secure CollaboratIve AnaLytics	2025	VLDB	4.9769913e-05
11,598	Agile-Ant: Self-managing Distributed Cache Management for Cost Optimization of Big Data Applications	2024	VLDB	4.9769913e-05
11,926	No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing	2022	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036817139
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022713652
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021908194
707	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014633741
1,394	Data Profiling with Metanome	2015	VLDB	0.00010791559

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	406	Deep Unsupervised Cardinality Estimation	2020	VLDB
2	2,975	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB
3	5,974	Understanding Cardinality Estimation using Entropy Maximization	2010	PODS
4	5,835	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB
5	11,341	The Accuracy of Cardinality Estimators: Unraveling the Evaluation Result Conundrum	2025	VLDB
6	5,655	Distributed Set-Expression Cardinality Estimation	2004	VLDB
7	1,065	Are We Ready For Learned Cardinality Estimation?	2021	VLDB
8	2,518	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB
9	981	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB
10	6,124	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD