Method and apparatus for XML query evaluation using early-outs and multiple passes

• US 7,716,210 B2
• Filed: 12/20/2006
• Issued: 05/11/2010
• Est. Priority Date: 12/20/2006
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Ozcan, Fatma, Ting, Edison Lao
• Primary Examiner(s): Alam; Shahid A
• Assistant Examiner(s): Mahmood; Rezwanul
• Application Number:
  US11/613,944
• Publication Number:
  US 20080154868A1
• Time in Patent Office: 1,238 Days
• Field of Search: 707/3, 707/101, 707/102, 707/2, 707/200
• US Class Current: 707/713
• CPC Class Codes: G06F 16/8365 Query optimisation

Abstract

A method and apparatus is disclosed for XML query evaluation using early-outs and multiple passes to evaluate an XML query. A multi-pass evaluation procedure evaluates the XML query one step at a time as needed to complete evaluation. The multi-pass evaluation procedure evaluates XML queries containing logical expressions such as “AND” expressions, “OR” expressions, and implied “AND” expressions within “FOR” clauses. Queries containing logical expressions are often satisfied before every component is evaluated. Thus, executing the multi-pass evaluation procedure allows the evaluation to exit early when the veracity of the query is determined, not necessarily when every component has been evaluated. The multi-pass evaluation procedure executes as long as a descendant axis of the XML query need not be evaluated past a child node. When evaluation of a descendant axis past a child node is required, the multi-pass evaluation procedure may switch to a single-pass evaluation procedure to complete evaluation.

Claims

1. A computer program product comprising a computer readable storage medium having computer usable program code programmed for Extensible Mark-up Language (“

XML”

) query evaluation using early-outs and multiple passes, the computer program product having operations comprising;

rewriting, by way of a processor executing instructions of a memory, an alterable XML query comprising multiple steps such that less selective steps of the XML query will be evaluated after more selective steps, wherein the XML query comprises logical expressions formatted according to one of an XPath expression language and an XQuery query language;

selectively evaluating the steps in the rewritten XML query using a multi-pass evaluation procedure to traverse the XML document, wherein the multi-pass evaluation procedure evaluates at least one step in the rewritten XML query with each pass through the XML document until veracity of the rewritten XML query is established; and

exiting the multi-pass evaluation procedure in response to determining that an XML document meets an exitable condition of the XML query, the exitable condition comprising a determination that the veracity of the XML query for a first predicate logically applies to the remaining predicates without evaluating the remaining steps of the XML query.

2. The computer program product of claim 1, wherein the operations further comprise switching from the multi-pass evaluation procedure to a single-pass evaluation procedure when steps of the rewritten XML query require evaluating a descendant axis past a child node, the single pass evaluation gathering sufficient data for the XML document to evaluate the rewritten XML query.

3. The computer program product of claim 1, wherein the operations further comprise deferring evaluation of the less selective steps in the XML query, such that more highly selective steps are evaluated before the less selective steps.

4. The computer program product of claim 1, wherein the operations further comprise evaluating a next step of the XML query in response to determining a non-exitable condition is met.

5. The computer program product of claim 1, wherein an exitable condition comprises a logical “

OR”

expression of the XML query.

6. The computer program product of claim 1, wherein an exitable condition comprises a logical “

AND”

expression of the XML query.

7. The computer program product of claim 1, wherein an exitable condition comprises a logical expression associated with a “

FOR”

clause of the XML query, wherein the “

FOR”

clause returns no matches.

8. An apparatus for Extensible Mark-up Language (“

XML”

) query evaluation using early-outs and multiple passes, the apparatus comprising;

a processor coupled to a memory, the memory comprising

a rewrite module configured to rewrite an alterable XML query comprising multiple steps such that less selective steps of the XML query are evaluated after more selective steps, wherein the XML query comprises logical expressions formatted according to one of an XPath expression language and an XQuery query language;

an evaluation module configured to selectively evaluate the steps in the rewritten XML query using a multi-pass evaluation procedure to traverse the XML document, wherein the multi-pass evaluation procedure evaluates at least one step in the rewritten XML query with each pass through the XML document until veracity of the rewritten XML query is established; and

an exit module configured to exit the multi-pass evaluation procedure in response to determining that an XML document meets an exitable condition of the XML query, the exitable condition comprising a determination that the veracity of the XML query for a first predicate logically applies to the remaining predicates without evaluating the remaining steps of the XML query.

9. The apparatus of claim 8, wherein the evaluation module is further configured to switch from the multi-pass evaluation procedure to a single-pass evaluation procedure when steps of the rewritten XML query require evaluation of a descendant axis below a child node, the single pass evaluation gathering sufficient data for the XML document to evaluate the rewritten XML query.

10. The apparatus of claim 8, wherein the evaluation module is further configured to defer evaluation of the less selective steps in the XML query, such that more highly selective steps are evaluated before the less selective steps.

11. The apparatus of claim 8, wherein the evaluation module is further configured to evaluate a next step of the XML query in response to determining a non-exitable condition is met.