Optimizing Concurrency Control: Robustness Against Read Committed Revisited

Abstract

While serializability always guarantees application correctness, lower isolation levels can be chosen to improve transaction throughput at the risk of introducing certain anomalies. A set of transactions is robust against a given isolation level if every possible interleaving of the transactions under the specified isolation level is serializable. Robustness therefore always guarantees application correctness with the performance benefit of the lower isolation level. In this thesis, we focus on robustness against Read Committed (RC), a popular isolation level o↵ered by many database systems. We consider di↵erent flavours of RC, both in single version (SVRC) and multiversion (MVRC) settings. The first main contribution of this thesis is a characterization of robustness against both isolation levels when the workload consists of a set of transactions. These characterizations are in terms of the absence of counterexample schedules of a specific form (multi-split schedules for SVRC and multiversion split schedules for MVRC). Based on these characterizations, we show that robustness against SVRC is coNP-hard and provide a polynomial time algorithm deciding robustness against MVRC. In practice, the total number of possible transactions might be huge, but all these transactions are often generated by a small set of predefined transaction programs. The second main contribution of this thesis is a study of robustness against MVRC where workloads are specified as a set of transaction programs. To identify such cases, we introduce an expressive model of transaction programs, called transaction templates, to better reason about the serializability of these workloads. We develop a tractable algorithm to decide whether any possible schedule over such a workload executed under MVRC is serializable. Our approach yields robust subsets that are larger than those identified by previous methods. We provide experimental evidence that workloads that are robust against MVRC can be evaluated faster under MVRC compared to stronger isolation levels. We discuss techniques for making workloads robust against MVRC by promoting selective read operations to updates. Depending on the scenario, the performance improvements can be considerable. Robustness testing and safely executing transactions under the lower isolation level MVRC can therefore provide a direct way to increase transaction throughput without changing DBMS internals. An important insight is that, by more accurately modeling transaction programs, we are able to recognize larger sets of workloads as robust. The third main contribution of this thesis is a further increase of the modeling power of transaction templates by extending them with functional constraints, which are useful for capturing data dependencies like foreign keys. We show that the incorporation of functional constraints can identify more workloads as robust against MVRC that otherwise would not be. Even though we establish that the robustness problem becomes undecidable in its most general form, we show that various restrictions on functional constraints lead to decidable and even tractable fragments that can be used to model and test for robustness against MVRC for realistic scenarios.