MongoDB Indexes Visualization | Compound, ESR, Multikey and Covered

The idea: an index is a sorted list of keys

A MongoDB index is a B-tree. Its leaf level is a list of keys in sorted order, and every key points to a RecordId, the place where the document is stored. The upper levels of the tree only help a query jump to the right spot in that list. So a query on an index does two things: it finds where its keys start and stops where they end (an IXSCAN over the index bounds), and then it reads each document by RecordId (a FETCH). The canvas draws the leaf level of one index at a time, next to the documents.

The keys a query needs are one contiguous range of the sorted leaf list; each key leads to one document by RecordId.

The data is the users collection from How MongoDB Runs a Command, now with 12 documents and two more fields:

db.users.insertMany([
  {_id: 1, name: "Ann", age: 25, status: "A", tags: ["db"]},
  {_id: 2, name: "Bob", age: 32, status: "A", tags: ["web", "db"]},
  ...                                       // 12 documents, r1 … r12
  {_id: 12, name: "Lea", age: 33, status: "A", tags: ["web"]}])
db.users.createIndex({status: 1, age: 1, name: 1})   // "status_1_age_1_name_1"
db.users.createIndex({status: 1, name: 1, age: 1})   // "status_1_name_1_age_1"
db.users.createIndex({tags: 1})                      // "tags_1", multikey

Each query names its index with .hint(), so the run is the same every time. How the planner picks an index on its own (a short trial race, then the plan cache) is on the MongoDB and query planner pages.

Compound keys and the prefix rule

A compound index such as {status: 1, age: 1, name: 1} sorts by status first, then by age among equal statuses, then by name among equal ages. The key order is part of the index: the same three fields in another order are a different index, with a different sorted list.

That order decides which queries can use the index. A query that fixes the first field, or the first two, finds its keys in one range: {status: "B"} is the last 4 keys of the list. A query on age alone cannot: the ages restart inside each status group, so the age > 35 keys are spread over both groups. This is the prefix rule: an index serves queries on a leftmost prefix of its fields ({status}, {status, age}, {status, age, name}), and with no index starting with age the query reads every document with a COLLSCAN. (Demo: prefix rule: 4 keys and 4 documents, then 12 documents read for 4 results.)

Because of the prefix rule, an index {status: 1, age: 1} next to {status: 1, age: 1, name: 1} is redundant: the longer one serves every query the shorter one does.

Reading explain(): stages and counters

db.users.find(…).explain("executionStats") shows the winning plan as a tree of stages. Each stage pulls results from the stage below it. The canvas draws the tree with the root on top.

Stage	What it does
`IXSCAN`	Reads keys inside the index bounds, in key order, and passes on RecordIds (or the keys themselves).
`FETCH`	Reads each document by RecordId; applies any part of the filter the bounds did not cover.
`COLLSCAN`	Reads every document in RecordId order and tests the filter. No index.
`SORT`	A blocking stage: takes in all its input, sorts it in memory, and only then returns the first result.
`PROJECTION_SIMPLE`	Keeps the requested fields of a fetched document.
`PROJECTION_COVERED`	Builds the output from the index key alone: no document is read.

Three counters tell you how much work a query did: totalKeysExamined (keys read), totalDocsExamined (documents read) and nReturned. A good index keeps all three close together. A big gap between docsExamined and nReturned means documents were read only to be thrown away. On a real server keysExamined can be one or two higher than the canvas shows, when the scan has to read a key just past a bound before it seeks on.

The ESR rule: Equality, Sort, Range

Take find({status: "A", age: {$gt: 30}}).sort({name: 1}). It has an equality (status), a sort (name) and a range (age). Which compound index serves it best?

{status, age, name} (E, R, S): the 5 matching keys are next to each other, so the scan reads exactly 5 keys. But inside the range they are in age order: Bob 32, Lea 33, Jon 35, Gus 36, Dan 41. A SORT stage has to collect all 5 documents in memory and sort them by name before it returns anything.
{status, name, age} (E, S, R): inside status A the keys are in name order. The age range is checked on each key: Ann, Fay and Ivy fail it and are skipped without a FETCH. The scan reads 8 keys, but the 5 results come out already sorted, so there is no SORT stage.

Left: the status A keys of status_1_age_1_name_1 in age order; the 5 keys with age over 30 are read and go into an in-memory SORT that reorders them Bob, Dan, Gus, Jon, Lea. Right: the status A keys of status_1_name_1_age_1 in name order; all 8 are read, Ann, Fay and Ivy fail the age bound on the key, and the 5 others come out already in name order with no SORT. — E-R-S reads fewer keys but needs a blocking in-memory SORT; E-S-R reads a few more keys and returns results in order at once.

