Techniques of efficient XML query using combination of XML table index and path/value index

• US 20080120321A1
• Filed: 11/17/2006
• Published: 05/22/2008
• Est. Priority Date: 11/17/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Arora, Vikas, Chang, Hui Joe, Krishnaprasad, Muralidhar, Liu, Zhen Hua
• Granted Patent: US 9,436,779 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/24542 Plan optimisation
• 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

Abstract

A mechanism is provided for accessing XML data in a database system using a combination of a XML Table Index table and a XML Path Index table. By using a combination of a XML Table Index and a XML Path Index, both selection access and navigational access involved in a query can be optimized. For example, the XML Table Index gives the database system an ability to readily evaluate the predicate expression, thereby improving the selection access. Moreover, in some embodiments, the selection access can be further improved by using secondary indexes on columns contained in the XML Table Index table. In a complementary manner, the XML Path Index table gives the database system an ability to navigate to a specific location given a path expression, thereby improving the navigational access. Thus, by combining both tables, both selection and navigational accesses are improved.

Claims

1. A method comprising performing a machine-executed operation involving instructions, wherein said instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform certain steps including:

intercepting, by a database system, a query for first information from the collection of XML documents,

wherein the collection of XML documents is stored in one or more data structures in the database system and indexed by a first table and a second table;

wherein the first table comprises a plurality of columns, each column of the plurality of columns being associated with one or more criteria and containing values of nodes which nodes (i) are in the collection of XML documents and (ii) satisfy one or more criteria;

wherein the second table comprises a set of entries, each entry in the set of entries being associated with a given node and including location data for locating XML content associated with the given node and path data that corresponds to a path, through the structure of the XML document that contains the given node, to the given node; and

wherein the query comprises a plurality of predicates, which plurality of predicates can be evaluated using the values of nodes contained in the plurality of columns in the first table; and

generating a first query plan using both the first table and the second table,

wherein the first query plan, when executed by the database system, causes the database system to perform;

identifying one or more first entries from the first table, each of the one or more first entries from the first table satisfying the plurality of predicates;

identifying second information from the one or more first entries identified from the first table;

extracting the first information from one or more second entries in the second table using the second information;

wherein the machine-executed operation is at least one of (a) sending said instructions over transmission media, (b) receiving said instructions over transmission media, (c) storing said instructions onto a machine-readable storage medium, and (d) executing the instructions.

2. The method of claim 1, further comprising building a secondary index for one or more columns in the plurality of columns in the first table.

3. The method of claim 1, further comprising performing a joining of the first table and the second table based on one or more columns indexed by a secondary index.

4. The method of claim 3, wherein one of the one or more columns indexed by a secondary index is a document identifier column.

5. The method of claim 3, wherein the one or more columns indexed by a secondary index comprise hierarchical order information.

6. The method of claim 1, further

rewriting the first query plan and identifying one or more different query plans with or without accessing both said first table and the second table;

and

determining cost information for each of the first query plan and the one or more different query plans; and

selecting a second query plan among the first query plan and the one or more different query plans using the cost information based on a set of selection criteria.

7. The method of claim 1, wherein the first table includes one or more references to a set of additional tables, and wherein the one or more references to the set of additional tables create a table chain.

8. The method of claim 1, wherein at least one XML document in the collection of XML documents is stored in aggregate storage.

9. The method of claim 1, wherein at least one XML document in the collection of XML documents is stored object-relationally.

10. The method of claim 1, wherein at least one XML document in the collection of XML documents is stored in a tree form.

11. The method of claim 1, wherein one of the plurality of columns is a virtual column.

12. The method of claim 1, wherein a column from the plurality of columns maps to two or more nodes.

13. The method of claim 1, wherein the first table includes at least one column of the plurality of columns that stores node hierarchical order information projected by a row pattern.

14. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

15. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

16. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

17. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

18. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

19. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

20. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

21. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

22. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

23. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

24. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

25. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

26. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.