Range-clustered tables in a database management system

• US 20040225673A1
• Filed: 05/05/2003
• Published: 11/11/2004
• Est. Priority Date: 05/05/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Valentin, Gary, Raphael, Roger C., Grosman, Ronen, Lashley, Scott David, Taylor, Paul Sherwood, Beck, Kevin Leo, Brett, Paul Michael
• Granted Patent: US 7,103,588 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method, apparatus and article of manufacture, implementing the method, accesses rows in a range-clustered table in a database management system. 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.

Claims

1. A method of operating a database management system having a table for storing data, the data being organized into rows and columns, at least one column being designated as an at least one key column, comprising:

accessing a particular row in the table based on a relationship between a specified key value and a predetermined range of key values associated with the at least one key column, wherein the table has slots for storing rows, the slots being organized in accordance with the values of the predetermined range.

2. The method of claim 1 wherein said accessing comprises determining a slot number representing a location of a particular slot based on the relationship between the specified key value and the predetermined range of key values, wherein each slot of the table is associated with a slot number.

3. The method of claim 2 further comprising:

receiving a starting search key value and a stopping search key value;

determining a stopping slot number based on the stopping search key value;

wherein said accessing the particular row determines the slot number such that the specified key value is the starting search key value to provide a starting slot number; and

repeatedly accessing rows stored at successive slot numbers until the stopping slot number is reached.

4. The method of claim 3 further comprising:

locking zero or more slots between the starting slot number and the stopping slot number in accordance with an isolation level.

5. The method of claim 1 wherein the table comprises an overflow area, and further comprising:

accessing the overflow area when the specified key column value is outside the specified range.

6. The method of claim 1 wherein the table has an overflow area, and further comprising:

accessing the overflow area when the specified key value is a duplicate of one of the key values stored in the table.

7. The method of claim 1 further comprising:

prior to said accessing, storing at least one page of the table in a memory;

after said accessing, second accessing the particular row to change a portion of the data stored in the particular row, wherein the at least one page remains in the memory until said second accessing is complete.

8. The method of claim 2 wherein the slots are organized in logical pages, the logical pages being associated with physical pages, the logical pages being associated with a logical page number, the physical pages being associated with a physical page number;

further comprising;

storing an extent map cache in memory, the extent map cache storing a mapping of logical to physical page numbers,

wherein said accessing comprises determining a logical page number of a logical page containing a slot storing the particular row, and determining a physical page number storing the particular row based on the logical page number and the extent map cache.

9. An apparatus for operating a database management system, comprising:

a computer having a data storage device connected thereto, wherein the data storage device stores a table for storing data, the data being organized into rows and columns, at least one column being designated as an at least one key column;

one or more computer programs, executed by the computer, for accessing a particular row in the table based on a relationship between a specified key value and a predetermined range of key values associated with the at least one key column, wherein the table has slots for storing rows, the slots being organized in accordance with the values of the predetermined range.

10. The apparatus of claim 9, wherein said one or more computer programs for accessing comprises determining a slot number representing a location of a particular slot based on the relationship between the specified key value and the predetermined range of key values, wherein each slot of the table is associated with a slot number.

11. The apparatus of claim 9, wherein said one or more computer programs is also for:

receiving a starting search key value and a stopping search key value;

determining a stopping slot number based on the stopping search key value;

wherein said accessing the particular row determines the slot number such that the specified key value is the starting search key value to provide a starting slot number; and

repeatedly accessing rows stored at successive slot numbers until the stopping slot number is reached.

12. The apparatus of claim 10, wherein said one or more computer programs is also for locking zero or more slots between the starting slot number and the stopping slot number in accordance with an isolation level.

13. The apparatus of claim 9, wherein the table comprises an overflow area, and the one or more computer programs are also for:

accessing the overflow area when the specified key column value is outside the specified range.

14. The apparatus of claim 9, wherein the one or more computer program are also for prior to said accessing, storing at least one page of the table in a memory;

after said accessing, second accessing the particular row to change a portion of the data stored in the particular row, wherein the at least one page remains in the memory until said second accessing is complete.

15. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform a method of operating a database management system having a table for storing data, the data being organized into rows and columns, at least one column being designated as an at least one key column, the method comprising:

accessing a particular row in the table based on a relationship between a specified key value and a predetermined range of key values associated with the at least one key column, wherein the table has slots for storing rows, the slots being organized in accordance with the values of the predetermined range.

16. The article of manufacture of claim 15 wherein said accessing comprises determining a slot number representing a location of a particular slot based on the relationship between the specified key value and the predetermined range of key values, wherein each slot of the table is associated with a slot number.

17. The article of manufacture of claim 16 wherein the method further comprises:

receiving a starting search key value and a stopping search key value;

determining a stopping slot number based on the stopping search key value;

wherein said accessing the particular row determines the slot number such that the specified key value is the starting search key value to provide a starting slot number; and

repeatedly accessing rows stored at successive slot numbers until the stopping slot number is reached.

18. The article of manufacture of claim 17, wherein the method further comprises:

locking zero or more slots between the starting slot number and the stopping slot number in accordance with an isolation level.

19. The article of manufacture of claim 19, wherein the table comprises an overflow area, and the method further comprises:

accessing the overflow area when the specified key column value is outside the specified range.

20. The article of manufacture of claim 19, wherein the method further comprises:

prior to said accessing, storing at least one page of the table in a memory;

after said accessing, second accessing the particular row to change a portion of the data stored in the particular row, wherein the at least one page remains in the memory until said second accessing is complete.