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

• US 9,436,779 B2
• Filed: 11/17/2006
• Issued: 09/06/2016
• Est. Priority Date: 11/17/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Liu, Zhen Hua, Krishnaprasad, Muralidhar, Chang, Hui Joe, Arora, Vikas
• Primary Examiner(s): ADAMS, CHARLES D
• Application Number:
  US11/601,146
• Publication Number:
  US 20080120321A1
• Time in Patent Office: 3,581 Days
• Field of Search: None
• US Class Current: 1/1
• 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 computer-implemented method comprising:

causing execution of an index generation statement identifying a plurality of path expressions and a plurality of columns of a first table for indexing a collection of documents, wherein said plurality of path expressions identify less than all nodes in the collection of documents;

wherein for each column of said plurality of columns, said index generation statement specifies an association between said each column and a respective path expression of said plurality of path expressions;

wherein execution of said index generation statement causes generation of said first table, wherein the first table comprises a first set of entries;

wherein for each column of the plurality of columns of said first table, each entry of the first set of entries contains a node value of a node identified by the respective path expression of said each column, said node value being from a document of said collection of documents;

wherein the collection of documents is also indexed by a second table, wherein the second table comprises a second set of entries, each entry in the second set of entries;

being associated with a given node of a document in the collection of documents, and

including location data for locating content in the document, wherein the content is associated with the given node and path data that corresponds to a path to the given node in the document;

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

wherein the query for first information does not reference said first table and said second table;

said database system rewriting the query for first information to generate a rewritten query that references said first table and said second table;

wherein the query comprises one or more predicates;

based on the rewritten query, said database system 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 that contain a node value that satisfies the one or more predicates;

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

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

wherein the first table and the second table are two different tables.

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 the secondary index is a document identifier column.

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

6. The method of claim 1, further

generating one or more different query plans 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 document in the collection of documents is stored in aggregate storage.

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

10. The method of claim 1, wherein at least one document in the collection of 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. The method of claim 1, further comprising generating the first table using a data definition language statement.

15. A volatile or non-volatile computer-readable medium storing one or more sequences of instructions which, when executed by one or more processors, cause:

executing an index generation statement identifying a plurality of path expressions and a plurality of columns of a first table for indexing a collection of documents wherein said plurality of path expressions identify less than all nodes in the collection of documents

wherein for each column of said plurality of columns, said index generation statement specifies an association between said each column and a respective path expression of said plurality of path expressions;

wherein execution of said index generation statement causes generation of said first table, wherein the first table comprises a first set of entries;

wherein for each column of the plurality of columns of said first table, each entry of the first set of entries contains a node value of a node identified by the respective path expression of said each column, said node value being from a document of said collection of documents;

wherein the collection of documents is also indexed by a second table, wherein the second table comprises a second set of entries, each entry in the second set of entries;

being associated with a given node of a document in the collection of documents, and

including location data for locating content in the document, wherein the content is associated with the given node and path data that corresponds to a path to the given node in the document; and

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

wherein the query for first information does not reference said first table and said second table;

said database system rewriting the query for first information to generate a rewritten query that references said first table and said second table;

wherein the query comprises one or more predicates;

based on the rewritten query, said database system 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 that contain a node value that satisfies the one or more predicates;

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

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

wherein the first table and the second table are two different tables.

16. The medium of claim 15, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, causes the one or more processors to perform building a secondary index for one or more columns in the plurality of columns in the first table.

17. The medium of claim 15, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, causes the one or more processors to perform a joining of the first table and the second table based on one or more columns indexed by a secondary index.

18. The medium of claim 17, wherein one of the one or more columns indexed by the secondary index is a document identifier column.

19. The medium of claim 17, wherein the one or more columns indexed by the secondary index comprise hierarchical order information.

20. The medium of claim 15, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, causes the one or more processors to perform:

generating one or more different query plans 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.

21. The medium of claim 15, 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.

22. The medium of claim 15, wherein at least one document in the collection of documents is stored in aggregate storage.

23. The medium of claim 15, wherein at least one document in the collection of documents is stored object-relationally.

24. The medium of claim 15, wherein at least one document in the collection of documents is stored in a tree form.

25. The medium of claim 15, wherein one of the plurality of columns is a virtual column.

26. The medium of claim 15, wherein a column from the plurality of columns maps to two or more nodes.

27. The medium of claim 15, 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.

28. The medium of claim 15, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, causes the one or more processors to perform generating the first table using a data definition language statement.