Query Size Estimation by Adaptive Sampling (Extended Abstract)

Summary: Adaptive random-sampling estimator for queries decomposable into bounded-cost answer blocks; adaptively chooses sample count so runtime remains stable despite widely varying sample costs. Yields R⋈S estimate in time linear in smaller relation (O(1) if per-tuple joins bounded), transitive closure ≈O(n√m) (linear for near-uniform degree), and applies to recursive Datalog. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h7e9da105f09c6786
Venue: PODS
Year: 1990
Pagerank: 0.00012489386
Overall Rank: 1,012 | 93.22%
DOI: 10.1145/298514.298540

Incoming Non-self Citations Over Time

Authors

1. Richard J. Lipton (Princeton University)
2. Jeffrey F. Naughton (University of Wisconsin)

BibTeX Citation

@inproceedings{lipton_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{Query Size Estimation by Adaptive Sampling (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/298514.298540},
        doi = {10.1145/298514.298540},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Lipton, Richard J. and Naughton, Jeffrey F.},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020265363
492	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.00017359343
518	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016918797
594	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015814493
750	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014246313
921	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013036878
1,206	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011510881
1,466	Substring Selectivity Estimation	1999	PODS	0.00010546176
1,469	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010533259
1,580	SchemaSQL - A Language for Interoperability in Relational Multi-database Systems	1996	VLDB	0.00010153792
1,681	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.8821344e-05
4,563	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5201574e-05
5,190	Toward Practical Constraint Databases	1993	VLDB	6.2213007e-05
8,346	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	5.3339321e-05
11,591	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9605343e-05
13,413	Learning Efficient Query Processing Strategies	1992	PODS	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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.0023948467
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047770864
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026701703
425	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00018437618
638	LDL: A Logic-Based Data-Language	1986	VLDB	0.0001531355
960	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00012825107
1,423	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010696781
1,433	Top-down statistical estimation on a database	1983	SIGMOD	0.00010661879
1,688	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8481921e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	58	Statistical Estimators for Relational Algebra Expressions	1988	PODS
2	1,681	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
3	1,187	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD
4	432	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS
5	12,001	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD
6	346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD
7	1,423	Estimating the Size of Generalized Transitive Closures	1989	VLDB
8	9,892	Analysis and Application of Adaptive Sampling	2000	PODS
9	4,011	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
10	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD