Efficient partitioning technique while managing large XML documents

CROSS REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of priority to U.S. Provisional Patent Application No. 60/829,652 filed on Oct. 16, 2006, entitled “ENHANCEMENTS FOR PROCESSING XML DATA” which is incorporated by reference in its entirety for all purposes as if originally set forth herein.

FIELD OF THE INVENTION

The present invention relates to managing XML content within a database, and more specifically to queries on that XML content.

BACKGROUND

The Extensible Markup Language (XML) is the standard for data and documents that is finding wide acceptance in the computer industry. XML describes and provides structure to a body of data, such as a file or data packet, referred to herein as an XML entity. The XML standard provides for tags that delimit sections of an XML entity referred to as XML elements. Each XML element may contain one or more name-value pairs referred to as attributes.

By defining an element that contains attributes and descendant elements, the XML entity defines a hierarchical tree relationship between the element, its descendant elements, and its attribute. A set of elements that have such a hierarchical tree relationship is referred to herein as an XML document.

An important standard for XML is the XQuery 1.0 and XPath 2.0 Data Model. (see W3C Candidate Recommendation 8 Jun. 2006, which is incorporated herein by reference). One aspect of this model is that a XML data is represented by a hierarchy of nodes that reflects the hierarchical nature of the XML data. A hierarchy of nodes is composed of nodes at multiple levels. The nodes at each level are each linked to one or more nodes at a different level. Each node at a level below the top level is a child node of one or more of the parent nodes at the level above. Nodes at the same level are sibling nodes. In a tree hierarchy or node tree, each child node has only one parent node, but a parent node may have multiple child nodes. In a tree hierarchy, a node that has no parent node linked to it is the root node, and a node that has no child nodes linked to it is a leaf node. A tree hierarchy has a single root node.

In a node tree that represents an XML document, a node can correspond to an element, the child nodes of the node correspond to an attribute or another element contained in the element. The node may be associated with a name and value.

It is important for object-relational database systems that store XML documents to be able to execute queries using XML query languages, such as XQuery/XPath. XML Query Language (“XQuery”) and XML Path Language (“XPath”) are important standards for a query language, which can be used in conjunction with SQL to express a large variety of useful queries. XPath is described in <i>XML Path Language </i>(<i>XPath</i>), version 1.0 (W3C Recommendation 16 Nov. 1999), which is incorporated herein by reference. XPath 2.0 and XQuery 1.0 are described in XQuery 1.0 and XPath 2.0 Full-Text. (W3C Working Draft 9 Jul. 2004), which is incorporated herein by reference.

Various types of storage mechanisms are used to store an XML document in a serialized form. XMLType is a data type used to store XML content on database systems. XML documents stored as an XMLType allows developers to manipulate XML content using built-in functions. One type of storage mechanism stores an XML document as a text file in a file system. This is based on the form of a CLOB, or character large object, storing the actual XML text.

Another type of storage mechanism uses object-relational database systems that have been enhanced to store and query XML documents. In an embodiment, an XML document is stored in a row of a table and nodes of the XML document are stored in separate columns in the row. An XML document may also be stored as a hierarchy of objects in an object-relational database; each object is an instance of an object class and stores one or more elements of an XML document. The object class defines, for example, the structure corresponding to an element, and includes references or pointers to objects representing the immediate descendants of the element. Tables and/or objects of a database system that hold XML values are referred to herein as base tables or objects.

An XML document may also be stored as a binary representation. This is stored as a BLOB, or binary large object, in some binary form of the XML. Storing the XML document in binary form is an efficient form of data storage because it allows for quick access and processing by the database server. Tables containing binary XML columns can be partioned based on a value in the XML document.

XML documents may be stored in a table that is divided into partitions. In partitioning, an object, such as a database table, is divided up into sub-tables, referred to as “partitions”. For various reasons, partitioning allows data stored in the object to be accessed more efficiently. Unfortunately, when storing an XML document in a partitioned table, the entire XML document must be stored in a buffer to determine the certain partition in which the XML document is stored. This overhead may be avoided by storing the XML document in a non-partitioned object, but at the cost of losing the advantage of being able to access data more efficiently in a partitioned table. Clearly, there is a need to store data in a partition in a way that avoids this sort of overhead.

