ISSUE SUMMARY
The plan ranker does not account for work spent skipping index keys when ranking plans against each other. For example, if the following indexes are present:

{a:1, b:1}
{a:1, x:1, b:1}

It is cheaper to use index {a:1, b:1} for queries with predicates over fields a and b, because for index {a:1, x:1, b:1} it may be necessary to skip many keys due to the interceding x field.

Another example where this issue appears is the following:

Indexes: {a:1}, {b:1, c:1}
Data: {a: i, b: i, c: i} for increasing values of i
Query: {a: 9, b: {$ne: 10}, c: 9}

Plans using the two indices tie in this case. This can cause the plan ranker to use index {b: 1, c: 1} rather than the obviously better {a: 1} index.

USER IMPACT
An inferior plan may be chosen, which may have a negative performance impact. See also related issues SERVER-13675 and SERVER-14525 for cases where plans tie.

WORKAROUNDS
Hinting on a different index may avert the performance impact.

AFFECTED VERSIONS
MongoDB 2.6 production releases up to 2.6.3 are affected by this issue.

FIX VERSION
The fix is included in the 2.6.4 production release.

RESOLUTION DETAILS
The bug arises from not counting a btree key skip as a unit of work. The resolution is therefore to properly account for the work done skipping keys in order to break the plan ranking tie.