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
5287
Venue
SIGMOD
Year
2017
Pagerank
9.1897043e-05
Overall Rank
2,254 | 84.33%
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
204 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00034784455
2,142 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 9.4507296e-05
3,646 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8853079e-05
3,824 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 6.7260705e-05
3,944 AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018 SIGMOD 6.6078243e-05
3,954 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 6.5926838e-05
4,523 Simplicity Done Right for Join Ordering 2021 CIDR 6.1135504e-05
4,681 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.0034918e-05
4,953 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 5.8085795e-05
5,401 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 5.5285035e-05
5,930 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 5.2682075e-05
6,493 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.0424713e-05
7,358 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7529363e-05
7,467 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7218691e-05
8,350 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 4.5404832e-05
8,394 Hypothetical Reasoning via Provenance Abstraction 2019 SIGMOD 4.527807e-05
8,502 Conditional Cuckoo Filters 2021 SIGMOD 4.4972336e-05
8,643 One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees 2022 SIGMOD 4.4777916e-05
9,621 ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation 2023 VLDB 4.3167167e-05
10,149 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.1945683e-05
10,624 Evaluating Methods for Efficient Entity Count Estimation 2025 VLDB 4.1945683e-05
10,639 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1945683e-05
10,833 Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects 2025 VLDB 4.1945683e-05
10,868 LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison 2025 VLDB 4.1945683e-05
10,981 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1945683e-05
10,993 SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs 2024 SIGMOD 4.1945683e-05
11,025 Sampling Methods for Inner Product Sketching 2024 VLDB 4.1945683e-05
11,698 Tighter Upper Bounds for Join Cardinality Estimates 2018 SIGMOD 4.1945683e-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
211 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00033981214
405 Approximate Query Processing Using Wavelets 2000 VLDB 0.00024057494
549 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020376603
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272061
762 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017036868
835 Finding Frequent Items in Data Streams 2008 VLDB 0.00016109621
943 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015145883
1,064 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014356481
1,193 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013414989
1,323 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00012601997
1,392 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012229045
1,939 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025655
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,369 Random Sampling over Joins Revisited 2018 SIGMOD 0.00012339777
8,959 Reservoir Sampling over Joins 2024 SIGMOD 4.4206222e-05
1,020 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00014624893
1,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
549 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020376603
18 On Random Sampling over Joins 1999 SIGMOD 0.00092385438
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
11,446 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD 4.1945683e-05
1,193 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013414989