Method for generating a multi-tiered index for partitioned data

• US 5,960,194 A
• Filed: 07/17/1996
• Issued: 09/28/1999
• Est. Priority Date: 09/11/1995
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Mohan, Chandrasekaran, Choy, David Mun-Hien
• Primary Examiner(s): AMSBURY, WAYNE P
• Assistant Examiner(s): Homere, Jean R.
• Application Number:
  US08/678,429
• Time in Patent Office: 1,168 Days
• Field of Search: 395/613, 395/612, 395/602, 395/603, 395/611, 395/497.04, 395/456, 395/480
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 9/355 Indexed addressing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• 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

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 generating a multi-tiered indexing structure for a partitioned database of objects, the partitioned database having a plurality of partitions, the method comprising the computer-implemented steps of:

a) creating a respective second index table of second index key values for each respective one of the partitions of the database, each second index table containing at least one second index entry for each object in the respective partition of the database; 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.

2. The method of claim 1 wherein each second index entry contained within each second index table created by the computer-implemented step a) of operating a second index table comprises:

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

b) a second index key value which relates to the identified object.

3. The method of claim 1 wherein each of the unique first index entries contained in the first index table created by the computer-implemented step b) of creating a first index table comprises:

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

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