1. A method of optimizing a query, comprising: determining a cost estimate for a query; determining a budget for optimizing the query based on the cost estimate; determining a complexity of the query; determining a strategy based on the complexity and the budget, wherein the strategy specifies a limit to a search space enumerated during optimization of the query; and optimizing the query based on the strategy.