Range-clustered tables in a database management system

[0001] 1. Field of the Invention

[0002] The invention relates to a technique, specifically a method, apparatus, and article of manufacture that implements the method, to organize and access rows in a range-clustered table in a database management system. This technique is particularly, though not exclusively, suited for use within a database management system.

[0003] 2. Description of the Related Art

[0004] Database management systems allow large volumes of data to be stored and accessed efficiently and conveniently in a computer system. In a database management system, data is stored in database tables which effectively organize the data into rows and columns. A database engine responds to user commands to store and access the data.

[0005] In FIG. 1, a database table 30 having rows 32 and columns 34 is shown. A row 32 has one or more columns 34. A row 32 is also referred to as a record.

[0006] In the database table 30, the columns 34 are associated with a datatype that defines the type of data stored in that column. The datatype may be selected from a set of predefined datatypes such as numeric, integer, decimal, string, character, date, time and timestamp, among others. In a typical database management system, some datatypes assign a predefined length to a column. Such exemplary datatypes include, and are not limited to, “INTEGER,” “DECIMAL,” “DATE,” “TIME,” “TIMESTAMP,” and “CHAR(N)” which allocates space for N bytes in a character column. Other datatypes store data having a varying length such as VARCHAR, Binary Large Object (BLOB), and VARGRAPHIC.

[0007] To more quickly access the data in a database table, an index is generated based on one or more specified columns of the database table. This set of specified columns is referred to as a key or index key. Each row of the database table is associated with a key. The value of the key is determined by the values stored in the columns making up the key. In the index, the values of the keys are ordered. Each key value is associated with a least one row identifier, or pointer, to its associated row of the database table. Therefore, the keys provide access to all the rows in a database table. The database engine accesses the index to quickly locate a row of data in a database table based on the value of the key. Because the columns of a key are a subset of the columns of the database table, the columns of the key are associated with a datatype, and this datatype information is stored as column description information for that index.

[0008] Traditionally, two types of methods are used to access rows—balanced tree (B-tree) indexes and hash indexes. In FIG. 2, a query uses a B-tree 40 to access a particular row 36 in the database table 30. A B-tree 40 is a data structure, stored on disk, that stores indexes. As shown in FIG. 3, the B-tree 40 has a primary data structure 42 that is used to access a secondary data structure 44 storing indexes 46. The indexes 46 of the secondary data structure point to the locations on the disk where the rows are stored. The B-tree 40 allows rows to be read in any order. When searching through a range of key values, the rows can be found efficiently even if those rows are distributed across the disk. The B-tree is typically structured to minimize the number of disk accesses to retrieve a row.

[0009] In FIG. 3, the primary data structure 42 has values A₁ . . . A_n. Index values less than A₁ are stored in secondary structure 44-1. Index values greater than or equal to A₁ are stored in secondary structure 44-2. Values greater than or equal to An are stored in secondary structure 44-3. The index value v(2,2) points to row 48, and the index value v(n+1,o) points to row 50.

[0010] The hash index transforms a key into an index value, which is used to store and retrieve a row of data. The hash index performs well when accessing unique keys, such as social security numbers. However, the hash index does not perform range searches efficiently because each row must be read. For example, the hash index cannot efficiently be used to search for all employee names that start with “T”.

[0011] Although B-tree indexes are efficient at retrieving rows and searching ranges of rows, B-tree indexes require many accesses to the hard disk and performance can be slow. Although hash indexes are efficient at retrieving rows with unique key values, hash indexes cannot perform range searches efficiently because each row must be scanned. Therefore, there is a need for a technique to access a database table that increases the speed of accessing data and allows range searches to be performed efficiently.

[0012] To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for accessing data in a range-clustered table in a database management system.

[0013] In accordance with the present invention, a table stores data that is organized into rows and columns. At least one column is designated as a key column. A particular row in the table is accessed based on a relationship between a specified key value and a predetermined range of key values associated with the key column. The table has slots for storing rows, and the slots are organized in accordance with the values of the predetermined range.

[0014] In another aspect of the invention, each slot is associated with a slot number. The particular row is accessed by determining a slot number that represents a location of a particular slot based on the relationship between the specified key value and the predetermined range of key values. In yet another aspect of the invention, an overflow area is provided to store rows having key values outside the predetermined range of a range-clustered area of the table.

[0015] In this way, the accessing of the range-clustered table improves the performance of the database management system by increasing the speed of accessing individual rows of data, and by performing range searches efficiently because rows having sequential key values are physically clustered.

[0045] To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to some of the figures.

[0046] After considering the following description, those skilled in the art will clearly realize that the teachings of the present invention can be utilized to improve performance in substantially any database management system with database tables which have at least one key column storing integer, or integer-like, data which has at least one range of ordered values. The invention is integrated as a component into a database management system. To simplify the following discussion and facilitate reader understanding, the present invention will be described in the context of use in a database management system that executes on a mainframe computer.

[0047] A range-clustered table, or portion thereof, physically clusters rows having key values within a specified range of key values. The rows are clustered in key value order. The range-clustered table has a contiguous group of logical slots to store rows, and each logical slot is associated with a key value. The logical slots correspond to physical slots on pages that are stored on disk.

[0048] A technique accesses a row of the range-clustered table by determining a logical slot, associated with the key value of the row, that corresponds to the position of the row within the range-clustered table, or range-clustered portion of the table. The technique accesses the row functionally, by executing a set of instructions, rather than using a physical data structure such as a B-tree. This technique can avoid the use of traditional indexing technology such as a B-tree which requires significantly more disk space, input-output operations, logging, and code path. The technique is an improvement over hash indexing because range searches are permitted. Because rows having sequential key values are physically clustered, range queries are very efficient. The technique also allows a secondary index, such as a B-tree, to be used with the range-clustered table.

[0049] FIG. 4 depicts an illustrative computer system 60 that utilizes the teachings of the present invention. The computer system 60 comprises a processor 62, display 64, input interfaces (I/F) 66, communications interface 68, memory 70, disk memories 74 such as hard disk drive 76 and optical disk drive 78, and output interface(s) 80, all conventionally coupled by one or more busses 82. The input interfaces 66 comprise a keyboard 84 and mouse 86. The output interface is a printer 88. The communications interface 68 is a network interface card (NIC) that allows the computer 60 to communicate via a network, such as the Internet.

[0050] The memory 70 generally comprises different modalities, illustratively semiconductor memory, such as random access memory (RAM), and disk drives. The memory 70 stores operating system (O/S) 90 and application programs such as the database management system 92. The O/S 90 may be implemented by any conventional operating system, such as z/OS® (Registered Trademark of International Business Machines Corporation), AIX® (Registered Trademark of International Business Machines Corporation), UNIX® (Registered Trademark of Unix System Laboratories), and Windows NT® (Registered Trademark of Microsoft Corporation).

[0051] The database management system 92 is a DB2® system (DB2® is a registered trademark of International Business Machines Corporation). However, the inventive technique is not meant to be limited to a DB2® database management system, and may be used with other database management systems.

[0052] The specific software modules that implement the present invention are incorporated in the database management system 92. The software modules are comprised of instructions which, when loaded into the memory 70, are executed by the processor 62.

[0053] A database engine 94 allows a user to execute commands to insert data into, delete data from, or search the database tables. In one embodiment, the commands are Structured Query Language (SQL) statements that conform to a Structured Query Language standard as published by the American National Standards Institute (ANSI) or the International Standards Organization (ISO). In alternate embodiments, languages other than SQL may be used.

[0054] Generally, the database management system software is tangibly embodied in a computer-readable medium, for example, memory 70 or, more specifically, one of the disk drives 74, and is comprised of instructions which, when executed, by the computer system 60, causes the computer system 60 to utilize the present invention.

[0055] In the memory 70, the database management system 92 is comprised of software modules and data. A software module may comprise one or more computer programs. In one embodiment, the memory 70 may store a portion of the software modules and data making up the database management system 92 in semiconductor memory, while other software modules and data are stored in disk memory. In some embodiments, the database management system 92 is comprised of the following:

[0056] A Compiler & Optimizer 96 that receives a SQL statement, compiles the statement and determines an appropriate execution plan to perform the SQL statement;

[0057] An Execution Engine 98 that executes an execution plan;

[0058] Data Management Services (DMS) 100 that comprise low-level functions to physically access the rows of a table in the database;

[0059] An Access Row Function 102, that is part of the DMS 100, that accesses a row in the range-clustered table (RCT);

[0060] A Search procedure 105, that is part of the DMS 100, that searches both the range-clustered and overflow areas of a range-clustered table;

[0061] A Search RCT procedure 106, that is part of the DMS 100, that searches the range-clustered area of a range-clustered table;

[0062] A Search Overflow procedure 108, that is part of the DMS 100, that searches an overflow area of a range-clustered table;

[0063] A log 110 that stores a history of activity in the database management system;

[0064] Range Clustered Table(s) 120 that have a range-clustered area to physically cluster rows having key values within a predetermined range of values;

[0065] Conventional Table(s) 122 that may include separate overflow tables;

[0066] Locking information 124 that stores locks on the range-clustered table in accordance with an isolation level;

[0067] An Extent Map Cache 126 that stores a mapping of logical to physical page numbers in memory; and

[0068] Secondary Index(es) 128, such as B-tree indexes, that may be used with the range-clustered table.

[0069] The present invention may be implemented as a method, apparatus, or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof. The term “article of manufacture” (or alternately, “computer program product”) as used herein is intended to encompass a computer program accessible from any computer-readable device, carrier, or media. Those skilled in the art will recognize many modifications may be made to this configuration without departing from the scope of the present invention.

[0070] Those skilled in the art will recognize that the exemplary computer illustrated in FIG. 4 is not intended to limit the present invention. Indeed, those skilled in the art will recognize that other alternative hardware environments may be used without departing from the scope of the present invention.

