Database Paper Browser

Back to papers

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
11596
Venue
VLDB
Year
2018
Pagerank
9.8687545e-05
Overall Rank
1,981 | 86.23%
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
204 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00034784455
1,254 Selectivity Estimation for Range Predicates using Lightweight Models 2019 VLDB 0.00013027411
1,703 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00010836769
2,142 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 9.4507296e-05
2,364 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 8.9554751e-05
3,169 QueryFormer: A Tree Transformer Model for Query Plan Representation 2022 VLDB 7.4498425e-05
3,646 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8853079e-05
3,702 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 6.8295759e-05
3,954 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 6.5926838e-05
4,359 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 6.2569955e-05
4,375 Sample Debiasing in the Themis Open World Database System 2020 SIGMOD 6.2427076e-05
4,523 Simplicity Done Right for Join Ordering 2021 CIDR 6.1135504e-05
4,694 Scalable Reservoir Sampling on Many-Core CPUs 2019 SIGMOD 5.9944898e-05
5,633 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 5.4011156e-05
5,645 Warper: Efficiently Adapting Learned Cardinality Estimators to Data and Workload Drifts 2022 SIGMOD 5.3923454e-05
5,880 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 5.2898074e-05
7,186 LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries 2024 SIGMOD 4.8063731e-05
7,854 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 4.6350172e-05
9,380 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD 4.3461329e-05
9,431 PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression 2024 VLDB 4.3434046e-05
10,639 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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.00059038975
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
99 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00050022914
629 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00018942366
1,105 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00013990395
1,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
4,571 Adaptive Statistics in Oracle 12c 2017 VLDB 6.0773174e-05
4,831 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 5.8924198e-05
5,905 Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA 2014 SIGMOD 5.2788785e-05
7,150 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 4.8163484e-05
8,893 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 4.4275272e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
1,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
2,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1320575e-05
9,380 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD 4.3461329e-05
7,581 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 4.7057641e-05
3,593 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9385476e-05
3,954 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 6.5926838e-05
372 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354779
3,651 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 6.8768678e-05