1. A method comprising: evaluating a plurality of plans for executing a query on a multi-database system, the plurality of plans including a first plan and a second plan different from the first plan, and, as a result of evaluating, selecting a first plan, the first plan having a first step and a second step, the second plan having a first step and a second step, the first step of the first plan being the same as the first step of the second plan, and the second step of the first plan being different from the second step of the second plan; executing the first step of the first plan, after evaluating the plurality of plans and selecting the first plan; re-evaluating the plan selection after executing the first step of the first plan but before executing the second step of the first plan and, as a result of re-evaluating, selecting the second plan to continue executing the query; executing a second step of the second plan to produce a result; and storing the result.