Multi-tiered query processing techniques for minus and intersect operators

• US 20070073643A1
• Filed: 09/27/2005
• Published: 03/29/2007
• Est. Priority Date: 09/27/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ahmed, Rafi, Ghosh, Bhaskar, Baer, Hermann
• Granted Patent: US 7,814,091 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

Various techniques are described for processing database commands that include MINUS and/or INTERSECT operators. The queries containing the MINUS and/or INTERSECT operators are transformed to create a plurality of transformed queries. Each of the transformed queries produces the same result as the original query, but does not include the MINUS and/or INTERSECT operator. To achieve the same result set as the original query, the transformed queries employ equijoins, antijoins, and/or semijoins, and duplicate elimination operations. Costs are estimated for each of the various transformed queries. Based on the cost estimates, one of the transformed queries is selected as the query that is to be executed to perform the operations specified in the original query.

Claims

1. A method comprising performing a machine-executed operation involving instructions, wherein the machine-executed operation is at least one of:

A) sending said instructions over transmission media;

B) receiving said instructions over transmission media;

C) storing said instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein said instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of;

receiving a query that includes a particular operator, wherein the particular operator is one of MINUS and INTERSECT;

generating a set of one or more transformed queries that produce the same result as said query but do not include said particular operator;

generating cost estimates for the transformed queries in said set of transformed queries; and

selecting from said set of transformed queries a particular transformed query to execute based, at least in part, on the cost estimates.

2. The method of claim 1 wherein:

the particular operator is INTERSECT; and

the step of generating a set of one or more transformed queries includes generating a transformed query in which said operator is replaced with a semi-join operator.

3. The method of claim 1 wherein:

the particular operator is INTERSECT; and

the step of generating a set of one or more transformed queries includes generating a transformed query in which said operator is replaced with an equi-join operator.

4. The method of claim 1 wherein:

the step of generating a set of one or more transformed queries includes generating a first transformed query associated with a first execution plan and a second transformed query associated with a second execution plan; and

the first execution plan differs from the second execution plan relative to where duplicate elimination is performed.

5. The method of claim 1 wherein:

the particular operator is INTERSECT operator;

the query specifies a left-hand source and a right-hand source for said INTERSECT operator; and

the set of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is only performed after an equijoin operation between the left-hand source and the right-hand source.

6. The method of claim 1 wherein:

the particular operator is INTERSECT operator;

the query specifies a left-hand source and a right-hand source for said INTERSECT operator; and

the set of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is only performed on the left-hand source prior to a semi-join between the left-hand source and the right-hand source.

7. The method of claim 1 wherein:

the particular operator is INTERSECT operator;

the query specifies a left-hand source and a right-hand source for said INTERSECT operator; and

the set of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is performed on the right-hand source prior to an equijoin between the left-hand source and the right-hand source, and duplicate elimination is performed on a result set produced by the equijoin operation.

8. The method of claim 1 wherein:

the particular operator is the INTERSECT operator;

the query specifies a left-hand source and a right-hand source for said INTERSECT operator; and

the set of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is performed on both the left-hand source and the right-hand source prior to an equijoin between the left-hand source and the right-hand source.

9. The method of claim 1 wherein:

the particular operator is MINUS; and

the step of generating a set of one or more transformed queries includes generating a transformed query in which said operator is replaced with an anti-join operator.

10. The method of claim 1 wherein:

the particular operator is the MINUS operator;

the query specifies a left-hand source and a right-hand source for said MINUS operator; and

the set of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is performed only after an anti-join is performed between the left-hand source and the right-hand source.

11. The method of claim 1 wherein:

the particular operator is the MINUS operator;

the query specifies a left-hand source and a right-hand source for said MINUS operator; and

the set of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is performed on the left-hand source before an anti-join is performed between the left-hand source and the right-hand source.

12. The method of claim 1 wherein:

the particular operator is the MINUS operator;

the query specifies a left-hand source and a right-hand source for said MINUS operator; and

the set of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is performed on the right-hand source before an anti-join is performed between the left-hand source and the right-hand source, and duplicate elimination is performed on a result set produced by said anti-join.

13. The method of claim 1 wherein:

the particular operator is the MINUS operator;

the query specifies a left-hand source and a right-hand source for said MINUS operator; and

the set of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is performed on the right-hand source before an anti-join is performed between the left-hand source and the right-hand source, and duplicate elimination is performed on a the left-hand source before an anti-join is performed between the left-hand source and the right-hand source.

14. The method of claim 1 wherein the query contains non-uniform set operators.