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: 14264
Venue: VLDB
Year: 2026
Pagerank: 4.1905499e-05
Overall Rank: 10,227 | 28.93%
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.0040465394
14	Online Aggregation	1997	SIGMOD	0.0010813443
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
133	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00043220055
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
380	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00024943236
634	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00018844568
736	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017414831
1,239	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013091459
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
1,683	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.0001091276
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
2,090	Balsa: Learning a Query Optimizer Without Expert Demonstrations	2022	SIGMOD	9.5668285e-05
2,781	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1282042e-05
2,937	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	7.8552033e-05
3,706	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8232992e-05
3,729	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB	6.8078013e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
6,382	Sample-Efficient Cardinality Estimation Using Geometric Deep Learning	2024	VLDB	5.0835686e-05
6,687	How Good are Learned Cost Models, Really? Insights from Query Optimization Tasks	2025	SIGMOD	4.957987e-05
9,824	Athena: An Effective Learning-based Framework for Query Optimizer Performance Improvement	2025	SIGMOD	4.2710095e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
1,104	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.0001398479
3,455	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	7.0760196e-05
1,756	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010659753
1,683	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.0001091276
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7082045e-05
2,359	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.967267e-05
7,340	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	4.7526052e-05
9,387	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.341968e-05