On the Relative Cost of Sampling for Join Selectivity Estimation

Summary: Quantifies when sampling (t_cross) is cheaper than computing the exact star-join for selectivity estimation, deriving bounds and approximations for relative cost as functions of input relation sizes, arity, and the estimator's precision criterion. Identifies dangling tuples as a major negative factor and characterizes mixed effects of data skew, yielding concrete regimes and thresholds that indicate when sampling is or isn't cost-effective for join selectivity estimation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h654566b737eab009
Venue: PODS
Year: 1994
Pagerank: 0.00010567959
Overall Rank: 1,467 | 90.14%
DOI: 10.1145/182591.182594

Incoming Non-self Citations Over Time

Authors

1. Peter J. Haas (IBM)
2. Jeffrey F. Naughton (University of Wisconsin)
3. Arun N. Swami (IBM)

BibTeX Citation

@inproceedings{haas_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{On the Relative Cost of Sampling for Join Selectivity Estimation}},
        url = {https://dl.acm.org/doi/10.1145/182591.182594},
        doi = {10.1145/182591.182594},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Haas, Peter J. and Naughton, Jeffrey F. and Swami, Arun N.},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
745	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014288286
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
2,216	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	8.8177753e-05
3,052	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7052471e-05
6,685	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.7086005e-05
9,429	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.1786456e-05
9,976	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	5.1031384e-05
11,257	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	4.9793485e-05
11,290	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026784195
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026389403
346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020329113
477	Random Sampling from B+ trees	1989	VLDB	0.00017632787
492	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.00017408001
1,011	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012529816
1,203	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011548537
1,229	Random Sampling from Hash Files	1990	SIGMOD	0.00011420642
1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010734049

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
2	5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB
3	1,011	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS
4	11,951	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD
5	57	On Random Sampling over Joins	1999	SIGMOD
6	1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
7	750	Join Size Estimation Subject to Filter Conditions	2015	VLDB
8	428	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS
9	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
10	1,203	Fixed-Precision Estimation of Join Selectivity	1993	PODS