International Business Machines Corporation

Ihab F Ilyas

Guy Maring Lohman

Eileen Tien Lin

Jun Rao

Dengfeng Gao

Peter Haas

Volker Gerhard Markl

Paul Geoffrey Brown

A compilation time estimator provides a quantified estimate of the optimizer compilation time for a given query optimizer. The estimator automates the optimizer to choose the right level of optimization in commercial database systems. The estimator reuses an optimizer's join enumerator to obtain actual number of joins, but bypasses plan generation to save estimation overhead, and maintains a small number of interesting physical properties to estimate the number of plans by using a linear regression model. The estimator uses the number of generated plans to estimate query compilation time.

Estimating the compilation time of a query optimizer

A system and method of discovering dependencies between relational database column pairs and application of discoveries to query optimization is provided. For each candidate column pair remaining after simultaneously generating column pairs, pruning pairs not satisfying specified heuristic constraints, and eliminating pairs with trivial instances of correlation, a random sample of data values is collected. A candidate column pair is tested for the existence of a soft functional dependency (FD), and if a dependency is not found, statistically tested for correlation using a robust chi-squared statistic. Column pairs for which either a soft FD or a statistical correlation exists are prioritized for recommendation to a query optimizer, based on any of: strength of dependency, degree of correlation, or adjustment factor; statistics for recommended columns pairs are tracked to improve selectivity estimates. Additionally, a dependency graph representing correlations and dependencies as edges and column pairs as nodes is provided.

Detecting correlation from data

Growing community of inventors

West Lafayette, IN, United States of America

Ihab F Ilyas