Matching and compensation tests for optimizing correlated subqueries within query using automatic summary tables

1. A method of optimizing a query in a computer system, the query being performed by the computer system to retrieve data from a database stored on the computer system, the method comprising the steps of:

(a) generating an automatic summary table for use in optimizing the query;

(b) analyzing the query using matching and compensation tests between the query, at least one correlated subquery within the query and the automatic summary table to determine whether there is a match between the query, the correlated subquery and the automatic summary table using a bottom-up traversal of boxes in query graph models (QGMs) for the query, correlated subquery and automatic summary table that tries to establish matches between the query, correlated subquery and automatic summary table, until it reaches a top of the QGM for the automatic summary table, so that expressions occurring in the query including the correlated subquery, but not in the automatic summary table, can be derived using the automatic summary table; and

(c) rewriting the query so that the automatic summary table is used when there is a match, wherein the rewritten query is performed by the computer system to retrieve data from the database.

2. The method of claim 1 , wherein the correlated subquery comprises an inner query block of the query that references one or more columns that appear in an outer query block of the query.

3. The method of claim 1 , wherein the determining step further comprises the steps of:

performing a navigator function to identify candidate subsumee and subsumer pairs from the QGMs for the query, correlated subquery and automatic summary table in an order such that the bottom-up traversal of the QGMs for the query, correlated subquery and automatic summary table is satisfied; and

performing a match function that takes as input the candidate subsumee and subsumer pair from the QGMs for the query, correlated subquery and automatic summary table, and returns information on whether the subsumee matches with the subsumer.

4. The method of claim 3 , wherein the navigator function guarantees that before an attempt is made to match a candidate subsumee and subsumer pair, all children of the pair have been matched with each other, and the sources of any correlated input columns that are referenced in the subsumee have also been matched with all of their candidate subsumers.

5. The method of claim 3 , wherein the match function maps a reference by the correlated subquery to a column in the outer query block to an equivalent expression in the automatic summary table, using any one of the available matches of a source of the correlated column.

6. The method of claim 5 , wherein the match function records which match was used, and at an appropriate later stage, detects whether the match used was a correct match, and if not, backtracks and tries another match.

7. The method of claim 3 , wherein the match function performs regrouping when it pulls up a predicate with correlated and constant columns only though a GROUP-BY subsumer that does not have any grouping columns.

8. A computer-implemented apparatus for optimizing a query, comprising:

(a) a computer system;

(b) logic, performed by the computer system, for

(1) generating an automatic summary table for use in optimizing the query;

(2) analyzing the query using matching and compensation tests between the query, at least one correlated subquery within the query and the automatic summary table to determine whether there is a match between the query, the correlated subquery and the automatic summary table using a bottom-up traversal of boxes in query graph models (QGMs) for the query, correlated subquery and automatic summary table that tries to establish matches between the query, correlated subquery and automatic summary table, until it reaches a top of the QGM for the automatic summary table, so that expressions occurring in the query including the correlated subquery, but not in the automatic summary table, can be derived using the automatic summary table; and

(3) rewriting the query so that the automatic summary table is used when there is a match, wherein the rewritten query is performed by the computer system to retrieve data from the database.

9. The apparatus of claim 8 , wherein the correlated subquery comprises an inner query block of the query that references one or more columns that appear in an outer query block of the query.

10. The apparatus of claim 8 , wherein the logic for determining further comprises logic for:

performing a navigator function to identify candidate subsumee and subsumer pairs from the QGMs for the query, correlated subquery and automatic summary table in an order such that the bottom-up traversal of the QGMs for the query, correlated subquery and automatic summary table is satisfied; and

performing a match function that takes as input the candidate subsumee and subsumer pair from the QGMs for the query, correlated subquery and automatic summary table, and returns information on whether the subsumee matches with the subsumer.

11. The apparatus of claim 10 , wherein the navigator function guarantees that before an attempt is made to match a candidate subsumee and subsumer pair, all children of the pair have been matched with each other, and the sources of any correlated input columns that are referenced in the subsumee have also been matched with all of their candidate subsumers.

12. The apparatus of claim 10 , wherein the match function maps a reference by the correlated subquery to a column in the outer query block to an equivalent expression in the automatic summary table, using any one of the available matches of a source of the correlated column.

13. The apparatus of claim 12 , wherein the match function records which match was used, and at an appropriate later stage, detects whether the match used was a correct match, and if not, backtracks and tries another match.

14. The apparatus of claim 10 , wherein the match function performs regrouping when it pulls up a predicate with correlated and constant columns only though a GROUP-BY subsumer that does not have any grouping columns.

15. An article of manufacture embodying logic for performing a method for optimizing a query, the query being performed by a computer system to retrieve data from a database stored in a data storage device coupled to the computer system, the method comprising the steps of:

(a) generating an automatic summary table for use in optimizing the query;

(b) analyzing the query using matching and compensation tests between the query, at least one correlated subquery within the query and the automatic summary table to determine whether there is a match between the query, the correlated subquery and the automatic summary table, so that expressions occurring in the query including the correlated subquery, but not in the automatic summary table, can be derived using the automatic summary table using a bottom-up traversal of boxes in query graph models (QGMs) for the query, correlated subquery and automatic summary table that tries to establish matches between the query, correlated subquery and automatic summary table, until it reaches a top of the QGM for the automatic summary table; and

(c) rewriting the query so that the automatic summary table is used when there is a match, wherein the rewritten query is performed by the computer system to retrieve data from the database.

16. The article of manufacture of claim 15 , wherein the correlated subquery comprises an inner query block of the query that references one or more columns that appear in an outer query block of the query.

17. The article of manufacture of claim 15 , wherein the determining step further comprises the steps of:

performing a navigator function to identify candidate subsumee and subsumer pairs from the QGMs for the query, correlated subquery and automatic summary table in an order such that the bottom-up traversal of the QGMs for the query, correlated subquery and automatic summary table is satisfied; and

performing a match function that takes as input the candidate subsumee and subsumer pair from the QGMs for the query, correlated subquery and automatic summary table, and returns information on whether the subsumee matches with the subsumer.

18. The article of manufacture of claim 17 , wherein the navigator function guarantees that before an attempt is made to match a candidate subsumee and subsumer pair, all children of the pair have been matched with each other, and the sources of any correlated input columns that are referenced in the subsumee have also been matched with all of their candidate subsumers.

19. The article of manufacture of claim 17 , wherein the match function maps a reference by the correlated subquery to a column in the outer query block to an equivalent expression in the automatic summary table, using any one of the available matches of a source of the correlated column.

20. The article of manufacture of claim 19 , wherein the match function records which match was used, and at an appropriate later stage, detects whether the match used was a correct match, and if not, backtracks and tries another match.

21. The article of manufacture of claim 17 , wherein the match function performs regrouping when it pulls up a predicate with correlated and constant columns only though a GROUP-BY subsumer that does not have any grouping columns.