US 5,551,027 A · Multi-tiered indexing method for partitioned data

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.

Claims11

Dependent claims

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.

15 more elements

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.

12 more elements

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.

7 more elements

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.

7 more elements

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.

5 more elements

Dependencies are inferred from the claim text.

Multi-tiered indexing method for partitioned data

Life of this patent

Multi-tiered indexing method for partitioned data

Life of this patent

Abstract

Claims11