Multi-tiered query processing techniques for minus and intersect operators

• US 7,814,091 B2
• Filed: 09/27/2005
• Issued: 10/12/2010
• Est. Priority Date: 09/27/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Baer, Hermann, Ahmed, Rafi, Ghosh, Bhaskar
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): Jami; Hares
• Application Number:
  US11/237,040
• Publication Number:
  US 20070073643A1
• Time in Patent Office: 1,841 Days
• Field of Search: 707/3, 707/705, 707711-719, 707/999.1, 7079993-9996
• US Class Current: 707/713
• 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 machine-executed method comprising the steps of:

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

generating a plurality of transformed queries, wherein each query of said plurality of transformed queries is generated by rewriting the particular query using a different combination of one or more transformations, and wherein each query of said plurality of transformed queries, if executed, produces a same result as said particular query but does not include said particular operator;

wherein each of the transformed queries comprises a different sequence of operators, and wherein at least one of the operators in each of the different sequences of operators eliminates duplicate values;

generating cost estimates for the transformed queries in said plurality of transformed queries;

comparing the cost estimate for one of the transformed queries to the cost estimate for another of the transformed queries; and

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

wherein each of said steps of said method is performed by one or more computing devices.

2. The method of claim 1 wherein:

the particular operator is INTERSECT; and

the step of generating a plurality of transformed queries includes generating a transformed query in which said particular operator is removed from said particular query, and in which said same result is produced with a semi-join operator.

3. The method of claim 1 wherein:

the particular operator is INTERSECT; and

the step of generating a plurality of transformed queries includes generating a transformed query in which said particular operator is removed from said particular query, and in which said same result is produced with an equi-join operator.

4. The method of claim 1 wherein:

the step of generating a plurality of 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 particular query specifies a left-hand source and a right-hand source for said INTERSECT operator; and

the plurality 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 particular query specifies a left-hand source and a right-hand source for said INTERSECT operator; and

the plurality 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 particular query specifies a left-hand source and a right-hand source for said INTERSECT operator; and

the plurality 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 particular query specifies a left-hand source and a right-hand source for said INTERSECT operator; and

the plurality 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.

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

9. A machine-executed method comprising the steps of:

receiving a particular query that includes a MINUS operator;

generating a plurality of transformed queries, wherein each query of said plurality of transformed queries, if executed, produces a same result as said query but does not include said MINUS operator;

generating cost estimates for the transformed queries in said plurality of transformed queries;

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

wherein each of said steps of said method is performed by one or more computing devices; and

wherein the step of generating a plurality of transformed queries includes generating a transformed query in which said particular operator is removed from said particular query, and in which said same result is produced with an anti-join operator.

10. The method of claim 9 wherein:

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

the plurality 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 9 wherein:

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

the plurality 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 9 wherein:

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

the plurality 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 9 wherein:

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

the plurality 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.

15. A non-transitory machine-readable storage medium carrying one or more sequence of instructions which, when executed by one or more processors, causes the one or more processor to perform:

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

generating a plurality of transformed queries, wherein each query of said plurality of transformed queries is generated by rewriting the particular query using a different combination of one or more transformations, and wherein each query of said plurality of transformed queries, if executed, produces a same result as said particular query but does not include said particular operator;

wherein each of the transformed queries comprises a different sequence of operators, and wherein at least one of the operators in each of the different sequences of operators eliminates duplicate values;

generating cost estimates for the transformed queries in said plurality of transformed queries;

comparing the cost estimate for one of the transformed queries to the cost estimate for another of the transformed queries; and

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

16. The machine-readable storage medium of claim 15, wherein:

the particular operator is INTERSECT; and

the generating a plurality of transformed queries includes generating a transformed query in which said particular operator is removed from said particular query, and in which said same result is produced with a semi-join operator.

17. The machine-readable storage medium of claim 15, wherein:

the particular operator is INTERSECT; and

the generating a plurality of transformed queries includes generating a transformed query in which said particular operator is removed from said particular query, and in which said same result is produced with an equi-join operator.

18. The machine-readable storage medium of claim 15, wherein:

the generating a plurality of 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.

19. The machine-readable storage medium of claim 15, wherein:

the particular operator is INTERSECT operator;

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

the plurality 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.

20. The machine-readable storage medium of claim 15, wherein:

the particular operator is INTERSECT operator;

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

the plurality 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.

21. The machine-readable storage medium of claim 15, wherein:

the particular operator is INTERSECT operator;

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

the plurality 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.

22. The machine-readable storage medium of claim 15, wherein:

the particular operator is the INTERSECT operator;

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

the plurality 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.

28. The machine-readable storage medium of claim 15, wherein:

wherein the particular query contains non-uniform set operators.

23. A non-transitory machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform:

receiving a particular query that includes a MINUS operator;

generating a plurality of transformed queries, wherein each query of said plurality of transformed queries, if executed, produces a same result as said particular query but does not include said MINUS operator;

generating cost estimates for the transformed queries in said plurality of transformed queries;

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

wherein each of said steps of said method is performed by one or more computing devices; and

wherein the step of generating a plurality of transformed queries includes generating a transformed query in which said particular operator is removed from said particular query, and in which said same result is produced with an anti-join operator.

24. The machine-readable storage medium of claim 23, wherein:

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

the plurality 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.

25. The machine-readable storage medium of claim 23, wherein:

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

the plurality 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.

26. The machine-readable storage medium of claim 23, wherein:

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

the plurality 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.

27. The machine-readable storage medium of claim 23, wherein:

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

the plurality 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.

29. A machine-executed method comprising the steps of:

receiving a particular query that includes an INTERSECT operator;

generating a plurality of transformed queries, wherein each query of said plurality of transformed queries, if executed, produces a same result as said particular query but does not include said INTERSECT operator;

generating cost estimates for the transformed queries in said plurality of transformed queries;

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

wherein each of said steps of said method is performed by one or more computing devices;

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

wherein the plurality of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is performed; and

wherein said performance of duplicate elimination includes one of the following;

performing duplicate elimination after an equijoin operation between the left-hand source and the right-hand source;

performing duplicate elimination on the left-hand source prior to a semi-join between the left-hand source and the right-hand source;

performing duplicate elimination 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; and

performing duplicate elimination 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.

30. A non-transitory machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform:

receiving a query that includes an INTERSECT operator;

generating a plurality of transformed queries, wherein each query of said plurality of transformed queries, if executed, produces a same result as said particular query but does not include said INTERSECT operator;

generating cost estimates for the transformed queries in said plurality of transformed queries;

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

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

wherein the plurality of transformed queries includes a transformed query that is associated with an execution plan in which duplicate elimination is performed; and

wherein said performance of duplicate elimination includes one of the following;

performing duplicate elimination after an equijoin operation between the left-hand source and the right-hand source;

performing duplicate elimination on the left-hand source prior to a semi-join between the left-hand source and the right-hand source;

performing duplicate elimination 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; and

performing duplicate elimination 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.