Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values

Summary: Shows that uniform and histogram selectivity estimates can badly mislead optimizers on Zipf-skewed columns, even for single-table queries. Proposes extensible user-defined estimators and evaluates skew-aware methods on a large bibliographic database. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: he5cb2422a92cfcc6
Venue: VLDB
Year: 1988
Pagerank: 0.00012865801
Overall Rank: 956 | 93.58%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Clifford A. Lynch (University of California)

BibTeX Citation

@article{lynch_vldb88,
        title = {{Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values}},
        author = {Lynch, Clifford A.},
        journal = {PVLDB},
        series = {{VLDB} '88},
        pages = {240},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
232	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023792809
833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013583955
1,011	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012529816
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
1,184	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00011611937
1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010734049
1,929	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3546057e-05
2,983	Optimizing Boolean Expressions in Object Bases	1992	VLDB	7.7839431e-05
3,005	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.7621043e-05
3,052	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7052471e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2250048e-05
5,949	DEX: Scalable Range Indexing on Disaggregated Memory	2024	VLDB	5.9368754e-05
9,718	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1353964e-05
10,128	Chimera: A system design of dual storage and traversal-join unified query processing for SQL/PGQ	2025	VLDB	5.0751052e-05
10,294	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.0431863e-05
13,426	Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence	1989	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
34	The Design Of Postgres	1986	SIGMOD	0.00049142315
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
96	The Database Language GEM	1983	SIGMOD	0.00034286345
3,530	Extended User-Defined Indexing with Application to Textual Databases	1988	VLDB	7.2276073e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,580	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD
2	4,933	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD
3	3,361	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD
4	3,210	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
5	283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
6	1,508	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD
7	169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD
8	1,929	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB
9	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
10	286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD