Abstract:
A method and apparatus are provided for using sibling-counts in XML indices to optimize single-path queries. Using a b-tree XML index with a SQL query logarithmically reduces the number of disk accesses by passing over index entries where it is determined that a match will not be found. However, because certain index entries are passed over, it is impossible to ascertain if a path expression occurs more than once in the XML index, as certain queries sometimes require. This hurdle can be overcome by maintaining a sibling count with each node entry in the XML index. Because the sibling count is stored with the index entry, the index will reveal whether the matching node is single or has other siblings. In additional to re-writing the original query for optimization by use of an XML index, it will be re-written to check for a single-path condition in the index.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     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. 
     This application is related to U.S. patent application Ser. No. 10/884,311, filed on Jul. 2, 2004, 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 
     The present invention relates to techniques for using eXtensible Markup Language (XML) data in a relational database system, and more specifically, for optimizing queries of information contained in XML documents stored in object-relational databases. 
     BACKGROUND 
     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 XPath queries. However, certain search operations are unable to effectively use XML indices, especially indices following a bottom-up evaluation of the XML document. 
     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 XPath 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 in the manner described in Manikutty into expressions that use the PATH table. 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. 
     However, using a b-tree index that passes over most rows of the PATH table when searching for a value means that certain information would no longer be determined during course of a search. For example, if a user needs to ensure that an XPath is unique in an XML document while searching for a value, this can be easily determined when executing a linear search down the rows of a PATH table. On the other hand, it would be impossible to make this determination of a single-path occurrence in the course of a value-based search if most of the rows of the PATH table are passed over by use of a b-tree index. 
     Based on the foregoing, it would be desirable to be able to use an index, like a b-tree index, with such a single-path query, such that a correct determination could be made about the single-path occurrence while making use of the index optimization. 
     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 
       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: 
         FIG. 1  is a tree diagram representing the XML document “employees.xml.” 
         FIG. 2  is a flowchart that represents how the PATH table is extended to maintain a sibling count for all nodes in an XML document, according to one embodiment of the invention. 
         FIG. 3  is a flowchart that represents how a single-path query is optimized by using a sibling count, according to one embodiment of the invention. 
         FIG. 4  is a block diagram that illustrates a computer system upon which an embodiment of the invention may be implemented. 
     
    
    
     DETAILED DESCRIPTION 
     Techniques for optimizing single-path queries of XML documents 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. 
     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: 
     
       
         
               
             
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 employees.xml 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 &lt;Person id=“5000”&gt; 
               
               
                   
                   &lt;Address&gt;1014 Dietz Avenue&lt;/Address&gt; 
               
               
                   
                   &lt;Name&gt;Justin&lt;/Name&gt; 
               
               
                   
                   &lt;Address&gt;1000 Stern Lane&lt;/Address&gt; 
               
               
                   
                 &lt;/Person&gt; 
               
               
                   
                   
               
             
          
         
       
     
     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 . 
     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. 
     
       
         
               
             
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 PathID-to-Path Mapping 
               
             
          
           
               
                 PathID 
                 Path 
               
               
                   
               
               
                 1 
                 /Person 
               
               
                 2 
                 /Person/@id 
               
               
                 3 
                 /Person/Address 
               
               
                 4 
                 /Person/Name 
               
               
                   
               
             
          
         
       
     
     
       
         
               
             
               
               
               
               
               
               
             
               
               
               
               
               
               
             
           
               
                 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 
                 1014 Dietz Avenue 
               
               
                 4 
                 R1 
                 4 
                 1.3 
                 Justin 
               
               
                 5 
                 R1 
                 3 
                 1.4 
                 1000 Stern Lane 
               
               
                   
               
             
          
         
       
     
     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. 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.” 
     A Single-PATH Query 
     The following example of a single-path query will be used to illustrate one embodiment of the invention. 
     
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 SELECT * 
               
               
                   
                 FROM EMPLOYEES 
               
               
                   
                 WHERE extractValue(object-value, ‘/Person/Address’) 
               
               
                   
                 LIKE ‘%Dietz’ 
               
               
                   
                   
               
             
          
         
       
     
     The Oracle SQL/XML operator “extractValue( )” is one that requires a single-path constraint. The operator takes in an XPath (‘/Person/Address’) as an argument, and obtains the value of the unique node identified by the XPath. If it is determined that the XPath matches more than one node, then the operator returns an error at run-time. In the above example, the query should return an error because “/ P erson/ A ddress” is not a unique path in “employees.xml.” 
     To make use of the PATH table, the query will be rewritten by the SQL engine at compile-time according to one of the methods described in Manikutty. More specifically, the expression using the “extractValue( )” operator will be replaced by a subquery referencing the PATH table: 
     
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 SELECT * 
               
               
                   
                 FROM EMPLOYEES 
               
               
                   
                 WHERE(SELECT value 
               
               
                   
                   FROM path_table 
               
               
                   
                   WHERE pathid=PATHID(‘/Person/Address’) 
               
               
                   
                    AND rid=BASE_TABLE_ROWID) 
               
               
                   
                 LIKE ‘%Dietz’ 
               
               
                   
                   
               
             
          
         
       
     
     For purposes of optimization, a cost-based optimizer will further transform the query into the following form: 
     
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 SELECT e.* 
               
               
                   
                 FROM EMPLOYEES e, path_table p 
               
               
                   
                 WHERE p.pathid=PATHID(‘/Person/Address’) 
               
               
                   
                   AND p.rid=e.rowid 
               
               
                   
                   AND p.value LIKE ‘%Dietz’ 
               
               
                   
                   
               
             
          
         
       
     
     Using the value index to evaluate the WHERE conditions in the preceding example would return an incorrect result for the original extractValue( ) query because there is no way to determine from the value index whether “/ P erson/ A ddress” is a unique path in the XML document. Such a value index would be navigated directly to the key containing “% Dietz %.” Thus, the WHERE condition would return the row in the PATH table containing “1014 Dietz Avenue” without determining whether “/ P erson/ A ddress” is a unique path. 
     According to one embodiment, a resolution to the above problem involves maintaining a sibling count in one of the columns of the PATH table. A sibling count for a node is the total number of nodes in the XML document that have the same node name, are located directly under a given parent, and therefore have identical paths. 
     The sibling relationship between nodes is shown in  FIG. 1 , which represents “employees.xml”  101  as a tree. The node “&lt;Address&gt;”  105  containing the text “1014 Dietz Avenue”  107  is a sibling of the node “&lt;Address&gt;”  109  containing the text “1000 Stern Lane”  111 . The XPath expression “/ P erson/ A ddress” refers to two nodes,  105  and  109 . Thus, both nodes  105  and  109  are given a sibling count of 2. 
     The sibling count of each node can be stored in the PATH table with the row for that node as follows: 
     
       
         
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                   
               
               
                   
                   
                   
                   
                   
                   
                 Sibling- 
               
               
                 rowid 
                 rid 
                 PathID 
                 OrderKey 
                 Value 
                 Locator 
                 Count 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 1 
                 R1 
                 1 
                 1 
                 NULL 
                   
                 1 
               
               
                 2 
                 R1 
                 2 
                 1.1 
                 5000 
                   
                 1 
               
               
                 3 
                 R1 
                 3 
                 1.2 
                 1014 Dietz Avenue 
                   
                 2 
               
               
                 4 
                 R1 
                 4 
                 1.3 
                 Justin 
                   
                 1 
               
               
                 5 
                 R1 
                 3 
                 1.4 
                 1000 Stern Lane 
                   
                 2 
               
               
                   
               
             
          
         
       
     
     According to another embodiment, a sibling count can be efficiently built up during XML index creation by simply maintaining a hash table based on the name of the element. The hash table only needs to be maintained at one level and can be discarded when the parent element goes out of scope. In the case of piece-wise updates to the index, the sibling count is kept in sync whenever an element is deleted or inserted. 
     An additional condition that limits query matches to those nodes having sibling_count=1 would be added to each re-written single-path query having an occurrence constraint as follows: 
     
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 SELECT e.* 
               
               
                   
                 FROM EMPLOYEES e, path_table p 
               
               
                   
                 WHERE p.pathid=PATHID(‘/Person/Address’) 
               
               
                   
                   AND p.rid=e.rowid 
               
               
                   
                   AND p.sibling_count=1 
               
               
                   
                   AND p.value LIKE ‘%Dietz’ 
               
               
                   
                   
               
             
          
         
       
     
     With the p.sibling_count=1 condition in the re-written query, a value index can be used without producing results that are incongruous to the ones produced by the original query. The rewritten query would return the same result as the original query having the “extractValue( )” operator. 
     Optimizing a Single-PATH Query 
       FIG. 2  and  FIG. 3  together represent how a single-path query is optimized by using a sibling count, according to one embodiment of the invention.  FIG. 2  shows the creation of one embodiment of an XML index. An XML index for an XML document is created (step  202 ). In one embodiment, creation of an XML index includes creation of the relational database structure of a PATH table (step  204 ). The sibling counts for all nodes are determined (step  206 ), and the sibling counts are stored in a PATH table column in a corresponding row (step  208 ). Finally, certain secondary indices, including a b-tree index on the value column of the PATH table, are created (step  210 ). 
     In  FIG. 3 , at step  301 , a query on the XML document is received. In this embodiment, the query may have the SQL/XML operator extractvalue( ). At step  303 , the expression using the extractValue( ) operator is re-written as a subquery that references the PATH table. At step  305 , the subquery is view-merged and re-written into a SQL query form having no subqueries. At step  307 , a condition requiring that the sibling_count=1 is added to the rewritten query. At step  309 , the final re-written is evaluated using one of the secondary indices (in particular, a b-tree index), on the value column of the PATH table. 
     Hardware Overview 
       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. 
     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. 
     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. 
     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. 
     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, punch cards, paper tape, 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  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 . 
     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, electromagnetic or optical signals that carry digital data streams representing various types of information. 
     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. 
     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 . 
     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. 
     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.