Multi-tiered indexing method for partitioned data

• US 5,551,027 A
• Filed: 09/11/1995
• Issued: 08/27/1996
• Est. Priority Date: 01/07/1993
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Mohan, Chandrasekaran, Choy, David M.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/526,723
• Time in Patent Office: 351 Days
• Field of Search: 395/600, 395/497.04, 395/456, 395/480, 395/416, 395/421.06, 364/DIG. 1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 9/355 Indexed addressing
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A multi-tiered indexing method is disclosed for a partitioned table in a parallel or distributed database system. A Local Index is created and maintained for each partition of the table and a Coarse Global Index is created and maintained. The Coarse Global Index identifies the indexed partition(s) by partition identifiers (PIDs) and associates the individual Index Key Values with their target partitions so that an access request with a highly partition-selective search predicate on the Index Key can be quickly and easily directed to the target partition(s) for processing. An index maintenance locking protocol is also disclosed which handles the insertion and deletion of index entries and assures the consistency between the Local Index entries and the Coarse Global Index entries during concurrent index accesses by different transactions. The locking protocol minimizes locking only to those cases involving an inserted or deleted key and to the key following and possibly the key preceding the inserted or deleted key to allow high concurrency between simultaneous Readers, Inserters, and Deleters. This method enhances the efficiency of complex query evaluation and index maintenance and attains a high throughput for transaction processing.

Claims

1. A method for maintaining consistency between a second index table and a first index table in a multi-tiered index structure to handle the insertion of an index entry into a unique index, the multi-tiered index structure including a respective second index table of index key values corresponding with each respective partition of a partitioned database and a first index table containing at least one unique first index entry for each index key value in each of the respective second index tables,

i) wherein the second index table has a second index identifier and contains second index entries, each of the second index entries having an identifier which identifies an object in the respective database partition corresponding with the second index table, and having a second index key value which relates to the identified object, at least some of the index key values being distinct, and

ii) wherein the first index table has at least one first index entry for each distinct one of the second index key values in each second index table, each of the first index entries having a second index identifier which identifies a second index table, and having a first index key value which relates to one of the second index key values in the identified second index table,

the method comprising the computer-implemented steps of:

A) determining if the second index key value in the index entry to be inserted is already present in the second index table;

B) if the second index key value in the index entry to be inserted is already present in the second index table, then rejecting the insertion; and

C) if the second index key value in the index entry to be inserted is not already present in the second index table, then performing the steps of;

1) inserting the index entry into the second index table;

2) determining if the first index key value which relates to the second index key value is already present in the first index table, and

3) if the first index key value which relates to the second index key value is already present, performing the steps of;

i) deleting the inserted second index entry from the second index table; and

ii) rejecting the insertion;

4) determining if the first index key value which relates to the second index key value is present in the first index table, and,

5) if the first index key value which relates to the second index key value is not present, then inserting, into the first index table,

i) a first index entry having a first index key value relating to the second index key value; and

ii) a second index identifier identifying the second index table.

2. A method for maintaining consistency between a second index table and a first index table in a multi-tiered index structure to handle the deletion of an index entry in a unique index, the multi-tiered index structure including a respective second index table of index key values corresponding with each respective partition of a partitioned database and a first index table containing at least one unique first index entry for each index key value in each of the respective second index tables,

i) wherein the second index table has a second index identifier and contains second index entries, each of the second index entries having an identifier which identifies an object in the respective database partition corresponding with the second index table, and having a second index key value which relates to the identified object, at least some of the index key values being distinct, and

ii) wherein the first index table has at least one first index entry for each distinct one of the second index key values in each second index table, each of the first index entries having a second index identifier which identifies a second index table, and having a first index key value which relates to one of the second index key values in the identified second index table,

the method comprising the computer-implemented steps of:

a) determining if the second index key value in an index entry to be inserted is already present in the second index table; and

b) if the second index key value is not already present, then performing the steps of;

1) deleting the index entry from the second index table; and

2) deleting from the first index table the first index entry relating to the second index key value and the second index identifier.

3. A method for maintaining consistency between a second index table and a first index table in a multi-tiered index structure to handle the insertion of an index entry into a non-unique index, the multi-tiered index structure including a respective second index table of index key values corresponding with each respective partition of a partitioned database and a first index table containing at least one unique first index entry for each index key value in each of the respective second index tables,

i) wherein the second index table has a second index identifier and contains second index entries, each of the second index entries having an identifier which identifies an object in the respective database partition corresponding with the second index table, and having a second index key value which relates to the identified object, at least some of the second index key values being distinct, and

ii) wherein the first index table has at least one first index entry for each distinct one of the second index key values in each second index table, each of the first index entries having a second index identifier which identifies a second index table, and having a first index key value which relates to one of the second index key values in the identified second index table,

