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

• US 5,995,957 A
• Filed: 02/28/1997
• Issued: 11/30/1999
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Min, Beavin, Thomas Abel, Iyer, Balakrishna Raghavendra, Shibamiya, Akira, Tie, Hong Sang
• Primary Examiner(s): Choules, Jack M.
• Application Number:
  US08/808,521
• Time in Patent Office: 1,005 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

The system, method, and program of this invention collects multi-column statistics, by a database management system, to reflect a relationship among multiple columns of a table in a relational database. These statistics are stored in the system catalog, and are used during query optimization to obtain an estimate of the number of qualifying rows when a query has predicates on multiple columns of a table.

A multi-column linear quantile statistic is collected by dividing the data of multiple columns into sub-ranges where each sub-range has approximately an even distribution of data, and determining a frequency and cardinality of each sub-range. A multi-column polygonal quantile statistic is collected by dividing the data of multiple columns into sub-spaces where each sub-space contains approximately the same number of tuples, and determining a frequency and cardinality of each sub-space.

The system catalog is accessed for the stored multi-column linear quantile statistic for a query having a single range predicate and at least one equal predicate to determine the selectivity value for the predicates of the query. The system catalog is accessed for the stored multi-column polygonal quantile statistic for a query having more than one range predicate. These statistics are used in various ways to determine the selectivity value for the predicates of the query.

Claims

1. 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 columns of a table; 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;

wherein the step of collecting at least one type of multi-column statistic further comprises collecting 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

determining a frequency and cardinality of each sub-range.

2. The method of claim 1 further comprising accessing the table for the first type of multi-column quantile statistics for the multiple columns for the query having a single range predicate and at least one equal predicate to determine the selectivity value for the predicates of the query.

3. The method of claim 2 further comprising determining the selectivity value as follows:

for predicates that are completely satisfied by one of the plurality of sub-ranges, the selectivity is the frequency;

for predicates that are partially satisfied by one of the sub-ranges, a final selectivity is equal to a selectivity of fully qualified sub-ranges plus a selectivity of partially qualified sub-ranges.

4. The method of claim 3 wherein the step of determining, for predicates that are partially satisfied by one of the sub-ranges, further comprises translating a boundary of a sub-range by concatenating a set of values of a lower boundary and concatenating a set of values of a higher boundary for the sub-range;

and using the concatenated values in the selectivity determination.

5. 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 columns of a table; 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;

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.

6. The method of claim 5 further comprising accessing the table for the second type of multi-column quantile statistics for the multiple columns for the query having a plurality of range predicates to determine the selectivity value for the predicates of the query.

7. The method of claim 6 wherein the step of determining the selectivity further comprises determining a final selectivity as being equal to a selectivity of fully qualified sub-spaces plus a selectivity of partially qualified sub-spaces.

8. The method of claim 7 wherein the selectivity of partially qualified sub-spaces is determined according to the following:

##EQU8## Where;

X1, X2 are the high and low bounds for the X-coordinate of the query

Y1, Y2 are the high and low bounds for the Y-coordinate of the query

Z1, Z2 are the high and low bounds for the Z-coordinate of the query

. . etc., for each coordinate (dimension) of the query

XA, XB are the high and low bounds for the X-coordinate of the quantile

YA, YB are the high and low bounds for the Y-coordinate of the quantile

ZA, ZB are the high and low bounds for the Z-coordinate of the quantile

. . etc., for each coordinate (dimension) of the quantile.

9. A database management system comprising:

means for collecting at least one type of multi-column statistic to reflect a relationship among multiple columns of a table; 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;

wherein the means for collecting at least one type of multi-column statistic further comprises means for collecting 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.

10. The system of claim 9 further comprising means for accessing the table for the first type of multi-column quantile statistics for the multiple columns for the query having a single range predicate and at least one equal predicate to determine the selectivity value for the predicates of the query.

11. The system of claim 10 further comprising means for determining the selectivity value as follows:

for predicates that are completely satisfied by one of the plurality of sub-ranges, the selectivity is the frequency;

for predicates that are partially satisfied by one of the sub-ranges, a final selectivity is equal to a selectivity of fully qualified sub-ranges plus a selectivity of partially qualified sub-ranges.

12. The system of claim 11 wherein the means for determining further comprises translating a boundary of a sub-range by concatenating a set of values of a lower boundary and concatenating a set of values of a higher boundary for the sub-range;

and using the concatenated values in the selectivity determination.

13. A database management system comprising:

means for collecting at least one type of multi-column statistic to reflect a relationship among multiple columns of a table; 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;

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.

14. The system of claim 13 further comprising means for accessing the table for the second type of multi-column quantile statistics for the multiple columns for the query having a plurality of range predicates to determine the selectivity value for the predicates of the query.

15. The system of claim 14 wherein the means for determining the selectivity further comprises means for determining a final selectivity as being equal to a selectivity of fully qualified sub-spaces plus a selectivity of partially qualified sub-spaces.

16. The system of claim 15 wherein the selectivity of partially qualified sub-spaces is determined according to the following:

##EQU9## Where;

X1, X2 are the high and low bounds for the X-coordinate of the query

Y1, Y2 are the high and low bounds for the Y-coordinate of the query

Z1, Z2 are the high and low bounds for the Z-coordinate of the query

. . etc., for each coordinate (dimension) of the query

XA, XB are the high and low bounds for the X-coordinate of the quantile

YA, YB are the high and low bounds for the Y-coordinate of the quantile

ZA, ZB are the high and low bounds for the Z-coordinate of the quantile

. . etc., for each coordinate (dimension) of the quantile.

17. 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 columns of a table; 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;

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 causing a determination of a frequency and cardinality of each sub-range.

18. The program product of claim 17 further comprising means for causing an access to the table for the first type of multi-column quantile statistics for the multiple columns for the query having a single range predicate and at least one equal predicate to cause a determination of the selectivity value for the predicates of the query.

19. The program product of claim 18 further comprising means for causing a determination of the selectivity value as follows:

for predicates that are completely satisfied by one of the plurality of sub-ranges, the selectivity is the frequency;

for predicates that are partially satisfied by one of the sub-ranges, a final selectivity is equal to a selectivity of fully qualified sub-ranges plus a selectivity of partially qualified sub-ranges.

20. The program product of claim 19 wherein the means for causing a determination further comprises means for causing a translation of a boundary of a sub-range by concatenating a set of values of a lower boundary and concatenating a set of values of a higher boundary for the sub-range;

and means for using the concatenated values in the selectivity determination.

21. 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 columns of a table; 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;

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.

22. The program product of claim 21 further comprising means for causing an access to the table for the second type of multi-column quantile statistics for the multiple columns for the query having a plurality of range predicates;

and means for causing a determination of the selectivity value for the predicates of the query.

23. The system of claim 22 wherein the means for causing the determination of the selectivity value further comprises means for causing a determination of a final selectivity as being equal to a selectivity of fully qualified sub-spaces plus a selectivity of partially qualified sub-spaces.