The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.

DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of an embodiment of the invention displaying an XML document being stored in a partitioned table of a database system.

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of a computer system on which embodiments of the invention may be implemented.

DETAILED DESCRIPTION

In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

According to an embodiment, an XML document is read into a buffer until information sufficient to determine what partition to store an XML document is encountered. Once the determination is made, the portions of the XML document already and subsequently read are stored in the partition. This measure eliminates the need to read and store the complete XML document in a buffer before storing the XML document in a partition. The information in an XML document used to determine which partition to store the XML document is referred to herein as partition key data. In an embodiment, the partition key data resides near the beginning of an XML document. Thus, only a relatively small portion of XML documents need be read before storing the XML document in a partition.

Partitioning

As mentioned previously, database partitioning improves the search efficiency of the database system in certain situations by avoiding the need to search an entire table. With database partitioning, an object, such as a database table, is divided up into sub-tables, referred to as “partitions”. The particular partition in which a row or object is stored depends on values in one or more columns of the table. These columns are referred to herein as partition keys and the values contained in them are referred to as partition key values.

The most common form of partitioning is referred to as range partitioning. With range partitioning, each individual partition corresponds to a certain range of partition key values. For example, a partition key of a table may store date values that fall within a certain year, and the table may be divided into twelve partitions, each of which corresponds to a month of that year. Rows with a date value that fall within a certain month are stored in the partition that corresponds to that month.

Another form of partitioning is referred to as hash partitioning. In hash partitioning, one or more values in partition keys are applied to a hash function to produce a hash value. A separate partition is established for a hash function value produced by the hash function, and rows having a partition key value that evaluates to that hash function value are stored within the partition.

Partition Key Data

Partition key data is in the XML document that is a partition key value or is data from which a partition key value is derived. For XML documents stored in a database system, the partition key can be expressed as an expression based on partition key data in an XML document. Such an expression is referred to herein as a key expression. Typically, a key expression uses XML operators. An example of such is: extractValue(object_value, ‘/PurchaseOrder/Reference’)

This expression gives the value of the XML element at the XPath ‘/PurchaseOrder/Reference’ in the given document. To evaluate a key expression, the entire document may be read and stored in a buffer to evaluate the key expression. This results in reading the XML document twice from its source, once for determining the partition key value and the second to store the XML document in a partition. This leads to serious performance degradation. It may also not be possible to read the document twice from its loading source due to complications from the network connection. <br /> Streaming Evaluation

Streaming evaluation is one of several ways of evaluating an XPath expression. Streaming evaluation refers to techniques for transferring data such that the data can be processed as a steady and continuous stream, and keeping only minimal state information about the part of the document that was read. In addition to evaluating each expression separately, it is possible to evaluate a set of expressions on the same document using a single pass over the document using the streaming evaluation technique.

According to an embodiment, partition key data generally appears near the beginning of the XML document and the key expressions are relatively simple. In an embodiment of the invention, key expressions are evaluated using streaming evaluation where only the part of the document from the beginning until the occurrence of the partition key data is read. Under streaming evaluation, certain types of simple key expressions can be evaluated by reading the document serially. Furthermore, only minimal state information about the part of the XML document read is stored to increase efficiency.

In an embodiment of the invention, during streaming evaluation, once a result for a key expression has been obtained, the evaluation stops. This enhancement is performed by reading each chunk of data as it is received from the source. The size of the data chunk varies from implementation to implementation, and can change based upon the availability of memory. The partition key expression is then evaluated to determine if a result can be obtained.

This technique significantly reduces the cost of the evaluation due to two reasons. The I/O cost, or cost to read and store the data, is reduced because only a part of the document is read to perform the evaluation. For example, previously the XML document had to be read in its entirety two times, once for expression evaluation of the partition key value and once to store the XML document in the partition. The CPU cost is reduced because streaming evaluation is less taxing than other types of evaluation. For instance, in DOM or domain object model streaming, the entire XML document must be constructed into a DOM tree utilizing far more CPU resources.

When Streaming Evaluation is Unavailable

