One or more computer-readable storage media storing instructions that, when executed by a computing device, perform a method of improving efficiency of a database query, the method (200; 400) comprising: receiving a database query; identifying one or more query portions of the database query as candidates for replacement; determining a plurality of alternative queries, the respective alternative queries including at least one substitute query portion in place of at least one of the candidates for replacement; determining an expected performance of at least some of the plurality of alternative queries; and based at least in part on the expected performance of the at least some of the plurality of alternative queries, selecting (210; 414) one or more alternative queries of the plurality of alternative queries as replacement database queries for the received database query; wherein determining the expected performance comprises: simulating the respective alternative queries giving an initial indication of performance not taking into account run-time optimization; based at least in part on results of the simulating, selecting a subset of the plurality of alternative queries, wherein the subset of the plurality of alternative queries has lower simulated query completion times than other alternative queries of the plurality of alternative queries; providing an additional evaluation of the subset of the plurality of alternative queries by performing the respective alternative queries of the subset using a sample dataset and estimating the effect of run-time optimization. receiving a database query; identifying one or more query portions of the database query as candidates for replacement; determining a plurality of alternative queries, the respective alternative queries including at least one substitute query portion in place of at least one of the candidates for replacement; determining an expected performance of at least some of the plurality of alternative queries; and based at least in part on the expected performance of the at least some of the plurality of alternative queries, selecting (210; 414) one or more alternative queries of the plurality of alternative queries as replacement database queries for the received database query; wherein determining the expected performance comprises: simulating the respective alternative queries giving an initial indication of performance not taking into account run-time optimization; based at least in part on results of the simulating, selecting a subset of the plurality of alternative queries, wherein the subset of the plurality of alternative queries has lower simulated query completion times than other alternative queries of the plurality of alternative queries; providing an additional evaluation of the subset of the plurality of alternative queries by performing the respective alternative queries of the subset using a sample dataset and estimating the effect of run-time optimization. simulating the respective alternative queries giving an initial indication of performance not taking into account run-time optimization; based at least in part on results of the simulating, selecting a subset of the plurality of alternative queries, wherein the subset of the plurality of alternative queries has lower simulated query completion times than other alternative queries of the plurality of alternative queries; providing an additional evaluation of the subset of the plurality of alternative queries by performing the respective alternative queries of the subset using a sample dataset and estimating the effect of run-time optimization.