Automatic discovery and use of column correlations in tables

A computer implemented method for discovering correlations between columns in tables, the method comprising:

• identifying likely candidate tables that have potential for correlation;
• determining, from the likely candidate tables, correlated columns;
• determining the significance of correlation between the correlated columns;
• if the correlated columns are significantly correlated, then constructing a correlation table that includes records representing distinct combinations of values corresponding to the correlated columns.

A computer-readable medium carrying one or more sequences of instructions for discovering correlations between columns in one or more tables, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

• identifying a set of significantly correlated columns from one or more tables, wherein the step of identifying the set of significantly correlated columns comprises identifying a set of correlated columns;
• determining the significance of correlation between the correlated columns in the set of correlated columns;
• and
• creating a correlation table that includes records representing distinct combinations of values corresponding to the correlated columns in the set of significantly correlated columns.

A computer-readable medium carrying one or more sequences of instructions for discovering correlations between columns in tables, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

• identifying likely candidate tables that have potential for correlation;
• determining, from the likely candidate tables, correlated columns;
• determining the significance of correlation between the correlated columns;
• if the correlated columns are significantly correlated, then constructing a correlation table that includes records representing distinct combinations of values corresponding to the correlated columns.

A computer-readable medium carrying one or more sequences of instructions for determining whether a correlation between two columns is significant, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

• determining that a ratio of
• a number of distinct combinations of values in the correlated columns, from at least a portion of the different tables, over
• a product of the number of distinct values in each of the correlated columns, from the same portion of the different tables,
• is significantly less than one.

A computer apparatus comprising:

• a memory;
• and
• one or more processors coupled to the memory and configured to execute one or more sequence of instructions for discovering correlations between columns in one or more tables, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:
• identifying a set of significantly correlated columns from one or more tables, wherein the step of identifying the set of significantly correlated columns comprises
• identifying a set of correlated columns;
• determining the significance of correlation between the correlated columns in the set of correlated columns;
• and
• creating a correlation table that includes records representing distinct combinations of values corresponding to the correlated columns in the set of significantly correlated columns.

A computer apparatus comprising:

• a memory;
• and
• one or more processors coupled to the memory and configured to execute one or more sequence of instructions for partition pruning, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:
• creating a correlation table having records representing distinct combinations of values corresponding to a first column and a second column, wherein the first column is a subject of a predicate in the query and the second column is a partitioning key for a table;
• and
• based on the predicate on the first column, using the correlation table to prune partitions from the table.