After the optimizer has finished expanding the memo, the best plan is extracted from (copied out of) the memo structure. This plan is the optimizer output and, like the optimizer input, is represented as a tree. The best plan is selected by applying the procedure find best to the final group. Among all of the plans represented in the final group, this should be the plan of lowest cost.


Find Best
           For each intermediate table (i.e. group), there will be, in general, many possible plans capable of producing it. Find best is the procedure for finding the optimal plan for any given group.¹⁸

           Ignoring contexts and physical properties for a second, find best works by selecting a physical expression from a specified group, and then recursively selecting a physical expression for each input (group) of the selected expression. When an expression is chosen, it is copied into a query tree that is built¹⁹ as the memo is traversed. Eventually find best finds physical expressions with no input groups, and the recursive descent ends. Since physical expressions always contain physical operators, the resulting query tree contains only physical operators -- i.e. its a plan.

           When more than one physical expression is available in a group, the optimizer will try to choose the one with the least cost. In finding the best plan in a group, we may specify that the plan satisfy a certain context -- i.e. a certain combination of physical properties. For example, a context may require that the plan produce a table sorted on a particular attribute and/or that the plan have a cost below a certain threshold. It is possible that no plan satisfying the context can be found. Find best will either produce the least cost plan included in this group which satisfies the context, or it will indicate failure.

---

18. Find best is called with a context which must be satisfied as well as the group from which to find the best plan. This forms part of the the enforcement mechanism to assure that plans are well-formed -- that the inputs to a merge join are sorted appropriately, for example.
19. In fact, only the very last call to find best (on the final group) will output a plan. For calls to find best during the optimization, find best will report various optimization information such as whether a legal plan satisfying the input context can be found and, if so, what physical expression corresponds to the cheapest plan and what the cheapest cost is.

3. Fundamental Concepts:	<Models> <Log> <Query Trees> <Groups> <Memo> <Phys> <Item> <Rules> <Opt Stages> <Find Best> <Complexity>   3.1: EQJOIN     3.2a: Query Tree     3.2b: Equiv.     3.3a: Init Memo     3.3b: Memo     3.3c: Key     3.4: Complexity     3.5: Phys Memo     3.6: Plan     3.7: Pred.     3.8: Op Types     3.9: Rule

		Page 29