Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries

Summary: Weighted distinct sampling (WDS) is proposed as a near-optimal framework for estimating SP cardinalities. The approach extends to SPJ queries, delivering the first non-trivial SPJ cardinality solution and is supported by extensive experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6101
Venue: SIGMOD
Year: 2021
Pagerank: 4.7529363e-05
Overall Rank: 7,358 | 48.82%
DOI: 10.1145/3448016.3452821

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,885	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.6674822e-05
5,368	Fine-Grained Modeling and Optimization for Intelligent Resource Management in Big Data Processing	2022	VLDB	5.5457532e-05
5,401	ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads	2024	VLDB	5.5285035e-05
8,617	A Spark Optimizer for Adaptive, Fine-Grained Parameter Tuning	2024	VLDB	4.4846425e-05
10,859	Graph Transformers for Query Plan Representation: Potentials and Challenges	2025	VLDB	4.1945683e-05
10,994	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 27 of 27 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
14	Online Aggregation	1997	SIGMOD	0.0010801504
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
308	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00028142852
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
383	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00024820873
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
727	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00017508726
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
943	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015145883
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
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,574	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00011287495
1,874	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010244443
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1897043e-05
2,914	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	7.9118579e-05
2,953	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.8267643e-05
3,152	AnalyticDB: Real-time OLAP Database System at Alibaba Cloud	2019	VLDB	7.4711766e-05
3,702	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8295759e-05
4,833	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	5.8916346e-05
6,244	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.139669e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
1,683	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010922679
5,633	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	5.4011156e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1897043e-05
10,227	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.1945683e-05
1,255	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013024064
9,380	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.3461329e-05
1,758	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010655546
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7137441e-05
1,105	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00013990395