Global query normalization to improve XML index based rewrites for path subsetted index

• US 7,991,768 B2
• Filed: 11/08/2007
• Issued: 08/02/2011
• Est. Priority Date: 11/08/2007
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Zhang, Ning, Tarachandani, Asha, Baby, Thomas, Chandrasekar, Sivasankaran, Agarwal, Nipun
• Primary Examiner(s): Chen; Susan Y
• Application Number:
  US11/937,268
• Publication Number:
  US 20090125494A1
• Time in Patent Office: 1,363 Days
• Field of Search: None
• US Class Current: 707/716
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/8365 Query optimisation

Abstract

Techniques for processing a query that includes a path expression are provided. A query processor determines whether an XML index may be used to execute the query instead of having to scan multiple XML documents. The query is parsed and normalized, which results in multiple normalized path expressions that are based on the original path expression. If the XML index is a path-subsetted index, then the query processor generates annotated path expressions based on the normalized path expressions. The query processor determines whether each of the annotated path expressions is satisfiable by the path-subsetted XML index. If so, then the XML index is used to process the query.

Claims

1. A method comprising:

receiving a query that specifies a particular path expression;

normalizing the query to generate a normalized query, wherein normalizing the query comprises generating, based on the particular path expression, a plurality of normalized path expressions;

generating, based on the particular path expression, from a subset of the plurality of normalized path expressions, one or more temporary path expressions;

determining whether each of the one or more temporary path expressions is subsumed by a path of a node that is indexed by a path-subsetted XML index that is associated with one or more subsetted path expressions that indicate a set of one or more nodes that are indexed by said path-subsetted XML index; and

in response to determining that each of the one or more temporary path expressions is subsumed by a path of a node that is indexed by said path-subsetted XML index, using the path-subsetted XML index to process the plurality of normalized path expressions;

wherein the method is performed by one or more computers.

2. The method of claim 1, wherein generating the one or more temporary path expressions includes modifying the subset of the plurality of normalized path expressions to include information from the particular path expression.

3. The method of claim 1, wherein the query conforms to the SQL/XML query language.

4. The method of claim 3, further comprising:

receiving a previous query that conforms to the XQuery query language; and

generating the query based on the previous query.

5. The method of claim 1, wherein at least a subset of the one or more subsetted path expressions are specified in a definition of the path-subsetted XML index.

6. The method of claim 1, wherein:

each subsetted path expression of the one or more subsetted path expressions is not in a particular set of path expressions;

the particular set of path expressions is specified in a definition of the path-subsetted XML index; and

each path expression in the particular set of path expressions specifies one or more nodes that are not indexed by the path-subsetted XML index.

7. The method of claim 1, wherein each normalized path expression in a subset of the plurality of normalized path expressions is subsumed by a subsetted path expression of the one or more subsetted path expressions.

8. The method of claim 1, further comprising:

for each temporary path expression of the one or more temporary path expressions, generating a first tree of nodes, wherein each node in the first tree corresponds to an element in said each temporary path expression; and

for each subsetted path expression of the one or more subsetted path expressions, generating a second tree of nodes, wherein each node in the second tree corresponds to an element in said each subsetted path expression;

wherein determining whether each of the one or more temporary path expressions is subsumed by a path of a node that is indexed by the path-subsetted XML index includes determining whether each first tree is equivalent to one of the second trees.

9. The method of claim 1, wherein:

the normalized query includes a plurality of extract operators, none of which appear in said query;

each extract operator of the plurality of extract operators takes as input a different normalized path expression of the plurality of normalized path expressions; and

using the path-subsetted XML index to process the plurality of normalized path expressions comprises rewriting each extract operator to use the path-subsetted XML index.

10. One or more non-transitory machine-readable media storing instructions which, when executed by one or more processors, cause:

receiving a query that specifies a particular path expression;

normalizing the query to generate a normalized query, wherein normalizing the query comprises generating, based on the particular path expression, a plurality of normalized path expressions

generating, based on the particular path expression, from a subset of the plurality of normalized path expressions, one or more temporary path expressions;

determining whether each of the one or more temporary path expressions is subsumed by a path of a node that is indexed by a path-subsetted XML index that is associated with one or more subsetted path expressions that indicate a set of one or more nodes that are indexed by said path-subsetted XML index; and

in response to determining that each of the one or more temporary path expressions is subsumed by a path of a node that is indexed by said path-subsetted XML index, using the path-subsetted XML index to process the plurality of normalized path expressions.

11. The one or more non-transitory machine-readable media of claim 10, wherein generating the one or more temporary path expressions includes modifying the subset of the plurality of normalized path expressions to include information from the particular path expression.

12. The one or more non-transitory machine-readable media of claim 10, wherein the query conforms to the SQL/XML query language.

13. The one or more storage non-transitory machine-readable media of claim 12, wherein the instructions, when executed by the one or more processors, further cause:

receiving a previous query that conforms to the XQuery query language; and

generating the query based on the previous query.

14. The one or more non-transitory machine-readable media of claim 10, wherein at least a subset of the one or more subsetted path expressions are specified in a definition of the path-subsetted XML index.

15. The one or more non-transitory machine-readable media of claim 10, wherein:

each subsetted path expression of the one or more subsetted path expressions is not in a particular set of path expressions;

the particular set of path expressions is specified in a definition of the path-subsetted XML index; and

each path expression in the particular set of path expressions specifies one or more nodes that are not indexed by the path-subsetted XML index.

16. The one or more non-transitory machine-readable media of claim 10, wherein each normalized path expression in a subset of the plurality of normalized path expressions is subsumed by a subsetted path expression of the one or more subsetted path expressions.

17. The one or more non-transitory machine-readable media of claim 10, wherein the instructions, when executed by the one or more processors, further cause:

for each temporary path expression of the one or more temporary path expressions, generating a first tree of nodes, wherein each node in the first tree corresponds to an element in said each temporary path expression; and

for each subsetted path expression of the one or more subsetted path expressions, generating a second tree of nodes, wherein each node in the second tree corresponds to an element in said each subsetted path expression;

wherein determining whether each of the one or more temporary path expressions is subsumed by a path of a node that is indexed by the path-subsetted XML index includes determining whether each first tree is equivalent to one of the second trees.

18. The one or more non-transitory machine-readable media of claim 10, wherein:

the normalized query includes a plurality of extract operators, none of which appear in said query;

each extract operator of the plurality of extract operators takes as input a different normalized path expression of the plurality of normalized path expressions; and

using the path-subsetted XML index to process the plurality of normalized path expressions comprises rewriting each extract operator to use the path-subsetted XML index.