Techniques of optimizing queries using NULL expression analysis

• US 20080065674A1
• Filed: 09/08/2006
• Published: 03/13/2008
• Est. Priority Date: 09/08/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Manikutty, Anand, Arora, Vikas, Kotsovolos, Susan, Chang, Hui Joe, Warner, James W., Krishnaprasad, Muralidhar, Liu, Zhen Hua
• Granted Patent: US 7,739,219 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/24537 of operators

Abstract

A method for optimizing queries is described. A query, which includes a first expression for determining whether each of a set of values evaluates to NULL or NOT NULL, is received. At compile-time, a first representation of the query is generated, where the first representation indicates that the query is to be performed based on the first expression. Based on the first expression, a second expression is determined. The second expression is such that the first expression would evaluate to any NOT NULL value if and only if the second expression would evaluate to any NOT NULL value. The second expression, when evaluated, is much more computationally efficient compared with the evaluation of the first expression. Based on the first representation, a second representation of the query is generated, where the second representation indicates that the query is to be performed based on the second expression. Thereafter, the query is executed based on the second representation.

Claims

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

A) sending the instructions over transmission media;

B) receiving the instructions over transmission media;

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

D) executing the instructions;

wherein the 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 specifies a target set of data, wherein the query includes a count operator that is to be performed over a first set of values;

wherein the count operator specifies a first expression which, when evaluated over the target set of data, would generate the first set of values;

generating a first representation of the query, wherein the first representation indicates that the count operator is to be performed based on the first expression;

determining a second expression based at least on the first expression, wherein the second expression is such that the first expression would evaluate to any NOT NULL value if and only if the second expression would evaluate to any NOT NULL value; and

based on the first representation, generating a second representation of the query which indicates that the count operator is to be performed based on the second expression.

2. The method of claim 1, wherein the second expression is a minimal expression that is NULLness equivalent to the first expression.

3. The method of claim 1, wherein the instructions further include instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of executing the query based on the second representation.

4. The method of claim 3, wherein:

the first representation and the second representation are expression trees of the query that are generated during the compilation of the query; and

the step of executing the query further comprises executing the query based on an execution tree that is generated based on the second representation.

5. The method of claim 1, wherein the target set of data is any one of:

a set of rows from one or more relational tables or views;

a set of objects from one or more object tables or views; and

a set of instances of XML data that are stored in tables or views in one of object-relational storage and Large Object (LOB) storage.

6. The method of claim 1, wherein the query is any one of a Structured Query Language (SQL) query, an XML Query Language (XQuery) query, and a SQL/XML query.

7. The method of claim 1, wherein the step of determining the second expression comprises:

analyzing the first expression by executing a function that includes the first expression as an input argument, wherein executing the function returns a status; and

determining the second expression based on the status returned from the function.

8. The method of claim 7, wherein the step of analyzing the first expression further comprises:

recursively calling the function, wherein at least one recursive call to the function uses as the input argument a particular expression that was returned as an output argument from a previous call to the function.

9. The method of claim 7, wherein:

the step of analyzing the first expression includes determining that the status returned from the function indicates that the first expression, when evaluated over the target set of data, would generate only NULL values in the first set of values; and

the step of determining the second expression based on the status includes establishing the second expression as a constant NULL value.

10. The method of claim 7, wherein:

the step of analyzing the first expression includes determining that the status returned from the function indicates that the first expression, when evaluated over the target set of data, would generate only NOT NULL values in the first set of values; and

the step of determining the second expression based on the status includes establishing the second expression as a constant NOT NULL value.

11. The method of claim 10, wherein:

the step of analyzing the first expression includes determining that the first expression is to be evaluated over a column of a table, wherein the column is declared as not nullable and can store only NOT NULL values.

12. The method of claim 10, wherein:

the step of analyzing the first expression includes determining that the first expression is an XMLElement operator with “

EMPTY ON NULL”

option that always evaluates to an XML element.

13. The method of claim 7, wherein:

the step of analyzing the first expression includes;

determining that the status returned from the function indicates that the first expression, when evaluated over the target set of data, would generate both NULL values and NOT NULL values in the first set of values depending on a sub-expression of the first expression;

wherein executing the function also returns the sub-expression as an output expression from the function; and

the step of determining the second expression based on the status includes establishing the second expression as the output expression.

14. The method of claim 13, wherein:

the step of analyzing the first expression further includes determining that the first expression is to be evaluated over a column of a table, wherein the column is declared as nullable;

