Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries

Summary: Sample-based distinct-count estimator for multi-attribute, multi-relation queries (MAMD), extending stored-sample CBO machinery beyond cardinalities to NDV under joins and selections. Shows moderately low error with low storage/runtime overhead on TPC-H and IMDB. (summarized by gpt-5.4-mini on Apr 12 2026)

Paper ID: 14263
Venue: VLDB
Year: 2026
Pagerank: 4.1945683e-05
Overall Rank: 10,227 | 28.86%
DOI: 10.14778/3797919.3797922

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 26 of 26 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040449103
14	Online Aggregation	1997	SIGMOD	0.0010801504
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
59	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064501896
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
134	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00042452811
308	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00028142852
378	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.0002497492
640	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00018759152
739	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017401518
1,254	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013027411
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
1,683	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010922679
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
2,121	Balsa: Learning a Query Optimizer Without Expert Demonstrations	2022	SIGMOD	9.5017232e-05
2,783	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1293383e-05
2,985	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	7.7795847e-05
3,702	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8295759e-05
3,727	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB	6.8141709e-05
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
6,383	Sample-Efficient Cardinality Estimation Using Geometric Deep Learning	2024	VLDB	5.0884322e-05
6,685	How Good are Learned Cost Models, Really? Insights from Query Optimization Tasks	2025	SIGMOD	4.9627485e-05
9,825	Athena: An Effective Learning-based Framework for Query Optimizer Performance Improvement	2025	SIGMOD	4.2751057e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
1,105	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00013990395
3,449	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	7.0824319e-05
1,758	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010655546
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7137441e-05
1,683	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010922679
2,356	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.9620762e-05
7,358	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	4.7529363e-05
9,380	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.3461329e-05