Optimizing correlated queries using automatic summary tables

• US 20030088558A1
• Filed: 11/05/2002
• Published: 05/08/2003
• Est. Priority Date: 05/20/1999
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Sun, Yang, Pirahesh, Mir Hamid, Lapis, George, Cochrane, Roberta Jo, Zaharioudakis, Markos
• Granted Patent: US 7,167,853 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method, apparatus, and article of manufacture for optimizing database queries using an automatic summary table. A query is analyzed using matching and compensation tests between the query at least one correlated subquery within the query and the automatic summary table to determine whether expressions occurring in the query, but not in the automatic summary table, can be derived using the automatic summary table. If so, the query is rewritten so that the automatic summary table is used.

Claims

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;

(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 expressions occurring in the query, but not in the automatic summary table, can be derived using the automatic summary table;

(c) rewriting the query so that the automatic summary table is used.

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 analyzing step comprises the step of determining 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 query, correlated subquery and automatic summary table, until it reaches a top of the QGM for the automatic summary table.

4. The method of claim 3, 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.

5. The method of claim 4, 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.

6. The method of claim 4, 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.

7. The method of claim 6, 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.

8. The method of claim 4, 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.

9. 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;

(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 expressions occurring in the query, but not in the automatic summary table, can be derived using the automatic summary table;

(3) rewriting the query so that the automatic summary table is used.

10. The apparatus of claim 9, 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.

11. The apparatus of claim 9,wherein the logic for analyzing comprises logic for determining 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 query, correlated subquery and automatic summary table, until it reaches a top of the QGM for the automatic summary table.

12. The apparatus of claim 11, 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.

13. The apparatus of claim 12, 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.

14. The apparatus of claim 12, 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.

15. The apparatus of claim 14, 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.

16. The apparatus of claim 12, 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.

17. 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;

(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 expressions occurring in the query, but not in the automatic summary table, can be derived using the automatic summary table;

(c) rewriting the query so that the automatic summary table is used.

18. The article of manufacture of claim 17, 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.

19. The article of manufacture of claim 17, wherein the analyzing step comprises the step of determining 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 query, correlated subquery and automatic summary table, until it reaches a top of the QGM for the automatic summary table.

20. The article of manufacture of claim 19, 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.

21. The article of manufacture of claim 20, 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.

22. The article of manufacture of claim 20, 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.

23. The article of manufacture of claim 22, 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.

24. The article of manufacture of claim 20, 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.