The plan enumerator can sometimes generate duplicate index union plans. SERVER-89110 fixed the issue by deduplicating plans via hashing. However, ideally the plan enumerator would not generate duplicate solutions in the first place. 

The issue is that because we currently can't simplify queries perfectly (while taking into account multikeyness information), we might end up with an $or where some branches are equivalent. If there's more than one index that could cover the equivalent branches, the enumerator will try the same combinations in different orders, leading to duplicate plans. See SERVER-89110 for a concrete example.

Here are some approaches I think could help:

1. Keep track of which index bounds combinations have already been generated for an (Lockstep)OrAssignment, and skip states that would produce duplicates.
2. Assuming the order of scans in an index union is irrelevant (I don't know if it is), we could only enumerate one permutation per each child state combination. E.g., for an (Lockstep)OrAssignment with two children that have two choices each, we would still enumerate (1, 1) and (2, 2), but only one of (1, 2) and (2, 1).
3. Implement simplifications that take into account multikeyness information. E.g. we know that (a > 1 && a == 1) is a contradiction iff we know that 'a' is not multikey. This could help us remove equivalent $or branches and avoid the root of the issue.