Indexing strategy with improved DML performance and space usage for node-aware full-text search over XML

• US 8,126,932 B2
• Filed: 12/30/2008
• Issued: 02/28/2012
• Est. Priority Date: 12/30/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Baby, Thomas, Liu, Zhen Hua, Lin, Wesley
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US12/346,393
• Publication Number:
  US 20100185683A1
• Time in Patent Office: 1,155 Days
• Field of Search: 707/803, 707/802, 707/809, 707/999.103, 707/102, 707/4, 707/999.1, 707/706, 707/705, 707/736, 707/758, 715/513
• US Class Current: 707/803
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

Techniques are provided for searching within a collection of XML documents. A relational table stores an entry for each node of a set of nodes in a collection of XML documents. Each entry of the relational table stores an order key and a path identifier along with the atomized value of the node. Instead of storing the atomized value in a full-text index, a virtual column can be created to represent, for each node, the atomized value of the node. Alternately, each entry of the relational table stores an order key and a path identifier along with, for simple nodes, the atomized value, and for complex nodes, a null value. For a complex node with a descendant text node, a separate entry is stored for the descendant text node in the relational table.

Claims

1. A computer-implemented method comprising:

storing a table that stores data for a plurality of nodes in one or more XML documents, the table comprising an entry for each node of the plurality of nodes, the entry of each node comprising;

an order key that specifies a hierarchical position of the node within the one or more XML documents;

an indication of a name of the node;

wherein the table comprises at least a first entry for a first node and a second entry for a second node, wherein the first node has a first node text value but does not have any descendant nodes, and wherein the second node has a second node text value and has one or more descendant nodes;

wherein the first entry for the first node comprises the first node text value;

wherein the second entry for the second node comprises a null node text value;

the table further comprising a third entry comprising the second node text value; and

storing an index of the node text values stored in the entries of the table;

wherein the method is performed by one or more computing devices.

2. The computer-implemented method of claim 1, wherein said node text values are stored in a column of said table, said column being of a character large object type.

3. The computer-implemented method of claim 1, further comprising:

receiving a query that requires a text search of the one or more XML documents; and

rewriting said query to produce a rewritten query, wherein said rewritten query is evaluated against the index.

4. The computer-implemented method of claim 1, further comprising:

receiving a query that specifies certain criteria, said criteria comprising;

one or more particular node text values; and

one or more particular node names;

evaluating the query against the index.

5. The computer-implemented method of claim 4, wherein at least one particular node text value of the one or more particular node text values span across node text values of two or more adjacent nodes, and wherein evaluating the query finds the at least one particular node text value in the two or more adjacent nodes.

6. The computer-implemented method of claim 5, wherein the at least one particular node text value comprises a first part and a second part, further comprising searching for the first part in a first adjacent node and a second part in a second adjacent node to compute whether at least one particular node text value exists in the node text values of the adjacent nodes.

7. The computer-implemented method of claim 4, further comprising rewriting the query to search for one or more indications of the one or more particular node names.

8. A computer-implemented method comprising:

receiving a query for specified text in one or more XML documents;

wherein said one or more XML documents comprise a plurality of nodes;

in response to receiving the query;

determining that the one or more XML documents are stored in a table comprising a plurality of rows, each row of said plurality of rows corresponding to a node of said plurality of nodes;

wherein each row of said plurality of rows includes;

an order key that indicates a hierarchical position of the node within the one or more XML documents, said order key being stored in a first column of said table; and

an indication of a name of the node, said indication stored in a second column of said table;

wherein the table comprises at least a first row for a first node and a second row for a second node, wherein the first node has a first node text value but does not have any descendant nodes, and wherein the second node has a second node text value and has one or more descendant nodes;

wherein the first row for the first node comprises the first node text value;

wherein the second row for the second node comprises a null node text value;

the table further comprising a third row comprising the second node text value; and

searching the node text values stored in the rows of the table for the specified text to determine at least one of a particular order key or a particular name of a particular node that contains the specified text;

wherein the method is performed by one or more computing devices.

9. The computer-implemented method of claim 8, further comprising determining whether a first part of the specified text exists in a first adjacent node of two or more adjacent nodes, and whether a second part of the specified text exists in a second adjacent node of two or more adjacent nodes.