wherein the sub-expression, which is returned from the function as the output expression, is established as the column.

15. The method of claim 13, wherein:

the step of analyzing the first expression further includes determining that the first expression is a user-defined function specifying a particular argument, wherein the user-defined function would evaluate to any NOT NULL value if and only if the particular argument would evaluate to any NOT NULL value;

wherein the sub-expression, which is returned from the function as the output expression, is established as the particular argument.

16. The method of claim 7, wherein:

the step of analyzing the first expression includes determining that the status returned from the function indicates that the second expression cannot be determined; and

the step of determining the second expression based on the status includes establishing the second expression as the first expression.

17. The method of claim 1, wherein the first expression is a SQL/XML operator that specifies a set of arguments, and wherein the step of determining the second expression comprises:

analyzing the SQL/XML operator by recursively calling a function with each of the set of arguments as an input argument, wherein recursively calling the function returns a set of statuses that corresponds to the set of arguments; and

determining the second expression based at least on the set of statuses.

18. The method of claim 17, wherein the SQL/XML operator is any one of an XMLConcat operator, an XMLForest operator with “

NULL ON NULL”

option, and an XMLElement operator with “

NULL ON NULL”

option.

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

A) sending the instructions over transmission media;

B) receiving the instructions over transmission media;

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

D) executing the instructions;

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

generating a first representation of a count( ) query, wherein the count( ) query includes a count operator to be performed based on a set of instances of XML data;

wherein the count operator specifies an XPath expression which indicates the location of the set of instances of XML data in one or more target XML documents; and

based on the XPath expression, rewriting the first representation into a second representation that corresponds to an equivalent query of the count( ) query, wherein the second representation indicates that the count operator is to be performed based on a set of rows stored in one or more relational tables, and wherein the second representation includes at least one operator which, when evaluated, identifies the set of rows in the one or more relational tables.

20. The method of claim 19, wherein the instructions further include instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of executing the count( ) query based on the second representation.

21. The method of claim 19, wherein:

the one or more relational tables store the target XML documents as object-relational storage; and

in the second representation, the at least one operator is included in at least one predicate for filtering the one or more relational tables to obtain the set of rows, wherein the at least one predicate is determined based on the XPath expression.

22. The method of claim 19, wherein:

the target XML documents are stored as any one of object relational storage and Large Object (LOB) storage;

the one or more relational tables store an XPath index over the target XML documents; and

in the second representation, the at least one operator is included in at least one predicate for filtering the one or more relational tables to obtain the set of rows, wherein the at least one predicate is determined based on the XPath expression.

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

A) sending the instructions over transmission media;

B) receiving the instructions over transmission media;

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

D) executing the instructions;

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

generating a first representation of a query, wherein the query includes a first expression for determining whether each of a set of values evaluates to any one of a NULL value and a NOT NULL value;

determining a second expression based at least on the first expression, wherein the second expression is such that the first expression would evaluate to any NOT NULL value if and only if the second expression would evaluate to any NOT NULL value; and

based on the first representation, generating a second representation of the query which indicates that the query is to be performed based on the second expression.

24. The method of claim 23, wherein the second expression is a minimal expression that is NULLness equivalent to the first expression.

25. The method of claim 23, wherein the instructions further include instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of executing the query based on the second representation.

26. The method of claim 25, wherein:

the first representation and the second representation are expression trees of the query that are generated during the compilation of the query; and

the step of executing the query further comprises executing the query based on an execution tree that is generated based on the second representation.

27. The method of claim 23, wherein the first expression is any one of an IS NULL operator and an IS NOT NULL operator.

28. The method of claim 23, wherein:

the query is any one of a Structured Query Language (SQL) query, an XML Query Language (XQuery) query, and a SQL/XML query; and

the first expression is included in a specific portion of the query, wherein the specific portion is any one of;

a predicate specified in any clause of the query;

an item specified in a SELECT clause of the query; and

a functional constraint specified in any clause of the query.

29. The method of claim 23, wherein the step of determining the second expression comprises:

analyzing the first expression by executing a function that includes the first expression as an input argument, wherein executing the function returns a status; and

determining the second expression based on the status returned from the function.

30. The method of claim 29, wherein the step of analyzing the first expression further comprises:

recursively calling the function, wherein at least one recursive call to the function uses as the input argument a particular expression that was returned as an output argument from a previous call to the function.