Your Index Has Three Jobs. A Sort Can Break One of Them.

I showed a colleague a query reading 109 documents to return one, and the index it was supposed to be using. He looked at both and said the obvious thing: “that’s not even the same index. It’s got four fields, your query filters on three completely different ones.”

He was right that they don’t look alike. He was wrong that it mattered, and the reason why is the most useful thing I’ve learned about indexes this year.

Execution count       2,247,787
Documents examined  245,351,482
Documents returned    2,247,344
Keys examined       245,351,482
Bytes read               329 GB
Total execution time   35.90 min
Average per call            1 ms

About 109 documents read for every one returned, two and a quarter million times a week.

Average call time is 1 ms, so nobody ever complained. The index exists. The index is used, 33 million times since it was built. And it still can’t do the one thing this query needs.

MongoDB on a production cluster, Spring Data MongoDB. Client details are anonymised; the explain output is real.

1. The query and the index don’t look alike

Here’s what’s in play. The index:

{ globalId_key: 1, version: 1, commitMetadata.id: -1, _id: -1 }

And the query:

db.snapshots.find({
    globalId_key: "...",
    type:    { $in: ["UPDATE", "INITIAL"] },
    version: { $lt: 154 }
})
.sort({ version: -1, _id: -1 })
.limit(1)

Four fields in the index, three in the filter, and only two of them appear in both. type isn’t in the index at all. commitMetadata.id isn’t in the query at all.

That mismatch is exactly what my colleague objected to, and the instinct behind it is completely reasonable: if the fields don’t match, the index can’t be doing its job.

The instinct is wrong because it assumes an index has one job.

2. An index has three jobs, judged separately

A compound index can do three different things for a query, and it can succeed at one while failing at another:

Lined up field by field, it looks like this:

index    globalId_key : 1     version : 1      commitMetadata.id : -1    _id : -1
              |                    |                    |                   |
query    globalId_key $eq     version $lt         (not in query)      sort _id: -1
              |                    |                    |                   |
role      BOUNDS the scan    EXTENDS the bound        unused           BREAKS the sort

The bounding half works beautifully. globalId_key plus version takes the search from 102 million documents down to 158. That’s a factor of six hundred thousand, from one index, doing exactly what it was built for.

Then the sort throws most of it away.

3. The prefix rule, which is the part everyone knows

An index is used left to right, with no gaps. That’s the rule people usually remember, and it’s worth restating because the sort rule is built on top of it.

Given { a: 1, b: 1, c: 1 }:

filter on  a          ->  YES       uses a
filter on  a, b       ->  YES       uses a + b
filter on  a, b, c    ->  YES       uses all three
filter on  a, c       ->  PARTIAL   bounds on a, then c is checked after fetching
filter on  b          ->  NO        no bound at all, the index is useless here
filter on  b, c       ->  NO        same

So “I only query one field out of a compound index” is fine, as long as it’s the leftmost one. You can enter from the left, never from the middle.

The phone book analogy holds all the way through this article, so it’s worth setting up now. A phone book sorted by surname then first name: looking up “Dupont” is instant. Finding every “Jean” is not, because there’s no way in except reading all of it.

4. The sort rule, which is the part that gets people

A sort can be served by the index only if it matches a contiguous run of index keys, read in one consistent direction.

That second clause is the one that catches people, mine included.

Here’s the alignment after globalId_key is bounded by equality:

index order after globalId_key is bound :  version:1  ,  commitMetadata.id:-1  ,  _id:-1
sort requested :                           version:-1 ,       (skipped)        ,  _id:-1
                                                             ^^^^^^^^^^^^^^^^
                                                             a key is skipped

Two separate things break at once, and either alone would be enough:

• The sort skips a key. It asks for version then _id, but the index has commitMetadata.id sitting between them. Not contiguous, so no.
• The directions contradict each other. To read version descending, MongoDB has to walk the index backwards. But walking backwards inverts everything after it too: commitMetadata.id and _id both become ascending. The sort asked for _id: -1. It can’t have both.

So MongoDB gives up on the index order and does it itself.

5. What “gives up” actually costs

This is where the phone book earns its place, because the failure isn’t obvious from the outside. The query returns the correct answer either way. It just takes a completely different route.

SORT SERVED BY THE INDEX

    MongoDB positions at the right place in the index
    reads one entry, follows it to one document, stops
    -> 1 document read


SORT NOT SERVED BY THE INDEX

    MongoDB cannot trust the index order
    -> fetches ALL 158 candidate documents off disk
    -> sorts them in memory
    -> keeps 1, discards 157

And limit(1) cannot rescue you. A limit only applies after the sort, and a blocking sort has to receive every document before it can emit any of them. You can’t know which one is first until you’ve seen them all.

Unless somebody has already sorted them for you. Which is precisely what an index is: a sort done in advance and maintained on every write.

limit(1) with an index-served sort   ->  stops after 1 read
limit(1) with a blocking sort        ->  stops after reading and sorting everything

There’s a fingerprint for this in the metrics at the top, and it’s worth committing to memory: keys examined and documents examined were exactly equal, 245,351,482 of each. Every index entry triggered a document fetch. That’s what a blocking sort looks like from the outside, because it pulls everything before deciding anything.

6. Proving it, three ways

Hypotheses are cheap. This took one explain("executionStats") run against production, same query and same index, changing only the sort:

