Accession Number:

ADA465777

Title:

Efficient Concurrency Control in Multidimensional Access Methods

Descriptive Note:

Corporate Author:

ILLINOIS UNIV AT URBANA-CHAMPAIGN DEPT OF COMPUTER SCIENCE

Report Date:

1999-01-01

Pagination or Media Count:

13.0

Abstract:

The importance of multidimensional index structures to numerous emerging database applications is well established. However, before these index structures can be supported as access methods AMs in a commercial-strength database management system DBMS, efficient techniques to provide transactional access to data via the index structure must be developed. Concurrent accesses to data via index structures introduce the problem of protecting ranges specified in the retrieval from phantom insertions and deletions the phantom problem. This paper presents a dynamic granular locking approach to phantom protection in Generalized Search Trees GiSTs, an index structure supporting an extensible set of queries and data types. The granular locking technique offers a high degree of concurrency and has a low lock overhead. Our experiments show that the granular locking technique 1 scales well under various system loads and 2 similar to the B-tree case, provides a significantly more efficient implementation compared to predicate locking for multidimensional AMs as well. Since a wide variety of multidimensional index structures can be implemented using GiST, the developed algorithms provide a general solution to concurrency control in multidimensional AMs. To the best of our knowledge, this paper provides the first such solution based on granular locking.

Subject Categories:

  • Information Science

Distribution Statement:

APPROVED FOR PUBLIC RELEASE