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.00017155121
Overall Rank
751 | 94.79%
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.00051431888
291 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00028778973
369 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025502381
531 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.0002079072
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272747
803 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016438972
941 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015147831
1,063 Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines 1990 VLDB 0.00014352292
1,254 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013018797
1,379 Substring Selectivity Estimation 1999 PODS 0.00012280308
1,420 SchemaSQL - A Language for Interoperability in Relational Multi-database Systems 1996 VLDB 0.00012068815
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1871115e-05
3,965 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.5786424e-05
4,793 Toward Practical Constraint Databases 1993 VLDB 5.9107617e-05
7,833 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6367487e-05
10,984 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1905499e-05
12,892 Learning Efficient Query Processing Strategies 1992 PODS 4.1905499e-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.0040465394
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080571183
37 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00075597514
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00071588702
226 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.0003243274
520 LDL: A Logic-Based Data-Language 1986 VLDB 0.00021145923
613 Top-down statistical estimation on a database 1983 SIGMOD 0.00019104493
896 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015486851
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
1,636 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00011058643
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
37 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00075597514
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1871115e-05
1,019 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00014623543
550 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020346247
11,449 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD 4.1905499e-05
369 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025502381
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
9,524 Analysis and Application of Adaptive Sampling 2000 PODS 4.3268997e-05
5,085 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.7040225e-05
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051431888