Abstract:
Provided are a method, system, and article of manufacture for the traversal of empty regions in a searchable data structure such as a table. A plurality of elements are allocated in logical storage, wherein the plurality of elements correspond to entries of the searchable data structure. An indicator is maintained corresponding to contiguously allocated empty elements in the plurality of elements. An operation is performed on the searchable data structure by avoiding the contiguously allocated empty elements.

Description:
BACKGROUND  
       [0001]     1. Field of the Invention  
         [0002]     The disclosure relates to a method, system, and article of manufacture for the traversal of empty regions in a searchable data structure, more specifically in a range clustered table.  
         [0003]     2. Background  
         [0004]     A range clustered table is a table whose data is tightly clustered across one or more columns in the table, i.e., range clustered tables may cluster rows in a table. In the table layout scheme of a range clustered table, each record in the table may have a predetermined record identifier which is an internal identifier used to locate a record in the table. Each record in a range clustered table has a predetermined offset from the logical start of the table, which allows rapid access to the data. As a result, data in range clustered tables can be accessed without needing an index. Range clustered tables are the subject of US Patent Application No. US2004/0225673A1 filed May 5, 2003 and entitled “Range-Clustered Tables in a Database Management System”, which is incorporated by reference in its entirety.  
         [0005]     Applications in which tightly clustered sequence key ranges are likely may use range clustered tables. A key may be used to generate the logical location of a row in a range clustered table. At table creation time, there are no records in the range clustered table. Space for the range clustered table is preallocated and reserved for use by the table even when records for the table are not filled in. The preallocation of the space for the range clustered table may be based on the record size and the maximum number of records to be stored in the range clustered table.  
         [0006]     Range clustered tables have range scan capabilities that require a range scan of the table to examine every possible row which could exist in a query range. When a large number of empty rows exist in a range clustered table, range scanning capabilities may result in large amount of input/output (I/O) operations and locking in order to lock and traverse empty regions of the range clustered table.  
       SUMMARY OF THE DESCRIBED EMBODIMENTS  
       [0007]     Provided are a method, system, and article of manufacture for the traversal of empty regions in tables. A plurality of elements are allocated in logical storage, wherein the plurality of elements correspond to entries of a searchable data structure. An indicator is maintained corresponding to contiguously allocated empty elements in the plurality of elements. An operation is performed on the searchable data structure by avoiding the contiguously allocated empty elements.  
         [0008]     In certain additional embodiments, the searchable data structure is a range clustered table in a database.  
         [0009]     In yet additional embodiments, the allocating of the plurality of elements further comprises preallocating space for the plurality of elements in the logical storage, and mapping empty entries of the searchable data structure to the contiguously allocated empty elements in the logical storage.  
         [0010]     In further embodiments, the maintaining of the indicator further comprises storing a pointer to a first possible non-empty element of the allocated plurality of elements, wherein all elements allocated in a sequence before the first possible non-empty element are empty.  
         [0011]     In yet further embodiments, the operation is an insertion operation, wherein the performing of the insertion operation further comprises determining whether a first element of the plurality of elements is locked. An exclusive lock is generated on the first element of the plurality of elements, in response to determining that the first element is not locked, wherein the exclusive lock exclusively locks the contiguously allocated empty elements starting from the first element. Data is inserted into one of the plurality of elements. The indicator is updated, in response to the inserting of the data.  
         [0012]     In additional embodiments, the operation is a query operation, wherein the performing of the query operation further comprises determining whether a first element of the plurality of elements is locked. A shared lock is generated on the first element of the plurality of elements, in response to determining that the first element is not locked, wherein the shared lock locks the contiguously allocated empty elements starting from the first element for shared access. The indicator is used to avoid the contiguously allocated empty elements. The indicator is updated and a response is made to the query operation.  
         [0013]     In yet additional embodiments, the operation is a deletion operation, wherein the performing of the deletion operation further comprises determining from the indicator a first possible non-empty element in the plurality of elements. A scanning is performed of the plurality of elements starting from the first possible non-empty element. Data corresponding to one element of the plurality of elements is deleted.  
         [0014]     In further embodiments, a single element of the contiguously allocated empty elements is locked in order to lock all elements of the contiguously allocated empty elements. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]     Referring now to the drawings in which like reference numbers represent corresponding parts throughout:  
         [0016]      FIG. 1  illustrates a block diagram of a computing environment in accordance with certain embodiments;  
         [0017]      FIG. 2  illustrates a block diagram that shows how storage is preallocated in range clustered tables, in accordance with certain embodiments;  
         [0018]      FIG. 3  illustrates a block diagram that shows how group locking is performed in a logical storage corresponding to a first exemplary range clustered table, in accordance with certain embodiments;  
         [0019]      FIG. 4  illustrates a block diagram that shows how group locking is performed in a logical storage corresponding to a second exemplary range clustered table, in accordance with certain embodiments;  
         [0020]      FIG. 5  illustrates operations for performing an insertion into a range clustered table, in accordance with certain embodiments;  
         [0021]      FIG. 6  illustrates operations for performing a query on a range clustered table, in accordance with certain embodiments;  
         [0022]      FIG. 7  illustrates operations for performing a deletion from a range clustered table, in accordance with certain embodiments; and  
         [0023]      FIG. 8  illustrates a system in which certain embodiments are implemented. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0024]     In the following description, reference is made to the accompanying drawings which form a part hereof and which illustrate several embodiments. It is understood that other embodiments may be utilized and structural and operational changes may be made.  
         [0025]     Certain embodiments provide a locking scheme along with an empty region traversal method to identify and bypass empty regions of range clustered tables.  
         [0026]      FIG. 1  illustrates a block diagram of a computing environment  100  in accordance with certain embodiments. The computing environment  100  comprises a computational device  102  and a database  104  that includes a range clustered table  106 .  
         [0027]     The computational device  102  may be any suitable device including those presently known in the art, such as, a personal computer, a workstation, a server, a mainframe, a hand held computer, a palm top computer, a telephony device, a network appliance, a blade computer, a storage server, etc. The database  104  may include any suitable searchable data structure, where query ranges may be used to search the suitable searchable data structure. For example, in certain embodiments the database  104  may include the IBM® DB2® database. (IBM and DB2 are registered trademarks of IBM Corporation.)  
         [0028]     The computational device  102  also includes a logical storage area  108 , a traversal application  110 , and a lookup table  112 . The logical storage area  108  stores contiguous elements corresponding to a range or row of the range clustered table  106 . The traversal application  110  is capable of performing insertions, deletions, queries and other database operations with respect to the range clustered table  106  of the database  104 .  
         [0029]     The traversal application  110  maintains the lookup table  112  in the computational device  102 . The traversal application  110  ensures that for any range of the range clustered table  106 , the traversal application  110  stores a pointer to the first possible non-empty element  114  stored in the logical storage area  108 .  
         [0030]     In certain embodiments, the traversal application  110  is capable of skipping over empty regions of the range clustered table  106  by using the lookup table  112  and the logical storage area  108 .  
         [0031]      FIG. 2  illustrates a block diagram that shows how storage is preallocated for range clustered tables, in accordance with certain embodiments. A user application  200  may perform a request  202  to the traversal application  110  included in the computational device  102 . The request  202  may include a read, write, delete or any other suitable database operation on the range clustered table  106 .  
         [0032]     In response to the request  202 , the traversal application  110  interprets the request  202  and exchanges information with the exemplary data structures  204  that comprise the range clustered table  106 , the lookup table  108  and the logical storage area  112  to generate a response  206  to the request  202 .  
         [0033]     The logical storage area  112  may include a sequence of elements  206   a ,  206   b ,  206   c ,  206   d , . . . ,  206   n  that have been preallocated (reference numeral  208 ) for each range or row of the range clustered table  106 . While  FIG. 2  illustrates a single exemplary sequence of elements  206   a , . . . ,  206   n , in alternative embodiments, there may be a plurality of exemplary sequence of elements where each sequence of elements corresponds to a range or row of the range clustered table  106 . The number of elements in the sequence of elements corresponding to different ranges or rows of the range clustered table  106  may be different.  
         [0034]     The lookup table  108  may include pointers corresponding to the preallocated sequence of elements in the logical storage area  112 . For example, the first possible non-empty element  114  may be a pointer to an element of the sequence of elements  206   a , . . . ,  206   n . The lookup table  108  may include a plurality of pointers where each pointer points to a different sequence of elements in the logical storage area  112 .  
         [0035]     In certain embodiments, the traversal application  110  may skip over empty regions of the range clustered table  106  while generating the response  206  by using the first possible non-empty element  114  pointers stored in the lookup table  108 .  
         [0036]      FIG. 3  illustrates a block diagram that shows how group locking is performed for a logical storage area  112  corresponding to a first exemplary range clustered table  300 , in accordance with certain embodiments. The exemplary range clustered table  300  is an embodiment of the range clustered table  106 .  
         [0037]     Ranges or rows of the range clustered table  300  are stored in the exemplary sequence of contiguous elements  302   a ,  302   b ,  302   c ,  302   d ,  302   e ,  302   f ,  302   g  in the preallocated space  304  of the logical storage area  108 . In certain embodiments, the exemplary sequence of elements  302   a , . . . ,  302   e  are empty and the exemplary sequence of elements  302   f ,  302   g  are non-empty.  
         [0038]     In certain embodiments, the traversal application  110  causes the first possible non-empty element  114  of the lookup table  112  to point to the element  302   f  of the preallocated space  304 . In such embodiments, the traversal application  110  guarantees that all elements from the start element  302   a , i.e., the 1 st  element  302   a , to the element  302   e , i.e., the N th  element, are empty. The first possible non-empty element in the preallocated space  304  is the element pointed to by the first possible non-empty element  114  pointer. In the embodiment illustrated in  FIG. 3  the first possible non-empty element  114  pointer points to a non-empty element  300   f . However, in alternative embodiments the first possible non-empty element  114  pointer may point an empty element.  
         [0039]     In certain embodiments, the traversal application  302  locks the 1 st  element  302  and the locking of the 1 st  element  302  causes a lock on all elements from the 1 st  element to the N th  element  302   e , where the N th  element  300   e  is the element just previous to the element  302   f  pointed to by the first possible non-empty element  114  pointer. Therefore, in certain embodiments a group locking  306  is performed on the elements  302   a , . . . ,  302   e  by locking the 1 st  element  302   a . In certain alternative embodiments, the group locking of the guaranteed empty elements  302   a , . . . ,  302   e  may be performed by locking some other element in the guaranteed empty elements  302   a , . . . ,  302   e.    
         [0040]      FIG. 3  illustrates an embodiment in which a locking of one element  302   a  in the range of elements  302   a , . . . ,  300   g  group locks  306  a range of guaranteed empty elements  302   a , . . . ,  302   e . Since a range of guaranteed empty elements are locked, the traversal application  110  can skip over contiguous empty elements corresponding to the range cluster table  300 .  
         [0041]      FIG. 4  illustrates a block diagram that shows how group locking is performed by the traversal application  110  in a second exemplary range clustered table  400 , in accordance with certain embodiments.  
         [0042]     Ranges or rows of the range clustered table  400  are stored in the exemplary sequence of contiguous elements  302   a ,  302   b ,  302   c ,  302   d ,  302   e ,  302   f ,  302   g  in the preallocated space  304  of the logical storage area  108 . In certain embodiments, the exemplary sequence of elements  302   a , . . . ,  302   e  are empty and the exemplary sequence of elements  302   f ,  302   g  are non-empty.  
         [0043]     In certain embodiments, the traversal application  110  causes the first possible non-empty element  114  of the lookup table  112  to point to the element  302   e  of the preallocated space. In such embodiments, the traversal application  110  guarantees that all elements from the start element  300   a , i.e., the 1 st  element  302   a  to the element stored just before the element  302   e  are empty. The first possible non-empty element in the preallocated space  304  is the element pointed to by the first possible non-empty element  114  pointer. In the embodiment illustrated in  FIG. 4  the first possible non-empty element  114  pointer points to an empty element  300   e . However, in alternative embodiments, such as the embodiment shown in  FIG. 3 , the first possible non-empty element  114  pointer may point a non-empty element. The first possible non-empty element  114  pointer guarantees that all elements of the sequence of elements  302   a , . . . ,  302   g  that are located before the element pointed to by the non-empty element  114  pointer are empty. The actual element pointed to by the non-empty element pointer may be empty or non-empty.  
         [0044]     In certain embodiments, the traversal application  110  locks the 1 st  element  302   a  and the locking of the 1 st  element  302   a  causes a lock on all elements from the 1 st  element  302   a  to the element just previous to the element  302   e  pointed to by the first possible non-empty  114  pointer. Therefore, in certain embodiments a group locking  402  is performed on the guaranteed empty elements  402  by locking the 1 st  element  302   a . In certain alternative embodiments, the group locking  402  of the guaranteed empty elements  402  may be performed by locking some other element in the guaranteed empty elements.  
         [0045]      FIG. 4  illustrates an embodiment in which a locking of one element  302   a  in the range of elements  302   a , . . . ,  300   g  group locks  402  a range of guaranteed empty elements. Since a range of guaranteed empty elements are locked, the traversal application  110  can skip over contiguous empty elements corresponding to the exemplary range cluster table  400 . In certain embodiments, requests are handled as part of a transaction and locking is used to enforce transactional consistency between different traversal applications.  
         [0046]      FIG. 5  illustrates operations for an insertion into a range clustered table  106 , in accordance with certain embodiments. The operations may be referred to as insertion operations  500  and may be implemented in the traversal application  110 .  
         [0047]     Control starts at block  500  where the traversal application  110  receives (at block  501 ) a request corresponding to an insertion of data for a row of the range clustered table  106 . The traversal application  110  determines (at block  502 ) whether the 1 st  element, such as element  206   a  or element  302   a , in the logical storage area  108  is locked, where insertion of data is restricted to other requests. If so, the traversal application  110  waits (at block  504 ) and determines (at block  502 ) again whether the 1 st  element in the logical storage area  108  is locked. In alternative embodiments, at block  502 , an a priori chosen element may be used to check for exclusive locking  
         [0048]     If the 1 st  element of the logical storage area  108  is not locked, then the traversal application  110  generates (at block  506 ) an exclusive lock on 1 st  element of the logical storage area  108 . The locking of the 1 st  element causes an exclusive group locking (e.g., reference numerals  306 ,  402 ) of the entire area between the 1 st  element and the element pointed to by the first possible non-empty element  114  of the lookup table  112 . The exclusive group locking prevents other requests from accessing the exclusively locked elements.  
         [0049]     The traversal application  10  exclusively locks (at block  508 ) the element of the logical storage area  108  to which insertion of data is to be performed. Subsequent to the locking, the traversal application  110  inserts (at block  510 ) data into the locked element.  
         [0050]     Then the traversal application  110  updates (at block  512 ) the lookup table  112  to update the first possible non-empty  114  pointer. For example, if the insertion is into an element which was guaranteed to be empty then the first possible non-empty element  114  pointer is updated to point to the element in which data is inserted. The traversal application  110  releases (at block  514 ) the exclusive locks when the transaction commits.  
         [0051]      FIG. 5  illustrates certain embodiments in which the traversal application  110  exclusively locks a plurality of guaranteed empty elements in the logical storage area  108  by locking a single element. After inserting data into an element the first possible non-empty element  114  pointer in the lookup table is updated  112 . Since a plurality of contiguous empty elements are group locked via a locking of a single element, the traversal application  110  can potentially skip over these group locked elements while inserting data. Therefore, empty regions of the range clustered table  108  may be skipped over by the traversal application  110 .  
         [0052]      FIG. 6  illustrates operations for performing a query on a range clustered table  106 , in accordance with certain embodiments. The operations may be referred to as query operations  600  and may be implemented in the traversal application  110 .  
         [0053]     Control starts at block  601 , where the traversal application  110  receives a request to read data corresponding to a row of the range clustered table  106 . The traversal application determines (at block  602 ) whether the first element  206   a ,  302   a  in the logical storage area  108  is exclusively locked. If so, the traversal application  110  waits (at block  604 ) and attempts to determine once again whether the first element  206   a ,  302   a  in the logical storage area  108  is exclusively locked. In alternative embodiments, at block  602 , an a priori chosen element may be used to check for exclusive locking.  
         [0054]     If the traversal application  110  determines (at block  602 ) that the first element in the logical storage area  108  is not exclusively locked then the traversal application  110  creates (at block  606 ) a shared lock on the first element of the logical storage area  108 . Creating a shared lock causes a group shared locking of all elements from the first element to the element immediately before the element pointed to by the first possible non-empty element  114  pointer. A shared locking allows other query operations to be satisfied, but no deletion or insertion operations may be performed on the locked elements.  
         [0055]     The traversal application  110  determines (at block  608 ) from the lookup table  112  the first possible non-empty element in the logical storage area  108 , where the logical storage area  108  has already stored the data for a row corresponding to the preallocated elements, such as, preallocated elements  206   a , . . . ,  206   n ,  302   a , . . . ,  302   g  where the query operations  600  are being performed on the row.  
         [0056]     The traversal application  110  determines (at block  608 ) whether the first non-empty element is empty. Therefore, the traversal application  110  skips over all the group locked elements which are guaranteed to be empty. The processing time that may have been required to read each empty element is not used by the traversal application  110 .  
         [0057]     If the traversal application  110  determines (at block  610 ) that the element is empty, then the traversal application traverses (at block  612 ) to the next element and determines (at block  610 ) whether the next element is empty.  
         [0058]     If the traversal application  610  determines (at block  610 ) that the element is non-empty, then the traversal application  610  updates (at block  614 ) the lookup table  112  to store the new pointer in the first possible non-empty element  114  pointer to the logical storage area  108 .  
         [0059]     The traversal application  110  responds (at block  616 ) to the read request with the data in the non-empty element and releases (at block  618 ) the shared lock when the transaction commits.  
         [0060]      FIG. 6  illustrates certain embodiments in which the traversal application  110  skips over elements that are guaranteed to be empty while performing a query. On encountering a non-empty element, the traversal application  110  updates the lookup table  112 , such that, the first possible non-empty element  114  pointer points to the encountered non-empty element.  
         [0061]      FIG. 7  illustrates operations for a deletion from a range clustered table  106 , in accordance with certain embodiments. The operations may be referred to as deletion operations  700  and may be implemented in the traversal application  110 .  
         [0062]     Control starts at block  702 , where the traversal application  110  receives a request for deletion of data corresponding to a row of the range clustered table  106 . The traversal application  110  determines (at block  704 ) the first possible non-empty element from the lookup table  112 .  
         [0063]     The traversal application starts scanning from the first possible non-empty element and deletes the corresponding entries of the logical storage area  106 . While deleting entries there is no need to update the pointer to the first possible non-empty element  114  in the lookup table  112 . The pointer to the first possible non-empty element  114  in the lookup table  112  merely guarantees that entries before the first possible non-empty element are all empty. Therefore, the pointer to the first possible non-empty element  114  is valid even when a non-empty element is deleted. In certain embodiments, the pointer to the first possible non-empty element  114  is updated while performing query operations on the range clustered table  106 .  
         [0064]     Therefore  FIG. 7  illustrates an embodiment in which the traversal application  110  can skip over the guaranteed empty elements in the logical storage area  112  by determining the first possible non-empty element in the logical storage area  112  from the lookup table  108 . Additionally, there is no need to update the lookup table  108  while performing a deletion operation.  
         [0065]     In certain embodiments, various database operations, such as, deletions, insertions, queries may be performed on range clustered tables by skipping over empty regions of the range clustered table. Additionally, a locking of a single element corresponding to a row of the range clustered table can lock contiguous empty elements starting from the first element stored in the logical storage area  108 . As a result, a plurality of elements may be locked for exclusive or shared access by locking a single element. Certain embodiments decrease processing time for operations on a range clustered table by decreasing the number of locks and by decreasing the number of elements to examine by skipping over empty elements.  
       Additional Embodiment Details  
       [0066]     The described techniques may be implemented as a method, apparatus or article of manufacture involving software, firmware, micro-code, hardware and/or any combination thereof. The term “article of manufacture” as used herein refers to program instructions, code and/or logic implemented in circuitry (e.g., an integrated circuit chip, Programmable Gate Array (PGA), ASIC, etc.) and/or a computer readable medium (e.g., magnetic storage medium, such as hard disk drive, floppy disk, tape), optical storage (e.g., CD-ROM, DVD-ROM, optical disk, etc.), volatile and non-volatile memory device (e.g., Electrically Erasable Programmable Read Only Memory (EEPROM), Read Only Memory (ROM), Programmable Read Only Memory (PROM), Random Access Memory (RAM), Dynamic Random Access Memory (DRAM), Static Random Access Memory (SRAM), flash, firmware, programmable logic, etc.). Code in the computer readable medium may be accessed and executed by a machine, such as, a processor. In certain embodiments, the code in which embodiments are made may further be accessible through a transmission medium or from a file server via a network. In such cases, the article of manufacture in which the code is implemented may comprise a transmission medium, such as a network transmission line, wireless transmission media, signals propagating through space, radio waves, infrared signals, etc. Of course, those skilled in the art will recognize that many modifications may be made without departing from the scope of the embodiments, and that the article of manufacture may comprise any information bearing medium known in the art. For example, the article of manufacture comprises a storage medium having stored therein instructions that when executed by a machine results in operations being performed.  
         [0067]      FIG. 8  illustrates a block diagram of a system  800  in which certain embodiments may be implemented. In certain embodiments, the computational device  102  may be implemented in accordance with the system  800 . The system  800  may include a circuitry  802  that may in certain embodiments include a processor  804 . The system  800  may also include a memory  806  (e.g., a volatile memory device), and storage  808 . Certain elements of the system  800  may or may not be found in the computational device  102 . The storage  808  may include a non-volatile memory device (e.g., EEPROM, ROM, PROM, RAM, DRAM, SRAM, flash, firmware, programmable logic, etc.), magnetic disk drive, optical disk drive, tape drive, etc. The storage  808  may comprise an internal storage device, an attached storage device and/or a network accessible storage device. The system  800  may include a program logic  810  including code  812  that may be loaded into the memory  806  and executed by the processor  804  or circuitry  802 . In certain embodiments, the program logic  810  including code  812  may be stored in the storage  808 . In certain other embodiments, the program logic  810  may be implemented in the circuitry  802 . Therefore, while  FIG. 8  shows the program logic  810  separately from the other elements, the program logic  810  may be implemented in the memory  806  and/or the circuitry  802 .  
         [0068]     At least certain of the operations of  FIGS. 5, 6 ,  7  may be performed in parallel as well as sequentially. In alternative embodiments, certain of the operations may be performed in a different order, modified or removed.  
         [0069]     Furthermore, many of the software and hardware components have been described in separate modules for purposes of illustration. Such components may be integrated into a fewer number of components or divided into a larger number of components. Additionally, certain operations described as performed by a specific component may be performed by other components.  
         [0070]     The data structures and components shown or referred to in  FIGS. 1-8  are described as having specific types of information. In alternative embodiments, the data structures and components may be structured differently and have fewer, more or different fields or different functions than those shown or referred to in the figures. Therefore, the foregoing description of the embodiments has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the embodiments to the precise form disclosed. Many modifications and variations are possible in light of the above teaching.