Efficient Concurrency Control in Multidimensional Access Methods * Kaushik Chakrabarti Department of Computer Science University of Illinois at Urbana-Champaign [email protected] 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. 1 Introduction Database systems are being increasingly deployed to support emerging applications such as computer-aided design (CAD), geographical information systems (GIS), multimedia content- based retrieval systems, time-series databases, medical/health care applications, spatio-temporal databases etc. To support these applications efficiently on top of a DBMS, database systems must allow application developers to (1) define their own data types and operations on those data types, and (2) define their own indexing mechanisms on the stored data which the database query optimizer can exploit to access the data efficiently. The Object Relational DBMS (ORDBMS)/ Universal Server (US) technology addresses the first problem effectively [21]. But the ability to allow application developers * This work was supported in part by the National Science Foundation under Grant No. IIS-9734300, in part by the Army Research Laboratory under Cooperative Agreement No. DAALOl-96-2-0003 and in part by NASA under Grant No. B9U415912. Permission to make digital or hard topics of all or part of this work fog personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies hear this notice and the full citation on the tirst page. To copy otherwise, to republish, to post on scrvcrs or to redistribute to lists, requires prior specific permission and/or a fee. SIGMOD ‘99 Philadelphia PA Copyright ACM 1999 I-581 13-084-8/99/05...$5.00 Sharad Mehrotra Department of Information and Computer Science University of California at Irvine [email protected] to easily define their own access methods (AMs) still remains an elusive goal. The Generalized Search Tree (GiST) [9] addresses the above problem. GiST is an index structure that is extensible “both” in the data types it can index and in the queries it can support. It is like a “template” - the application developer can implement her own AM using GiST by simply registering a few extension methods with the DBMS. GiST solves two problems: Over the last few years, several multidimensional data structures have been developed for specific application domains. Implementing these data structures from scratch every time requires a significant coding effort. GiST can be adapted to work like these data structures, a much easier task than implementing the tree package from scratch. Since GiST is extensible, if it is supported in a DBMS, the DBMS can allow application developers to define their own AM, a task that was not possible before. Although GiST considerably reduces the effort of integrating new AMs in DBMSs, before it can be supported in a “commer- cial strength” DBMS, efficient techniques to support concurrent access to data via the GiST must be developed. Developing con- currency control (CC) techniques for GiST have several impor- tant benefits. (1) Since a wide variety of index structures can be implemented using GIST, developing CC techniques in the con- text of GiST would solve the CC problem for multidimensional index structures in general. (2) Experience with B-trees has shown that the implementation of CC protocols requires writing complex code and accounts for a major fraction of the effort for the AM implementation [8]. Developing the protocols for GiST is particularly beneficial since it would need writing the code only once and would allow concurrent access to the database via any index structure implemented in the DBMS using GiST, thus avoiding the need to write the code for each index structure separately. Concurrent access to data via a general index structure introduces two independent concurrency control problems: l Preserving consistency of the data structure in presence of concurrent insertions, deletions and updates. l Protecting search regions from phantoms This paper addresses the problem of phantom protection in GiSTs. In our previous research, we had studied a granular locking (GL) solution for phantom protection in R-trees [4]. We refer to it as the GUR-tree protocol. Due to fundamental differences between R-tree and GiST in the notion of a search key, the approach developed for R-trees is not a feasible solution for GiST. Specifically, the GL/R-tree protocol needs several modifications for making it applicable to GiSTs and 25Figure 1: A GiST for a key set comprising of rectangles in 2 dimensional space. 0 11 is a new object being inserted in node a search region. Predicates Pl through P6 are the BPS of the nodes N2 through N7 respectively. the modified algorithms, when applied to GiSTs, impose a significant overhead, botlh in terms of disk I/O as well as