1. A computer implemented method comprising: partitioning a plurality of queries into a plurality of clusters, each cluster containing a plurality of queries; (a) for each query of the plurality of queries, generating a plurality of suggested rewrites, wherein each suggested rewrite of said plurality of suggested rewrites is the result of applying a query rewrite policy, the query rewrite policy being an ordered set of one or more query rewrite techniques, each query rewrite technique of said one or more query rewrite techniques being provided by a query rewrite provider of a plurality of query rewrite providers; (b) for each query, generating a set of rewrite scores, wherein each rewrite score of said set of rewrite scores reflects the quality of a particular suggested query rewrite generated for the query by a respective query rewrite policy; (c) for each cluster, generating aggregate rewrite scores by aggregating the rewrite scores of the same query rewrite policy for the same cluster; (d) based on the aggregate rewrite scores generated, query features of each query of said plurality of queries, and the rewrite scores generated for each query of the plurality of queries, generating a partitioning function by which to partition said plurality of queries into clusters; (e) based on the partitioning function, repartitioning said plurality of queries into a new set of clusters; repeating steps (a), (b), (c), (d) and (e) one or more times; and wherein the steps are performed by one or more computers.