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

Summary: Introduces MAMD, a stored-sample method for distinct-count estimation over multiple attributes and joined datasets, with or without selections. Demonstrates moderately low error, low storage and compilation cost on TPC-H/IMDB, including scalability. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h8dff9a1d63287cc7
Venue: VLDB
Year: 2026
Pagerank: 4.9769913e-05
Overall Rank: 10,710 | 28.02%
DOI: 10.14778/3797919.3797922
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

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

Authors

1. Mehnaz Tabassum Mahin (University of California Riverside)
2. Michael J. Carey (University of California Irvine)
3. Vassilis J. Tsotras (University of California Riverside)

BibTeX Citation

@article{mahin_vldb26,
        title = {{Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries}},
        author = {Mahin, Mehnaz Tabassum and Carey, Michael J. and Tsotras, Vassilis J.},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {6},
        pages = {1115--1127},
        doi = {10.14778/3797919.3797922},
        url = {https://doi.org/10.14778/3797919.3797922},
        year = {2026}
}

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.0023943337
9	Online Aggregation	1997	SIGMOD	0.00076265429
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.0004772731
57	On Random Sampling over Joins	1999	SIGMOD	0.00040095727
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040025054
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036817139
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034748721
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026384065
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
361	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00020000855
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016297598
691	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014737455
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013934719
1,065	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202293
1,195	Balsa: Learning a Query Optimizer Without Expert Demonstrations	2022	SIGMOD	0.00011574218
1,515	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	0.00010418766
1,537	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010324934
1,735	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7566604e-05
2,686	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB	8.1300913e-05
3,132	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.6107287e-05
3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.2548566e-05
5,316	How Good are Learned Cost Models, Really? Insights from Query Optimization Tasks	2025	SIGMOD	6.1827415e-05
5,630	Sample-Efficient Cardinality Estimation Using Geometric Deep Learning	2024	VLDB	6.056758e-05
9,556	Athena: An Effective Learning-based Framework for Query Optimizer Performance Improvement	2025	SIGMOD	5.1580326e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
2	1,065	Are We Ready For Learned Cardinality Estimation?	2021	VLDB
3	688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
4	1,258	Sampling-Based Query Re-Optimization	2016	SIGMOD
5	2,518	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB
6	1,537	Cardinality Estimation: An Experimental Survey	2018	VLDB
7	2,432	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD
8	1,931	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB
9	7,368	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD
10	9,640	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD