Cost estimation may often estimate different plans to have the same cost.

This may result in non-deterministic behavior when plans are enumerated in a different order. In such cases a different plan from the set of plans with equal costs will be chosen as the optimal one. This will be problematic both for testing and for the end-users.

Few simple ideas how to impose an order on equal-cost plans:

• Add a different minimum cost for each type of node, so that when all CEs of all leaf nodes are the same, the costs of different plans are different.
• Improve the resolution of the cost model, so that it takes more plan properties into account, e.g. the average size of keys/documents.
• Consider some structural properties of plans that may affect their cost.
• Order the plans according to some stable property
  • plan hash - if it is consistent, or
  • string comparison of the string representation of the plan.