Method for generating a multi-tiered index for partitioned data

Details Method for generating a multi-tiered index for partitioned data Method for generating a multi-tiered index for partitioned data

1996-07-17

1999-09-28

Amsbury, Wayne

395602, 395603, 395612, 395614, 395611, 395456, 395480, 39549704, G06F 9355, G06F 1200

Patent

active

059601949

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.

REFERENCES:
patent: 4468728 (1984-08-01), Wang
patent: 4811199 (1989-03-01), Kuechler et al.
patent: 4853843 (1989-08-01), Ecklund
patent: 4914569 (1990-04-01), Levine et al.
patent: 4933848 (1990-06-01), Haderle et al.
patent: 4937760 (1990-06-01), Beitel et al.
patent: 4961134 (1990-10-01), Crus et al.
patent: 4961139 (1990-10-01), Hong et al.
patent: 5058002 (1991-10-01), Nakamura et al.
patent: 5093911 (1992-03-01), Parks et al.
patent: 5247672 (1993-09-01), Mohan
patent: 5257365 (1993-10-01), Powers et al.
patent: 5261088 (1993-11-01), Baird et al.
patent: 5293595 (1994-03-01), Caldarale et al.
patent: 5293616 (1994-03-01), Flint
patent: 5301286 (1994-04-01), Rajani
patent: 5404510 (1995-04-01), Smith et al.
patent: 5442784 (1995-08-01), Powers et al.
patent: 5499359 (1996-03-01), Vijayknmar
patent: 5511190 (1996-04-01), Sharma et al.
patent: 5515531 (1996-05-01), Fujiwara et al.
patent: 5551027 (1996-08-01), Choy et al.
Elmasri et al. "Fundamentals of Database Systems", The Benjamin/Cummings Publishing Company, Inc., 1989, pp. 101-127.
C. Mohan, Commit-LSN: A Novel and Simple Method for Reducing Locking ans Latching in Transaction Processing Systems, Proceesings of the 16th VLDB Conf. Brisbane, Australia, Aug. 1990.
C. Mohan, Aries/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes, Proceedings of the 16th VLDB Conference, Brisbane, Australia, Aug. 1990.
C. Mohan et al., ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging, Proc. SIGMOD International Conference on Management of Data, San Diego, Jun. 1992.
C. Mohan et al., Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques, Data Base Technology Institute, IBM Almaden and Data Base Technology Institute IBM Santa Teresa Lab, San Jose, pp. 29-40.
D. M. Choy et al., An Efficient Indexing Method for Partitioned Data, to be presented at 9th International Conf. on Data Engineering, Apr. 21, 1993-Apr. 23, 1993 at Vienna, Austria.

Affiliated with

Also associated with

Rating

Method for generating a multi-tiered index for partitioned data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for generating a multi-tiered index for partitioned data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating a multi-tiered index for partitioned data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-714144