The management of large distributed databases is becoming more complex as user demand grows. Further, global access causes points of geographic contention to ‘follow the sun’ during the day giving rise to a dynamic optimisation problem where the goal is to constantly maximise the quality of service seen by the database users. A key quality criterion is to optimise the quality of service perceived by the worst-served user by finding a choice of client-server mapping which best balances issues such as exploitation of fast servers and communications links, and the degradation in response-time due to over-use of such servers/links. Any approach to solving the problem must be fast (so that results remain applicable) and successful over a variety of different database usage scenarios and quality of service metrics. This paper investigates the effectiveness of several local and evolutionary search approaches to this problem, focusing on the variations in performance across a range of QoS metrics.