[0071] FIG. 5 depicts an exemplary row 130 of a table. The row 130 has seven columns 132. Each block represents a column 132, and a column number 134 is shown below each block. Some columns have a fixed length, designated by an “F”, and other columns have a variable length, designated by a “V”. The numbers above each block 136 represent the maximum length of that column. For example, column one has a length of five bytes. Three columns are designated as key columns—columns one, two and four. In a range-clustered table, the key comprises columns having non-null, integer values. In an alternate embodiment, the key may also comprise columns having integer-like values, such as a date or time. In another embodiment, NULL values are allowed in the key and a NULL value is represented by a designated integer value. In an alternate embodiment, non integer-like values, such as, for example, a fixed length character datatype, are allowed in the key.

[0072] FIG. 6 depicts an embodiment of a range-clustered table 140 that has N logical slots 142. Each logical slot stores a row 144. The logical slots of the table correspond to key values in accordance with the range(s) associated with the key column(s). The rows are stored in the logical slots in key-ordered sequence. A table header 146 precedes the range-clustered area. The table header 146 stores information describing the range-clustered table.

[0073] FIG. 7 depicts an alternate embodiment 150 of a range-clustered table that has a table header 152 that contains information describing a range-clustered area 154 and an overflow area 156. The range-clustered area stores rows as described above with respect to FIG. 6. The overflow area 156 stores rows that have key values outside the specified range(s) of the range-clustered area. In an alternate embodiment, the overflow area 156 also stores rows having duplicate key values of rows already stored in the range-clustered area.

[0074] FIG. 8 depicts another alternate embodiment 160 of a range-clustered table 162 that has an associated overflow table 164. The range-clustered table 162 stores rows having key values within the specified range(s), as described above. The range-clustered table 162 also has a table header 163 that contains information describing a range-clustered area 165. The overflow table 164 stores rows having key values outside the range(s) of the range-clustered table 162. In an alternate embodiment, the overflow table 164 also stores rows having duplicate key values, even if those key values are within the ranges(s) of the range-clustered table 162. The overflow table 164 also has a table header 166 that contains information describing an overflow area 168. The range-clustered table 162 and overflow table 164 can appear unified using the Union operator of SQL. In another embodiment, the range-clustered table 162 and overflow table 164 can be unified using internal algorithms, some of which are described below.

[0075] FIG. 9 depicts the processing of a SQL statement through the database engine. The compiler and optimizer 96 receives and parses a SQL statement. Within the compiler, the optimizer generates alternative execution plans, determines a cost for each plan, and selects an appropriate execution plan. To determine a cost for accessing the range-clustered table, the range-clustered table is modeled using a virtual index in which the range-clustered table is represented as a large B-tree having one level. In other words, the range-clustered table is modeled as a conventional table having a large one-level index. Therefore, the cost for accessing the range-clustered table is relatively low. In practice, this virtual index works well because of the speed of accessing the rows of the range-clustered table and the clustering of rows having sequential key values. Alternatively, a specific cost for the range-clustered table can be constructed using well-known methods for determining cost.

[0076] The execution engine 98 executes the execution plan selected by the optimizer. The execution engine 98 invokes the data management services (DMS) 100 which invoke the access row function 102 to access the desired row(s) 144 of the database table 140. In one embodiment, the access row function is part of the DMS.

[0077] FIG. 10 depicts a high-level flowchart of a process to create and access a range-clustered table. In step 170, a range-clustered table is created using the create range-clustered table procedure 104 of FIG. 4. In step 172, the range-clustered table is accessed using the access row function of FIGS. 4 and 9.

[0078] FIG. 11 depicts a more detailed flowchart of a process of creating a range-clustered table that is implemented by the create range-clustered table procedure 104 of FIG. 4. In step 182, a SQL statement to create a range-clustered table is received. The SQL statement specifies one or more, up to n, columns as key columns. Each key column i is associated with a specified range having a minimum value (Min(i)) and a maximum value (Max(i)).

[0079] In step 184, a number of logical slots, that is, an amount of logical space, to store the rows of the range-clustered table is determined. Each key column i has a range defined by a maximum value (Max(i)) and a minimum value (Min(i)). The total number of logical slots is determined as follows:

[0080] $\mathrm{Total}\mathrm{number}\mathrm{of}\mathrm{logical}\mathrm{slots}=\prod _{i=1}^n\left(\mathrm{Max}\left(i\right)-\mathrm{Min}\left(i\right)+1\right)$

[0081] The slots have a predetermined length based on the number, length and type of columns making up a row. If any columns have a variable length, the length of the slot is determined based on the maximum length of the columns of the row.

[0082] In step 186, a number of slot-pages to store the logical slots is determined as follows:

[0083] Total slot-pages=Total number of logical slots/rows per page.

[0084] The number of rows per page is a predefined value which is set by a user or, alternately, computed by the database management system automatically.