the method comprising the computer-implemented steps of:

a) determining if the second index key value in the index entry to be inserted is already present in the second index table; and

b) if the second index key value in the index entry to be inserted is not already present, then;

1) inserting the index entry into the second index table; and

2) inserting into the first index table a first index entry having a first index key value relating to the second index key value and a second index identifier identifying the second index table.

4. A method for maintaining consistency between a second index table and a first index table in a multi-tiered index structure to handle the deletion of an index entry into a non-unique index, the multi-tiered index structure including a respective second index table of index key values corresponding with each respective partition of a partitioned database and a first index table containing at least one unique first index entry for each index key value in each of the respective second index tables,

i) wherein the second index table has a second index identifier and contains second index entries, each of the second index entries having an identifier which identifies an object in the respective database partition corresponding with the second index table, and having a second index key value which relates to the identified object, at least some of the second index key values being distinct, and

ii) wherein the first index table has at least one first index entry for each distinct one of the second index key values in each second index table, each of the first index entries having a second index identifier which identifies a second index table, and having a first index key value which relates to one of the second index key values in the identified second index table,

the method comprising the computer-implemented steps of:

a) deleting the index entry from the second index table;

b) determining if the second index key value in the index entry deleted is still present in the second index table; and

c) if the second index key value in the index entry deleted is not present any longer, then deleting from the first index table a first index entry having a first index key value relating to the second index key value and a second index identifier identifying the second index table.

5. A method for generating a multi-tiered indexing structure for a partitioned database of objects, the database including a plurality of partitions, the method comprising the computer-implemented steps of:

a) creating a respective second index table for each respective one of the partitions of the database wherein the second index table contains at least one second index entry for each object of interest in the respective partition of the database, the second index entry comprising;

1) an object identifier identifying an object in the respective partition; and

2) a second index key value which relates to the identified object; and

b) creating a first index table containing at least one unique first index entry for each distinct second index key value in each of the respective second index tables, each of the first index entries comprising;

1) a second index identifier which identifies a second index table; and

2) a first index key value which relates to a second index key value in the identified second index table.

6. A computer program product, for use in a partitioned computer database system of objects, the database system including a plurality of partitions, for generating a multi-tiered indexing on structure, the computer program product comprising:

a) a magnetic recording medium for retaining a set of computer program instructions;

b) means, recorded on said magnetic recording medium, for instructing said computer system to create a respective second index table for each respective one of the partitions of the database, wherein the second index table contains at least one second index entry for each object in the respective partition of the database, the second index entry comprising;

i) an object identifier identifying an object in the respective partition; and

ii) a second index key value which relates to the identified object; and

c) means, recorded on said magnetic recording medium, for instructing said computer system to create a first index table containing at least one unique first index entry for each distinct second index key value in each of the respective second index tables, the first index entry comprising;

i) a second index identifier which identifies a second index table; and

ii) a first index key value which relates to a second index key value in the identified second index table.

7. A computer program product for use in a partitioned computer database system of objects for maintaining consistency between a second index table and a first index table in a multi-tiered index structure to handle the insertion of an index entry into a unique index, the multi-tiered index structure including a respective second index table of index key values corresponding with each respective partition of a partitioned database and a first index table containing at least one unique first index entry for each index key value in each of the respective second index tables,

i) wherein the second index table has a second index identifier and contains second index entries, each of the second index entries having an identifier which identifies an object in the respective database partition corresponding with the second index table, and having a second index key value which relates to the identified object, at least some of the second index key values being distinct, and

ii) wherein the first index table has at least one first index entry for each distinct one of the second index key values in each second index table, each of the first index entries having a second index identifier which identifies a second index table, and having a first index key value which relates to one of the second index key values in the identified second index table,

the computer program product comprising:

a) a magnetic recording medium for retaining a set of computer program instructions;

b) means, recorded on said magnetic recording medium, for instructing said computer system to determine if the second index key value in the index entry to be inserted is already present in the second index table;

c) means, recorded on said magnetic recording medium, for instructing said computer system to reject the insertion, the means for directing to reject being operable if the second index key value in the index entry to be inserted is already present; and

d) means, recorded on the magnetic recording medium and operable if the second index key value in the index entry to be inserted is not already present in the second index table, for instructing said computer system;

i) to insert the index entry into the second index table;

ii) to determine if the first index key value which relates to the second index key value is already present in the first index table,

iii) if the first index key value which relates to the second index key value is already present, to delete the inserted second index entry from the second index table,

iv) to reject the insertion;

v) to determine if the first index key value which relates to the second index key value is present in the first index table; and

vi) if the first index key value which relates to the second index key value is not present, then inserting into the first index table a first index entry having a first index key value relating to the second index key value and a second index identifier identifying the second index table.