sort {version:-1, _id:-1}                       docs = 158    SORT stage = yes
sort {version:-1}                               docs =   1    SORT stage = no
sort {version:-1, commitMetadata.id:1, _id:1}   docs =   1    SORT stage = no

Read those three lines and the whole mechanism is there.

Line 1 is what production runs. 158 documents, blocking sort.

Line 2 drops _id: -1. One document, no sort stage. The index serves it.

Line 3 is the proof that the index isn’t the problem. Hand it the full inverted suffix in index order, version descending then commitMetadata.id and _id ascending, and the sort is served again. That’s exactly what “read the index backwards” produces, and MongoDB accepts it happily.

The index was never wrong. The query was asking for an order that no single pass through that index can produce.

Here’s the winning plan for line 1, in case you want to recognise the shape:

SORT  <-  FETCH  <-  IXSCAN [globalId_key_1_version_1_commitMetadata.id_-1__id_-1]
keysExamined  = 158
docsExamined  = 158
nReturned     = 1

A SORT stage sitting above a FETCH is the thing to look for. It means every one of those fetched documents exists only to be sorted and mostly thrown away.

7. The suspect that turned out to be innocent

My first theory was the type filter. It’s $in: ["UPDATE", "INITIAL"], it isn’t in the index at all, so MongoDB has to open each document to check it. That looked like the obvious culprit.

It isn’t, and line 2 of the test proves it: type is still unindexed there and it examines exactly one document.

The reason is a distribution the index knows nothing about:

UPDATE + INITIAL    93.5 %  of documents
TERMINAL             6.5 %

The first candidate passes the filter 93.5% of the time. On average that’s about 1.07 documents opened, not 158.

Which is a useful general point: an unindexed filter costs you nothing when it rejects nothing. It’s expensive in proportion to how much it throws away, not in proportion to being unindexed. Worth checking the selectivity before you add a field to an index to “fix” it.

8. How to find this in your own database

Nothing above needed a hypothesis. It needed the right column to sort by and one explain run, and both are worth knowing because this class of problem never announces itself.

Sort your slow-query view by documents examined, not by ratio or by latency. A blocking sort on a small candidate set has a fine ratio and a fine average time. It only looks wrong in aggregate.

Then look for keys examined equal to documents examined. When those two numbers match exactly, every index entry is triggering a document fetch, which means the index found the rows but something downstream needs the whole document. A blocking sort is one cause. A projection asking for a field the index doesn’t have is another, which is the subject of the previous article in this series.

Then run explain("executionStats") on the real query with real values and read three things:

"stage": "SORT"       above a FETCH, this is the problem
"totalDocsExamined"   how many you paid for
"nReturned"           how many you wanted

A SORT stage means every document below it was fetched purely to be ordered and mostly discarded.

Finally, if you see one, change only the sort and run it again. That was the entire diagnosis here. Three runs, same query, same index, and the difference between 158 documents and 1 was four characters in a sort spec. It takes a minute and it tells you whether the index needs changing or the query does, which are very different amounts of work.

9. The fix

.with(Sort.by(Sort.Direction.DESC, FIELD_VERSION))   // was: .and(Sort.by(DESC, "_id"))

One line. No new index, nothing added to the 60.6 GB this collection already carries in indexes.

That last part matters more than it looks. The obvious fix for a sort the index can’t serve is to build an index that can, in this case { globalId_key: 1, type: 1, version: -1, _id: -1 }. It would work. It would also be a full index over 102 million documents, several gigabytes, to avoid deleting four characters.

Expected effect, from line 2 of the test:

documents read   245,351,482  ->  ~2.25 M      (1 per call)
I/O                   329 GB  ->  a few GB
cluster time        35.90 min  ->  seconds

One thing to check before you copy this. The _id: -1 was presumably there to break ties between equal versions. In this schema version is unique per entity, so it’s redundant, but that’s a property of the data rather than something the code guarantees. If two documents in your collection can share a sort key, removing the tiebreaker makes the result non-deterministic between them. Confirm before deleting.

10. What generalises

An index doesn’t have to resemble your query. It’s used as a prefix, and it does up to three separate jobs, so “do the fields match?” is the wrong test. The three questions that replace it:

• Does the leftmost run of keys bound my scan?
• Can a contiguous run after that serve my sort, in one direction?
• Do I need any field the index doesn’t carry?

Sort direction is part of the contract, not a detail. {a: 1, b: -1} and {a: 1, b: 1} are different indexes with different capabilities, and a single index read backwards inverts every key at once. Mixed directions in a compound index are a commitment to one specific sort and its exact inverse, nothing else.

Heavy usage is not the same as good usage. This index has been used 33.8 million times since it was built. It’s the second most used index on the collection. Those 33.8 million uses were hiding 245 million unnecessary document reads. A dashboard showing index usage would have called it a star performer.

And a 1 ms average hides anything. Nobody waits on this query, nobody filed a ticket, and the per-call number looks perfect. It only shows up when you multiply by two and a quarter million and look at the total. That’s the same shape as the query that read two billion documents a week, where a perfect efficiency ratio hid the volume. Different mechanism, same blind spot: the metric that looks healthiest per call is the one most likely to be concealing the bill.

This query lives in an audit collection, and the reason one entity has 154 versions to sort through is explained in JaVers from first principles.