Enhancing Parallelism and Scalability of Database-Centric Applications in Presence of Database Deadlocks

Currently, in Database-Centric Applications (DCAs), database deadlocks are typically detected at runtime within database engines using special algorithms that analyze whether resources are held in cyclic dependencies, and these database engines resolve database deadlocks by forcibly breaking the hold-and-wait cycle. That is, once a deadlock occurs, the database rolls back one of the SQL statements that is involved in the circular wait. This resolution causes severe performance degradation, since DCAs should repeat the rolled back SQL statements to ensure functional correctness. Doing so not only reduces parallelism in executing SQL statements by databases, but also requires these databases to re-execute the same SQL statements thus decreasing the throughput and negatively affecting the scalability of the DCAs. We present novel solutions to a fundamental problem of predicting and preventing database deadlocks (PD)2 in DCAs, and we rigorously evaluate these solutions on several different open-source and commercial DCAs, some of which still exhibit database deadlocks after having been used for close to two decades. In evaluating (PD)2, we addressed various research questions that establish the effectiveness of our solutions.