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: 6102
Venue: SIGMOD
Year: 2021
Pagerank: 4.7526052e-05
Overall Rank: 7,340 | 48.99%
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,886	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.6610704e-05
5,373	Fine-Grained Modeling and Optimization for Intelligent Resource Management in Big Data Processing	2022	VLDB	5.5410059e-05
5,405	ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads	2024	VLDB	5.5243727e-05
8,585	A Spark Optimizer for Adaptive, Fine-Grained Parameter Tuning	2024	VLDB	4.4856045e-05
10,863	Graph Transformers for Query Plan Representation: Potentials and Challenges	2025	VLDB	4.1905499e-05
10,997	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1905499e-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.0010813443
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
449	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00022914472
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
737	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00017377393
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
941	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015147831
955	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015069776
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,574	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00011289028
1,867	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010264932
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
2,918	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	7.9043213e-05
2,954	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.8218804e-05
3,153	AnalyticDB: Real-time OLAP Database System at Alibaba Cloud	2019	VLDB	7.4706916e-05
3,706	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8232992e-05
4,835	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	5.8861112e-05
6,243	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.1348218e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
1,683	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.0001091276
5,639	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	5.3972261e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
10,227	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.1905499e-05
1,254	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013018797
9,387	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.341968e-05
1,756	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010659753
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7082045e-05
1,104	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.0001398479