Optimization technique of generalized disjunctive semi/anti join

Patent metadata

Field	Value
Publication number	US-10726010-B2
Application number	US-201213603302-A
Country	US
Kind code	B2
Filing date	Sep 4, 2012
Priority date	Sep 4, 2012
Publication date	Jul 28, 2020
Grant date	Jul 28, 2020

Abstract

A method, apparatus, and stored instructions are provided for transforming a query representation by unnesting a predicate condition that is based on whether or not a result exists for a subquery of the predicate condition. An initial query representation is received. The initial query representation represents an initial query that includes an EXISTS-equivalent predicate or a NOT-EXISTS-equivalent predicate and at least one other predicate in a disjunction. The initial query representation is transformed into a semantically equivalent transformed query representation that represents a transformed query. The transformed query includes, instead of the EXISTS-equivalent predicate or a NOT-EXISTS-equivalent predicate, a join operator that references the data object. The transformed query representation, when used for execution, causes the at least one other predicate to be applied separately from a join operation caused by the join operator such that execution of the initial representation is semantically equivalent to execution of the transformed representation.

First claim

What is claimed is:

1. A method comprising:
receiving a first representation of a first query, wherein the first query includes at least one disjunctive predicate condition in disjunction with a particular predicate condition, wherein the particular predicate condition is based on whether a result exists for a subquery of the particular predicate condition, wherein the subquery comprises a correlated predicate that refers to a second data object and a data object that is initially referenced outside of the subquery;
transforming the first representation into a second representation of a second query;
wherein the second query includes, in replacement of the particular predicate condition, a generalized disjunctive join operator that applies to:
the at least one disjunctive predicate condition, and a join predicate for a specified join operation between the data object and the second data object;

wherein the first representation is semantically equivalent to the second representation;
storing a flag in association with a base table in the second representation to mark that the specified join operation should be applied to each row of the rows of the data object that do not satisfy the at least one disjunctive predicate condition;
responsive to the flag, evaluating the generalized disjunctive operator, wherein evaluating the generalized disjunctive operator comprises:
evaluating the at least one disjunctive predicate condition to determine:
rows of the data object that satisfy the at least one disjunctive predicate condition;
rows of the data object that do not satisfy the at least one disjunctive prediction condition;
evaluating the specified join operation for each row of the rows of the data object that do not satisfy any of the at least one disjunctive predicate condition;
wherein the join predicate for the specified join operation is not evaluated for the rows of the data object that satisfy one or more of the at least one disjunctive predicate condition;

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

2. The method of claim 1 , wherein the particular predicate condition comprises an EXISTS operator and the subquery.

3. The method of claim 1 , wherein the particular predicate condition comprises a NOT EXISTS operator and the subquery.

4. The method of claim 1 , wherein the particular predicate condition comprises an ANY, ALL, IN, or NOT IN operator and the subquery.

5. The method of claim 2 , wherein the generalized disjunctive join operator is a generalized disjunctive semi-join operator and the specified join operation is a semi-join operation between the data object and the second data object.

6. The method of claim 3 , wherein the generalized disjunctive join operator is a generalized disjunctive anti join operator and the specified join operation is an anti-join operation between the data object and the second data object.

7. The method of claim 1 , wherein transforming the first representation into the second representation comprises storing the second query in temporary storage; and wherein applying the generalized disjunctive join operator comprises sending, to a query execution engine, the second query and an indication that the specified join operation should be applied to each row of the rows of the data object that do not satisfy the at least one disjunctive predicate condition.

8. The method of claim 1 , wherein transforming the first representation into the second representation comprises storing, in temporary storage, information that describes the second query; and wherein applying the generalized disjunctive join operator comprises sending, to a query execution engine, the information that describes the second query.

9. The method of claim 1 , wherein applying the generalized disjunctive join operator comprises causing at least one row of a base table that was referenced by the subquery in the first representation to be excluded from the specified join operation.

10. One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause:
receiving a first representation of a first query, wherein the first query includes at least one disjunctive predicate condition in disjunction with a particular predicate condition, wherein the particular predicate condition is based on whether a result exists for a subquery of the particular predicate condition, wherein the subquery comprises a correlated predicate that refers to a second data object and a data object that is initially referenced outside of the subquery;
transforming the first representation into a second representation of a second query;
wherein the second query includes, in replacement of the particular predicate condition, a generalized disjunctive join operator that applies to:
the at least one disjunctive predicate condition, and a join predicate for a specified join operation between the data object and the second data object;

wherein the first representation is semantically equivalent to the second representation;
storing a flag in association with a base table in the second representation to mark that the specified join operation should be applied to each row of the rows of the data object that do not satisfy the at least one disjunctive predicate condition;
responsive to the flag, evaluating the generalized disjunctive operator, wherein evaluating the generalized disjunctive operator comprises:
evaluating the at least one disjunctive predicate condition to determine:
rows of the data object that satisfy the at least one disjunctive predicate condition;
rows of the data object that do not satisfy the at least one disjunctive prediction condition;
evaluating the specified join operation for each row of the rows of the data object that do not satisfy any of the at least one disjunctive predicate condition;
wherein the join predicate for the specified join operation is not evaluated for the rows of the data object that satisfy one or more of the at least one disjunctive predicate condition.

11. The one or more non-transitory storage media of claim 10 , wherein the particular predicate condition comprises an EXISTS operator and the subquery.

12. The one or more non-transitory storage media of claim 10 , wherein the particular predicate condition comprises a NOT EXISTS operator and the subquery.

13. The one or more non-transitory storage media of claim 10 , wherein the particular predicate condition comprises an ANY, ALL, IN, or NOT IN operator and the subquery.

14. The one or more non-transitory storage media of claim 11 , wherein the generalized disjunctive join operator is a generalized disjunctive semi-join operator and the specified join operation is a semi-join operation between the data object and the second data object.

15. The one or more non-transitory storage media of claim 12 , wherein the generalized disjunctive join operator is a generalized disjunctive anti join operator and the specified join operation is an anti-join operation between the data object and the second data object.

16. The one or more non-transitory storage media of claim 10 , wherein transforming the first representation into the second representation comprises storing the second query in temporary storage; and wherein applying the generalized disjunctive join operator comprises sending, to a query execution engine, the second query and an indication that the specified join operation should be applied to each row of the rows of the data object that do not satisfy the at least one disjunctive predicate condition.

17. The one or mo

Assignees

• Ahmed Rafi
• Lin Chun Chieh
• Zait Mohamed
• Oracle Int Corp

Inventors

• Ahmed Rafi
• Lin Chun-Chieh
• Zait Mohamed

Classifications

• G06F16/24544 Primary

  Join order optimisation · CPC title