Join factorization of union/union all queries

• US 7,644,062 B2
• Filed: 03/08/2007
• Issued: 01/05/2010
• Est. Priority Date: 03/15/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Su, Hong, Zait, Mohamed, Ahmed, Rafi, Lee, Allison, Cruanes, Thierry
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Nguyen; Merilyn P
• Application Number:
  US11/716,010
• Publication Number:
  US 20070219969A1
• Time in Patent Office: 1,034 Days
• Field of Search: 707 1- 4, 707/100, 707/101, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

Under a type of query transformation referred to herein as join factorization, the branches of an UNION/UNION ALL query that join a common table are combined to reduce accesses to the common table. The transformation can be expressed as (T1 join T2) union all (T1 join T3)=T1 join (T2 union all T3), where T1, T2 and T3 are three tables. A given query may be rewritten in many alternate ways using join factorization. Evaluating each alternative can be expensive. Therefore, the alternatives are generated and evaluated in a way that minimizes the cost of evaluating the alternatives.

Claims

1. A computer implemented method, comprising:

transforming a base query to generate a transformed query;

wherein the base query includes a union between each base branch of a plurality of base branches;

wherein each of two or more base branches of said plurality of base branches joins a set of tables;

wherein the sets of tables of the two or more base branches of the plurality of base branches include a common table set shared by all the sets of tables, said common table set including a common table;

wherein each of the two or more base branches of the plurality of base branches include a respective set of tables that does not include said common table set;

wherein the step of transforming the base query includes replacing the plurality of base branches with a first group branch that joins the common table and an inline view, the inline view comprising a union between a plurality of respective branches, wherein the plurality of respective branches includes, for each base branch of said plurality of base branches, a FROM list that;

references the respective set of tables, and

does not reference the common table; and

wherein the method is performed by one or more computing devices.

2. The method of claim 1,

wherein each base branch of said plurality of base branches includes a respective join condition based on a particular column of said common table and a particular join condition operator;

wherein the first group branch includes a join condition based on the join condition operator, a column of the inline view, and the column of the common table; and

wherein each branch of said plurality of respective branches excludes the respective join condition.

3. The method of claim 1,

wherein each base branch of said plurality of base branches includes a respective join condition based on a particular column of said common table and a particular join condition operator;

and

wherein each respective branch of said plurality of respective branches includes said respective join condition.

4. The method of claim 1, wherein the common table set includes at least one other common table.

5. The method of claim 4, wherein the first group branch joins the common table, inline view, and the at least one other common table.

6. The method of claim 1, wherein:

the base query includes a union between a set of base branches that include said plurality of base branches and at least another branch; and

said transformed query includes said another branch.

7. The method of claim 1, wherein:

the base query includes a union between a set of base branches that include said plurality of base branches and a second plurality of base branches;

each base branch of said second plurality of base branches joins a set of tables;

the sets of tables of the second plurality of base branches include a second common table; and

the step of transforming the base query includes replacing the second plurality of base branches with a second group branch that joins the second common table and second inline view.

8. The method of claim 7, wherein at least one branch of the plurality of base branches joins the second common table.

9. The method of claim 1, wherein the plurality of base branches are contained with a query block within the base query.

10. The method of claim 1, wherein the base query contains a second plurality of branches within the union and the transformed query contains the same second plurality of branches.

11. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, cause to perform:

transforming a base query to generate a transformed query;

wherein the base query includes a union between each base branch of a plurality of base branches;

wherein each of two or more base branches of said plurality of base branches joins a set of tables;

wherein the sets of tables of the two or more base branches of the plurality of base branches include a common table set shared by all the sets of tables, said common table set including a common table;

wherein each of the two or more base branches of the plurality of base branches include a respective set of tables that does not include said common table set;

wherein the step of transforming the base query includes replacing the plurality of base branches with a first group branch that joins the common table and an inline view, the inline view comprising a union between a plurality of respective branches, wherein the plurality of respective branches includes, for each base branch of said plurality of base branches, a FROM list that;

references the respective set of tables, and

does not reference the common table.

12. The computer-readable storage medium of claim 11, wherein:

each base branch of said plurality of base branches includes a respective join condition based on a particular column of said common table and a particular join condition operator;

the first group branch includes a join condition based on the join condition operator, a column of the inline view, and the column of the common table; and

each branch of said plurality of respective branches excludes the respective join condition.

13. The computer-readable storage medium of claim 11, wherein:

each base branch of said plurality of base branches includes a respective join condition based on a particular column of said common table and a particular join condition operator; and

each respective branch of said plurality of respective branches includes said respective join condition.

14. The computer-readable storage medium of claim 11, wherein the common table set includes at least one other common table.

15. The computer-readable storage medium of claim 14, wherein the first group branch joins the common table, inline view, and the at least one other common table.

16. The computer-readable storage medium of claim 11, wherein:

the base query includes a union between a set of base branches that include said plurality of base branches and at least another branch; and

said transformed query includes said another branch.

17. The computer-readable storage medium of claim 11, wherein:

the base query includes a union between a set of base branches that include said plurality of base branches and a second plurality of base branches;

each base branch of said second plurality of base branches joins a set of tables;

the sets of tables of the second plurality of base branches includes a second common table; and

the step of transforming the base query includes replacing the second plurality of base branches with a second group branch that joins the second common table and second inline view.

18. The computer-readable storage medium of claim 17, wherein at least one branch of the plurality of base branches joins the second common table.

19. The computer-readable storage medium of claim 11, wherein the plurality of base branches are contained with a query block within the base query.

20. The computer-readable storage medium of claim 11, wherein the base query contains a second plurality of branches within the union and the transformed query contains the same second plurality of branches.