The claimed subject matter provides a system and method for automatic allocation of tenants to database services. An exemplary method comprises determining a query plan based on a workload for each tenant. A distance metric is created based on the query plan for each tenant, and tenants are clustered based on the distance metric into a predetermined number of clusters which is equal to the predetermined number of databases.