There are instances when the evaluation for the partition key is too complex to be performed using streaming evaluation. When this occurs, XML documents are converted into a DOM-based tree model which is an in-memory hierarchical representation of the XML document. The DOM-based tree model can then be traversed to retrieve and evaluate elements based on the XPath expression. This requires reading the entire XML document and storing it in the buffer and then building the DOM tree model node by node. The buffer of the database system includes all temporary storage memory in the buffer including volatile and non-volatile memory.

In an embodiment of the invention, the DOM tree model is built in a streaming manner incrementally. Thus, as the XML document is being read, the DOM tree model is built incrementally and the entire document need not be read before constructing the DOM tree model. This enhancement occurs because after reading each chunk of data from the source, the expression is evaluated by assuming that all ancestor elements, or those elements from which the present element descends, end after the last fully formed element. Then, as soon as a result is obtained, the evaluation is stopped.

This method increases efficiency because multiple passes are not used when reading and evaluating the XML document. Furthermore, the evaluation for the key expression usually occurs more quickly.

Storing in the Partition

In another embodiment, as the XML document is being read by the database server to evaluate the key expression, the XML document is stored in the buffer. The buffer includes all temporary storage memory in the buffer including volatile and non-volatile memory.

Once the partition key value is determined, the document is written to the target partition. In an embodiment of the invention, the database server is aware of the portion of the XML document that is stored in the buffer and the portion yet to be read from the original source. The database server retrieves the portion of the XML document stored in the buffer and the unread portion of the XML document from the original source to write to the partition. This reduces the I/O costs of the database system because the entire XML document is no longer re-read from the original source.

In another embodiment, the database system stores the XML document in the volatile buffer and the non-volatile buffer separately. Only when the XML document exceeds memory limits of the volatile buffer does the database server use the non-volatile buffer to store the XML document. Portions of the XML document are now stored in the volatile buffer, the non-volatile buffer or yet to be read from the original source. The database server is aware of the sections of the XML document that are stored in the volatile buffer, the non-volatile buffer or yet to be read from the original source. The portions of the XML document already read are retrieved from the volatile buffer and non-volatile buffer and only the unread portion of the XML document is retrieved from the source and written to the partition.

Example of an Embodiment

<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram illustrating an embodiment of the invention. The figure presented only displays a single embodiment of the invention and an embodiment of the invention is not limited to this single embodiment. The embodiment consists of the XML Document <b>101</b> stored on the original source and the database system <b>102</b>. The database system <b>102</b> includes the database server <b>103</b> and database storage <b>104</b>. Within the database storage <b>104</b> is a database table <b>105</b>. The database table is partitioned into two partitions, partition A <b>106</b> and partition B <b>107</b>. Depending on the partition key value of the XML document <b>101</b>, the XML document may be stored in either of the two partitions.

A portion of the XML document is read <b>110</b> by the database server <b>103</b> whereupon the key expression is computed for the XML document. The database server computes the key expression using streaming evaluation. Should the key expression be too complex for streaming evaluation, then a DOM tree model is incrementally constructed until the expression is computed. In either case, once the key is evaluated and the resulting partition key value computed, evaluation is stopped before the entire XML document is read. The portions already read into the buffer are stored in the particular partition of the partition key value. Subsequently read portions of the XML document are stored in the partition. In this example, assume partition B <b>107</b> is the correct partition. Rather than re-reading the entire XML document from its original source, the portion of the XML document in the buffer <b>108</b> is stored <b>115</b> in partition B <b>107</b>. Any unread portion of the XML document that was not required to evaluate the key expression is read and stored from the original source <b>101</b> into partition B <b>107</b>.

Hardware Overview

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram that illustrates a computer system <b>200</b> upon which an embodiment of the invention may be implemented. Computer system <b>200</b> includes a bus <b>202</b> or other communication mechanism for communicating information, and a processor <b>204</b> coupled with bus <b>202</b> for processing information. Computer system <b>200</b> also includes a main memory <b>206</b>, such as a random access memory (RAM) or other dynamic storage device, coupled to bus <b>202</b> for storing information and instructions to be executed by processor <b>204</b>. Main memory <b>206</b> also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor <b>204</b>. Computer system <b>200</b> further includes a read only memory (ROM) <b>208</b> or other static storage device coupled to bus <b>202</b> for storing static information and instructions for processor <b>204</b>. A storage device <b>210</b>, such as a magnetic disk or optical disk, is provided and coupled to bus <b>202</b> for storing information and instructions.

