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: 11784
Venue: VLDB
Year: 2018
Pagerank: 0.00010460864
Overall Rank: 1,536 | 89.47%
DOI: 10.14778/3213880.3213882

Incoming Non-self Citations Over Time

Authors

1. Magnus Müller (University of Mannheim)
2. Guido Moerkotte (University of Mannheim)
3. Oliver Kolb (University of Mannheim)

BibTeX Citation

@article{muller_vldb18,
        title = {{Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses}},
        author = {Müller, Magnus and Moerkotte, Guido and Kolb, Oliver},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {9},
        pages = {1016--1028},
        doi = {10.14778/3213880.3213882},
        url = {https://doi.org/10.14778/3213880.3213882},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
697	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014888851
1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012369764
1,499	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010564536
1,573	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010328171
2,355	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	8.7022189e-05
2,940	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9381573e-05
3,162	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	7.6785856e-05
3,215	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.6324234e-05
3,545	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.3249967e-05
3,959	Simplicity Done Right for Join Ordering	2021	CIDR	6.9879431e-05
4,205	Sample Debiasing in the Themis Open World Database System	2020	SIGMOD	6.8337021e-05
4,612	Warper: Efficiently Adapting Learned Cardinality Estimators to Data and Workload Drifts	2022	SIGMOD	6.6072026e-05
4,800	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	6.502434e-05
4,900	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.4534715e-05
5,010	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	6.4023732e-05
6,760	LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries	2024	SIGMOD	5.7826781e-05
7,193	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6770249e-05
7,351	PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression	2024	VLDB	5.6354898e-05
9,455	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.2653318e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
388	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019410042
694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014911698
1,186	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011764128
4,277	Adaptive Statistics in Oracle 12c	2017	VLDB	6.7873816e-05
4,405	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.7218674e-05
5,693	Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA	2014	SIGMOD	6.1189424e-05
7,443	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	5.6166792e-05
8,998	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	5.3355988e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
2	1,186	Fixed-Precision Estimation of Join Selectivity	1993	PODS
3	35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
4	2,308	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB
5	9,455	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD
6	7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS
7	3,788	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD
8	3,162	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
9	280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
10	3,309	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD