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: 8046
Venue: VLDB
Year: 1988
Pagerank: 0.00013108714
Overall Rank: 934 | 93.60%
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
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
100	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034385207
222	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00024193708
811	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013859761
992	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012790174
1,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259
1,172	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00011825923
1,382	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010965236
1,936	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.4557372e-05
2,923	Optimizing Boolean Expressions in Object Bases	1992	VLDB	7.9578414e-05
2,984	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.8920597e-05
3,086	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7708642e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05
5,852	DEX: Scalable Range Indexing on Disaggregated Memory	2024	VLDB	6.0658952e-05
9,944	Chimera: A system design of dual storage and traversal-join unified query processing for SQL/PGQ	2025	VLDB	5.1915905e-05
9,958	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1879626e-05
10,875	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.093636e-05
13,136	Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence	1989	SIGMOD	5.093636e-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.0024089429
34	The Design Of Postgres	1986	SIGMOD	0.00049302774
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
92	The Database Language GEM	1983	SIGMOD	0.00034759032
3,469	Extended User-Defined Indexing with Application to Textual Databases	1988	VLDB	7.3893582e-05

Semantically Similar Papers

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