Computer system <b>200</b> may be coupled via bus <b>202</b> to a display <b>212</b>, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device <b>214</b>, including alphanumeric and other keys, is coupled to bus <b>202</b> for communicating information and command selections to processor <b>204</b>. Another type of user input device is cursor control <b>216</b>, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor <b>204</b> and for controlling cursor movement on display <b>212</b>. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

The invention is related to the use of computer system <b>200</b> for implementing the techniques described herein. According to one embodiment of the invention, those techniques are performed by computer system <b>200</b> in response to processor <b>204</b> executing one or more sequences of one or more instructions contained in main memory <b>206</b>. Such instructions may be read into main memory <b>206</b> from another machine-readable medium, such as storage device <b>210</b>. Execution of the sequences of instructions contained in main memory <b>206</b> causes processor <b>204</b> to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

The term “machine-readable medium” as used herein refers to any medium that participates in providing data that causes a machine to operation in a specific fashion. In an embodiment implemented using computer system <b>200</b>, various machine-readable media are involved, for example, in providing instructions to processor <b>204</b> for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device <b>210</b>. Volatile media includes dynamic memory, such as main memory <b>206</b>. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus <b>202</b>. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications. All such media must be tangible to enable the instructions carried by the media to be detected by a physical mechanism that reads the instructions into a machine.

Common forms of machine-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, punchcards, papertape, any other physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave as described hereinafter, or any other medium from which a computer can read.

Various forms of machine-readable media may be involved in carrying one or more sequences of one or more instructions to processor <b>204</b> for execution. For example, the instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system <b>200</b> can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus <b>202</b>. Bus <b>202</b> carries the data to main memory <b>206</b>, from which processor <b>204</b> retrieves and executes the instructions. The instructions received by main memory <b>206</b> may optionally be stored on storage device <b>210</b> either before or after execution by processor <b>204</b>.

Computer system <b>200</b> also includes a communication interface <b>218</b> coupled to bus <b>202</b>. Communication interface <b>218</b> provides a two-way data communication coupling to a network link <b>220</b> that is connected to a local network <b>222</b>. For example, communication interface <b>218</b> may be an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface <b>218</b> may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface <b>218</b> sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link <b>220</b> typically provides data communication through one or more networks to other data devices. For example, network link <b>220</b> may provide a connection through local network <b>222</b> to a host computer <b>224</b> or to data equipment operated by an Internet Service Provider (ISP) <b>226</b>. ISP <b>226</b> in turn provides data communication services through the world wide packet data communication network now commonly referred to as the “Internet” <b>228</b>. Local network <b>222</b> and Internet <b>228</b> both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link <b>220</b> and through communication interface <b>218</b>, which carry the digital data to and from computer system <b>200</b>, are exemplary forms of carrier waves transporting the information.

Computer system <b>200</b> can send messages and receive data, including program code, through the network(s), network link <b>220</b> and communication interface <b>218</b>. In the Internet example, a server <b>230</b> might transmit a requested code for an application program through Internet <b>228</b>, ISP <b>226</b>, local network <b>222</b> and communication interface <b>218</b>.

The received code may be executed by processor <b>204</b> as it is received, and/or stored in storage device <b>210</b>, or other non-volatile storage for later execution. In this manner, computer system <b>200</b> may obtain application code in the form of a carrier wave.

In the foregoing specification, embodiments of the invention have been described with reference to numerous specific details that may vary from implementation to implementation. Thus, the sole and exclusive indicator of what is the invention, and is intended by the applicants to be the invention, is the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction. Any definitions expressly set forth herein for terms contained in such claims shall govern the meaning of such terms as used in the claims. Hence, no limitation, element, property, feature, advantage or attribute that is not expressly recited in a claim should limit the scope of such claim in any way. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.