Abstract:
One embodiment of the present invention provides a system that uses an index that is hash-partitioned to access a table that is not hash-partitioned. During system operation, the database receives a request to perform an operation involving a table in the database. If performing the operation involves looking up a key in the hash-partitioned index, the database applies a hash function to the key to identify a unique partition within the hash-partitioned index for the key, and uses the key to perform a lookup in the identified partition to identify zero or more rows of the table that match the key.

Description:
This application hereby claims priority under 35 U.S.C. §119 to U.S. Provisional Patent Application No. 60/569,122 filed on 6 May 2004, entitled “Eliminating Resource Contention During Maintenance of an Index Defined on Monotonically Increasing Keys,” by inventor Vikram Shukla. 
    
    
     BACKGROUND 
     1. Field of the Invention 
     The present invention relates to the process of accessing a table within a database system. More specifically, the present invention relates to a method and an apparatus for using a hash-partitioned index to access a table that is not hash-partitioned. 
     2. Related Art 
     Many database applications use automatically generated keys as column values in relation tables. In such applications, the automatically generated key typically has a monotonically increasing value. For example, the transaction identifier in an Online Transaction Processing (OLTP) environment is usually an automatically generated key that is incremented to generate successive key values. Similarly, surrogate keys that are used in star schemas of data warehousing environments also tend to be automatically generated with monotonically increasing values. 
     Often, these automatically generated keys with monotonically increasing values have indexes defined on them. As a result, index accesses and maintenance activities tend to occur in a highly localized area of the index (e.g., the right-most edge of the index). These localized areas are known as “hotspots.” A hotspot can cause severe resource contention during periods of increased database activity, which can result in a performance degradation of the database system, such as, an increased response time for database transactions and reduced throughput. 
     Two methods are presently used to reduce hotspots. The first method reverses the bytes in the key and then uses the reversed key to perform operations in the index. This method largely eliminates the formation of hotspots because it disperses the reversed keys across the whole index. One of the drawbacks of this approach is that since it disperses the reversed keys in a highly random fashion, it causes continuous random movement of the disk head, which causes the disk seek-time to increase considerably because locality-of-reference is lost. Thus, although this method eliminates hotspots, it may, in fact, degrade the overall performance of the system. The second method is to use hash-partitioned tables, in which rows are mapped into partitions based on applying the hash function to the partitioning key. Since each partition of a hash-partitioned table has its own index, the index accesses and maintenance activities are equally distributed among all the partitions, thereby eliminating the formation of a single large hotspot. The drawback of this method is that it forces the user to partition tables using the hash-partitioning technique, which may not be the optimal partitioning technique for certain database applications. For example, in OLTP applications, it is quite common to use range-partitioned tables that are partitioned using the date fields for simplifying database management and for improving database performance. Thus, for such applications, we cannot use hash-partitioning to eliminate hotspots. 
     Hence, what is needed is a method and an apparatus for accessing a table that does not have the above-described drawbacks of the existing techniques. 
     SUMMARY 
     One embodiment of the present invention provides a system that uses an index that is hash-partitioned to access a table that is not hash-partitioned. During system operation, the database receives a request to perform an operation involving a table in the database. If performing the operation involves looking up a key in the hash-partitioned index, the database applies a hash function to the key to identify a unique partition within the hash-partitioned index for the key. Next, the database uses the key to perform a lookup in the identified index partition to identify zero or more rows of the table that match the key. 
     In a variation on this embodiment, the table is not partitioned. 
     In a variation on this embodiment, the table is range-partitioned. 
     In a variation on this embodiment, the table is list-partitioned. 
     In a variation on this embodiment, the operation can include: querying the table to identify rows that match a logical condition; updating an existing row in the table; deleting an existing row in the table; inserting a new row in the table; creating a hash-partitioned index for the table; adding a partition to the hash-partitioned index; and coalescing a partition in the hash-partitioned index. 
     In a variation on this embodiment, the hash function is applied to a prefix of the key, instead of the entire key. 
     In a variation on this embodiment, identifying a unique partition for the key involves calculating a partition number. 
     In a variation on this embodiment, if performing the operation involves creating a hash-partitioned index, the database first obtains a key for each row in the table. Then, it applies a hash function to the key to identify a unique partition within the hash-partitioned index for the key. Finally, it inserts the key into the identified partition. 
     In a variation on this embodiment, if performing the operation involves adding a partition to the hash-partitioned index, and if the hash function has the prefix property, the database identifies a source partition in the hash-partitioned index to be subdivided to create two new partitions to replace the source partition. If the source partition is marked usable, the system then subdivides the source partition by first scanning through all the keys in the source partition, applying a new hash function to each key in the source partition to identify one of the two new partitions, and inserting the key into the identified new partition. Finally, it replaces the source partition with the two new partitions, thereby creating an additional partition. 
     In a variation on this embodiment, if performing the operation involves adding a partition to the hash-partitioned index, and if the hash function has the prefix property, the database identifies a source partition in the hash-partitioned index to be subdivided to create two new partitions to replace the source partition. If the source partition is marked unusable, the system then attempts to identify a second index, wherein the index key of the second index is a superset of the index key of the hash-partitioned index. If a second index is successfully identified, the system then subdivides the source partition by first scanning through one or more keys in the second index and applying the hash function to each key to determine whether the key maps to the source partition. Next, if the key maps to the source partition, the system applies a new hash function to the key to identify one of the two new partitions, and inserts the key into the identified new partition. Finally, it replaces the source partition with the two new partitions, thereby creating an additional partition. 
     In a variation on this embodiment, if performing the operation involves adding a partition to the hash-partitioned index, and if the hash function has the prefix property, the database identifies a source partition in the hash-partitioned index to be subdivided to create two new partitions to replace the source partition. If the source partition is marked unusable, the system then subdivides the source partition by first scanning through all the rows in the table, obtaining a key for each row, and applying the hash function to the key to determine whether the key maps to the source partition. Next, if the key maps to the source partition, the system applies a new hash function to the key to identify one of the two new partitions, and inserts the key into the identified new partition. Finally, it replaces the source partition with the two new partitions, thereby creating an additional partition. 
     In a variation on this embodiment, if performing the operation involves adding a partition to the hash-partitioned index, and if the hash function does not have the prefix property, the database creates a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one greater than the number of existing partitions. It then scans through all the keys in the existing partitions, applies a new hash function to each key to identify a unique partition within the set of new partitions for the key, and inserts the key into the identified partition. Finally, it replaces the existing set of partitions with the new set of partitions, thereby increasing the number of partitions by one. 
     In a variation on this embodiment, if performing the operation involves adding a partition to the hash-partitioned index, and if the hash function does not have the prefix property, the database creates a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one greater than the number of existing partitions. It then scans through all the rows in the table, obtains a key for each row, applies a new hash function to the key to identify a unique partition within the set of new partitions for the key, and inserts the key into the identified partition. Finally, it replaces the existing set of partitions with the new set of partitions, thereby increasing the number of partitions by one. 
     In a variation on this embodiment, if performing the operation involves coalescing a partition in the hash-partitioned index, and if the hash function has the prefix property, the database identifies two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition. It then coalesces the two source partitions to create the new partition by scanning through all the keys in the two source partitions, and inserting the keys into the single new partition. Finally, it replaces the two source partitions with the new partition, thereby reducing the number of partitions by one. 
     In a variation on this embodiment, if performing the operation involves coalescing a partition in the hash-partitioned index, and if the hash function has the prefix property, the database identifies two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition. If at least one of the two source partitions is marked unusable, the system then attempts to identify a second index, wherein the index key of the second index is a superset of the index key of the hash-partitioned index. If a second index is successfully identified, the system then coalesces the two source partitions by first scanning through one or more keys in the second index and applying the hash function to each key to determine whether the key maps to one of the source partitions. Next, if the key maps to one of the source partitions, the system inserts the key into the new partition. Finally, it replaces the two source partitions with the new partition, thereby reducing the number of partitions by one. 
     In a variation on this embodiment, if performing the operation involves coalescing a partition in the hash-partitioned index, and if the hash function has the prefix property, the database identifies two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition. If at least one of the two source partitions is marked unusable, the system then coalesces the two source partitions by first scanning through all the rows in the table, obtaining a key for each row, and applying the hash function to the key to determine whether the key maps to one of the source partitions. Next, if the key maps to one of the source partitions, the system inserts the key into the new partition. Finally, it replaces the two source partitions with the new partition, thereby reducing the number of partitions by one. 
     In a variation on this embodiment, if performing the operation involves coalescing a partition in the hash-partitioned index, and if the hash function does not have the prefix property, the database creates a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one less than the number of existing partitions. It then scans through all the keys in the existing partitions, applies a new hash function to each key to identify a unique partition within the set of new partitions for the key, and inserts the key into the identified partition. Finally, it replaces the existing set of partitions with the new set of partitions, thereby reducing the number of partitions by one. 
     In a variation on this embodiment, if performing the operation involves coalescing a partition in the hash-partitioned index, and if the hash function does not have the prefix property, the database creates a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one less than the number of existing partitions. It then scans through all the rows in the table, obtains a key for each row, applies a new hash function to the key to identify a unique partition within the set of new partitions for the key, and inserts the key into the identified partition. Finally, it replaces the existing set of partitions with the new set of partitions, thereby reducing the number of partitions by one. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         FIG. 1  illustrates a computer system with a database in accordance with an embodiment of the present invention. 
         FIG. 2  presents a flow chart illustrating the process of accessing a table in accordance with an embodiment of the present invention. 
         FIG. 3  presents a flow chart illustrating the process of creating a hash-partitioned index in accordance with an embodiment of the present invention. 
         FIG. 4A  and  FIG. 4B  illustrate how a partition is added to a hash-partitioned index, if the hash function has the prefix property, in accordance with an embodiment of the present invention. 
         FIG. 5  presents a flow chart illustrating the process of adding a partition to a hash-partitioned index, if the hash function has the prefix property, in accordance with an embodiment of the present invention. 
         FIG. 6A  and  FIG. 6B  illustrate how a partition is coalesced in a hash-partitioned index, if the hash function has the prefix property, in accordance with an embodiment of the present invention. 
         FIG. 7  presents a flow chart illustrating the process of coalescing a partition in a hash-partitioned index, if the hash function has the prefix property, in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein. 
     The data structures and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video). 
     Computer System 
       FIG. 1  illustrates a computer system  102  with a database  104  in accordance with an embodiment of the present invention. Computer system  102  can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance. 
     Database  104  can include any type of system for storing data in non-volatile storage. This includes, but is not limited to, database systems based upon magnetic, optical, and magneto-optical storage devices, as well as storage devices based on flash memory and/or battery-backed up memory. Database  104  includes a non-partitioned table  106  comprised of a collection of rows  108 . Table  106  can be referenced through one or more hash-partitioned indexes, such as index  110 . Note that indexes, including hash-partitioned indexes, provide a quick way to find rows with specific column values. In the absence of indexes, database  104  would have to scan through the whole table  106  in order to identify the rows  108  that match specific column values, which would be very inefficient. A hash-partitioned index contains two or more index partitions ( 112 ,  114 ,  116 , and  118 ), wherein each index partition  118  contains index records  120  that identify the location of a row  108  in the table  106 . Index records  120  are typically stored in a tree data structure, such as, B + -tree, that uses keys to facilitate efficient lookup and insert operations. 
     Accessing a Table 
       FIG. 2  presents a flow chart illustrating the process of accessing a table  106  in accordance with an embodiment of the present invention. Upon receiving a request (step  202 ), the system identifies an index partition  118  by applying a hash function to the key (step  204 ). Note that the hash function distributes the keys among all the partitions ( 112 ,  114 ,  116 , and  118 ), so that, typically, each partition comprises approximately the same number of keys. Next, the system uses the key to identify an index record  120  (step  206 ) that contains a pointer to the location of the table rows  108 . Finally, the system uses the index record  120  to access the table rows  108  (step  208 ). 
     Note that, although the index  110  is hash-partitioned, table  106  may not be partitioned or may be partitioned using a different technique. For example, table  106  may be range-partitioned, as is often the case in OLTP applications. Furthermore, note that, since the index  110  is hash-partitioned, index accesses and maintenance activities are equally distributed among all the partitions ( 112 ,  114 ,  116 , and  118 ), thereby eliminating the formation of a single large hotspot. 
     Creating a Hash-Partitioned Index 
       FIG. 3  presents a flow chart illustrating the process of creating a hash-partitioned index  110  in accordance with an embodiment of the present invention. The system starts by obtaining a key for each row  108  in the table  106  (step  302 ). Next, the system identifies an index partition  118  by applying the hash function to the key (step  304 ) within the hash-partitioned index  110 . Finally, the system inserts the key into the identified partition  118  (step  306 ). 
     Adding a Partition 
       FIG. 4A  and  FIG. 4B  illustrate how a partition is added to a hash-partitioned index  110 , if the hash function has the prefix property, in accordance with an embodiment of the present invention. In  FIG. 4A , a source partition  112  is subdivided to create two new partitions  400  and  402 . In  FIG. 4B , the source partition  112  is replaced by the two new partitions  400  and  402  to create a new hash-partitioned index  404  that comprises of one additional partition. 
       FIG. 5  presents a flow chart illustrating the process of adding a partition to a hash-partitioned index  110 , if the hash function has the prefix property, in accordance with an embodiment of the present invention. The system identifies a source partition  112  (step  502 ) to be subdivided into two new partitions  400  and  402 . Next, if the source partition is marked usable, the system scans through all the keys in the source partition  112  (step  504 ). Then, the system applies a new hash function to the key to identify one of the two new partitions  400  and  402  (step  506 ). Next, the system inserts the key into the identified partition (step  508 ). Finally, the system replaces the source partition  112  with the new partitions  400  and  402  (step  510 ). 
     Coalescing a Partition 
       FIG. 6A  and  FIG. 6B  illustrate how a partition is coalesced in a hash-partitioned index  110 , if the hash function has the prefix property, in accordance with an embodiment of the present invention. In  FIG. 6A , two source partitions  114  and  118  are coalesced to create a new partitions  600 . In  FIG. 4B  the source partitions  114  and  118  are replaced by the new partition  600  to create a new hash-partitioned index  602  that comprises of one less partition. 
       FIG. 7  presents a flow chart illustrating the process of coalescing a partition in a hash-partitioned index  110 , if the hash function has the prefix property, in accordance with an embodiment of the present invention. The system identifies two source partitions  114  and  118  (step  702 ) to be coalesced into a single new partition  600 . Next, if both of the source partitions are marked usable, the system scans through all the keys in the source partitions  114  and  118  (step  704 ). Then, the system inserts the keys into the new partition  600  (step  706 ). Finally, the system replaces the source partitions  114  and  118  with the new partition  600  (step  708 ). 
     The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.