Database Paper Browser

Back to papers

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
887
Venue
PODS
Year
1990
Pagerank
0.00017036868
Overall Rank
762 | 94.71%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
315 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.0002802103
367 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025509745
530 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00020803682
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272061
811 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016425612
943 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015145883
1,063 Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines 1990 VLDB 0.00014362773
1,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
1,379 Substring Selectivity Estimation 1999 PODS 0.00012286879
1,422 SchemaSQL - A Language for Interoperability in Relational Multi-database Systems 1996 VLDB 0.00012056887
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1897043e-05
3,966 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.580483e-05
4,793 Toward Practical Constraint Databases 1993 VLDB 5.9164359e-05
7,827 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6411831e-05
10,981 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1945683e-05
12,882 Learning Efficient Query Processing Strategies 1992 PODS 4.1945683e-05
Previous Page 1 / 1 Next

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.0040449103
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080435857
39 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00074745564
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00070894702
228 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00032269684
519 LDL: A Logic-Based Data-Language 1986 VLDB 0.00021154077
615 Top-down statistical estimation on a database 1983 SIGMOD 0.00019128024
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
897 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015528028
1,712 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00010804573
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
39 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00074745564
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1897043e-05
1,020 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00014624893
549 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020376603
11,446 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD 4.1945683e-05
367 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025509745
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
9,523 Analysis and Application of Adaptive Sampling 2000 PODS 4.331052e-05
5,104 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.6946113e-05
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959