Join predicate push-down optimizations

• US 20070219951A1
• Filed: 03/08/2007
• Published: 09/20/2007
• Est. Priority Date: 03/15/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Das, Dinesh, Ahmed, Rafi, Lee, Allison
• Granted Patent: US 7,945,562 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation

Abstract

Join predicate push down transformations push down a join predicate of an outer query into a view. Among the types of views for which join predicate push down is performed are a view with a GROUP BY or DISTINCT operator, an anti-joined or semi-joined view, and a view that contains one or more nested views. During optimization, join predicate push down may be used to generate many transformed queries for comparison. The number of query transformations performed for comparison is managed.

Claims

1. A computer-implemented method, comprising:

generating a transformed query based on a particular query, wherein said particular query includes;

an outer query;

a view within a FROM list of the outer query;

a join predicate that references;

a column of an outer table of the outer query, and

a column returned by the view;

wherein said view includes;

a GROUP BY operator that references a certain column upon which the column returned by the view is based, or

a DISTINCT operator that references a certain column upon which the column returned by view is based; and

wherein generating the transformed query includes pushing down the join predicate to create a pushed down join predicate that references the column of the outer table and a certain column returned by the view is based.

2. The computer-implemented method of claim 1, wherein the step of generating a transformed query includes removing the GROUP BY operator from the view.

3. The computer-implemented method of claim 1, wherein the step of generating a transformed query includes removing the DISTINCT operator from the view.

14. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

15. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

16. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

4. A computer-implemented method, comprising:

generating a transformed query based on a particular query, wherein said particular query includes;

an outer query;

a view within a FROM list of the outer query;

a join predicate that references;

a column of an outer table of the outer query, and

a column returned by the view;

wherein generating the transformed query includes pushing down the join predicate to create a pushed down join predicate that references the column of the outer table and a certain column returned by the view;

generating an estimated query execution cost for each of a set of candidate queries that includes said particular query and said transformed query; and

selecting as an optimized query for said particular query a candidate query of said candidate queries.

17. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

5. A computer-implemented method, comprising:

generating a transformed query based on a particular query, wherein said particular query includes;

an outer query;

a view within a FROM list of the outer query;

a certain predicate for an anti-join, said certain predicate referencing;

a column of an outer table of the outer query, and

a column returned by the view;

wherein generating the transformed query includes pushing down the certain predicate to create a pushed down join predicate that references the column of the outer table and a certain column returned by the view;

generating an estimated query execution cost for each of a set of candidate queries that includes said particular query and said transformed query; and

selecting as an optimized query for said particular query a candidate query of said candidate queries.

18. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

6. A computer-implemented method, comprising:

generating a transformed query based on a particular query, wherein said particular query includes;

an outer query;

a view within a FROM list of the outer query;

a certain predicate for a semi-join that references;

a column of an outer table of the outer query, and

a column returned by the view;

wherein generating the transformed query includes pushing down the certain predicate to create a pushed down join predicate that references the column of the outer table and a certain column returned by the view;

generating an estimated query execution cost for each of a set of candidate queries that includes said particular query and said transformed query; and

selecting as an optimized query for said particular query a candidate query of said candidate queries.

19. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

7. A computer-implemented method, comprising:

a database system generating a search space for optimizing a particular query, wherein said particular query includes;

an outer query;

a plurality of views in a FROM list of the outer query;

for each view of said plurality of views, a certain join predicate of the outer query that references;

a column of an outer table of the outer query, and

a column returned by said each view;

wherein the step of generating a search space includes generating a search space that includes one or more query transformations that each involve pushing down the respective certain join predicate into at least one view of said plurality of views, said search space including said particular query; and

selecting an optimized query from among the search space based on query execution costs estimated for the queries in said search space.

8. The computer-implemented method of claim 7, wherein the step of generating a search space includes

performing in an order for each view of said plurality of views, certain steps of:

generating a transformed query that pushes down the respective certain join predicate of said each view;

estimating a query execution cost for said the transformed query;

making a determination of whether the estimated query execution cost is lower than a previous estimated query execution cost; and

wherein said transformed query pushes down the respective certain join predicate of any view of said plurality of views for which a previous determination was made that the query execution is lower than a previous estimated query execution cost.

9. The computer-implemented method of claim 7, wherein generating a search space includes generating a search space that:

includes a query wherein, for each view of said plurality of views, the respective certain join predicate is not pushed down; and

for any query in the search space for which a certain join predicate of a particular view of the plurality of views is pushed in the particular view, includes a transformed query in which for each view of said plurality of views, the respective certain join predicate is pushed down into said each view if one or more criteria are satisfied.

10. The computer-implemented method of claim 7, wherein generating a search space includes generating a search space that includes a transformed query for every combination of join predicate push downs that can be performed with respect to said plurality of views.

11. The computer-implemented method of claim 7, wherein the step of generating a search space that includes one or more query transformations that each involve pushing down the respective certain join predicate into at least one view of said plurality of views includes generating a search space that includes one or more query transformations that push down a join predicate only if one or more criteria are satisfied, said one or more criteria including that said pushed down predicate open an index access path for a view of said plurality of views.

20. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

21. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

22. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

23. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

24. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

12. A computer-implemented method, comprising:

generating a search space for a particular query, wherein said particular query includes;

an outer query;

a first view within the FROM list of the outer query;

a first join predicate of the outer query that references;

a column of an outer table of the outer query, and

a column returned by said first view;

a second view within the FROM list of the first view;

a second join predicate of the second view that references a column returned by said first view;

generating a search space that includes one or more query transformations that each involve pushing down a join predicate of the outer query to the second view; and

selecting an optimized query from among the search space.

25. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

13. A computer-implemented method, comprising:

generating a transformed query by creating a view in the transformed query;

wherein said transformed query includes;

an outer query with a FROM list that includes said view; and

a join predicate of the outer query that references;

a column of an outer table of the outer query, and

a column returned by said view;

generating a second transformed query by performing steps that include pushing down the join predicate into the view to create a pushed down join predicate that references the column of the outer table and a certain column upon which the column returned by the view is based.

selecting an optimized query from among the search space.

26. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.