10. The computer-implemented method of claim 8, further comprising rewriting the query to search for one or more order keys or node names.

11. A volatile or non-volatile computer-readable storage medium storing one or more sequences of instruction, wherein execution of the one or more sequences of instruction by one or more processors causes the one or more processors to perform:

storing a table that stores data for a plurality of nodes in one or more XML documents, the table comprising an entry for each node of the plurality of nodes, the entry of each node comprising;

an order key that specifies a hierarchical position of the node within the one or more XML documents;

an indication of a name of the node;

wherein the table comprises at least a first entry for a first node and a second entry for a second node, wherein the first node has a first node text value but does not have any descendant nodes, and wherein the second node has a second node text value and has one or more descendant nodes;

wherein the first entry for the first node comprises the first node text value;

wherein the second entry for the second node comprises a null node text value;

the table further comprising a third entry comprising the second node text value; and

storing an index of the node text values stored in the entries of the table.

12. The volatile or non-volatile computer-readable storage medium of claim 11, wherein said node text values are stored in a column of said table, said column being of a character large object type.

13. The volatile or non-volatile computer-readable storage medium of claim 11, wherein execution of the one or more sequences of instruction by the one or more processors further causes the one or more processors to perform:

receiving a query that requires a text search of the one or more XML documents; and

rewriting said query to produce a rewritten query, wherein said rewritten query is evaluated against the index.

14. The volatile or non-volatile computer-readable storage medium of claim 11, wherein execution of the one or more sequences of instruction by the one or more processors further causes the one or more processors to perform:

receiving a query that specifies certain criteria, said criteria comprising;

one or more particular node text values; and

one or more particular node names;

evaluating the query against the index.

15. The volatile or non-volatile computer-readable storage medium of claim 14, wherein at least one particular node text value of the one or more particular node text values span across node text values of two or more adjacent nodes, and wherein evaluating the query finds the at least one particular node text value in the two or more adjacent nodes.

16. The volatile or non-volatile computer-readable storage medium of claim 15, wherein the at least one particular node text value comprises a first part and a second part, wherein execution of the one or more sequences of instruction by the one or more processors further causes the one or more processors to perform searching for the first part in a first adjacent node and a second part in a second adjacent node to compute whether the at least one particular node text value exists in the node text values of the adjacent nodes.

17. The volatile or non-volatile computer-readable storage medium of claim 14, wherein execution of the one or more sequences of instruction by the one or more processors further causes the one or more processors to perform rewriting the query to search for one or more indications of the one or more particular node names.

18. A volatile or non-volatile computer-readable storage medium storing one or more sequences of instruction, wherein execution of the one or more sequences of instruction by one or more processors causes the one or more processors to perform:

receiving a query for specified text in one or more XML documents;

wherein said one or more XML documents comprise a plurality of nodes;

in response to receiving the query;

determining that the one or more XML documents are stored in a table comprising a plurality of rows, each row of said plurality of rows corresponding to a node of said plurality of nodes;

wherein each row of said plurality of rows includes;

an order key that indicates a hierarchical position of the node within the one or more XML documents, said order key being stored in a first column of said table; and

an indication of a name of the node, said indication stored in a second column of said table;

wherein the table comprises at least a first row for a first node and a second row for a second node, wherein the first node has a first node text value but does not have any descendant nodes, and wherein the second node has a second node text value and has one or more descendant nodes;

wherein the first row for the first node comprises the first node text value;

wherein the second row for the second node comprises a null node text value;

the table further comprising a third row comprising the second node text value; and

searching the node text values stored in the rows of the table for the specified text to determine at least one of a particular order key or a particular name of a particular node that contains the specified text;

wherein the method is performed by one or more computing devices.

19. The volatile or non-volatile computer-readable storage medium of claim 18, wherein execution of the one or more sequences of instruction by the one or more processors further causes determining whether a first part of the specified text exists in a first adjacent node of two or more adjacent nodes, and whether a second part of the specified text exists in a second adjacent node of two or more adjacent nodes.

20. The volatile or non-volatile computer-readable storage medium of claim 18, wherein execution of the one or more sequences of instruction by the one or more processors further causes rewriting the query to search for one or more order keys or node names.