Hybrid binary XML storage model for efficient XML processing

• US 10,055,128 B2
• Filed: 10/17/2015
• Issued: 08/21/2018
• Est. Priority Date: 01/20/2010
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Idicula, Sam, Sthanikam, Balasubramanyam, Agarwal, Nipun
• Primary Examiner(s): Waldron, Scott A.
• Assistant Examiner(s): Mina, Fatima P
• Application Number:
  US14/886,031
• Publication Number:
  US 20160042086A1
• Time in Patent Office: 1,039 Days
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/8373 Query execution
• CPC Class Codes: G06F 16/986 Document structures and storage, e.g. HTML extensions
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/146 Coding or compression of tree-structured data
• CPC Class Codes: G06F 40/149 Adaptation of the text data for streaming purposes, e.g. Efficient XML Interchange [EXI] format

Abstract

A method for storing XML documents a hybrid navigation/streaming format is provided to allow efficient storage and processing of queries on the XML data that provides the benefits of both navigation and streaming and ameliorates the disadvantages of each. Each XML document to be stored is independently analyzed to determine a combination of navigable and streamable storage format that optimizes the processing of the data for anticipated access patterns.

Claims

1. A method for determining a storage representation for nodes within an eXtensible Markup Language (XML) document, the method comprising:

for each node in said nodes within the XML document,

determining a storage representation for said each node based at least on characteristics of a sub-tree rooted at said each node;

wherein determining the storage representation for said each node further comprises;

determining whether the characteristics of the sub-tree rooted at said each node meet a first criterion; and

in response to determining that the characteristics of the sub-tree rooted at said each node meet the first criterion, determining to store said each node in navigable storage;

wherein storing said each node in the navigable storage causes said each node to be stored in a navigable representation of said each node, the navigable representation of said each node includes at least one pointer to another node in the navigable storage,

said at least one pointer to the other node in the navigable storage being one of;

 

a pointer to a parent node of said each node,

 

a pointer to a child node of said each node,

 

a pointer to a sibling node of said each node, or

 

a pointer to a previous sibling node of said each node;

in response to determining that the characteristics of the sub-tree rooted at said each node do not meet the first criterion, determining to store said each node in streamable storage;

wherein storing said each node in the streamable storage causes said each node to be stored in a document order of the XML document;

wherein the steps of the method are performed by one or more computing devices.

2. The method of claim 1, wherein determining whether the characteristics of the sub-tree rooted at said each node meet the first criterion includes:

determining whether a suitability metric evaluated over the sub-tree rooted at said each node exceeds a threshold value.

3. The method of claim 2, wherein the suitability metric is based at least on a number of nodes contained in the sub-tree and an amount of space occupied by content of the sub-tree.

4. The method of claim 2, wherein the suitability metric is based at least on one of a processing speed or I/O speed of a computer.

5. The method of claim 2, wherein the threshold value is manually configured.

6. The method of claim 2, further comprising automatically determining the threshold value based on evaluating historical query access patterns and characteristics of nodes of a collection of documents that were accessed in the historical query access patterns.

7. The method of claim 2, further comprising automatically determining the threshold value based on capabilities of a computer that stores the XML document.

8. The method of claim 2, wherein the suitability metric is based at least on a number of nodes contained in the sub-tree.

9. The method of claim 2, wherein the suitability metric is based at least on an amount of space occupied by content of the sub-tree.

10. The method of claim 1, wherein determining the storage representation for said each node includes:

determining whether the characteristics of the sub-tree rooted at said each node meet a second criterion; and

in response to determining that the characteristics of the sub-tree rooted at said each node meet the second criterion and do not meet the first criterion, determining to store said each node in the streamable storage.

11. The method of claim 10, wherein determining whether the characteristics of the sub-tree rooted at said each node meet the second criterion includes:

determining whether a percentage of full retrieval of the sub-tree rooted at said each node exceeds a threshold value.

12. One or more non-transitory computer-readable media storing instructions, wherein the instructions include:

instructions which, when executed by one or more hardware processors, cause, for each node in nodes within an eXtensible Markup Language (XML) document,

determining a storage representation for said each node based at least on characteristics of a sub-tree rooted at said each node;

wherein determining the storage representation for said each node further comprises;

determining whether the characteristics of the sub-tree rooted at said each node meet a first criterion; and

in response to determining that the characteristics of the sub-tree rooted at said each node meet the first criterion, determining to store said each node in navigable storage;

wherein storing said each node in the navigable storage causes said each node to be stored in a navigable representation of said each node, the navigable representation of said each node includes at least one pointer to another node in the navigable storage,

said at least one pointer to the other node in the navigable storage being one of;

 

a pointer to a parent node of said each node,

 

a pointer to a child node of said each node,

 

a pointer to a sibling node of said each node, or

 

a pointer to a previous sibling node of said each node;

in response to determining that the characteristics of the sub-tree rooted at said each node do not meet the first criterion, determining to store said each node in streamable storage;

wherein storing said each node in the streamable storage causes said each node to be stored in a document order of the XML document.

13. The one or more non-transitory computer-readable media of claim 12, wherein the instructions further include instructions which, when executed by one or more hardware processors, cause determining whether a suitability metric evaluated over the sub-tree rooted at said each node exceeds a threshold value.

14. The one or more non-transitory computer-readable media of claim 13, wherein the suitability metric is based at least on a number of nodes contained in the sub-tree and an amount of space occupied by content of the sub-tree.

15. The one or more non-transitory computer-readable media of claim 13, wherein the suitability metric is based at least on one of a processing speed or I/O speed of a computer.

16. The one or more non-transitory computer-readable media of claim 13, wherein the threshold value is manually configured.

17. The one or more non-transitory computer-readable media of claim 13, wherein the instructions further include instructions which, when executed by one or more hardware processors, cause automatically determining the threshold value based on evaluating historical query access patterns and characteristics of nodes of a collection of documents that were accessed in the historical query access patterns.

18. The one or more non-transitory computer-readable media of claim 13, wherein the instructions further include instructions which, when executed by one or more hardware processors, cause automatically determining the threshold value based on capabilities of a computer that stores the XML document.

19. The one or more non-transitory computer-readable media of claim 13, wherein the suitability metric is based at least on a number of nodes contained in the sub-tree.

20. The one or more non-transitory computer-readable media of claim 13, wherein the suitability metric is based at least on an amount of space occupied by content of the sub-tree.

21. The one or more non-transitory computer-readable media of claim 12, wherein the instructions further include instructions which, when executed by one or more hardware processors, cause:

determining whether the characteristics of the sub-tree rooted at said each node meet a second criterion; and

in response to determining that the characteristics of the sub-tree rooted at said each node meet the second criterion and do not meet the first criterion, determining to store said each node in the streamable storage.

22. The one or more non-transitory computer-readable media of claim 21, wherein the instructions further include instructions which, when executed by one or more hardware processors, cause determining whether a percentage of full retrieval of the sub-tree rooted at said each node exceeds a threshold value.