[0085] In step 188, pages are allocated to store a table header and the slot-pages. In yet another embodiment, a unique costing-index is created in the catalog tables, but not on disk. The costing-index is the virtual index, described above, used by the optimizer to determine a cost for executing a SQL statement using the access row function and the range-clustered table.

[0086] FIG. 12 depicts a more detailed flowchart of an embodiment of a technique to access a range-clustered table that is implemented by the access row function 102 of FIG. 4. In step 192, a logical slot is determined based on specified key values for each key column i as follows:

[0087] $\mathrm{logical}\mathrm{slot}\mathrm{number}=\left[\sum _{i=1}^n\left(\mathrm{value}\left(i\right)-\mathrm{Min}\left(i\right)\right)\left(\mathrm{Mult}\left(i\right)\right)\right]+1$

[0088] where n is the last key column, and Mult(1)=1 for key column 1.

[0089] $\mathrm{Mult}\left(i\right)=\prod _{j=1}^{i-1}\left(\mathrm{Max}\left(i\right)-\mathrm{Min}\left(i\right)+1\right),\mathrm{where}\mathrm{column}i>1.$

[0090] In step 194, a page number and physical slot number are determined based on the logical slot number. The page number that stores a particular logical slot is determined as follows:

[0091] page number=(logical slot number/rows per page)+1+number of header pages.

[0092] The page number described above is relative to the table, and is a logical page number.

[0093] The physical slot number on the page that stores the particular slot is determined as follows:

[0094] physical slot number=(logical slot number MOD rows per page).

[0095] In step 196, the values stored in the row are accessed based on the page number and physical slot number. In an alternate embodiment, a page number representing the physical location of that page on a disk, i.e., a physical page number, is determined from an extent map, or alternately, an extent map cache, based on the logical page number and will be described in further detail below with reference to FIG. 27.

[0096] In an alternate embodiment, the first logical slot is slot zero, rather than slot one. In this embodiment, the logical slot number is determined as follows:

[0097] $\mathrm{logical}\mathrm{slot}\mathrm{number}=\left[\sum _{i=1}^n\left(\mathrm{value}\left(i\right)-\mathrm{Min}\left(i\right)+1\right)\left(\mathrm{Mult}\left(i\right)\right)\right].$

[0098] The embodiments described above determine the logical slot number with respect to the first slot at the beginning of the range-clustered area. In an alternate embodiment, the logical slot number can be determined with respect to the last slot in the range-clustered area of the table.

[0099] FIG. 13 depicts an exemplary SQL statement 200 to create a range-clustered table in accordance with FIG. 11 without an overflow area. The create statement 200 creates a table having six columns. The portion of the statement reciting, “ORGANIZE BY KEY SEQUENCE ( ),” indicates that the table to be created is a range-clustered table, and specifies the ranges associated with each key column. The portion of the statement reciting, “DISALLOW OVERFLOW,” prevents the creation of an overflow area. In an alternate embodiment, a range-clustered table without an overflow area is created by default, that is, without reciting “DISALLOW OVERFLOW” in the SQL statement.

[0100] The create statement of FIG. 13 designates columns C_W, C_NUM, and C_ID as key columns one, two and three, respectively. For key column one, C_W, the minimum value of the range (Min(1)) is equal to one, and the maximum value of the range (Max(1)) is equal to five. For key column two, C_NUM, the minimum value of the range (Min(2)) is equal to one, and the maximum value of the range (Max(2)) is equal to three. For key column three, C_ID, the minimum value of the range (Min(3)) is equal to one, and the maximum value of the range (Max(3)) is equal to two. This exemplary create statement does not create an overflow area for the range-clustered table.

[0101] The total number of logical slots allocated for the range-clustered table is determined as follows:
total number of logical slots=(Max(1)−Min(1)+1)*(Max(2)−Min(2)+1)*(Max(3)−Min(3)+1) (5−1+1)*(3−1+1)*(2−1+1)=30

[0102] FIG. 14 depicts an exemplary range-clustered table 210 created by the SQL command 200 of FIG. 13. The table 210 has thirty logical slots which are numbered consecutively from one to thirty. The logical slot number associated with a slot is shown on the left. The tuples of key sequence values (C_ID, C_NUM, C_W) that are associated with the slots are shown on the right. For example, the tuple (1,2,1) is associated with logical slot six.

[0103] For example, to access a row of the range-clustered table of FIG. 14, Mult(1) is equal to one, Mult(2) is equal to five and Mult(3) is equal to fifteen. Therefore, for the table of FIG. 14, a logical slot number for a particular key is determined as follows:
logical slot number=[((value(1)−1)*(1))+((value(2)−1)*(5))+((value(3)−1)*(15))]+1.

[0104] The logical slot number associated with the key having values of C_W=2, C_NUM=2, and C_ID=1, value(1), value(2) and value(3), respectively, is equal to seven. In another example, the logical slot number associated with the key having values of C_W=5, C_NUM=3, and C_ID=2, value(1), value(2) and value(3), respectively, is equal to thirty.