The rule: put the Equality fields first, then the Sort fields, then the Range fields. Equality fields keep the scan to one block of keys. Sort fields right after them keep that block in the order the query wants. Range fields go last, because a range on an earlier field breaks the sort order of everything after it. Reading a few extra keys is cheap; a blocking sort holds every result in memory, returns nothing until the end, and cannot stop early for a limit() the way an ordered index scan can. (Demo: ESR rule: 5 keys, 5 documents and an in-memory SORT, then 8 keys, 5 documents and no SORT.)

Index	keysExamined	docsExamined	nReturned	SORT stage
`{status: 1, age: 1, name: 1}`	5	5	5	yes, in memory
`{status: 1, name: 1, age: 1}`	8	5	5	no

An index can also be walked backwards: {status: 1, name: 1, age: 1} serves sort({name: -1}) too, and in general a sort matches an index when it is the index's key pattern (after the equality fields) or its exact reverse.

Multikey indexes on arrays

When an indexed field holds an array, the index becomes multikey: it stores one key per array element. Bob's tags: ["web", "db"] gives two keys, "db" → r2 and "web" → r2. The 12 documents make 16 keys in tags_1, and explain() shows isMultiKey: true.

So one document can be found more than once. find({tags: {$in: ["db", "ml"]}}) scans two intervals, ["db", "db"] and ["ml", "ml"]. Eve (["db", "ml"]) is in both. The IXSCAN remembers the RecordIds it has already returned and drops the second one (dupsTested, dupsDropped), so each document is fetched and returned once. (Demo: multikey index: 10 keys, 1 duplicate dropped, 9 documents.)

A compound multikey index may hold at most one array field per document: {tags: 1, langs: 1} is refused for a document where both are arrays, because the index would need every pair of elements.

Covered queries

A query is covered when the filter and every returned field are in the index. Then the answer can be built from the keys alone: no FETCH, docsExamined: 0, and the plan is PROJECTION_COVERED ← IXSCAN.

The catch is _id: it is returned unless you exclude it. find({status: "A", age: {$gt: 30}}, {name: 1, age: 1}) still fetches all 5 documents, only to read their _id. Adding _id: 0 makes it covered. (Demo: covered query: docsExamined 5, then 0.)

Two plans side by side. Left: projection {name: 1, age: 1} gives PROJECTION_SIMPLE over FETCH over IXSCAN, docsExamined 5, because _id is not in the key. Right: projection {_id: 0, name: 1, age: 1} gives PROJECTION_COVERED over IXSCAN, docsExamined 0. — Excluding _id lets the key alone answer the query, so the FETCH stage disappears.

A multikey index cannot cover a query on its array field (one key holds only one element of the array), and a query on a field of an embedded document is only covered when the projection names that dotted path.

Sorting without an index

When no index can give the order a query asks for, the planner adds a SORT stage over whatever produced the documents. find({age: {$gte: 30}}).sort({name: 1}) has no index starting with age or name, so it is SORT ← COLLSCAN: 12 documents read, 8 kept in memory, sorted, then returned. (Demo: sort without an index.)

A blocking sort may use at most 100 MB of memory (internalQueryMaxBlockingSortMemoryUsageBytes). Past that, it writes sorted runs to temporary files and merges them, which is allowed by default since MongoDB 6.0 (allowDiskUseByDefault); with allowDiskUse: false the query fails instead. In explain() a sort that spilled shows usedDisk: true.

What the page leaves out

The B-tree's inner pages and page splits (see B-Tree and B+ Tree as a Database Index); the canvas shows only the leaf level.
The planner's trial race and the plan cache (on the MongoDB page); every query here is hinted.
Index intersection (AND_SORTED, AND_HASH), OR plans, and SORT_MERGE of several index ranges.
Unique, partial, sparse, TTL, hashed, text, 2dsphere, wildcard and clustered indexes, and collation.
How WiredTiger stores keys (prefix compression, the key format with the RecordId appended), building an index on a live collection, and the write cost: every insert adds a key to every index, and one per element to a multikey index.
The extra key a real IXSCAN may read past a bound before it seeks, and the exact byte size of the sort buffer.

For the same ideas in MySQL (leftmost prefix, covering index, index condition pushdown) see MySQL Index Access Paths; for heap versus clustered storage see Clustered vs Secondary Index.