Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values
Clifford A. Lynch · Very Large Data Bases · 1988
When column values in a large dat.abase follow highly skewed distributions (such as Zipf distributions, typi( ally found in textual dnt,abascs), qnery optimizers in c111 rem relat.ional syst,ems often fail to choose optimal query plans cvcn for simple single-relation queries. The rtrnjor cause of these optil+rization failures is incorrect predicate selectivity estimation; the likelihood and cost of such errors are quantified. A scheme for adding userclrfin~~d selectivity estimators to a relational DBMS is propc,.:cd. The paper defines a series of new selectivity estimation methods that work well with highly skewed v&e distributions and then compares them to currently used methods such as uniform approximation and histograms. Empirical data from a large bibliographic database is used throughout the a.nalyses in this paper.