[0105] FIGS. 15A and 15B collectively depict a high-level flowchart of a process of updating, inserting and deleting a row from a range-clustered table using the technique of FIG. 12. In step 222, a SQL statement is received. Step 224 determines whether the SQL statement is an update statement.

[0106] If not, step 226 determines whether the SQL statement is an insert statement. If so, in step 228, a new logical slot is determined using the technique of FIG. 12, and the new row is inserted into the new logical slot.

[0107] If step 226 determines that an insert statement was not received, step 230 determines whether the SQL statement is a delete statement. If so, in step 232, a current logical slot of the row to be deleted is determined, and the row is deleted from that logical slot. If not, the process continues to identify the type of SQL statement received as shown by arrow 233.

[0108] If step 224 determines that the SQL statement is an update statement, the process continues to step 234 of FIG. 15B. In step 234, a current logical slot associated with the row to be updated is determined. The current row is retrieved from the current logical slot. The row in the current logical slot is accessed using the technique of FIG. 12. A new logical slot, associated with the current row, as updated, is determined.

[0109] Step 236 determines whether the current logical slot is equal to the new logical slot. If so, in step 238, the updated row is inserted into the current logical slot. If not, in step 240, the updated row is inserted into the new logical slot, and the row is deleted from the current logical slot using the technique of FIG. 12.

[0110] FIGS. 16A–16F depict exemplary SQL statements and their results. As shown in FIGS. 16A and 16B, a SQL statement 252 inserts a row 253 into logical slot seven of the range-clustered table of FIG. 14. As shown in FIGS. 16C and 16D, another SQL statement 254 updates a value of the row 255 at logical slot seven of the range-clustered table. As shown in FIGS. 16E and 16F; yet another SQL statement 256 deletes the contents of the row 257 at logical slot seven of the range-clustered table.

[0111] FIG. 17 depicts an exemplary SQL statement 260 to create a range-clustered table having an overflow area. The SQL statement 260 creates an overflow area to store rows having key values outside the specified range(s) of the range-clustered table. Alternately, the overflow area may also store rows having duplicate keys that have values within the specified range(s) of the range-clustered table. In an alternate embodiment, the SQL statement recites “ALLOW OVERFLOW,” to create an overflow area.

[0112] FIG. 18 depicts an exemplary page layout 270 of a range-clustered table. Pages zero and one, 272 and 274, respectively, store table header information. However, the invention is not meant to be limited to two header pages. Alternately, any number of header pages, such as 3, 4, . . . h, may be used. In one embodiment, the page numbers of FIG. 18 are logical page numbers.

[0113] In one embodiment, pages two through p, 276–280, each have a range-clustered area, 282–286, respectively, to store a number s of logical slots. The number of pages that store logical slots was determined in accordance with FIG. 11. In another embodiment, each page 276–280 that has a range-clustered area 282–286 also has an overflow area 292–296 that stores a predetermined number (t) of overflow slots.

[0114] In yet another embodiment, at least one additional page, 302 and 304, provides an overflow area. In another alternate embodiment, the range-clustered table has overflow areas on the same pages as the range-clustered areas, and also has at least one separate overflow page.

[0115] In an alternate embodiment, on page zero, in the table header, a last-object-page-in-the-table value 306 and a last-page-which-is-in-range value 308 are stored. These values are used to determine whether an overflow page has any rows, and will be further described below. In another embodiment, each page 276–280 that stores logical slots also has a slot directory 310–314, respectively, to reflect the rows as deleted.

[0116] FIG. 19 depicts a high-level flowchart of a process of inserting a row in an overflow area of a range-clustered table. The overflow area stores rows having at least one key column value outside the specified range(s) of the range-clustered area of the table. In an alternate embodiment, the rows of the overflow area may be accessed using well-known methods including, but not limited to, hash indexing and B-tree indexing.

[0117] The steps of FIG. 19 may be performed after a SQL insert statement is identified, for example, after step 226 of FIG. 15A. Step 312 determines whether any key column values are outside the predefined range(s) of the range-clustered area. If not, in step 314, the range-clustered area is accessed as described above. If any key column values are outside the specified ranges of the range-clustered area, step 316 determines whether an overflow area is defined, that is whether an overflow area exists. If not, step 318 returns an error.

[0118] If step 320 determines that an overflow area is defined, step 324 determines whether the overflow area has been initialized. If so, step 324 determines whether the table has unique keys. If so, step 326 scans the overflow area searching for an available empty slot and verifying that the key values do not already exist in the overflow area.

[0119] Step 328 determines whether any duplicate keys exist. If so, in step 330, a duplicate key error is returned. In one embodiment, steps 326, 328 and 330 are combined such that the scan ends if a duplicate key is found, and a duplicate key error is returned.

