Multiple Join Size Estimation by Virtual Domains (extended abstract)

Summary: Introduces "virtual domains" to estimate sizes of intermediate relations for complex multi-equijoin expressions, avoiding the unrealistic underestimates caused by attribute-independence assumptions while requiring little database statistics. Presents an exact model plus a lightweight, fast approximation tailored for optimizer search over many alternative plans. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h2737276e9626709e
Venue: PODS
Year: 1993
Pagerank: 7.7621043e-05
Overall Rank: 3,005 | 79.80%
DOI: 10.1145/153850.153872

Incoming Non-self Citations Over Time

Authors

1. Allen Van Gelder (University of California Santa Cruz)

BibTeX Citation

@inproceedings{gelder_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Multiple Join Size Estimation by Virtual Domains (extended abstract)}},
        url = {https://dl.acm.org/doi/10.1145/153850.153872},
        doi = {10.1145/153850.153872},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Van Gelder, Allen},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202282
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
1,929	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3546057e-05
3,052	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7052471e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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.0023947656
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029179719
470	Optimization of Large Join Queries	1988	SIGMOD	0.00017755852
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017462723
708	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014629998
725	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014465736
859	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013418999
956	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00012865801
8,148	Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies	1992	SIGMOD	5.3906029e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
2	750	Join Size Estimation Subject to Filter Conditions	2015	VLDB
3	91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD
4	8,462	On the Optimality of Strategies for Multiple Joins	1990	PODS
5	5,918	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS
6	3,992	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
7	4,881	Evaluation Of The Size Of A Query Expressed In Relational Algebra	1981	SIGMOD
8	1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
9	1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
10	1,184	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD