RITA: an index-tuning advisor for replicated databases

Given a replicated database, a divergent design tunes the indexes in each replica differently in order to specialize it for a specific subset of the workload. Empirical studies have shown that this specialization brings significant performance gains compared to the common practice of having the same indexes in all replicas. However, reaping the benefits of divergent designs requires the development of new tuning tools for database administrators, and the existing tools unfortunately suffer from severe shortcomings: they assume a fixed number of replicas and a known workload distribution, and ignore the possibility of replica failures and the subsequent effect on load imbalance.

To address these shortcomings, we analyze the theory and practice of tuning the divergent design of a replicated database. We design and implement RITA, a novel divergent-tuning advisor that offers several essential features not found in existing tools: (1) it generates robust divergent designs that allow the system to adapt gracefully to replica failures; (2) it computes designs that spread the load evenly among specialized replicas, both during normal operation and when replicas fail; (3) it monitors the workload online in order to detect changes that require a recomputation of the divergent design; and, (4) it offers suggestions to elastically reconfigure the system (by adding/removing replicas or adding/dropping indexes) to respond to workload changes. The key technical innovation in this paper is the formulation the problem of selecting an optimal design as a Binary Integer Program (BIP). The BIP has a relatively small number of variables, thereby enabling an efficient solution using any off-the-shelf linear-optimization software. Experimental results demonstrate that RITA improves on the performance of the computed designs of existing tools by a factor of up to three, and at the same time has a low runtime overhead that enables fast tuning sessions.