Integrated performance analysis of caching, recovery, and concurrency control algorithms in database systems

This dissertation presents performance analyses of database system algorithms using a comprehensive analytic modeling framework. The objective of the research is to realistically model and compare the normal run-time overhead of database recovery algorithms that use general purpose computer hardware. The framework includes non-uniform data access, main memory caching, hardware resource contention, and concurrency control. Transaction throughput and response time are computed for the studied recovery algorithms as performance measures. The independent reference model (IRM) is used to model the locality of data reference in the study. The modular framework includes a cache performance model, resource contention queuing models, and a concurrency control data contention model.; Database caching performance is studied using the least recently used (LRU) cache page replacement rule. The study yields a technique for computing the cache-hit ratio that has much lower computational complexity than previous methods, and also derives expressions for other cache performance measures not previously available. The analytic results are verified by simulation and found to be highly accurate.; The specific database algorithms modeled and compared are the database-cache recovery algorithm of Bayer, its three variants, before-image logging, and an algorithm free of recovery related overhead. The parameters needed for the hardware resource queuing models are computed by performing a detailed probabilistic analysis of each database recovery algorithm, utilizing the results of the caching study. The detailed queuing networks are solved using mean value analysis technique. The analytic results are verified by a simulation study. Numerical examples are given to illustrate the performance enhancement in transaction throughput and response time that can be achieved by database-cache as compared with other techniques.; Next, a Markov model of 2-phase locking concurrency control is developed to quantify the amount blocking that transactions experience due to data contention. To complete the comprehensive framework, a method is developed that integrates the results of the concurrency control model with the results of the hardware resource queuing models, yielding the overall transaction throughput and response time. The overall results are compared with a simulation study and are found to be highly accurate.