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 implications 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 ing D 4 8 Operating Systems Performance simulation modeling and prediction General Terms Algorithms Additional process Performance 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 PerformConference on Management ance Alternatives and Implications in Proceedings of the International 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 multiversion timestamp ordering in 30 The performance of several alternatives for handling deadlock in locking algorithms was studied in 6 Results of experiments 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 concurrency control algorithm is equivalent to some serial log i e one in which all requests from each individual transaction are adjacent in the log Algorithm correctness work has therefore been guided by the existence of this widely accepted standard approach based on logs and serializability Algorithm performance work has not been so fortunate no analogous standard performance model has been available to guide the work in this area As we will see shortly the result is that nearly every study has been based on its own unique set of assumptions regarding database system resources transaction behavior and other such issues In this paper we begin by establishing a performance evaluation framework based on a fairly complete model of a database management system Our model ACM