1. A method for executing database commands, the method comprising: persistently maintaining, for a particular command, baseline data indicating a plurality of acceptable plans for executing the particular command; while persistently maintaining the baseline data, receiving a first request to execute the particular command; estimating, for each plan in the plurality of acceptable plans, predicted costs for satisfying the first request according to the plan; based on the predicted costs for each plan in the plurality of acceptable plans, selecting a particular plan from the set of acceptable plans; and in response to the first request to execute the particular command, executing the particular command according to the particular plan.