System, method, and program for using direct and indirect pointers to logically related data and targets of indexes
First Claim
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;
means for updating an 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.
1 Assignment
0 Petitions
Accused Products
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. As such, each data element, that points to a targeted data element, has a direct pointer associated with it having a unique identifier of the targeted data element, assigned by the DBMS at the time a data element is created, a partition id of the targeted segment, a reorganization number, and a pointer to a location of the targeted data element. Each targeted data element has an entry in an indirect index where the unique identifier is the key into the index. Each entry is updated, with a new location, whenever the targeted data element is moved. The DBMS also maintains, in memory, a current reorganization number for each partition. Upon reference to a targeted element, the reorganization number in memory is compared with the reorganization number in the direct pointer. If they match, the direct pointer is used to locate the targeted element. If they do not match, the indirect index is used by indexing into it by using the unique id in the direct pointer. The current location and current reorg number from the indirect index are used to update the direct pointer. The direct pointer can then be used, directly, to locate the targeted data element on subsequent references until a next reorganization involves the targeted data segment.
139 Citations
19 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; means for updating an 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. A database system comprising:
-
direct pointing means associated with a first data element for locating a specific targeted data element related to the first data element; an indirect index for each targeted data element, the indirect index containing a unique identifier and a current location of each targeted data element; means for determining whether the direct pointing means are valid; means for locating the targeted data element using the direct pointing means if the means for determining determines the direct pointing means to be valid; means for using the current location in the indirect index to locate the targeted data element if the means for determining determines the direct pointing means to be invalid. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9)
-
-
10. 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 an indirect index with the new physical storage location of the targeted data element when the targeted data element is relocated; 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.
-
-
11. A method, for use in a database system, for locating a targeted data element from a related data element, the method comprising:
-
updating an indirect index with a current location of the targeted data element when the targeted data element is moved; determining whether a direct pointer, associated with the related data element, that directly points to the targeted data element, is valid; using the direct pointer to locate the targeted data element if the direct pointer is determined to be valid; and using the current location in the indirect index to locate the targeted data element if the direct pointer is determined to be invalid. - View Dependent Claims (13, 15)
-
-
12. A method, for use in a database system, for locating a targeted data element from a related data element, the method comprising:
-
assigning an unique identifier to each data element; updating an indirect index having the unique identifier as the key into the indirect index with a current location of the targeted data element when the targeted data element is moved; determining whether a direct pointer, associated with the related data element, that directly points to the targeted data element is valid; using the direct pointer to locate the targeted data element if the direct pointer is determined to be valid; and using the current location in the indirect index to locate the targeted data element if the direct pointer is determined to be invalid. - View Dependent Claims (14)
-
-
16. 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; a second 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 second reorganization number. - View Dependent Claims (17)
-
-
18. A program product, for use with a database system, having program code, on a computer usable medium, comprising:
-
means for causing an assignment of a unique identifier for each data segment in a database; means for determining, for each data segment that is moved, whether the data segment is logically related to a related data segment or is a target of an index, whereby if the data segment is logically related or a target of an index it is a targeted data segment; and means for using the unique identifier of the targeted data segment as a key into a indirect index data structure to update the indirect index data structure with a reorganization number indicative of a latest move of the targeted data segment and a new location of the targeted data segment.
-
-
19. 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, that is updated with a newer location of the targeted data element when the targeted data element is moved, to locate the targeted data element using the newer location if the first reorganization number and the second reorganization number are different.
-
Specification