Database Paper Browser

Back to papers

Two-Level Sampling for Join Size Estimation

Summary: Two-Level Sampling for Join Size Estimation proposes a one-pass, hybrid method for join cardinality. It leverages l_k-norms and heavy hitters to deliver accurate estimates for PK–FK, many-to-many, and complex joins with simple implementation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5288
Venue
SIGMOD
Year
2017
Pagerank
9.1871115e-05
Overall Rank
2,254 | 84.34%
DOI
10.1145/3035918.3035921

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
203 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00034868567
2,143 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 9.4437798e-05
3,644 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8842065e-05
3,827 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 6.7195959e-05
3,944 AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018 SIGMOD 6.6056349e-05
3,955 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 6.5895015e-05
4,526 Simplicity Done Right for Join Ordering 2021 CIDR 6.1079584e-05
4,679 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 5.9978792e-05
4,926 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 5.8184457e-05
5,405 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 5.5243727e-05
5,931 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 5.2632167e-05
6,481 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.039683e-05
7,340 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7526052e-05
7,465 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7186055e-05
8,345 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 4.5361313e-05
8,392 Hypothetical Reasoning via Provenance Abstraction 2019 SIGMOD 4.5234647e-05
8,499 Conditional Cuckoo Filters 2021 SIGMOD 4.4929219e-05
8,642 One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees 2022 SIGMOD 4.4734993e-05
9,621 ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation 2023 VLDB 4.3125802e-05
10,149 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.1905499e-05
10,632 Evaluating Methods for Efficient Entity Count Estimation 2025 VLDB 4.1905499e-05
10,647 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1905499e-05
10,837 Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects 2025 VLDB 4.1905499e-05
10,872 LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison 2025 VLDB 4.1905499e-05
10,984 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1905499e-05
10,996 SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs 2024 SIGMOD 4.1905499e-05
11,028 Sampling Methods for Inner Product Sketching 2024 VLDB 4.1905499e-05
11,703 Tighter Upper Bounds for Join Cardinality Estimates 2018 SIGMOD 4.1905499e-05
Previous Page 1 / 1 Next

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
212 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00033997204
416 Approximate Query Processing Using Wavelets 2000 VLDB 0.00023773968
550 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020346247
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272747
751 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017155121
831 Finding Frequent Items in Data Streams 2008 VLDB 0.00016094846
941 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015147831
1,065 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014344675
1,194 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013411666
1,320 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00012606067
1,394 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012218557
1,938 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025547
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,372 Random Sampling over Joins Revisited 2018 SIGMOD 0.0001233325
8,964 Reservoir Sampling over Joins 2024 SIGMOD 4.4163852e-05
1,019 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00014623543
1,254 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013018797
550 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020346247
18 On Random Sampling over Joins 1999 SIGMOD 0.00092569117
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
11,449 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD 4.1905499e-05
1,194 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013411666