Hybrid binary XML storage model for efficient XML processing

• US 10,191,656 B2
• Filed: 10/17/2015
• Issued: 01/29/2019
• 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,032
• Publication Number:
  US 20160041763A1
• Time in Patent Office: 1,200 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 adding nodes to navigable storage, the method comprising:

parsing an XML document of a plurality of XML documents;

in response to parsing the XML document, receiving a first token from the XML document;

determining that the first token is a start of a first XML element;

allocating a first amount of space within navigable storage for a first node that represents the first XML element;

receiving a second token from the XML document;

determining whether the second token represents a start of a second XML element or represents an end of the first XML element,

if the second token is determined to represent the start of the second XML element, allocating a second amount of space within the navigable storage for a second node;

if the second token is determined to represent the end of the first XML element;

determining whether to store the first node in the navigable storage, and

in response to determining not to store the first node in the navigable storage, deallocating said first amount of space within the navigable storage;

wherein the navigable storage stores a node in a navigable representation of said node, the navigable representation of said 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 node,

a pointer to a child node of said node,

a pointer to a sibling node of said node, or

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

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

2. The method of claim 1, further comprising:

receiving a third token that is an end of the second XML element; and

determining that the second node should be stored in the navigable storage.

3. The method of claim 1, wherein determining whether to store the first node in the navigable storage is based in part on evaluating data stored within the first node.

4. The method of claim 3, wherein the data stored in the first node includes a count of a number of nodes in a sub-tree rooted at the first node and an amount of disk space needed to represent a streaming representation of said first node.

5. The method of claim 1, further comprising:

updating data in the first node to include a count for a number of nodes and a size of a sub-tree for said second node.

6. The method of claim 1, wherein determining whether to store the first node in the navigable storage includes:

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

7. The method of claim 1, wherein determining whether to store the first node in the navigable storage includes:

determining whether a child node of the first node is stored in the navigable storage.

8. The method of claim 1, further comprising:

in response to determining that the first token is the start of the first XML element, allocating a first amount of stack space for the first node, the first amount of stack space storing at least one of;

a pointer to the first amount of space within the navigable storage for the first node;

a pointer to the second amount of space within the navigable storage for the second node, wherein the second node is a child node of the first node;

a pointer to the second amount of space within the navigable storage for the second node, wherein the second node is a sibling node of the first node;

a pointer to the second amount of space within the navigable storage for the second node, wherein the second node is a parent node of the first node;

a count for a number of nodes contained in a sub-tree rooted at the first node;

or

a size of the sub-tree rooted at the first node.

9. The method of claim 8, further comprising:

in response to determining that the second token represents the start of the second XML element, allocating a second amount of stack space for the second node.

10. The method of claim 8, further comprising:

in response to determining that the second token represents the start of the second XML element, incrementing the count for the number of nodes contained in the sub-tree rooted at the first node.

11. The method of claim 1, further comprising:

in response to receiving the second token from the XML document and in response to determining that the second token represents the end of the first XML element, allocating an amount of space within streamable storage for contents of the first node.

12. The method of claim 1, further comprising:

in response to determining not to store the first node in the navigable storage, allocating a first amount of space within streamable storage for the first node.

13. The method of claim 12, further comprising:

creating a dummy node in the navigable storage with a pointer to point to a start of the first amount of space within the streamable storage for the first node.

14. The method of claim 12, further comprising:

creating a back pointer, within the streamable storage at an end of the first amount of space within the streamable storage, to point to an end of the second amount of space within navigable storage for the second node.

15. The method of claim 14, further comprising:

in response to determining that the second node should be stored in the navigable storage, modifying the back pointer to point to a start of the second amount of space within the navigable storage for the second node.

16. 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:

parsing an XML document of a plurality of XML documents;

in response to parsing the XML document, receiving a first token from the XML document;

determining that the first token is a start of a first XML element;

allocating a first amount of space within navigable storage for a first node that represents the first XML element;

receiving a second token from the XML document;

determining whether the second token represents a start of a second XML element or represents an end of the first XML element;

if the second token is determined to represent the start of the second XML element, allocating a second amount of space within the navigable storage for a second node;

if the second token is determined to represent the end of the first XML element;

determining whether to store the first node in the navigable storage, and

in response to determining not to store the first node in the navigable storage, deallocating said first amount of space within the navigable storage; and

wherein the navigable storage stores a node in a navigable representation of said node, the navigable representation of said 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 node,

a pointer to a child node of said node,

a pointer to a sibling node of said node, or

a pointer to a previous sibling node of said node.

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

receiving a third token that is an end of the second XML element; and

determining that the second node should be stored in the navigable storage.

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

determining whether to store the first node in the navigable storage based in part on evaluating data stored within the first node.

19. The one or more non-transitory computer-readable media of claim 18, wherein the data stored in the first node includes a count of a number of nodes in a sub-tree rooted at the first node and an amount of disk space needed to represent a streaming representation of said first node.

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

updating data in the first node to include a count for a number of nodes and a size of a sub-tree for said second node.

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

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

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

determining whether a child node of the first node is stored in the navigable storage.

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

in response to determining that the first token is the start of the first XML element, allocating a first amount of stack space for the first node, the first amount of stack space storing at least one of;

a pointer to the first amount of space within the navigable storage for the first node;

a pointer to the second amount of space within the navigable storage for the second node, wherein the second node is a child node of the first node;

a pointer to the second amount of space within the navigable storage for the second node, wherein the second node is a sibling node of the first node;

a pointer to the second amount of space within the navigable storage for the second node, wherein the second node is a parent node of the first node;

a count for a number of nodes contained in a sub-tree rooted at the first node;

or

a size of the sub-tree rooted at the first node.

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

in response to determining that the second token represents the start of the second XML element, allocating a second amount of stack space for the second node.

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

in response to determining that the second token represents the start of the second XML element, incrementing the count for the number of nodes contained in the sub-tree rooted at the first node.

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

in response to receiving the second token from the XML document and in response to determining that the second token represents the end of the first XML element, allocating an amount of space within streamable storage for contents of the first node.

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

in response to determining not to store the first node in the navigable storage, allocating a first amount of space within streamable storage for the first node.

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

creating a dummy node in the navigable storage with a pointer to point to a start of the first amount of space within streamable storage for the first node.

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

creating a back pointer, within the streamable storage at an end of the first amount of space within the streamable storage, to point to an end of the second amount of space within navigable storage for the second node.

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

in response to determining that the second node should be stored in the navigable storage, modifying the back pointer to point to a start of the second amount of space within the navigable storage for the second node.