1. A method of managing a database, comprising: receiving a set of one or more queries on a data set; receiving a set of statistics associated with the data set; and determining an optimal distribution policy to distribute data comprising the data set across a plurality of database servers, the determining comprising, after determining an initial candidate distribution policy, performing iterations, each iteration comprising: obtaining a policy set including one or more candidate distribution policies, the policy set initially including the initial candidate distribution policy; obtaining, from a query optimizer, a respective query plan of the set of one or more queries for each candidate distribution policy in the policy set by feeding the set of one or more queries to the query optimizer as inputs under the each candidate distribution policy; estimating, using each query plan and the set of statistics, a respective cost associated with each candidate distribution policy in the policy set, the cost representing a respective amount of estimated data movement under the query plan associated with the each candidate distribution policy; upon determining that a termination condition is satisfied, designating a candidate query plan in the policy set that is associated with a lowest cost as the optimal distribution policy and terminating the iterations; and upon determining that the termination condition is not satisfied, generating a distribution policy alternative based on a candidate distribution policy in the policy set and an amount of estimated data movement under that candidate distribution policy, adding the distribution policy alternative to the policy set as a new candidate distribution policy, and continuing the iterations.