The emerging paradigms of service oriented architectures and utility-based computing have the potential greatly reduce the cost of data management. Data management service providers negotiate with their customers agree on a service level agreement (SLA) that guarantees performance and reliability. However, these providers have the freedom to cut costs by taking advantage of economies of scale across multiple customers.

In this paper, we examine the problem of choosing a QoS level for each table or index in a service provider?s backend databases so as to minimize the dollar cost of provisioning storage while satisfying application-level SLAs. This problem is difficult because changes in the access cost of different portions of the database can cause the database to alter its access patterns. We develop an algorithm that optimizes the choice of query execution plans and storage layout simultaneously to meet an SLA at minimum cost.

In our experiments we use a part of the TPC-H benchmark as the workload and several models of the incremental cost of placing a volume at a high quality of service. Our results show that significant cost savings are possible through selective use of high storage QoS levels.