[0120] If step 328 determines that no duplicate keys exist, then step 332 determines whether there is an empty slot in the overflow area. If so, in step 334, a new row is assigned, that is, inserted, into the slot in the overflow area.

[0121] If step 320 determined that the overflow area had not been initialized, step 336 initializes the overflow area. The value of variables, referred to as startOverflowRSN and endOverflowRSN, which define the first and last logical slots in the overflow area, respectively, are initialized. In one embodiment, the value of startOverflowRSN is derived from the value of the last-page-which-is-in-range which is stored in the table header. For example, the value of startOverflowRSN is equal to the value of the last-page-which-is-in-range multiplied by the number of rows per page; the result of this multiplication is then incremented by one to have startOverflowRSN point to the slot following the range-clustered area. Initially, the value of endOverflowRSN is set to the same value as startOverflowRSN. In another embodiment, if the overflow page is full, another overflow page is allocated and the value of the last-object-page-in-the-table 306 (FIG. 18) is updated.

[0122] In step 338, an overflow slot is allocated, the value of endOverflowRSN is incremented by one, and the process continues to step 334.

[0123] If step 324 determined that the table does not have unique keys, the process continues to step 332.

[0124] If step 332 determines that there are no empty slots, then the process continues to step 338 which allocates an overflow slot.

[0125] FIG. 20 depicts a block diagram of a page 340 of a range-clustered table having duplicate key values in accordance with another embodiment of the invention. Duplicate key values are permitted and are stored in such a way as to maintain good overall clustering. The range-clustered area 342 is mapped to a set of pages. To accommodate duplicate values, each page is configured to contain some extra slots. The extra slots can be chained together in a set of configurable or static hash chains, to minimize conflicts between independent duplicate values.

[0126] Rows having duplicate key values are stored in an overflow area 344 on the same page as the “home” logical slot 346 in the range-clustered area. Each slot is associated with a Duplicate Flag (DupFlag) 348 and a duplicate pointer 350. If a slot has a duplicate value, the duplicate flag is set to “True” to indicate that a duplicate value is stored, and the duplicate pointer, for example, DupPtr1, points to the logical slot 352 storing the row with the duplicate key value. The duplicate pointer chains the rows having the same key value. In FIG. 20, two duplicate rows are stored in the overflow area.

[0127] FIG. 21 depicts a block diagram of deleting a duplicate row from an overflow area 344 of the range-clustered table 340 of FIG. 20. As duplicates are removed from the chain, links, that is, pointers, are updated but rows are not moved. When a row having a duplicate key 352 is deleted from the overflow area, the duplicate pointer in the previous row 346 is set equal to the value of the duplicate pointer of the row being deleted (DupPtr2). The duplicate pointer of the row being deleted 352 is set equal to NULL.

[0128] FIG. 22 depicts a block diagram of storing duplicate rows on a different page from the page storing range-clustered area 360. The rows having duplicate key values are stored in the overflow page 362.

[0129] In another embodiment, when a row insertion occurs, the “home slot” for the row in the range-clustered area, which is a logical slot, is first checked. If a row already exists at that slot, the new row is stored in the overflow space on the page. If there is no more space on the page, then space is allocated from another overflow page and the new row is inserted into that space, and that overflow space is linked into the hash chain. The original slot that the key mapped to is flagged to note that an overflow area exists for the key and a forward pointer is stored to point to the next row in the chain. As duplicates are added to the list, the duplicates are chained together. This technique allows secondary B-tree indexes to point directly to the rows which can eliminate chain scans when searching for rows based on secondary key indexes and can eliminate B-tree updates when the chain is updated with duplicates. In another embodiment, locking is performed on the logical slot associated with the key, the “home slot,” to avoid deadlocking when managing duplicates lists.

[0130] FIG. 23 depicts a high-level flowchart of an embodiment of a technique to scan, or search, a range-clustered table with an overflow area that is implemented by the search procedure 105 of FIG. 4. The scanning may be performed in response to a query, that is, a SQL SELECT statement. In step 372, a SQL statement to perform a search is received. The search request has one or more lower search key column values and one or more upper search key column values. Step 374 determines whether all the search key column values are within the key values of the range-clustered area. If so, step 376 searches the range-clustered area.

[0131] If not, step 378 determines whether all the search key column values are outside the key column values of the range-clustered area. If so, in step 380, the overflow area is searched.

[0132] If some of the search key column values are within the range key values of the range-clustered area and other search key column values are outside the range key values of the range-clustered area, both the range-clustered areas and overflow areas are searched. In step, 382 the range-clustered area is searched. The search parameters, upper and/or lower bounds, for the key columns having search key column values that are outside the range of key values of the range-clustered area are adjusted. For any search key column value that is less than the predefined minimum value for its associated key column, the minimum key value for the range-clustered area is used as the minimum search key column value, that is, the lower bound, to provide a start key value(s). For any search key column value that is greater than the predefined maximum value for its associated key column, the maximum key value for the range-clustered area is used as the maximum search key column value, that is, the upper bound, to provide a stop key value(s). Lower and upper logical slot numbers, which form the boundaries of the search, are derived from the start and stop key values, respectively. The range-clustered area is searched based on the lower and upper logical slot values to provide a first set of results.

