Cost-based subquery correlation and decorrelation

• US 20060287979A1
• Filed: 06/17/2005
• Published: 12/21/2006
• Est. Priority Date: 06/17/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lin, Fen-Ling, Zeng, Ying, Tsuji, Yoichi, Beavin, Thomas Abel, Chen, Yao-Ching Stephen, Xia, Li, Cai, Mengchu, Cheng, Hsiuying Yen, Liu, Irene Ching-Hua, Ni, Demai, Mukai, Jerry
• Granted Patent: US 7,376,646 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Techniques are provided that determine that a query includes at least one subquery that may be correlated or decorrelated. An internal representation of the query that represents the subquery in both correlated and decorrelated form is generated, wherein the internal representation includes at least one virtual table.

Claims

1. A method for processing a query, comprising:

determining that the query includes at least one subquery that may be correlated or decorrelated; and

generating an internal representation of the query that represents the subquery in both correlated and decorrelated form, wherein the internal representation includes at least one virtual table.

2. The method of claim 1, further comprising:

determining correlated costs for the subquery in correlated form; and

determining non-correlated costs for the subquery in decorrelated form.

3. The method of claim 2, further comprising:

selecting an access path associated with a form having a lowest cost.

4. The method of claim 1, further comprising:

setting an indicator to indicate that at least one of correlated or non-correlated costs are to be determined.

5. The method of claim 1, wherein generating the internal representation further comprises:

internally representing each section of the query in an internal structure, wherein each section comprises a query block and wherein the internal structure comprises a query block array.

6. The method of claim 5, further comprising:

for each query block, internally representing each table to be accessed within that query block; and

for each query block, internally representing each predicate to be applied within that query block.

7. The method of claim 1, wherein the internal representation represents the query using one or more query blocks and further comprising:

selecting a bottom-most query block;

determining correlated costs of the query block in response to determining that correlated costs are to be determined; and

determining non-correlated costs of the query block in response to determining that non-correlated costs are to be determined.

8. The method of claim 1, wherein the query includes an outer table and wherein the internal representation includes a join of the virtual table and the outer table.

9. The method of claim 8, wherein determining non-correlated costs further comprises:

joining the virtual table in decorrelated form to the outer table; and

joining the outer table to the virtual table in decorrelated form.

10. The method of claim 8, wherein determining correlated costs further comprises:

joining the outer table to the virtual table in correlated form.

11. An article of manufacture for processing a query, wherein the article of manufacture comprises a computer readable medium storing instructions, and wherein the article of manufacture is operable to:

determine that the query includes at least one subquery that may be correlated or decorrelated; and

generate an internal representation of the query that represents the subquery in both correlated and decorrelated form, wherein the internal representation includes at least one virtual table.

12. The article of manufacture of claim 11, wherein the article of manufacture is operable to:

determine correlated costs for the subquery in correlated form; and

determine non-correlated costs for the subquery in decorrelated form.

13. The article of manufacture of claim 12, wherein the article of manufacture is operable to:

select an access path associated with a form having a lowest cost.

14. The article of manufacture of claim 11, wherein the article of manufacture is operable to:

set an indicator to indicate that at least one of correlated or non-correlated costs are to be determined.

15. The article of manufacture of claim 11, wherein the article of manufacture is operable to:

internally represent each section of the query in an internal structure, wherein each section comprises a query block and wherein the internal structure comprises a query block array.

16. The article of manufacture of claim 15, wherein the article of manufacture is operable to:

for each query block, internally represent each table to be accessed within that query block; and

for each query block, internally represent each predicate to be applied within that query block.

17. The article of manufacture of claim 11, wherein the internal representation represents the query using one or more query blocks and wherein the article of manufacture is operable to:

select a bottom-most query block;

determine correlated costs of the query block in response to determining that correlated costs are to be determined; and

determine non-correlated costs of the query block in response to determining that non-correlated costs are to be determined.

18. The article of manufacture of claim 11, wherein the query includes an outer table and wherein the internal representation includes a join of the virtual table and the outer table.

19. The article of manufacture of claim 18, wherein the article of manufacture is operable to:

join the virtual table in decorrelated form to the outer table; and

join the outer table to the virtual table in decorrelated form.

20. The article of manufacture of claim 18, wherein the article of manufacture is operable to:

join the outer table to the virtual table in correlated form.

21. A system for processing a query, comprising:

logic capable of causing operations to be performed, the operations comprising;

determining that the query includes at least one subquery that may be correlated or decorrelated; and

generating an internal representation of the query that represents the subquery in both correlated and decorrelated form, wherein the internal representation includes at least one virtual table.

22. The system of claim 21, wherein the operations further comprise:

determining correlated costs for the subquery in correlated form; and

determining non-correlated costs for the subquery in decorrelated form.

23. The system of claim 22, wherein the operations further comprise:

selecting an access path associated with a form having a lowest cost.

24. The system of claim 21, wherein the operations further comprise:

setting an indicator to indicate that at least one of correlated or non-correlated costs are to be determined.

25. The system of claim 21, wherein the operations for generating the internal representation further comprise:

internally representing each section of the query in an internal structure, wherein each section comprises a query block and wherein the internal structure comprises a query block array.

26. The system of claim 25, wherein the operations further comprise:

for each query block, internally representing each table to be accessed within that query block; and

for each query block, internally representing each predicate to be applied within that query block.

27. The system of claim 21, wherein the internal representation represents the query using one or more query blocks and wherein the operations further comprise:

selecting a bottom-most query block;

determining correlated costs of the query block in response to determining that correlated costs are to be determined; and

determining non-correlated costs of the query block in response to determining that non-correlated costs are to be determined.

28. The system of claim 21, wherein the query includes an outer table and wherein the internal representation includes a join of the virtual table and the outer table.

29. The system of claim 28, wherein the operations for determining non-correlated costs further comprise:

joining the virtual table in decorrelated form to the outer table; and

joining the outer table to the virtual table in decorrelated form.

30. The system of claim 28, wherein the operations for determining correlated costs further comprise:

joining the outer table to the virtual table in correlated form.