System, method, and program for using duplicated direct pointer sets in keyed database records to enhance data recoverability without logging

• US 5,881,379 A
• Filed: 05/20/1996
• Issued: 03/09/1999
• Est. Priority Date: 05/20/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Beier, Harley Al, Kornelis, Sidney, Watts, Vern L.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/650,702
• Time in Patent Office: 1,023 Days
• Field of Search: 707/200, 707/202, 707/204, 707/100, 707/101, 707/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The system, method, and program product of this invention allows a database management system to internally use direct and indirect pointing to locate targeted data elements that are logically related to another data element or are a target of a secondary index. By using direct and indirect pointing, the number of steps involved in a reorganization of the database can be reduced. After a reorganization, the database management system does not go back, in a separate process, to update all of the direct pointers that have pointed to segments that have moved as a result of the reorganization. Instead, the direct pointer is updated, by using the indirect pointer, only upon a first reference to the targeted data element that has moved. Each targeted data element has an entry in an indirect index where a unique identifier of the targeted data element is the key into the index. The indirect index has two direct pointer slots. Which pointer slot is used by the DBMS is determined by the odd/even reorganization number. For each reorganization, the DBMS alternates between the two portions of the indirect index to update the appropriate one of the two pointers with a new location whenever the targeted data element is moved. As a result, the indirect index contains the most recent update and the most recent previous update. If the reorganization fails, the most recent previous pointer is used to find the location of the targeted data element. Consequently, as the reorganization process is proceeding, the update to the assigned slot for the new reorganization number can be made without logging and without involving unnecessary overhead associated with maintaining direct recoverability of the keyed data records.

Claims

1. A database system for reorganizing a database having at least one related data element related to a targeted data element, the database system comprising:

means for relocating to a new physical storage location the targeted data element independently of updating a direct pointer associated with the related data element to indicate a location of the targeted data element;

an indirect index having a unique indirect list entry key associated with two direct pointers;

the first pointer containing information relating to a relocation to the new physical storage location as a result of a most recent reorganization; and

the second pointer for containing previous information relating to a previous relocation to a previous storage location resulting from a previous reorganization;

means for updating the indirect index with the new physical storage location of the targeted data element when the targeted data element is relocated; and

means for updating, using the updated indirect index, the direct pointer at a first reference of the targeted data element after the targeted data element is relocated.

2. The database system of claim 1 wherein the means for updating the direct pointer further comprises means for using the second pointer in the indirect index if the relocation to the new physical storage location as the result of the most recent reorganization is backed out or not committed.

3. A database system, having at least one data element, comprising:

means for maintaining a reorganization number representing an update state of the data element wherein each subsequent update state is alternatingly associated with an odd or even reorganization number;

a data record having a keyed entry for at least each data element that is dependent, each keyed entry having duplicate direct pointers, a first direct pointer associated with the odd reorganization number and a second direct pointer associated with the even reorganization number, for pointing to a location of the data element;

means for determining whether to update the first direct pointer or the second direct pointer during a current reorganization depending upon whether the current reorganization number is odd or even;

updating the entry of the data record independently of logging the update in a separate record, whereby the entry contains, after an update, a current location and a most recent previous location;

accessing the first direct pointer for a current location of the data element if the current reorganization number is even and a current reorganization fails; and

accessing the second direct pointer for the current location of the data element if the current reorganization number is odd and the current reorganization fails.

4. A computer system comprising:

means for monatomically incrementing a number stored in memory representing an update state wherein each subsequent update state is alternatingly associated with an odd or even number;

a data structure in memory having two sets of fields for storing a most recently updated set of information and a previously updated set of information wherein a first set of fields, in a first part of the data structure, is associated with an odd number update and a second set of fields, in a second part of the data structure is associated with an even number update; and

means for accessing the first and second parts of the data structure in an alternating manner, dependent upon whether a current update state is associated with the odd or even number, during subsequent updates to information in the data structure.

5. The computer system of claim 4 further comprising means for accessing the second set of fields having previously updated set of information if the current update state is associated with an odd number and the current update state fails to complete.

