CORDS
Ihab F. Ilyas, Volker Markl, Peter J. Haas et al. · Proceedings - ACM-SIGMOD International Conference on Management of Data · 2004
The rich dependency structure found in the columns of real-world relational databases can be exploited to great advantage, but can also cause query optimizers---which usually assume that columns are statistically independent---to underestimate the selectivities of conjunctive predicates by orders of magnitude. We introduce CORDS, an efficient and scalable tool for automatic discovery of correlations and soft functional dependencies between columns. CORDS searches for column pairs that might have interesting and useful dependency relations by systematically enumerating candidate pairs and simultaneously pruning unpromising candidates using a flexible set of heuristics. A robust chi-squared analysis is applied to a sample of column values in order to identify correlations, and the number of distinct values in the sampled columns is analyzed to detect soft functional dependencies. CORDS can be used as a data mining tool, producing dependency graphs that are of intrinsic interest. We focus primarily on the use of CORDS in query optimization. Specifically, CORDS recommends groups of columns on which to maintain certain simple joint statistics. These "column-group" statistics are then used by the optimizer to avoid naive selectivity estimates based on inappropriate independence assumptions. This approach, because of its simplicity and judicious use of sampling, is relatively easy to implement in existing commercial systems, has very low overhead, and scales well to the large numbers of columns and large table sizes found in real-world databases. Experiments with a prototype implementation show that the use of CORDS in query optimization can speed up query execution times by an order of magnitude. CORDS can be used in tandem with query feedback systems such as the LEO learning optimizer, leveraging the infrastructure of such systems to correct bad selectivity estimates and ameliorating the poor performance of feedback systems during slow learning phases.
Cited by 315 works. doi:10.1145/1007568.1007641
Authors
References
- An introduction to probability theory and its applications
- Mathematical Methods of Statistics.
- Categorical Data Analysis
- Measures of Association for Cross Classifications
- An Introduction to Probability Theory and Its Applications.
- Categorical Data Analysis
- The non-central chi2- and F-distributions and their applications.
- An Introduction to Probability Theory and Its Applications, Volume II
- Mining quantitative association rules in large relational tables
- Measures of Association for Cross Classifications*