Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses

Summary: Novel approach to fuse synopses (histograms) and sampling for conjunctive-query selectivity estimation. It extracts mutually consistent statistics from both sources, then computes an admissible combined estimate and benchmarks its accuracy and tradeoffs against state-of-the-art methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11597
Venue: VLDB
Year: 2018
Pagerank: 9.8764627e-05
Overall Rank: 1,978 | 86.26%
DOI: 10.14778/3213880.3213882

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
203	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034868567
1,239	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013091459
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
2,364	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	8.955077e-05
3,167	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	7.4561078e-05
3,644	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	6.8842065e-05
3,706	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8232992e-05
3,955	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	6.5895015e-05
4,352	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	6.2542257e-05
4,372	Sample Debiasing in the Themis Open World Database System	2020	SIGMOD	6.2367043e-05
4,526	Simplicity Done Right for Join Ordering	2021	CIDR	6.1079584e-05
4,689	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	5.9899401e-05
5,528	Warper: Efficiently Adapting Learned Cardinality Estimators to Data and Workload Drifts	2022	SIGMOD	5.4571136e-05
5,639	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	5.3972261e-05
5,886	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2847297e-05
7,188	LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries	2024	SIGMOD	4.8017628e-05
7,854	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	4.6306186e-05
8,414	PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression	2024	VLDB	4.5135713e-05
9,387	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.341968e-05
10,647	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
627	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018959896
1,104	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.0001398479
1,254	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013018797
4,566	Adaptive Statistics in Oracle 12c	2017	VLDB	6.073045e-05
4,815	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	5.8978716e-05
5,907	Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA	2014	SIGMOD	5.2741214e-05
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8128138e-05
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4232868e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
1,254	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013018797
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
9,387	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.341968e-05
2,779	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.1314377e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05
3,597	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9337747e-05
3,955	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	6.5895015e-05
373	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354685
3,656	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	6.8712579e-05