Phase 4: Indexing, SBE Query Planner & Aggregation Pipeline¶

Audience: Principal Distributed Systems Architect & Query Performance Tuning Specialist
Source References: src/mongo/db/query/, src/mongo/db/pipeline/, src/mongo/db/exec/sbe/

1. Cellular B-Tree Index Representation in WiredTiger¶

In MongoDB, secondary indexes are stored as independent WiredTiger tables (index-*.wt).

WiredTiger Index Leaf Page:
┌──────────────────────────────────────┬──────────────────────────────────────┐
│ Index Key (e.g., status="ACTIVE")    │ RecordId (Internal 64-bit Row ID)    │
│ Prefix Compressed BSON bytes         │ Points to Base Collection Document   │
└──────────────────────────────────────┴──────────────────────────────────────┘

1.1 Prefix Compression¶

WiredTiger compresses identical index key prefixes across adjacent entries in a B-Tree leaf. If 1,000 adjacent keys share "ACTIVE", the string is stored once in the page header, saving up to 70% of RAM.

2. Enterprise Indexing Strategies & The ESR Rule¶

2.1 The ESR Rule (Equality, Sort, Range)¶

When designing compound indexes to satisfy complex queries with equality filters, sorting requirements, and range filters, the fields must strictly follow ESR order:

Optimal Compound Index Field Sequence:
[ 1. EQUALITY FIELDS ] ──► [ 2. SORT FIELDS ] ──► [ 3. RANGE FIELDS ]

Why ESR is Mathematically Optimal:¶

Consider the query:

db.orders.find({ tenant_id: 104, total: { $gte: 500 } }).sort({ created_at: -1 })

- If index is (tenant_id, created_at, total) (ESR Order): 1. E (tenant_id): Fast B-Tree descent isolates tenant 104 in $O(\log N)$ time. 2. S (created_at): Keys within tenant 104 are already sorted in disk order. Zero in-memory sorting required! 3. R (total): Scans linearly through the sorted keys and filters by total >= 500. - If index is (tenant_id, total, created_at) (Violating ESR): 1. The B-Tree scan finds all orders with total >= 500. 2. Within that subset, created_at values are scrambled across different total values. 3. MongoDB must pull all documents into RAM and perform an expensive in-memory sort (SORT stage)!

2.2 Multikey Index Pathology (The Array Explosion)¶

When an index includes an array field, MongoDB creates an index entry for every single element in that array. - If a document contains an array of 50 tags: 1 insert generates 50 index entries. - The Compound Multikey Restriction: MongoDB structurally forbids indexing two array fields in the same compound index because it would generate an $M \times N$ Cartesian product explosion of index keys, instantly exhausting memory and disk.

2.3 Covered Queries: The Ultimate Optimization¶

A query is Covered when: 1. All fields in the query filter are present in the index. 2. All fields in the projection are present in the index. 3. The _id field is explicitly excluded ({ _id: 0 }).

Covered Query Execution Flow:
[Client Query] ──► [IXSCAN (Reads index-*.wt)] ──► Returns Data!
(Stage FETCH is completely omitted! Zero disk reads to base collection-*.wt!)

3. Query Planner Execution Stages¶

The query planner evaluates candidate indexes by running trial executions during the plan evaluation phase (MultiPlanStage).

Common Execution Stages in explain("executionStats"):
┌─────────────────┬──────────────────────────────────────────────────────────────┐
│ Stage Name      │ Meaning & Performance Impact                                 │
├─────────────────┼──────────────────────────────────────────────────────────────┤
│ COLLSCAN        │ Collection Scan: Scans every single document. (Avoid in prod)│
│ IXSCAN          │ Index Scan: Traverses B-Tree index pages.                     │
│ FETCH           │ Retrieval: Fetches full BSON document from collection table. │
│ SORT            │ In-memory sort: Exceeding 100MB RAM aborts query.            │
│ PROJECTION_SIMPLE│ Prunes unwanted fields from retrieved document.             │
│ COUNT_SCAN      │ Fast count using index metadata without reading documents.   │
└─────────────────┴──────────────────────────────────────────────────────────────┘

4. The Slot-Based Execution Engine (SBE)¶

Introduced in MongoDB 5.0 and expanded in 6.0/7.0, SBE replaces the legacy tree-of-iterators execution engine.

Legacy Engine (Volcano Model):
[FetchStage] ── virtual work() call ──► [IndexScanStage]
(Heavy CPU instruction cache misses, BSON serialization overhead at every node)

Slot-Based Execution Engine (SBE):
┌────────────────────────────────────────────────────────┐
│ Pre-Allocated Fast Memory Slot Array (e.g., Slots 0..7)│
├────────────────────────────────────────────────────────┤
│ Slot 0: RecordId                                       │
│ Slot 1: Uncompressed field "tenant_id"                │
│ Slot 2: Uncompressed field "total"                     │
└────────────────────────────────────────────────────────┘
                           ▲
                           │ Executed via JIT-like bytecode loops
┌────────────────────────────────────────────────────────┐
│ SBE Virtual Machine Interpreter                        │
│ - Zero virtual function overhead                       │
│ - Vectorized batch processing                          │
│ - Filter evaluation directly in CPU registers          │
└────────────────────────────────────────────────────────┘

5. Aggregation Pipeline Optimizations¶

MongoDB compiles the aggregation pipeline using query rewrite rules:

5.1 Pipeline Stage Coalescing¶

$match Pushdown: If a $match stage appears after a $sort, MongoDB pushes $match before $sort to minimize the number of documents passed into the sort buffer.
$sort + $limit Coalescence: When $sort is followed immediately by $limit N, MongoDB maintains a bounded in-memory min/max heap of size $N$, reducing memory consumption from $O(\text{Total Docs})$ to $O(N)$.
$project Pushdown: Unused fields are pruned immediately after $match to reduce memory serialization across pipeline stages.

5.2 Memory Limits¶

Each stage in an aggregation pipeline is restricted to 100 MB of RAM. If a $group or $sort exceeds 100 MB without an index: - In MongoDB $< 6.0$: Query throws an exception unless { allowDiskUse: true } is enabled. - In MongoDB $\ge 6.0$: Pipeline stages automatically spill temporary blocks to the _tmp directory on disk.