The ordering of the branches in an OR stage should not affect the performance of the plan, since all branches must be executed in full in order for the plan to complete. However, the order of the children can matter for plan selection, e.g. for users who are affected by SERVER-20616. The ordering chosen by the access planner is not only arbitrary right now, but it is not stable. That is, multiple executions of the same query could theoretically choose a different OR ordering. The improvement tracked by this ticket is to ensure that the planner always chooses a particular, if arbitrary, ordering.

The ordering chosen right now is a function of the sort by TagComparison done in preparation for access planning. The problem is that two very different MatchExpression nodes can easily sort equally under this comparison. In particular, $and MatchExpression nodes can sort equally. To fix this, we can refine the comparator function to consider two nodes' children if they would otherwise be considered equal.