In this well-organized paper, an integrated concurrency control method is suggested for B-trees and its correctness is proven. All concurrency control methods belong to one of the following two categories: pessimistic or optimistic concurrency control methods. Methods which rely on locking of data objects are called pessimistic, since database resources are locked even though operations may not conflict with other executing operations. Since locking may be necessary only in the worst case, it may unnecessarily prevent operations from being executed concurrently. Another type of approach is based on the idea that conflicts are infrequent situations and, therefore, appropriate actions to preserve database integrity should only be taken when necessary. Hoping that conflicts between operations will not occur, these methods rely mainly on operation restart as a control mechanism and are called optimistic.
From these basic ideas, the author draws the following obvious conclusions: if conflicting operations are rather likely, locking should be used instead of the optimistic method, since restart would be rather frequent and might lead to starvation in the extreme case. However, if the probability of conflict is rather low, then the optimistic method should be used since restart will be the exception, whereas lock maintenance would be expensive and potential concurrency be reduced.
The major contribution of the paper is the suggestion of a concurrency control method integrating locking and the optimistic method such that locking is used only when conflicts are likely. For this purpose, two types of operations are introduced: o-type operations which are executed under the optimistic method, and 1-type operations which use locking at least with respect to a subtree of the B-tree. Both type of operations use the local/global phase operation model, which is the basis for the optimistic method. Subsequently, it is shown that the suggested integrated concurrency control method guarantees serializability for concurrent executions of o-type and 1-type operations and thus its correctness is proven. The paper concludes with a number of criteria which may determine the decision whether to use o-type or 1-type operations; i.e., whether to use the optimistic method or locking. This criterion may be the type of operation (search, insert, delete, or update), the key value of the operation, the storage utilization factor of the B-tree, or the number of restarts in the optimistic method.
Experimental performance comparisons of the optimistic method versus locking carries out by the reviewer for multidimensional B-trees point out the following: percentage of queries in the operation mix is the most important criterion for deciding whether to use the optimistic method or locking.