8. A computer program product for use in a partitioned computer database system of objects for maintaining consistency between a second index table and a first index table in a multi-tiered index structure to handle the deletion of an index entry in a unique index, the multi-tiered index structure including a respective second index table of index key values corresponding with each respective partition of a partitioned database and a first index table containing at least one unique first index entry for each index key value in each of the respective second index tables,

i) wherein the second index table has a second index identifier and contains second index entries, each of the second index entries having an identifier which identifies an object in the respective database partition corresponding with the second index table, and having a second index key value which relates to the identified object, at least some of the second index key values being distinct, and

ii) wherein the first index table has at least one first index entry for each distinct one of the second index key values in each second index table, each of the first index entries having a second index identifier which identifies a second index table, and having a first index key value which relates to one of the second index key values in the identified second index table,

the computer program product comprising:

a) a magnetic recording medium for retaining a set of computer program instructions;

b) means, recorded on said magnetic recording medium, for instructing said computer system to determine if the second index key value in an index entry to be inserted is already present in the second index table; and

c) means, operable if the index entry to be inserted is not already present, recorded on said magnetic recording medium, for instructing said computer system;

i) to delete the index entry from the second index table; and

ii) to delete, from the first index table, the first index entry relating to the second index key value and the second index identifier.

9. A computer program product for use in a partitioned computer database system of objects for maintaining consistency between a second index table and a first index table in a multi-tiered index structure to handle the insertion of an index entry into a non-unique index, the multi-tiered index structure including a respective second index table of index key values corresponding with each respective partition of a partitioned database and a first index table containing at least one unique first index entry for each index key value in each of the respective second index tables,

i) wherein the second index table has a second index identifier and contains second index entries, each of the second index entries having an identifier which identifies an object in the respective database partition corresponding with the second index table, and having a second index key value which relates to the identified object, at least some of the second index key values being distinct, and

ii) wherein a first index table has at least one first index entry for each distinct one of the second index key values in each second index table, each of the first index entries having a second index identifier which identifies a second index table, and having a first index key value which relates to one of the second index key values in the identified second index table,

the computer program product comprising:

a) a magnetic recording medium for retaining a set of computer program instructions;

b) means, recorded on said magnetic recording medium, for instructing said computer system to determine if the second index key value in an index entry to be inserted is already present in the second index table; and

c) means, operable if the second index key value in the index entry to be inserted is not already present in the second index table, recorded on said magnetic recording medium, for instructing said computer system;

i) to insert the index entry from the second index table; and

ii) to insert into the first index table a first index entry having a first index key value relating to the second index key value and a second index identifier identifying the second index table.

10. A computer program product for use in a partitioned computer database system of objects for maintaining consistency between a second index table and a first index table in a multi-tiered index structure to handle the deletion of an index entry in a unique index, the multi-tiered index structure including a respective second index table of index key values corresponding with each respective partition of a partitioned database and a first index table containing at least one unique first index entry for each index key value in each of the respective second index tables,

i) wherein the second index table has a second index identifier and contains second index entries, each of the second index entries having an identifier which identifies an object in the respective database partition corresponding with the second index table, and having a second index key value which relates to the identified object, at least some of the second index key values being distinct, and

ii) wherein the first index table has at least one first index entry for each distinct one of the second index key values in each second index table, each of the first index entries having a second index identifier which identifies a second index table, and having a first index key value which relates to one of the second index key values in the identified second index table,

the computer program product comprising:

a) a magnetic recording medium for retaining a set of computer program instructions;

b) means, recorded on said magnetic recording medium, for instructing said computer system to delete the index entry from the second index table;

c) means, recorded on said magnetic recording medium, for instructing said computer system to determine if the second index key value in the index entry deleted is still present in the second index table; and

d) means, operable if the second index key value in the index entry deleted is not present any longer, recorded on said magnetic recording medium, for instructing said computer system to delete from the first index table a first index entry having a first index key value relating to the second index key value and a second index identifier the second index table.

11. A partitioned database computer system comprising:

a) a processor for processing information within said partitioned database computer system;

b) at least two respective data storage devices, the database computer system being configured as at least two respective partitioned database subsystems divided by at least one database partition;

c) database management means for reading and updating database information from said at least one database disk; and

d) a multi-tiered indexing structure comprising;

i) a respective second index table for each respective one of the partitions, each respective one of the index tables having at least one second index entry for each object in the respective one of the partitions, each second index entry comprising;

an object identifier identifying an object in the respective partition; and

a second index key value which relates to the identified object; and

ii) a first index table having at least one unique first index entry for each distinct second index key value in each of the respective second index tables, each first index entry comprising;

a second index identifier which identifies a second index table; and

a first index key value which relates to a second index key value in the identified second index table.