DBScholar

Back to papers

Consistently Estimating the Selectivity of Conjuncts of Predicates

Summary: Introduces a maximum-entropy (ME) framework for consistently estimating the selectivity of conjunctive predicates under multivariate statistics. ME exploits all available information, avoids ad hoc bias, and falls back to uniform/independence when data are sparse, improving cardinality estimates and plan quality. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9510
Venue
VLDB
Year
2005
Pagerank
9.4557372e-05
Overall Rank
1,936 | 86.72%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{markl_vldb05,
        title = {{Consistently Estimating the Selectivity of Conjuncts of Predicates}},
        author = {Markl, V. and Megiddo, N. and Kutsch, M. and Tran, T.M. and Haas, P. and Srivastava, U.},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {373--384},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank Citing Paper Year Venue Pagerank
18 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059284255
411 Worst-case Optimal Join Algorithms 2012 PODS 0.00018902089
694 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014911698
1,061 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012369764
1,170 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011827259
2,944 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9335187e-05
4,280 Measure-driven Keyword-Query Expansion 2009 VLDB 6.7853952e-05
5,860 Understanding Cardinality Estimation using Entropy Maximization 2010 PODS 6.0636893e-05
6,325 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9125893e-05
7,206 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 5.6731116e-05
7,554 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.6001388e-05
8,191 Probabilistic Database Summarization for Interactive Data Exploration 2017 VLDB 5.4699738e-05
9,920 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB 5.1955087e-05
13,823 MAXENT: Consistent Cardinality Estimation in Action 2006 SIGMOD -
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank Cited Paper Year Venue Pagerank
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048481081
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00048351457
89 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00035031529
100 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034385207
159 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00028129426
280 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00022454217
365 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00020041735
448 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00018292618
664 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.00015167825
692 Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data 2001 SIGMOD 0.00014919816
934 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00013108714
2,149 Probabilistic Optimization of Top N Queries 1999 VLDB 9.0821709e-05
2,984 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.8920597e-05
3,093 Statistics on Views 2003 VLDB 7.7664764e-05
3,309 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.5368417e-05
4,591 Automated Statistics Collection in DB2 UDB 2004 VLDB 6.614318e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 101 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB
2 10,515 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB
3 5,860 Understanding Cardinality Estimation using Entropy Maximization 2010 PODS
4 1,536 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB
5 6,009 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB
6 280 Selectivity Estimation using Probabilistic Models 2001 SIGMOD
7 566 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD
8 934 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB
9 3,309 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD
10 13,823 MAXENT: Consistent Cardinality Estimation in Action 2006 SIGMOD