The Equality, Sort, Range Rule

Given a query with equality matches, a sort and a range, a compound index's fields should run Equality first, then Sort, then Range. Take "the twenty oldest shipped orders over $4,000": equality on status, range on total, sort on createdAt. Build both candidate orders and hint each in turn.

ESR versus ERS on the same query

db.orders.createIndex({ status: 1, total: 1, createdAt: 1 }, { name: 'ers' });
db.orders.createIndex({ status: 1, createdAt: 1, total: 1 }, { name: 'esr' });
const q = { status: 'shipped', total: { $gt: 4000 } };   // 3,920 matching orders
for (const name of ['ers', 'esr']) {
  const e = db.orders.find(q).sort({ createdAt: 1 }).limit(20).hint(name)
    .explain('executionStats');
  const s = e.executionStats, b = e.queryPlanner.winningPlan.inputStage.inputStage.indexBounds;
  print(`${name}: ${s.executionStages.stage} keys=${s.totalKeysExamined} ` +
        `docs=${s.totalDocsExamined} ms=${s.executionTimeMillis}`);
  print('  ' + Object.keys(b).map(k => k + ' ' + b[k]).join('  '));
}

Output

ers: FETCH keys=3920 docs=20 ms=5
  status ["shipped", "shipped"]  total (4000, inf]  createdAt [MinKey, MaxKey]
esr: LIMIT keys=78 docs=20 ms=0
  status ["shipped", "shipped"]  createdAt [MinKey, MaxKey]  total (4000, inf]

Fifty times fewer keys for the same twenty documents. Both indexes cover the same three fields; only the order differs.

Why a range before the sort key destroys the index order

Equality on status pins both scans to one contiguous block, and what comes next decides everything. Unhinted, the planner names esr the winner and lists ers among two rejectedPlans.

Three corollaries. Equality fields can go in any order among themselves — put the more selective first anyway, so the index also serves as a prefix. $in counts as equality: status: { $in: ['shipped', 'paid'] } gives a SORT_MERGE over one scan per value, and ten documents still cost 11 keys. $ne, $nin and $exists: false are not selective, so treat them as ranges and keep them last.

MENU

The Equality, Sort, Range Rule