Join predicate push-down optimizations

• US 7,945,562 B2
• Filed: 03/08/2007
• Issued: 05/17/2011
• Est. Priority Date: 03/15/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Lee, Allison, Das, Dinesh, Ahmed, Rafi
• Primary Examiner(s): PANNALA, SATHYANARAYA R
• Application Number:
  US11/716,190
• Publication Number:
  US 20070219951A1
• Time in Patent Office: 1,531 Days
• Field of Search: None
• US Class Current: 707/718
• 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-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform steps of:

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 in the WHERE clause of the outer query that references;

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

a returned column that is returned by the view and that is equivalent to an equivalent column in the SELECT clause of the view;

wherein said view includes;

a GROUP BY operator that references said equivalent column, or

a DISTINCT operator that references said equivalent column; and

wherein generating the transformed query includes pushing down the join predicate into said view, wherein pushing down the join predicate includes (1) removing the join predicate from the outer query and (2) creating, within said view, a new join predicate that references the outer table column of the outer table and said equivalent column.

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

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

4. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform steps of:

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 in the WHERE clause of the outer query that references;

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

a returned column that is returned by the view and that is equivalent to an equivalent column in the SELECT clause of the view;

wherein generating the transformed query includes pushing down the join predicate into said view, wherein pushing down the join predicate includes (1) removing the join predicate from the outer query and (2) creating, within said view, a new join predicate that references the outer table column of the outer table and said equivalent column;

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.

5. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform steps of:

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 in the WHERE clause of the outer query for an anti-join, said certain predicate referencing;

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

a returned column that is returned by the view and that is equivalent to an equivalent column in the SELECT clause of the view;

wherein generating the transformed query includes pushing down the certain predicate into said view, wherein pushing down the certain predicate includes (1) removing the certain predicate from the outer query and (2) creating, within said view, a new join predicate that references the outer table column of the outer table and said equivalent column;

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.

6. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform steps of:

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 in the WHERE clause of the outer query for an semi-join, said certain predicate referencing;

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

a returned column that is returned by the view and that is equivalent to an equivalent column in the SELECT clause of the view;

wherein generating the transformed query includes pushing down the certain predicate into said view, wherein pushing down the certain predicate includes (1) removing the certain predicate from the outer query and (2) creating, within said view, a new join predicate that references the outer table column of the outer table and said equivalent column;

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.

7. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform steps of:

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 in said plurality of views, a join predicate in the WHERE clause of the outer query, said join predicate referencing;

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

a returned column that is returned by the view and that is equivalent to an equivalent column in the SELECT clause of the view;

wherein the step of generating a search space includes generating a search space that includes said particular query and one or more query transformations that involve pushing down a join predicate into a respective view of said plurality of views, wherein pushing down the join predicate includes (1) removing the join predicate from the outer query and (2) creating, within said respective view, a new join predicate that references the outer table column of the outer table and the respective equivalent column; 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-readable storage medium 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 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 join predicate of any view of said one or more views for which a determination was made that the query execution is lower than a previous estimated query execution cost.

9. The computer-readable storage medium 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 one or more views.

10. The computer-readable storage medium of claim 7, wherein the step of generating a search space 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.

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

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 in the WHERE clause of the outer query, said first predicate referencing;

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

a first returned column that is returned by said first view and that is equivalent to a first equivalent column in the SELECT clause of the first view;

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

a second join predicate of the first view that references a second returned column that is returned by said second view and that is equivalent to a second equivalent column in the SELECT clause of the second 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 first join predicate into said second view, wherein pushing down the first join predicate includes (1) removing the first join predicate from the outer query and (2) creating, within said second view, a new join predicate that references the outer table column of the outer table and said second equivalent column; and

selecting an optimized query from among the search space.

12. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform steps of:

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;

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

a returned column that is returned by the view and that is equivalent to an equivalent column in the SELECT clause of the view;

generating a second transformed query by pushing down the join predicate into said view, wherein pushing down the join predicate includes (1) removing the join predicate from the outer query and (2) creating, within said view, a new join predicate that references the outer table column of the outer table and said equivalent column; and

selecting an optimized query from among the search space.