Query optimization through the use of multi-column statistics to avoid the problems of non-indexed column correlation

A method for use in a database management system for optimizing a query, the method comprising:

• collecting at least one type of multi-column statistic to reflect a relationship among multiple selected non-indexed columns of a table, wherein the step of collecting at least one type of multi-column statistic further comprises collecting a second type of multi-column quantile statistics for indicating a number of rows between two given sets of values by dividing the data into a plurality of sub-spaces, each sub-space containing approximately a same number of tuples, and determining a frequency and cardinality of each sub-space;
• and
• storing the at least one type of multi-column statistic in a table for subsequent use in determining a selectivity value (a number of qualified rows) for predicates in the query, wherein the selectivity value is used in optimizing execution of the query.

A database management system comprising:

• means for collecting at least one type of multi-column statistic to reflect a relationship among multiple non-indexed columns of a table, wherein the means for collecting at least one type of multi-column statistic further comprises means for collecting a first type of multi-column quantide statistics for indicating a number of rows between two given values by dividing the data into a plurality of sub-ranges, each sub-range having an even distribution of data, and means for determining a frequency and cardinality of each sub-range;
• and
• means for storing the at least one type of multi-column statistic in a table for subsequent use in determining a selectivity value (a number of qualified rows) for predicates in the query, wherein the selectivity value is used in optimizing execution of the query.

A database management system comprising:

• means for collecting at least one type of multi-column statistic to reflect a relationship among multiple non-indexed columns of a table, wherein the means for collecting at least one type of multi-column statistic further comprises means for collecting a second type of multi-column quantile statistics for indicating a number of rows between two given sets of values by dividing the data into a plurality of sub-spaces, each sub-space containing approximately a same number of tuples, and means for determining a frequency and cardinality of each sub-space;
• and
• means for storing the at least one type of multi-column statistic in a table for subsequent use in determining a selectivity value (a number of qualified rows) for predicates in the query, wherein the selectivity value is used in optimizing execution of the query.

Computer programming code residing on at least one computer usable medium (i.e., a program product) for use in a database management system, the program product comprising:

• means for causing a collection of at least one type of multi-column statistic to reflect a relationship among multiple non-indexed columns of a table, wherein the means for causing a collection of at least one type of multi-column statistic further comprises means for causing a collection of a first type of multi-column quantile statistics for indicating a number of rows between two given values by dividing the data into a plurality of sub-ranges, each sub-range having an even distribution of data, and means for determining a frequency and cardinality of each sub-range;
• and
• means for causing a storing of the at least one type of multi-column statistic in a table for subsequent use in determining a selectivity value (a number of qualified rows) for predicates in the query, wherein the selectivity value is used in optimizing execution of the query.

Computer programming code residing on at least one computer usable medium (i.e., a program product) for use in a database management system, the program product comprising:

• means for causing a collection of at least one type of multi-column statistic to reflect a relationship among multiple non-indexed columns of a table, wherein the means for causing a collection of at least one type of multi-column statistic further comprises means for causing a collection of a second type of multi-column quantile statistic for indicating a number of rows between two given sets of values by dividing the data into a plurality of sub-spaces, each sub-space containing approximately a same number of tuples, and means for causing a determination of a frequency and cardinality of each sub-space;
• and
• means for causing a storing of the at least one type of multi-column statistic in a table for subsequent use in determining a selectivity value (a number of qualified rows) for predicates in the query, wherein the selectivity value is used in optimizing execution of the query.