6. The computer system of claim 4 further comprising means for accessing the first set of fields having the previously updated set of information if the current update state is associated with an even number and the current update state fails to complete.

7. A method of reorganizing a database having at least one related data element related to a targeted data element, the method comprising:

relocating to a new physical storage location the targeted data element independently of updating a direct pointer associated with the related data element to indicate a location of the targeted data element;

updating, in an alternating fashion, an indirect index with the new physical storage location of the targeted data element when the targeted data element is relocated, the indirect index having a unique indirect list entry key associated with two direct pointers;

the first pointer containing information relating to a relocation to the new physical storage location as a result of a most recent reorganization; and

the second pointer for containing previous information relating to a previous relocation to a previous storage location resulting from a previous reorganization; and

updating, using the updated indirect index, the direct pointer at a first reference of the targeted data element after the targeted data element is relocated.

8. The method of claim 7 wherein the step for updating the direct pointer further comprises using the second pointer in the indirect index if the relocation to the new physical storage location as the result of the most recent reorganization is backed out or not committed.

9. A method for use in a database system, the method comprising:

monatomically incrementing a number stored in memory representing an update state wherein each subsequent update state is alternatingly associated with an odd or even number; and

accessing, in an alternating manner, each one of two sets of fields of a data structure in memory for storing a most recently updated set of information and a previously updated set of information wherein a first set of fields, in a first part of the data structure, is associated with an odd number update and a second set of fields, in a second part of the data structure is associated with an even number update;

whereby the first and second parts of the data structure are accessed in an alternating manner dependent upon whether a current update state is associated with the odd or even number, during subsequent updates to information in the data structure.

10. A memory, for use with a database management system, for accessing a targeted data element from a related data segment, the memory comprising:

a direct pointer data structure comprising;

a first reorganization number indicating a reorganization level of a partition containing the targeted data element;

a relative byte address of a first location of the targeted data element associated with the first reorganization number;

a unique segment identifier of the targeted data element;

an indirect index data structure having the unique segment identifier as a key into the indirect index data structure comprising;

duplicated fields wherein a first set of fields is associated with an even reorganization number and a second set of fields is associated with an odd reorganization number, the first and second fields each containing;

the even or odd reorganization number indicating the reorganization level of the partition containing the targeted data element; and

a relative byte address of a second location of the targeted data element associated with the reorganization level indicated by the even or odd reorganization number;

whereby the indirect index has a most recent location of the targeted data element and a most recent previous location of the targeted data element.

11. A program product, for use with a database system having at least one related data element related to a targeted data element, the program product having program code, on a computer usable medium, comprising:

means for causing a determination that the targeted data element needs to be accessed from the related data element;

means for causing a use of a direct pointer data structure, associated with the related data element, having a first location of the targeted data element, a partition identifier of the targeted data element, and a first reorganization number associated with the location of the targeted data element for comparing the first reorganization number to a second reorganization number in memory for the targeted data element;

means for causing a use of the first location to locate the targeted data element if the first reorganization number and the second reorganization number are the same; and

means for causing a use of an indirect index data structure, by using the partition identifier as a key into the indirect data structure, the indirect index data structure having an odd and even portion reflecting the odd or even nature of the second reorganization number, the indirect index being updated with a newer location of the targeted data element in a portion associated with the odd or even nature of a latest reorganization number when the targeted data element is moved, to locate the targeted data element by using the newer location in the portion of the indirect index associated with the odd or even nature of the second reorganization number, if the first and second reorganization number are different.

12. A program product, for use with a database system, the program product having program code, on a computer usable medium, comprising:

means for causing a monatomical increment of a number stored in memory representing an update state wherein each subsequent update state is alternatingly associated with an odd or even number; and

means for causing an access, in an alternating manner, each one of two sets of fields of a data structure in memory for storing a most recently updated set of information and a previously updated set of information wherein a first set of fields, in a first part of the data structure, is associated with an odd number update and a second set of fields, in a second part of the data structure is associated with an even number update;

whereby the first and second parts of the data structure are accessed in an alternating manner dependent upon whether a current update state is associated with the odd or even number, during subsequent updates to information in the data structure.