[0133] In step 384, the overflow area is searched. During the search of the overflow area, each row is checked to determine whether its key values are within the lower and upper key values of the search. If so, that row is included in a second set of results.

[0134] In step 386, the first and second sets of results of the search of the range-clustered and overflow areas, respectively, are aggregated to produce a combined result which is returned to the user.

[0135] FIG. 24 depicts a detailed flowchart of an embodiment of a technique to scan a range-clustered table that may also include duplicates. In one embodiment, the technique of FIG. 24 is implemented by the Search RCT procedure 106 of FIG. 4, and may be used by steps 376 and 382 of FIG. 23. In other words, the Search Procedure 105 (FIG. 4) may invoke the Search RCT procedure 106 (FIG. 4) to search the range-clustered area of the table.

[0136] In step 392, a start key and a stop key are received. The start key and stop key are search parameters comprised of key column values. In step 394, start and stop logical slots, also referred to as start and stop row sequence numbers (RSNs) (startRSN and stopRSN), are determined for the start and stop keys, respectively. A value of the variable representing the current logical slot (currentRSN) is set equal to the value of the start RSN.

[0137] Step 396 determines whether the value of the current RSN is greater than the value of the stop RSN. If so, the scan is complete (step 398). If not, in step 400, the contents of the row associated with the current RSN is output, and the value of the duplicate flag (DuplFlag) of the row associated with the current RSN is retrieved.

[0138] Step 402 determines whether the value of the duplicate flag (DuplFlag) is “TRUE” which indicates that there are duplicate key values for the current row. If so, step 404 sets the value of a variable called duplRSN equal to the value of the duplicate row pointer (dupPTR). Step 406 outputs the value of the row associated with the duplicate RSN, and retrieves the value of the duplicate flag (DuplFlag) for the duplicate RSN, and proceeds to step 402 to determine whether there are additional rows with duplicate key values.

[0139] If step 402 determines that there are no further duplicate values for the current RSN, that is, the duplicate flag (DuplFlag) is “FALSE,” step 408 advances the current RSN to point to the next logical slot, and the process continues at step 396. In one embodiment, the current RSN is incremented by one to point to the next logical slot.

[0140] FIG. 25 depicts a flowchart of a technique to scan the overflow area of a range-clustered table. In one embodiment, the technique of FIG. 25 may be implemented by the Search Overflow procedure 108 of FIG. 4, and used by steps 380 and 384 of FIG. 23. In this embodiment, the overflow area has been provided as shown in FIG. 18, as a set of slots. In other words, the Search Procedure 105 (FIG. 4) may invoke the Search Overflow procedure 108 (FIG. 4) to search the overflow area of the table.

[0141] In step 410, a start key and a stop key are received. The start key and stop key are search parameters comprised of key column values. In step 412, the logical slots, startOverflowRSN and stopOverflowRSN row sequence numbers (RSNs) (startRSN and stopRSN) are determined for the stop and start keys, respectively.

[0142] Step 414 determines whether there are any overflow areas. If not, the process ends (step 416). If there are overflow areas, in step 418, a variable called OverflowRSN is set equal to startOverflowRSN. OverflowRSN is used as a slot counter to access slots in the overflow area, and is initialized to equal the value of a startOverflow RSN variable.

[0143] Step 420 determines whether the search of the overflow area is complete. If the value of OverflowRSN is greater than the value of endOverflowRSN, the process ends (step 422).

[0144] If the value of OverflowRSN is not greater than the value of endOverflowRSN, step 424 retrieves the row associated with the value of OverflowRSN and stores the row in a variable called Temp. Step 426 determines whether the key values of the row in Temp are within the values of the start and stop keys. If so, in step 428, the row in Temp, is output. In step 429, the value of the slot counter, OverflowRSN, is advanced, by a function called advanceOneRow( ), to point to the next slot. In one embodiment, the value of OverflowRSN is incremented by one, and the process continues to step 420.

[0145] If step 426 determines that the keys values of the row in Temp are not within the values of the start and stop keys, the process continues to step 429.

Locking in a Range-Clustered Table

[0146] FIG. 26 depicts a diagram of a sequence of slots 430 of a range-clustered table to illustrate locking in another alternate embodiment. The database engine uses locks to control concurrent access to the data in the table. An isolation level is specified for applications that access the table to define the type of locking. The isolation levels include the well-known repeatable-read (RR), read stability (RS), uncommitted read (UR) and cursor stability (CS).

[0147] The range-clustered table locks rows using discrete-locking, in contrast to conventional key locking and next-key locking. Discrete-locking means that all rows that are affected by an operation are locked. The number of rows locked depends on the isolation level. For the range-clustered table, discrete-locking implies that an RR scanner will lock every row between the start and stop key, whether that row is present or not, to protect the scanner from phantom inserts. For RS scanners, all rows that matched the set of predicates are locked. For CS scanners, the row which the cursor is currently pointing to and any rows which were altered during the scan are locked. For UR scanners, only the rows which will be altered are locked.

