Mechanism for efficiently evaluating operator trees

• US 7,603,347 B2
• Filed: 09/16/2004
• Issued: 10/13/2009
• Est. Priority Date: 04/09/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Sedlar, Eric, Thusoo, Ashish, Chandrasekar, Sivasankaran, Murthy, Ravi, Agarwal, Nipun
• Primary Examiner(s): Wong; Leslie
• Application Number:
  US10/944,171
• Publication Number:
  US 20050228768A1
• Time in Patent Office: 1,853 Days
• Field of Search: 707 3- 5, 707/101, 707/104.1, 707/E17.122, 707/E17.125, 707/E17.127, 715/234
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

An XPath expression is converted into a tree-based representation where each node represents an operation to be performed and the links between nodes in the tree represent the flow of data between operations. The conversion may involve creating a parse tree for the XPath expression, and then converting the parse tree into an operator tree. The operator tree is constructed in such a way that execution of the XPath expression begins at the leaf nodes of the operator tree, and the results are then passed up the tree. After each node is executed, the results are either (1) passed to a filter that filters the results with a predicate statement or (2) passed to another node to be operated upon. This occurs until no nodes remain to be executed.

Claims

1. A method for processing XPath expressions, comprising the steps of:

receiving an XPath expression, wherein the XPath expression is associated with a requested operation;

generating, based on said XPath expression, an operator tree of the XPath expression;

wherein the operator tree comprises nodes and links;

wherein a subset of the nodes represents operations to be performed;

wherein each link in a subset of the links between the nodes represents a flow of data between the operations that are represented by the nodes that are linked by said each link; and

storing the operator tree in volatile or non-volatile memory; and

applying one or more rules to the operator tree to generate data,

wherein the data specifies operations which, when executed, cause a database server to perform at least a portion of the requested operation;

based on the operator tree, executing the requested operation;

wherein executing the requested operation includes;

beginning at leaf nodes of the operator tree, performing operations associated with the leaf nodes; and

passing results of operations up to parent nodes of the nodes that performed the operations;

wherein passing the results includes;

if the parent of a node associated with an operation is a filter, then passing results of the operation to the filter, wherein the filter filters the results with a predicate statement; and

if the parent of a node associated with an operation is an operator node, then passing results of the operation to the parent and executing the operation associated with the parent on said results.

2. The method of claim 1 wherein the step of generating a tree-based representation includes:

creating a parse tree for the XPath expression, and

converting the parse tree into the operator tree.

3. The method of claim 2 wherein the step of generating an operator tree further comprises the step of normalizing the parse tree by converting one or more reverse axes to forward axes.

4. The method of claim 2 wherein:

the XPath expression includes a location step; and

the step of converting the parse tree into the operator tree includes defining a filter operator for a relation predicate on the location step, wherein the filter operator has, on its right hand side, an operator tree corresponding to the relation predicate.

5. The method of claim 1, wherein applying the one or more rules to the operator tree comprises applying one or more rules to the operator tree to generate one or more database commands.

6. The method of claim 5, wherein the one or more database commands are Structured Query Language (SQL) commands.

7. The method of claim 6 wherein the step of applying the one or more rules to generate the SQL commands includes generating SQL commands that access an XML Index to perform the requested operation.

8. The method of claim 6 wherein the method further comprises:

determining whether a SQL command can be generated; and

if the SQL command cannot be generated, then functionally evaluating operators in the operator tree to perform a particular requested operation.

9. A method for processing XPath expressions, comprising the steps of:

receiving an XPath expression, wherein the XPath expression is associated with a requested operation;

creating a parse tree for the XPath expression;

converting the parse tree into an operator tree;

wherein converting the parse tree into the operator tree includes at least one of;

converting an axis in the parse tree into a corresponding operator in the operator tree, or

converting a pre-defined function in the parse tree into a corresponding operator in the operator tree;

wherein the operator tree comprises nodes and links;

wherein at least a subset of the nodes are nodes that represent operations to be performed;

wherein each link in at least a subset of the links between the nodes represents a flow of data between the operations that are represented by the nodes that are linked by said each link; and

storing the operator tree in volatile or non-volatile memory.

10. The method of claim 9, wherein the step of converting the parse tree into the operator tree further comprises the step of normalizing the parse tree by converting one or more reverse axes to forward axes.

11. The method of claim 9, wherein:

the XPath expression includes a location step; and

the step of converting the parse tree into the operator tree includes defining a filter operator for a relation predicate on the location step, wherein the filter operator has, on its right hand side, a second operator tree corresponding to the relation predicate.

12. The method of claim 9, further comprising, based on the operator tree, executing an operation associated with the XPath expression.

13. The method of claim 12, wherein the step of executing includes:

beginning at leaf nodes of the operator tree, performing operations associated with the leaf nodes; and

passing results of operations up to parent nodes of the nodes that performed the operations.

14. The method of claim 13, wherein the step of passing results includes:

if the parent of a node associated with an operation is a filter, then passing results of the operation to the filter, wherein the filter filters the results with a predicate statement; and

if the parent of a node associated with an operation is an operator node, then passing results of the operation to the parent and executing the operation associated with the parent on said results.

15. The method of claim 9, further comprising the step of applying one or more rules to the operator tree generate one or more database commands which, when executed, cause a database server to perform at least a portion of the requested operation.

16. The method of claim 15, wherein applying the one or more rules comprises generating one or more database commands that access an XML Index to perform the portion of the requested operation.

