Methods are provided for automatically discovering correlations between values in columns of tables. A set of significantly correlated columns is identified by identifying correlated columns, and by determining the significance of the correlation between the correlated columns from one or more tables. If the correlated columns are considered significantly correlated, a correlation table is constructed that includes records representing distinct combinations of values corresponding to the correlated columns. Embodiments include methods for identifying correlated columns, for determining the significance of the correlation between the correlated columns, and for using the resultant correlation table to enhance performance of a query execution process. One particular embodiment provides for using a correlation table for partition pruning a partitioned table, with respect to a query execution plan.