[0148] In the example of FIG. 26, a range scan and the locks obtained for RR, RS and CS isolation levels are shown. The start key 432 corresponds to logical slot 501 and the stop key 434 corresponds to logical slot 509. The current cursor position 436 (current row) is at logical slot 506. For an RR scanner, all slots from the start key (slot 501) to the current cursor position (slot 506) are locked including empty slots. For an RS scanner, the slots having rows are locked (502, 504–506), empty slots are not locked. For a CS scanner, the current slot (506) is locked. For a UR scanner, no locks are acquired. The locks are stored as locking information 124 of FIG. 4.

Locking on Overflows

[0149] In another embodiment, locking on overflows is implemented as described above, except that when new rows inserted into the overflow region, a table exclusive lock will wait for all executing RR scanners to exit and prevent new scanners from accessing the table. This also locks out RS scanners, therefore, in an alternate embodiment, a table lock which locks out only RR scanners may be used.

Extent Map Cache

[0150] FIG. 27 depicts a diagram of an extent map cache 126 which is used when accessing a range-clustered table in another embodiment of the present invention. An extent map provides a mapping from a logical page number to a physical page number that identifies where the page is stored on a disk. Typically, a persistent extent map is stored on the disk and provides a lookup table of logical-to-physical relative page numbers. The extent map cache is a partial copy of the persistent extent map. The extent map cache is stored in random access memory.

[0151] When a row of a table is accessed, the extent map cache is used to determine the location of the physical page storing that row on the disk. In particular, when accessing a particular row, the logical page number and physical slot number are determined as described above. The physical page number storing that slot is determined from the extent map cache based on the logical page number.

[0152] Without the extent map cache, determining the physical page number of a given logical page number requires a disk access to read the persistent extent map. Since a disk access is costly, the extent map cache reduces the number of disk accesses and improves performance.

Detecting the Presence of Overflows

[0153] Referring back to FIG. 18, the problem of detecting the presence of rows in the overflow area without reserving a separate bit that needs to be logged was solved by storing a variable called the-last-object-page-in-the-table 306 (FIG. 18), which is a logged value, and storing the page number of the last page of the range-clustered table (last-page-which-is-in-range) 308 (FIG. 1). If the value of the-last-object-page-in-the-table 306 is greater than the last-page-which-is-in-range 308, overflows exist in the table. In one embodiment, the pages numbers of the-last-object-page-in-the-table 306 and the last-page-which-is-in-range 308 are logical page numbers.

Latch Separation on Searched Updates and Deletes

[0154] Latching refers to reserving a page for a predetermined period of time to prevent others from using the page. Pinning refers to keeping a page in random access memory so that the page cannot be written to a disk.

[0155] Conventionally, a searched update or searched delete is performed in two phases. In a first phase, the rows are searched, and in a second phase the rows are updated or deleted. When using a B-tree, the search is performed on the tree and the delete is performed in the table. Two different pages are accessed, and each page is latched and pinned independently.

[0156] Using the range-clustered table, on searched updates and searched deletes, a target page is visited once to locate the row, and again to perform the update or the delete. The page is latched and pinned for the first visit, and remains pinned until the operation in the second visit completes.

[0157] FIG. 28 depicts a high-level flowchart of an embodiment of a process of latching and pinning pages of the range-clustered table when performing the updating of FIG. 15B that is implemented by the DMS 100 of FIG. 4. FIG. 28 is similar to FIG. 15B. In step 440, a current logical slot associated with the current row is determined. A current page storing the current logical slot is also determined., The current page is latched and pinned. The current row is read from the current logical slot. A new logical slot associated with the updated row is determined. The current page is unlatched.

[0158] Step 442 determines whether the current logical slot is equal to the new logical slot. If so, in step 444, the current page is latched. The updated row is inserted into the current logical slot. The current page is then unlatched and unpinned.

[0159] If step 442 determines that the current logical slot is not equal to the new logical slot, in step 446, a new page storing the new logical slot is determined. The current page is latched. The current row is deleted from the current logical slot, and the current page is unlatched and unpinned. The new page is latched and pinned, and the updated row is inserted into the new logical slot. The new page is unlatched and unpinned.

[0160] The present invention retains the benefits of conventional methods for unclustered or sparse data while improving the performance of the database management system when accessing and storing tightly clustered data. Because the technique preserves the B-tree indexing interface, much existing code can be reused, thereby reducing the implementation cost. Additionally, because the technique is compatible with the concept of a row identifier (RID), secondary indexes may be constructed as if the table was organized using conventional database management system methods.

[0161] The invention has been described by way of specific embodiments, but those skilled in the art will understand that various changes in form and detail may be made without deviating from the spirit or scope of the invention.