EFFICIENT EVALUATION OF XQUERY AND XPATH FULL TEXT EXTENSION

• US 20100211560A1
• Filed: 02/18/2009
• Published: 08/19/2010
• Est. Priority Date: 02/18/2009
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chakraborty, Sukhendu, Baby, Thomas, Liu, Zhen Hua, Novoselsky, Anguel
• Granted Patent: US 8,312,030 B2
• Time in Patent Office: Days
• US Class Current: 707/720
• CPC Class Codes: G06F 16/835 Query processing

Abstract

Techniques are provided for efficiently evaluating XML queries that conform to an extension of an XML language (e.g., XQuery or XPath). The extension allows XML queries to have full-text search capabilities. Such an XML query is compiled to generate a tree of nodes that correspond to one or more conditions in the full-text portion of the query. In one technique, the amount of memory for the execution state of the tree is determined at compile time and allocated only once throughout execution of the query. In another technique, to ensure at most a single scan of a document, all the words or phrases in the full-text portion of an XML query are located before any of the other conditions in the full-text portion are evaluated. In another technique, the elements of the full-text portion of an XML query are analyzed to determine, based at least in part on cost, which evaluation strategy, of a plurality of evaluation strategies, should be employed.

Claims

1. A method comprising the machine-implemented steps of:

receiving an XML query that conforms to a specification that extends one or more XML-based query languages to include full-text search capabilities;

compiling the XML query to generate a tree that comprises a plurality of nodes, wherein each node in the plurality of nodes corresponds to a full-text operator defined by the specification;

before evaluating any of the nodes in the tree;

determining a size of the execution state for each node of the plurality of nodes; and

allocating, based at least in part on the size of the execution state for each node of the plurality of nodes, a portion of memory for said each node; and

fully evaluating the tree to determine a final result without de-allocating or allocating memory for each node of the plurality of nodes.

2. The method of claim 1, wherein the step of determining is performed during the step of compiling the XML query.

3. The method of claim 1, wherein the XML query includes a bind variable, wherein the value of the bind variable is not known during the step of compiling the XML query, the method further comprises the steps of:

after compiling the XML query, determining the value of the bind variable; and

determining the size of one or more nodes of the plurality of nodes based, at least in part, on the value of the bind variable.

4. The method of claim 1, further comprising the steps of:

determining that the XML query specifies an ‘

all’

option that indicates that all words or phrases in a full-text portion of the XML query must be contained in an item in a search context that is specified in the XML query;

in response to determining that the XML query specifies the ‘

all’

option, generating a full-text operator that combines two or more full-text selections.

5. The method of claim 1, further comprising the step of:

determining that the XML query specifies a number of times that a word or phrase in a full-text portion of the XML query must be contained in an item in a search context that is specified in the XML query;

wherein allocating the portion of memory for each node is based, at least in part, on the number.

13. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 1.

14. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 2.

15. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 3.

16. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 4.

17. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 5.

6. A method comprising the machine-implemented steps of:

receiving an XML query that conforms to a specification that extends one or more XML-based query languages to include full-text search capabilities, wherein the XML query specifies a search context and a full-text selection expression;

compiling the XML query to generate a tree that comprises a plurality of nodes that includes a plurality of leaf nodes, wherein each node in the plurality of nodes corresponds to a full-text operator defined by the specification, wherein each of the plurality of leaf node corresponds to a different word or phrase in the full-text selection expression;

while evaluating the tree;

evaluating each of the plurality of leaf nodes before evaluating any parent node of any of the plurality of leaf nodes; and

in response to identifying at least one occurrence of each word or phase, corresponding to each of the plurality of leaf nodes, in an item of the search context, evaluating one or more parent nodes of the plurality of leaf nodes.

7. The method of claim 6, wherein:

evaluating each of the plurality of leaf nodes includes identifying a plurality of occurrences of a particular word or phrase in the full-text selection expression before identifying any occurrence of another word or phrase in the full-text selection expression; and

storing information about each occurrence of the plurality of occurrences of the particular word or phrase in association with the leaf node that corresponds to the particular word or phrase.

8. The method of claim 7, further comprising before evaluating any of the plurality of leaf nodes, allocating an amount of memory that is large enough to store information about a particular number of occurrences of the particular word.

18. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 6.

19. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 7.

20. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 8.

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

receiving an XML query that conforms to a specification that extends one or more XML-based query languages to include full-text search capabilities, wherein the XML-based query specifies a search context and a full-text selection expression;

determining a first selectivity value that corresponds to the selectivity of the search context;

determining a second selectivity value that corresponds to the selectivity of the full-text selection expression;

determining, based at least in part on the first and second selectivity values, a particular evaluation strategy from a plurality of evaluation strategies; and

executing the XML query based, at least in part, on the particular evaluation strategy.

10. The method of claim 9, wherein:

the first and second selectivity values indicate that the selectivity of the search context is lower relative to the full-text selection expression; and

the particular evaluation strategy comprises;

evaluating the search context to determine a first set of one or more nodes, and

for each node of the first set of nodes, evaluating the full-text selection expression.

11. The method of claim 9, wherein:

the first and second selectivity values indicate that the selectivity of the full-text selection expression is lower relative to the search context; and

the particular evaluation strategy comprises;

evaluating the full-text selection expression to determine a first set of one or more nodes, and

for each node in the first set of nodes, evaluating the search context.

12. The method of claim 9, wherein the particular evaluation strategy comprises:

evaluating the search context to determine a first set of nodes,

evaluating the full-text selection expression to determine a second set of nodes, and

determining whether a node in the second set of nodes is a descendant node of a node in the first set of nodes.

21. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 9.

22. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 10.

23. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 11.

24. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 12.