17. The method of claim 9, further comprising:

determining whether a database command can be generated; and

if a database command cannot be generated, then functionally evaluating one or more operators in the operator tree to perform a particular requested operation.

18. A machine-readable storage medium storing instructions for processing XPath expressions, wherein the instructions, when executed by one or more processors, causes the one or more processors to perform the steps of:

receiving an XPath expression, wherein the XPath expression is associated with a requested operation;

generating, based on said XPath expression, an operator tree of the XPath expression;

wherein the operator tree comprises nodes and links;

wherein a subset of the nodes represents operations to be performed;

wherein each link in a subset of the links between the nodes represents a flow of data between the operations that are represented by the nodes that are linked by said each link; and

storing the operator tree in volatile or non-volatile memory; and

applying one or more rules to the operator tree to generate,

wherein the data specifies operations which, when executed, cause a database server to perform at least a portion of the requested operation;

based on the operator tree, executing the requested operation;

wherein executing the requested operation includes;

beginning at leaf nodes of the operator tree, performing operations associated with the leaf nodes; and

passing results of operations up to parent nodes of the nodes that performed the operations;

wherein passing the results includes;

if the parent of a node associated with an operation is a filter, then passing results of the operation to the filter, wherein the filter filters the results with a predicate statement; and

if the parent of a node associated with an operation is an operator node, then passing results of the operation to the parent and executing the operation associated with the parent on said results.

19. The machine-readable storage medium of claim 18, wherein the step of generating a tree-based representation includes:

creating a parse tree for the XPath expression, and converting the parse tree into the operator tree.

20. The machine-readable storage medium of claim 19, wherein the step of generating an operator tree further comprises the step of normalizing the parse tree by converting one or more reverse axes to forward axes.

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

the XPath expression includes a location step; and

the step of converting the parse tree into the operator tree includes defining a filter operator for a relation predicate on the location step, wherein the filter operator has, on its right hand side, an operator tree corresponding to the relation predicate.

22. The machine-readable storage medium of claim 18, wherein applying the one or more rules to the operator tree comprises applying one or more rules to the operator tree to generate one or more database commands.

23. The machine-readable storage medium of claim 22, wherein the one or more database commands are Structured Query Language (SQL) commands.

24. The machine-readable storage medium of claim 23, wherein the step of applying the one or more rules to generate the SQL commands includes generating SQL commands that access an XML Index to perform the requested operation.

25. The machine-readable storage medium of claim 23, wherein the instructions include instructions which, when executed by the one or more processors, further cause the one or more processors to perform the steps of:

determining whether a SQL command can be generated; and

if the SQL command cannot be generated, then functionally evaluating one or more operators in the operator tree to perform a particular requested operation.

26. A machine-readable storage medium storing instructions for processing XPath expressions, wherein the instructions, when executed by one or more processors, cause the one or more processors to perform the steps of:

receiving an XPath expression, wherein the XPath expression is associated with a requested operation;

creating a parse tree for the XPath expression;

converting the parse tree into an operator tree;

wherein converting the parse tree into the operator tree includes at least one of;

converting an axis in the parse tree into a corresponding operator in the operator tree, or

converting a pre-defined function in the parse tree into a corresponding operator in the operator tree;

wherein the operator tree comprises nodes and links;

wherein at least a subset of the nodes are nodes that represent operations to be performed;

wherein each link in at least a subset of the links between the nodes represents a flow of data between the operations that are represented by the nodes that are linked by said each link; and

storing the operator tree in volatile or non-volatile memory.

27. The machine-readable storage medium of claim 26, wherein the step of converting the parse tree into the operator tree further comprises the step of normalizing the parse tree by converting one or more reverse axes to forward axes.

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

the XPath expression includes a location step; and

the step of converting the parse tree into the operator tree includes defining a filter operator for a relation predicate on the location step, wherein the filter operator has, on its right hand side, a second operator tree corresponding to the relation predicate.

29. The machine-readable storage medium of claim 26, wherein the instructions include instructions which, when executed by the one or more processors, further cause the one or more processors to perform the step of, based on the operator tree, executing an operation associated with the XPath expression.

30. The machine-readable storage medium of claim 29, wherein the step of executing includes:

beginning at leaf nodes of the operator tree, performing operations associated with the leaf nodes; and

passing results of operations up to parent nodes of the nodes that performed the operations.

31. The machine-readable storage medium of claim 30, wherein the step of passing results includes:

if the parent of a node associated with an operation is a filter, then passing results of the operation to the filter, wherein the filter filters the results with a predicate statement; and

if the parent of a node associated with an operation is an operator node, then passing results of the operation to the parent and executing the operation associated with the parent on said results.

32. The machine-readable storage medium of claim 26, wherein the instructions include instructions which, when executed by the one or more processors, further cause the one or more processors to perform the steps of applying one or more rules to the operator tree generate one or more database commands which, when executed, cause a database server to perform at least a portion of the requested operation.

33. The machine-readable storage medium of claim 32, wherein applying the one or more rules comprises generating one or more database commands that access an XML Index to perform the portion of the requested operation.

34. The machine-readable storage medium of claim 26, wherein the instructions include instructions which, when executed by the one or more processors, further cause the one or more processors to perform the steps of:

determining whether a database command can be generated; and

if a database command cannot be generated, then functionally evaluating one or more operators in the operator tree to perform a particular requested operation.