Concurrency Control Performance Modeling: Alternatives and Implications RAKESH AGRAWAL AT&T Bell Laboratories MICHAEL J. CAREY and MIRON LIVNY University of Wisconsin A number of recent studies have examined the performance of concurrency control algorithms for database management systems. The results reported to date, rather than being definitive, have tended to be contradictory. In this paper, rather than presenting “yet another algorithm performance study,” we critically investigate the assumptions made in the models used in past studies and their implica- tions. We employ a fairly complete model of a database environment for studying the relative performance of three different approaches to the concurrency control problem under a variety of modeling assumptions. The three approaches studied represent different extremes in how transaction conflicts are dealt with, and the assumptions addressed pertain to the nature of the database system’s resources, how transaction restarts are modeled, and the amount of information available to the concurrency control algorithm about transactions’ reference strings. We show that differences in the underlying assumptions explain the seemingly contradictory performance results. We also address the question of how realistic the various assumptions are for actual database systems. Categories and Subject Descriptors: H.2.4 [Database Management]: Systems-transaction process- ing; D.4.8 [Operating Systems]: Performance-simulation, modeling and prediction General Terms: Algorithms, Performance Additional Key Words and Phrases: Concurrency control 1. INTRODUCTION Research in the area of concurrency control for database systems has led to the development of many concurrency control algorithms. Most of these algorithms are based on one of three basic mechanisms: locking [23,31,32,44,48], timestamps [8,36,52], and optimistic concurrency control (also called commit-time validation or certification) [5, 16, 17, 271. Bernstein and Goodman [9, 101 survey many of A preliminary version of this paper appeared as “Models for Studying Concurrency Control Perform- ance: Alternatives and Implications, ” in Proceedings of the International Conference on Management of Data (Austin, TX., May 28-30, 1985). M. J. Carey and M. Livny were partially supported by the Wisconsin Alumni Research Foundation under National Science Foundation grant DCR-8402818 and an IBM Faculty Development Award. Authors’ addresses: R. Agrawal, AT&T Bell Laboratories, Murray Hill, NJ 07974; M. J. Carey and M. Livny, Computer Sciences Department, University of Wisconsin, Madison, WI 53706. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1987 ACM 0362~5915/87/1200-0609 $01.50 ACM Transactions on Database Systems, Vol. 12, No. 4, December 1987, Pages 609-654.610 l R. Agrawal et al. the algorithms that have been developed and describe how new algorithms may be created by combining the three basic mechanisms. Given the ever-growing number of available concurrency control algorithms, considerable research has recently been devoted to evaluating the performance of concurrency control algorithms. The behavior of locking has been investigated using both simulation [6, 28, 29, 39-41, 471 and analytical models [22,24, 26,35, 37,50,51,53]. A qualitative study that discussed performance issues for a number of distributed locking and timestamp algorithms was presented in [7], and an empirical comparison of several concurrency control schemes was given in [34]. Recently, the performance of different concurrency control mechanisms has been compared in a number of studies. The performance of locking was compared with the performance of basic timestamp ordering in [21] and with basic and multi- version timestamp ordering in [30]. The performance of several alternatives for handling deadlock in locking algorithms was studied in [6]. Results of experi- ments comparing locking to the optimistic method appeared in [42 and 431, and the performance of several variants of locking, basic timestamp ordering, and the optimistic method was compared in [12 and 151. Finally, the performance of several integrated concurrency control and recovery algorithms was evaluated in [l and 21. These performance studies are informative, but the results that have emerged, instead of being definitive, have been very contradictory. For example, studies by Carey and Stonebraker [15] and Agrawal and Dewitt [2] suggest that an algorithm that uses blocking instead of restarts is preferable from a performance viewpoint, but studies by Tay [50, 511 and Balter et al, [6] suggest that restarts lead to better performance than blocking. Optimistic methods outperformed locking in [20], whereas the opposite results were reported in [2 and 151. In this paper, rather than presenting “yet another algorithm performance study,” we examine the reasons for these apparent contradictions, addressing the models used in past studies and their implications. The research that led to the development of the many currently available concurrency control algorithms was guided by the notion of serializability as the correctness criteria for general-purpose concurrency control algorithms [ 11, 19, 331. Transactions are typically viewed as sequences of read and write requests, and the interleaved sequence of read and write requests for a concurrent execution of transactions is called the execution log. Proving algorithm correctness then amounts to proving that any log that can be generated using a particular