@article {13380,
	title = {Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions},
	journal = {Proceedings of the VLDB Endowment},
	volume = {4},
	year = {2011},
	month = {2011///},
	abstract = {As a result of decades of research and industrial development, mod-ern query optimizers are complex software artifacts. However, the
quality of the query plan chosen by an optimizer is largely deter-
mined by the quality of the underlying statistical summaries. Small
selectivity estimation errors, propagated exponentially, can lead to
severely sub-optimal plans. Modern optimizers typically maintain
one-dimensional statistical summaries and make the attribute value
independence and join uniformity assumptions for efficiently esti-
mating selectivities. Therefore, selectivity estimation errors in to-
day{\textquoteright}s optimizers are frequently caused by missed correlations be-
tween attributes. We present a selectivity estimation approach that
does not make the independence assumptions. By carefully using
concepts from the field of graphical models, we are able to fac-
tor the joint probability distribution of all the attributes in the data-
base into small, usually two-dimensional distributions. We describe
several optimizations that can make selectivity estimation highly
efficient, and we present a complete implementation inside Post-
greSQL{\textquoteright}s query optimizer. Experimental results indicate an order
of magnitude better selectivity estimates, while keeping optimiza-
tion time in the range of tens of milliseconds.
},
	author = {Tzoumas,K. and Deshpande, Amol and Jensen,C. S}
}
