Abstract:
A method and apparatus for accelerating value-based lookups of XML documents in XQuery is provided. XML indices can help to optimize SQL queries of XML documents stored in object-relational databases. Certain SQL/XML functions such as XMLTABLE( ) use XQuery expressions to query XML documents. Previously, such queries could not use the XML index because the PATH table of the XML index was not defined for XQuery semantics. Techniques described herein extend the XML index for use with queries that require evaluation of XQuery expressions. Consequently, techniques described herein accelerate value-based lookups of XML documents in XQuery by introducing the possibility of an index-assisted evaluation of XQuery expressions.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is related to U.S. Pat. No. 7,120,645 issued to Manikutty et al. (“Manikutty”), the entire contents of which are hereby incorporated by reference as if fully set forth herein. 
         [0002]    This application is related to U.S. patent application Ser. No. 10/884,311 by Chandrasekar et al. (“Chandrasekar”), the entire contents of which are hereby incorporated by reference as if fully set forth herein. 
     
    
     FIELD OF THE INVENTION 
       [0003]    The present invention relates to techniques for searching eXtensible Markup Language (XML) data maintained in a relational database system, and more specifically, for accelerating value-based XQuery lookups of XML documents stored in databases. 
       BACKGROUND 
       [0004]    Querying and searching information contained in XML documents that are stored within an object-relational database can be especially inefficient given certain queries. XML-aware indices, such as described in Chandrasekar, are available for providing quicker access to XML data in response to queries. Apart from XPath, XQuery is another XML query language that was developed for querying XML documents. The SQL/XML extension of SQL allows queries using XPath expressions to be evaluated on XML documents stored natively in a relational database system. 
         [0005]    An XML index may be composed of a PATH table and a set of secondary indices on the PATH table. The PATH table contains one row per indexed node of an XML document. Each column of the table contains information associated with the indexed nodes, like the paths of the nodes or the value of the nodes; secondary indices can be built on the columns. An example of a secondary index is a b-tree index on the value column of the PATH table, also referred to as a value index. The XML index may be accessed when a user submits a query referencing one or more XML documents. The query can be decomposed and re-written with expressions that use the PATH table in the manner described in Chandrasekar. 
         [0006]    An optimization engine may evaluate an expression using a secondary index in lieu of evaluating directly from the PATH table. A query that includes a value-based search is an example of a type of query that can be optimized by use of a secondary index. To search for a particular value within the XML document, a user may perform a linear search down the value column of the PATH table, performing as many comparisons as there are rows in the PATH table. Executing a search in this manner requires that each row is read from disk, a costly operation that should be minimized. Building a secondary index, like a b-tree index, on the value column would allow for index-based searching, thereby logarithmically reducing disk accesses for each search. 
         [0007]    XML indices are especially valuable for accelerating value-based XQuery lookups because determining the string value of a node in XQuery is an expensive operation. Since a value of a node in XQuery is defined as the concatenation of all descendant text nodes of the node, an entire section of the tree hierarchy below the target node in an XML document would need to be accessed and read from disk to determine the string value of a high level node in XQuery. 
         [0008]    While the benefit of using an XML index with a value-based query is clear, prior versions of the XML index are not optimized for value-based queries that use the semantics of XQuery. An XML index was previously defined only to store values of simple nodes (i.e., leaf nodes with no children nodes) in the value column of the PATH table, in accordance with the semantics of XPath. The value for complex nodes (i.e., nodes with one or more child nodes) in a PATH table is set to NULL. This is incompatible with the semantics of XQuery, which defines a value of a complex node as the concatenation of all descendant text nodes of the node. 
         [0009]    Based on the foregoing, it would be desirable to extend the PATH table infrastructure, especially the value column, to efficiently accommodate queries using XQuery. 
         [0010]    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. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0011]    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: 
           [0012]      FIG. 1  is a tree diagram representing the example XML document, “employees.xml.” 
           [0013]      FIG. 2  is a flowchart that represents a technique for extending a PATH table to be compatible with XQuery semantics by populating the value column for all nodes, both simple and complex, according to an embodiment of the invention. 
           [0014]      FIG. 3  is a flowchart that represents a technique for accelerating value-based lookup of XML documents in XQuery, according to an embodiment of the invention. 
           [0015]      FIG. 4  is a block diagram that illustrates a computer system upon which an embodiment of the invention may be implemented. 
       
    
    
     DETAILED DESCRIPTION 
       [0016]    Techniques for accelerating value-based lookups of XML documents in XQuery are described. 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. 
         [0017]    For the purpose of explanation, examples shall be given hereinafter with reference to the following XML document and PATH tables shown in TABLE 1 and TABLE 3, respectively: 
         [0000]    
       
         
               
             
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 employees.xml 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 &lt;Person id=“5000”&gt; 
               
               
                   
                  &lt;Name&gt; 
               
               
                   
                   &lt;regular&gt;Geoff &lt;/regular&gt; 
               
               
                   
                   &lt;bold&gt;Lee&lt;/bold&gt; 
               
               
                   
                  &lt;/Name&gt; 
               
               
                   
                  &lt;Address&gt;1014 Dietz Avenue&lt;/Address&gt; 
               
               
                   
                 &lt;/Person&gt; 
               
               
                   
                   
               
             
          
         
       
     
         [0018]    As shown in TABLE 1, “employees.xml” is an example of an XML document. The techniques described herein are not limited to XML documents having any particular types, structure, or content. The nodes of “employees.xml” are represented as a hierarchical tree in  FIG. 1 . 
         [0019]    For the purposes of explanation, the following examples of PathID-to-Path Mapping (TABLE 2) and the PATH table (TABLE 3) were generated based on the preceding XML document shown in TABLE 1. 
         [0000]    
       
         
               
             
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 PathID-to-Path Mapping 
               
             
          
           
               
                 PathID 
                 Path 
               
               
                   
               
               
                 1 
                 /Person 
               
               
                 2 
                 /Person/@id 
               
               
                 3 
                 /Person/Name 
               
               
                 4 
                 /Person/Name/regular 
               
               
                 5 
                 /Person/Name/bold 
               
               
                 6 
                 /Person/Address 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
               
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 PATH Table 
               
             
          
           
               
                 rowid 
                 rid 
                 PathID 
                 OrderKey 
                 Value 
                 Locator 
               
               
                   
               
               
                 1 
                 R1 
                 1 
                 1 
                 NULL 
                   
               
               
                 2 
                 R1 
                 2 
                 1.1 
                 5000 
               
               
                 3 
                 R1 
                 3 
                 1.2 
                 NULL 
               
               
                 4 
                 R1 
                 4 
                 1.2.1 
                 Geoff[ ] 
               
               
                 5 
                 R1 
                 5 
                 1.2.2 
                 Lee 
               
               
                 6 
                 R1 
                 6 
                 1.3 
                 1014 Dietz Avenue 
               
               
                   
               
             
          
         
       
     
         [0020]    Further details on implementing a PATH table can be found in Chandrasekar. In the following discussion, it will be assumed that “employees.xml” is stored in an object-relational database table called EMPLOYEES. The ‘rid’ column in the PATH table refers to a row in the base structure that is an object-relational table row containing the XML document “employees.xml.” 
       Value-Based Lookup in XQuery 
       [0021]    The following is an example of a value-based lookup of an XML document in XQuery and SQL that will be used to illustrate one embodiment of the invention. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 SELECT e.object_value 
               
               
                   
                 FROM EMPLOYEES e, 
               
               
                   
                  XMLTABLE(‘/Person/Name’ 
               
               
                   
                   PASSING e.object_value 
               
               
                   
                   COLUMNS 
               
               
                   
                    “Name” VARCHAR2(30) PATH ‘.’ 
               
               
                   
                   ) p 
               
               
                   
                 WHERE p.Name=“Geoff Lee” 
               
               
                   
                   
               
             
          
         
       
     
         [0022]    XMLTABLE is an example of a SQL/XML function that supports the embedding of XQuery to query XML documents that are stored natively in a relational database table. XMLTABLE returns the result in the same form as a relational database table so that it can be queried with SQL like other tables. In the above example, for each row in the passed-in table EMPLOYEES e, XMLTABLE evaluates the XQuery expression ‘/Person/Name’, which gives the row pattern for the rows of the table resulting from evaluating XMLTABLE. The XQuery expression‘.’ gives the column pattern for a column named “Name”, of SQL data type VARCHAR2, of the table resulting from evaluating XMLTABLE. Here, the result of evaluating the XQuery expression ‘/Person/Name’ is the value ‘Geoff Lee’, concatenated from the child nodes &lt;regular&gt;  109  and &lt;bold&gt;  113  of the node&lt;Name&gt;  107 . The FROM clause joins the table e with the table created by XMLTABLE, p. The query returns the rows of e from the column e.object_value having the XML document matching the SQL condition WHERE p.Name=“Geoff Lee”. 
         [0023]    Determining the string value for a node using XQuery requires that all nodes that are descendants of the target node are read from disk, which is a costly operation that should be minimized. Indexing all the concatenated string values for each node would require only one tree navigation when the index is first created; thereafter, value-based lookups can be achieved with the index without further navigation of the original XML document. 
         [0024]    Therefore, in one embodiment of the invention, a PATH table would store the value of each node in a separate row, thereby allowing the value to be retrieved more directly in fewer disk-read operations. To use the XML Index, the query submitted by a user is rewritten by the SQL engine at compile-time according to one of the methods described in Manikutty. More specifically, in one embodiment, XQuery operators that compute the value of the node are rewritten to use the value column of the PATH table. 
       Extending Path Table 
       [0025]    In prior approaches, the PATH table, which had been previously defined for XPath semantics, would not be correctly defined for evaluating XQuery expressions because the PATH table did not define values for all nodes as required by XQuery. In XQuery, the string value of a complex node is the concatenation of the string values of all of the complex node&#39;s descendant text nodes, in document order. Therefore, under XQuery semantics, the value of /Person/Name is “Geoff Lee,” concatenated from the child nodes &lt;regular&gt;  109  and &lt;bold&gt;  113  of the parent node &lt;Name&gt;  107 . In contrast, under XPath semantics, which formed the basis of the previous implementation of the PATH table, the value referenced by the XPath/Person/Name is NULL because the node is not a simple node. 
         [0026]    Therefore, in one embodiment of the invention, in order to use the PATH table in evaluating XQuery expressions, the PATH table infrastructure is extended to accommodate the XQuery definition for values. This is accomplished for one embodiment as shown in the flowchart shown in  FIG. 2 . In one embodiment, a database system stores an XML document as a relational database object (step  202 ). The database system creates an XML index on the XML document according to the method of Chandrasekar (step  204 ). In one embodiment, creation of an XML index includes creation of the relational database structure of a PATH table (step  206 ). 
         [0027]    Steps  208  populate the PATH table to extend the method of Chandrasekar according to XQuery semantics. For each row in the PATH table, it is determined whether the node that is referenced in that row is a simple node (step  210 ). For each simple node, the string value of the node is stored in the value column for that node&#39;s row in the PATH table (step  212 ). For each complex node, the value is determined from the concatenation of all the descendant text nodes of that complex node in document order (steps  214  and  216 ), and then stored in the value column of that complex node&#39;s row in the PATH table (step  218 ). 
         [0028]    TABLE 4 shows the extended PATH table of the XML index for employee.xml that supports XQuery evaluations: 
         [0000]    
       
         
               
             
               
               
               
               
               
               
             
           
               
                 TABLE 4 
               
             
             
               
                   
               
               
                 EXTENDED PATH TABLE 
               
             
          
           
               
                 Rowed 
                 rid 
                 PathID 
                 OrderKey 
                 Value 
                 Locator 
               
               
                   
               
               
                 1 
                 R1 
                 1 
                 1 
                 5000Geoff Lee1014 Dietz 
                   
               
               
                   
                   
                   
                   
                 Avenue 
               
               
                 2 
                 R1 
                 2 
                 1.1 
                 5000 
               
               
                 3 
                 R1 
                 3 
                 1.2 
                 Geoff Lee 
               
               
                 4 
                 R1 
                 4 
                 1.2.1 
                 Geoff[ ] 
               
               
                 5 
                 R1 
                 5 
                 1.2.2 
                 Lee 
               
               
                 6 
                 R1 
                 6 
                 1.3 
                 1014 Dietz Avenue 
               
               
                   
               
             
          
         
       
     
         [0029]    In one embodiment, in order to reduce the space overhead incurred by storing more non-null values in the value column, the value stored in step  218  for complex nodes is a prefix of the concatenation of step  216 . A prefix of a small size is chosen, such as 200 bytes. In practice, this does not constrain the use of the XML Index because users are unlikely to query string literals longer than 200 bytes, and because casts into the most commonly-available primitive types (such as integer, date, etc.) need only the first 200 bytes of the concatenated string. 
       Virtual Value Column 
       [0030]    In spite of storing in the value column only a prefix of a concatenated string for the value of a complex node in one embodiment, space overhead remains a challenge because a value of a text node is duplicated in the PATH table for the entries of each node along the text node&#39;s hierarchical path up to the root node. For example, in an embodiment, if “Geoff” were a text value corresponding to a node one hundred levels deep, then “Geoff” is duplicated one hundred times, once in each level of the path hierarchy for each intermediate node between the “Geoff” node and the root node. In TABLE 4, which represents the extended PATH table for XML document  101 , “Geoff” is duplicated three times in the value entries of Row 1, Row 3, and Row 4. In one embodiment, such space challenges are resolved by replacing the value column of the PATH table with a virtual column. 
         [0031]    In one embodiment, a virtual column does not have any physical presence on disk, but the virtual column can be queried by a user as if that column physically existed. Instead of storing many non-null values for all the nodes of a document in the PATH table, a new operator is evaluated at run-time to compute the value of any node as needed. For a simple node, the new operator returns a prefix of the node&#39;s string value. For a complex node, the new operator returns a prefix of the string obtained by concatenating, in document order, the string values of all the descendant simple nodes of the complex node. 
         [0032]    This method effectively trades space for extra expression evaluation costs. For infrequently-accessed XML documents, incurring the expression evaluation costs is more efficient in comparison to the cost of the storage space that would be required to support an extended PATH table for every XML document in a database. 
         [0033]    The virtual column framework ensures that the value column is not materialized in the table, but yet the value column remains available for defining secondary indices for frequently-accessed documents. In one embodiment, secondary indices are built on either a virtual value column or a physical value column of the new PATH table. Building a secondary index, like a b-tree index, on the value column would allow for index-based searching, thereby logarithmically reducing disk accesses for each search. Such a secondary value index may have keys comprising the concatenated string values of the complex nodes, as well as keys comprising the text values of simple nodes. The keys of the secondary index may be associated with the rowid of a row in the PATH table for nodes having that value. Type-aware secondary indices also may be built by creating appropriate functional indices on the value column, where the function is an appropriate cast operator. Such indices are further described in Chandrasekar. 
         [0034]    In one embodiment, the query optimization engine uses the secondary value index as much as possible to evaluate value-based lookups in XQuery. In one embodiment, the virtual column as evaluated during query run-time is used only when the query cannot use a secondary value index. 
       Accelerating Value-Based Lookup of XML Documents in XQuery 
       [0035]      FIG. 3  shows one embodiment of a technique for accelerating a value-based lookup of XML documents in XQuery. In one embodiment, a database system receives a query requiring a value-based lookup in XQuery (step  301 ). The database system rewrites the query according to one of the methods of Manikutty in order to use the XML Index infrastructure, including the PATH table and any secondary indices on a column of the PATH table, to evaluate the query (step  303 ). After determining that the query requires a value-based lookup, it is determined whether a secondary index exists on the value column of the PATH table (step  305 ). If a secondary value index exists, then the secondary value index is navigated to find the entry that has the value that is being searched, and the PATH table rowid that is paired with the value is identified (step  307 ). The node that is associated with the rowid is returned (step  309 ). 
         [0036]    If a secondary index does not exist on the value column of the PATH table, then the new virtual column operator is evaluated to retrieve the values of the nodes of the XML document (step  311 ). For each value retrieved, it is determined whether the value matches the value that is being searched (step  313 ), effectively in the same manner as in navigating a physical value column in a PATH table. If a match is found, then the node that corresponds to the row in the PATH table associated with the virtual value is returned (step  309 ). The process repeats until there are no more rows to evaluate (step  317 ). If there are no more rows, and no matches are found, then no nodes are returned (step  319 ). 
       Hardware Overview 
       [0037]      FIG. 4  is a block diagram that illustrates a computer system  400  upon which an embodiment of the invention may be implemented. Computer system  400  includes a bus  402  or other communication mechanism for communicating information, and a processor  404  coupled with bus  402  for processing information. Computer system  400  also includes a main memory  406 , such as a random access memory (RAM) or other dynamic storage device, coupled to bus  402  for storing information and instructions to be executed by processor  404 . Main memory  406  also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor  404 . Computer system  400  further includes a read only memory (ROM)  408  or other static storage device coupled to bus  402  for storing static information and instructions for processor  404 . A storage device  410 , such as a magnetic disk or optical disk, is provided and coupled to bus  402  for storing information and instructions. 
         [0038]    Computer system  400  may be coupled via bus  402  to a display  412 , such as a cathode ray tube (CRT), for displaying information to a computer user. An input device  414 , including alphanumeric and other keys, is coupled to bus  402  for communicating information and command selections to processor  404 . Another type of user input device is cursor control  416 , such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor  404  and for controlling cursor movement on display  412 . 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. 
         [0039]    The invention is related to the use of computer system  400  for implementing the techniques described herein. According to one embodiment of the invention, those techniques are performed by computer system  400  in response to processor  404  executing one or more sequences of one or more instructions contained in main memory  406 . Such instructions may be read into main memory  406  from another machine-readable medium, such as storage device  410 . Execution of the sequences of instructions contained in main memory  406  causes processor  404  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. 
         [0040]    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  400 , various machine-readable media are involved, for example, in providing instructions to processor  404  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  410 . Volatile media includes dynamic memory, such as main memory  406 . Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus  402 . 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. 
         [0041]    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. 
         [0042]    Various forms of machine-readable media may be involved in carrying one or more sequences of one or more instructions to processor  404  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  400  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  402 . Bus  402  carries the data to main memory  406 , from which processor  404  retrieves and executes the instructions. The instructions received by main memory  406  may optionally be stored on storage device  410  either before or after execution by processor  404 . 
         [0043]    Computer system  400  also includes a communication interface  418  coupled to bus  402 . Communication interface  418  provides a two-way data communication coupling to a network link  420  that is connected to a local network  422 . For example, communication interface  418  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  418  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  418  sends and receives electrical, electro-magnetic or optical signals that carry digital data streams representing various types of information. 
         [0044]    Network link  420  typically provides data communication through one or more networks to other data devices. For example, network link  420  may provide a connection through local network  422  to a host computer  424  or to data equipment operated by an Internet Service Provider (ISP)  426 . ISP  426  in turn provides data communication services through the world wide packet data communication network now commonly referred to as the “Internet”  428 . Local network  422  and Internet  428  both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link  420  and through communication interface  418 , which carry the digital data to and from computer system  400 , are exemplary forms of carrier waves transporting the information. 
         [0045]    Computer system  400  can send messages and receive data, including program code, through the network(s), network link  420  and communication interface  418 . In the Internet example, a server  430  might transmit a requested code for an application program through Internet  428 , ISP  426 , local network  422  and communication interface  418 . 
         [0046]    The received code may be executed by processor  404  as it is received, and/or stored in storage device  410 , or other non-volatile storage for later execution. In this manner, computer system  400  may obtain application code in the form of a carrier wave. 
         [0047]    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.