1. A method comprising: accessing, by a server in a network-based system, performance characteristics of each query of a query mix of a database; generating, by the server, a query quadtree decomposition for each query of the query mix, the quadtree decomposition for said query being based on the performance characteristics of said query, the quadtree decomposition for said query modeling a cost estimate of said query as a function of one or more system configuration parameters; generating, by the server, a mix quadtree decomposition for the query mix based on the quadtree decompositions for each query of the query mix, the mix quadtree decomposition modeling a multi-set of cost estimates of the set of queries when executed concurrently as a function of the one or more system configuration parameters; and generating a cost quadtree decomposition based on a cost classification function and the mix quadtree decomposition, the cost quadtree decomposition modeling a distribution of a cost-class label for the query mix as a function of the one or more system configuration parameters.