MongoDB SORT_MERGE

How MongoDB answers $in + sort + limit queries without a blocking sort — traced through the server source code

MongoDB can merge multiple index scans and emit their results in sorted order (the SORT_MERGE stage). In this post we look at why this capability matters, which queries benefit from it, and how it works internally.

WHERE A = ? ORDER BY B LIMIT ?

Assume a composite index on (A, B), where A is a string column and B is a numeric column. As in the figure above, the index keys are stored in sorted order, top to bottom.

Because B is sorted in ascending order within each value of A, a query that filters A with an equality condition and sorts by B can be executed efficiently.

# e.g. fetch a user's most recent orders
SELECT *
FROM orders
WHERE user_id = ?
ORDER BY order_date DESC
LIMIT 10;

# e.g. fetch a store's most recent orders
SELECT *
FROM orders
WHERE store_id = ?
ORDER BY order_date DESC
LIMIT 15;

This is a very common pattern in production. Such queries need to return multiple rows, already sorted, quickly. Both MySQL and MongoDB can answer them with an index scan alone, without a sort operation.

MySQL:

> EXPLAIN
SELECT *
FROM orders1
WHERE o_c_id = 2292
ORDER BY o_entry_d DESC
LIMIT 3;
+----+-------------+---------+------------+------+-----------------+-----------------+---------+-------+------+----------+---------------------+
| id | select_type | table   | partitions | type | possible_keys   | key             | key_len | ref   | rows | filtered | Extra               |
+----+-------------+---------+------------+------+-----------------+-----------------+---------+-------+------+----------+---------------------+
|  1 | SIMPLE      | orders1 | NULL       | ref  | ix_ocid_oentryd | ix_ocid_oentryd | 5       | const |  130 |   100.00 | Backward index scan |
+----+-------------+---------+------------+------+-----------------+-----------------+---------+-------+------+----------+---------------------+

> EXPLAIN ANALYZE
SELECT *
FROM orders1
WHERE o_c_id = 2292
ORDER BY o_entry_d DESC
LIMIT 3;
+---------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                     |
+---------------------------------------------------------------------------------------------------------------------------------------------+
| -> Limit: 3 row(s)  (cost=879 rows=3) (actual time=27.6..27.6 rows=3 loops=1)
    -> Index lookup on orders1 using ix_ocid_oentryd (o_c_id=2292) (reverse)  (cost=879 rows=1000) (actual time=27.6..27.6 rows=3 loops=1)
|
+---------------------------------------------------------------------------------------------------------------------------------------------+

MySQL accesses the ix_ocid_oentryd (o_c_id, o_entry_d) index, seeks on the o_c_id key, and then scans o_entry_d in reverse order. No separate sort takes place, and execution stops as soon as the 3 required rows have been returned.

MongoDB:

> db.ORDERS.find({"O_C_ID": 2292}).sort({"O_ENTRY_D": -1}).limit(10).explain()
{
  queryPlanner:
    ...
    winningPlan: {
      stage: 'LIMIT',
      limitAmount: 3,
      inputStage: {
        stage: 'FETCH',
        inputStage: {
          stage: 'IXSCAN',
          keyPattern: { O_C_ID: 1, O_ENTRY_D: 1 },
          indexName: 'O_C_ID_1_O_ENTRY_D_1',
          isMultiKey: false,
          multiKeyPaths: { O_C_ID: [], O_ENTRY_D: [] },
          isUnique: false,
          isSparse: false,
          isPartial: false,
          indexVersion: 2,
          direction: 'backward',
          indexBounds: {
            O_C_ID: [ '[2292, 2292]' ],
            O_ENTRY_D: [ '[MaxKey, MinKey]' ]
          }
        }
      }
    },
    ...
}

MongoDB uses the O_C_ID_1_O_ENTRY_D_1: { O_C_ID: 1, O_ENTRY_D: 1 } index and follows essentially the same flow as MySQL.

WHERE A IN (?, ?) ORDER BY B LIMIT ?

The difference from the previous query is that A now has two (or more) equality values. In this case, a large amount of extra reading and a sort operation are required.

The reason is that the result of looking up multiple A values in the (A, B) index is not sorted by B. So every index record for those A values has to be read first and then sorted. The amount of data accessed is very large, and the sort consumes more system resources.

MySQL:

> EXPLAIN
SELECT *
FROM orders1
WHERE o_c_id IN (2292,1732,2802)
ORDER BY o_entry_d DESC
LIMIT 10;
+----+-------------+---------+------------+-------+-----------------+-----------------+---------+------+------+----------+---------------------------------------+
| id | select_type | table   | partitions | type  | possible_keys   | key             | key_len | ref  | rows | filtered | Extra                                 |
+----+-------------+---------+------------+-------+-----------------+-----------------+---------+------+------+----------+---------------------------------------+
|  1 | SIMPLE      | orders1 | NULL       | range | ix_ocid_oentryd | ix_ocid_oentryd | 5       | NULL | 1226 |   100.00 | Using index condition; Using filesort |
+----+-------------+---------+------------+-------+-----------------+-----------------+---------+------+------+----------+---------------------------------------+

> EXPLAIN ANALYZE
SELECT *
FROM orders1
WHERE o_c_id IN (2292,1732,2802)
ORDER BY o_entry_d DESC
LIMIT 10;
+-----------------------------------------------------------------------------------------------------------------------------------------
| EXPLAIN
+-----------------------------------------------------------------------------------------------------------------------------------------
| -> Limit: 10 row(s)  (cost=3590 rows=10) (actual time=391..391 rows=10 loops=1)
    -> Sort: orders1.o_entry_d DESC, limit input to 10 row(s) per chunk  (cost=3590 rows=3000) (actual time=391..391 rows=10 loops=1)
        -> Index range scan on orders1 using ix_ocid_oentryd over (o_c_id = 1732) OR (o_c_id = 2292) OR (o_c_id = 2802),
           with index condition: (orders1.o_c_id in (2292,1732,2802))  (cost=3590 rows=3000) (actual time=2.38..390 rows=3000 loops=1)
|
+-----------------------------------------------------------------------------------------------------------------------------------------

Here MySQL reads every index entry matching (o_c_id = 1732) OR (o_c_id = 2292) OR (o_c_id = 2802) and stores them in a temporary in-memory area. It then sorts them by o_entry_d and returns the final 10 rows.

You can reduce the initial amount of data accessed — for example, by adding a condition such as o_entry_d BETWEEN ? AND ? — but the sort always happens.

MongoDB:

> db.ORDERS.find({"O_C_ID": {$in: [2292,1732,2802]}}).sort({"O_ENTRY_D": -1}).limit(10).explain()
{
  queryPlanner: {
    ...
    winningPlan: {
      stage: 'LIMIT',
      limitAmount: 10,
      inputStage: {
        stage: 'FETCH',
        inputStage: {
          stage: 'SORT_MERGE',
          sortPattern: { O_ENTRY_D: -1 },
          inputStages: [
            {
              stage: 'IXSCAN',
              indexName: 'O_C_ID_1_O_ENTRY_D_1',
              direction: 'backward',
              indexBounds: {
                O_C_ID: [ '[2802, 2802]' ],
                O_ENTRY_D: [ '[MaxKey, MinKey]' ]
              }
            },
            {
              stage: 'IXSCAN',
              indexName: 'O_C_ID_1_O_ENTRY_D_1',
              direction: 'backward',
              indexBounds: {
                O_C_ID: [ '[2292, 2292]' ],
                O_ENTRY_D: [ '[MaxKey, MinKey]' ]
              }
            },
            {
              stage: 'IXSCAN',
              indexName: 'O_C_ID_1_O_ENTRY_D_1',
              direction: 'backward',
              indexBounds: {
                O_C_ID: [ '[1732, 1732]' ],
                O_ENTRY_D: [ '[MaxKey, MinKey]' ]
              }
            }
          ]
        }
      }
    },
    ...
}

A stage called SORT_MERGE appears in MongoDB’s plan. It reads the data for O_C_ID: 2802, O_C_ID: 2292, and O_C_ID: 1732, and returns the final 10 documents ordered by O_ENTRY_D.

It looks similar to MySQL, but the SORT_MERGE stage lets each O_C_ID lookup and the O_ENTRY_D ordering run efficiently.

Reading the plan in a bit more detail:

1. The O_C_ID lookup is split into 3 ranges, each handled by its own IXSCAN stage.
2. Each scan reads in reverse (direction: 'backward') to match the sort requirement.
3. The SORT_MERGE stage merge-sorts the outputs of the IXSCAN stages.
4. The FETCH stage goes back to the collection to retrieve fields that are not in the index (fields other than the index keys).
5. The LIMIT stage returns 10 documents (limitAmount: 10).

SORT_MERGE minimizes the amount of data actually read. Here are the actual execution statistics:

> db.ORDERS.find({"O_C_ID": {$in: [2292,1732,2802]}}).sort({"O_ENTRY_D": -1}).limit(10).explain("executionStats")
{
  ...
  executionStats: {
    executionSuccess: true,
    nReturned: 10,
    executionTimeMillis: 0,
    totalKeysExamined: 12,
    totalDocsExamined: 10,
    executionStages: {
      stage: 'LIMIT',
      limitAmount: 10,
      nReturned: 10,
      works: 23,
      inputStage: {
        stage: 'FETCH',
        nReturned: 10,
        works: 22,
        docsExamined: 10,
        inputStage: {
          stage: 'SORT_MERGE',
          nReturned: 10,
          works: 22,
          sortPattern: { O_ENTRY_D: -1 },
          inputStages: [
            {
              stage: 'IXSCAN',
              nReturned: 4,
              works: 4,
              indexName: 'O_C_ID_1_O_ENTRY_D_1',
              direction: 'backward',
              indexBounds: {
                O_C_ID: [ '[2802, 2802]' ],
                O_ENTRY_D: [ '[MaxKey, MinKey]' ]
              },
              keysExamined: 4,
              seeks: 1,
            },
            {
              stage: 'IXSCAN',
              nReturned: 4,
              works: 4,
              indexName: 'O_C_ID_1_O_ENTRY_D_1',
              direction: 'backward',
              indexBounds: {
                O_C_ID: [ '[2292, 2292]' ],
                O_ENTRY_D: [ '[MaxKey, MinKey]' ]
              },
              keysExamined: 4,
              seeks: 1,
            },
            {
              stage: 'IXSCAN',
              nReturned: 4,
              indexName: 'O_C_ID_1_O_ENTRY_D_1',
              direction: 'backward',
              indexBounds: {
                O_C_ID: [ '[1732, 1732]' ],
                O_ENTRY_D: [ '[MaxKey, MinKey]' ]
              },
              keysExamined: 4,
              seeks: 1,
            }
          ]
        }
      }
    }
  },
  ...
}

Each IXSCAN examined only about 4 keys (keysExamined) — a tiny number compared to the actual data volume.

> db.ORDERS.aggregate([
  { $match: {"O_C_ID": {$in: [2292,1732,2802]}} },
  { $group: { "_id": "$O_C_ID", "count": { $sum: 1 } } }
])
[
  { _id: 2292, count: 5000 },
  { _id: 2802, count: 5000 },
  { _id: 1732, count: 5000 }
]

As the result above shows, the collection holds 5,000 documents for each O_C_ID. Yet the IXSCAN stages did not read all of them; they read only a small portion, in descending order of O_ENTRY_D.

In MySQL, the index scan finishes reading all of its data before handing it off to the sort. In MongoDB, the outputs of the index scans are merged one entry at a time, and each stage works only as much as needed. It feels as if the upper stage directly controls the lower stages.

In other words, data flows in this direction:

IXSCAN(s) → SORT_MERGE → FETCH → LIMIT

but the stages are actually driven in this order:

LIMIT → FETCH → SORT_MERGE → IXSCAN(s)

How stages are executed

The stages that appear in a MongoDB query plan each perform one part of the data processing needed to produce the query result. Multiple stages are combined into a tree to process a query.

Many stages are not described in the official MongoDB documentation. The full list can be found in stage_types.h, and what each stage does can be found under mongo/db/exec.

Every stage has a doWork method, which implements the stage's actual work.

# https://github.com/mongodb/mongo/blob/r4.4.23/src/mongo/db/exec/limit.cpp#L61
PlanStage::StageState LimitStage::doWork(WorkingSetID* out) {
    if (0 == _numToReturn) {  ## If there is nothing left to return, return IS_EOF and finish
        // We've returned as many results as we're limited to.
        return PlanStage::IS_EOF;
    }
    WorkingSetID id = WorkingSet::INVALID_ID;
    StageState status = child()->work(&id); ## Tell the child stage to do work and get its result
    if (PlanStage::ADVANCED == status) {  ## If the child produced a result, put it in the working set
        *out = id;
        --_numToReturn;  ## Decrement the number of results still to return
    } else if (PlanStage::FAILURE == status) {
        // The stage which produces a failure is responsible for allocating a working set member
        // with error details.
        invariant(WorkingSet::INVALID_ID != id);
        *out = id;
    } else if (PlanStage::NEED_YIELD == status) {  ## Must wait for the child's result -> yield execution resources (CPU) to other threads
        *out = id;
    }
    return status;
}

doWork returns a state (PlanStage::StageState) such as IS_EOF, FAILURE, ADVANCED, or NEED_YIELD; it tells the child stage to work and passes results through a shared area, the WorkingSet.

As with the LIMIT stage above, ordinary query processing has the upper stage drive the lower stage only as many times as it needs (_numToReturn). In some cases, however, the upper stage has to wait until the lower stage has processed all of its data before receiving any result (the SORT stage).

When is the SORT_MERGE stage used?

# https://github.com/mongodb/mongo/blob/r4.4.23/src/mongo/db/exec/merge_sort.h#L47
/**
 * Merges the outputs of N children, each of which is sorted in the order specified by
 * 'pattern'.  The output is sorted by 'pattern'.  Practically speaking, all of this stage's
 * children are indices.
 *
 * AKA the SERVER-1205 stage.  Allows very efficient handling of the following query:
 * find($or[{a:1}, {b:1}]).sort({c:1}) with indices {a:1, c:1} and {b:1, c:1}.
 *
 * Preconditions: For each field in 'pattern' all inputs in the child must handle a
 * getFieldDotted for that field.
 */
class MergeSortStage final : public PlanStage {
  ...

The SORT_MERGE stage merges and sorts the outputs of N child stages. It can be used only when all child stages are index scans (IXSCAN stages), and each of them must read in an order that matches the sort requirement.

It can even merge the outputs of different indexes. Given the indexes {a:1, c:1} and {b:1, c:1}, running:

find($or[{a:1}, {b:1}]).sort({c:1})

executes two separate index scans and merges and sorts their outputs.

Get Case’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In short, SORT_MERGE is considered when an index scan can be split (“exploded”) and the sort requirement can be satisfied by the index scans. This is evaluated during plan generation.

# https://github.com/mongodb/mongo/blob/r4.4.23/src/mongo/db/query/planner_analysis.h#L40
static QuerySolutionNode* QueryPlannerAnalysis::analyzeSort(const CanonicalQuery& query,
                                                     const QueryPlannerParams& params,
                                                     QuerySolutionNode* solnRoot,
                                                     bool* blockingSortOut) {
    ...
    // Sort not provided, can't reverse scans to get the sort.  One last trick: We can "explode"
    // index scans over point intervals to an OR of sub-scans in order to pull out a sort.
    // Let's try this.
    if (explodeForSort(query, params, &solnRoot)) {
        return solnRoot;
    }
    ...

The planner’s sort analysis (QueryPlannerAnalysis::analyzeSort) examines the query's sort requirement and checks whether the IXSCAN stage can be split and replaced with a SORT_MERGE stage (explodeForSort).

Evaluating SORT_MERGE

explodeForSort checks that the leaf node is an index scan (IXSCAN), and inspects the index's key pattern and bounds to determine whether the scan range can be split.

It also checks how many scans the split would produce. The maximum is limited by the internalQueryMaxScansToExplode parameter, which defaults to 200. If the limit is exceeded, the SORT_MERGE evaluation is abandoned and a SORT stage is considered instead.

# https://github.com/mongodb/mongo/blob/r4.4.23/src/mongo/db/query/planner_analysis.cpp#L544
bool QueryPlannerAnalysis::explodeForSort(const CanonicalQuery& query,
                                          const QueryPlannerParams& params,
                                          QuerySolutionNode** solnRoot) {
    ...
    // Too many ixscans spoil the performance.
    if (totalNumScans > (size_t)internalQueryMaxScansToExplode.load()) {
        LOGV2_DEBUG(
            20950,
            5,
            "Could expand ixscans to pull out sort order but resulting scan count({numScans}) is "
            "too high",
            "Could expand ixscans to pull out sort order but resulting scan count is too high",
            "numScans"_attr = totalNumScans);
        return false;
    }

How is the SORT_MERGE stage executed?

Processing in the SORT_MERGE stage

For testing, create a simple test collection:

// a
db.test.insertOne({"A":"a", "B": 97})
db.test.insertOne({"A":"a", "B": 100})
db.test.insertOne({"A":"a", "B": 101})
// b
db.test.insertOne({"A":"b", "B": 98})
db.test.insertOne({"A":"b", "B": 99})
// c
db.test.insertOne({"A":"c", "B": 102})
db.test.insertOne({"A":"c", "B": 103})
// add index
db.test.createIndex({"A": 1, "B": 1},{"name": "ix_A_B"})

The following query meets the requirements for splitting (exploding) the IXSCAN stage and merge-sorting the results with a SORT_MERGE stage:

db.test.find({"A": {$in: ["a", "b", "c"]}}).sort({"B": 1}).limit(5)

So a plan of the form LIMIT → FETCH → SORT_MERGE → IXSCAN(s) is generated. The actual execution statistics (executionStats) show how many times each stage was worked (works).

> db.test.find({"A": {$in: ["a", "b", "c"]}}).sort({"B": 1}).limit(5).explain("executionStats")
{
  ...
  executionStats: {
    executionSuccess: true,
    nReturned: 5,
    executionTimeMillis: 0,
    totalKeysExamined: 6,
    totalDocsExamined: 5,
    executionStages: {
      stage: 'LIMIT',
      nReturned: 5,
      executionTimeMillisEstimate: 0,
      works: 13,
      advanced: 5,
      needTime: 7,
      needYield: 0,
      saveState: 0,
      restoreState: 0,
      isEOF: 1,
      limitAmount: 5,
      inputStage: {
        stage: 'FETCH',
        nReturned: 5,
        executionTimeMillisEstimate: 0,
        works: 12,
        advanced: 5,
        needTime: 7,
        needYield: 0,
        saveState: 0,
        restoreState: 0,
        isEOF: 0,
        docsExamined: 5,
        alreadyHasObj: 0,
        inputStage: {
          stage: 'SORT_MERGE',
          nReturned: 5,
          executionTimeMillisEstimate: 0,
          works: 12,
          advanced: 5,
          needTime: 7,
          needYield: 0,
          saveState: 0,
          restoreState: 0,
          isEOF: 0,
          sortPattern: { B: 1 },
          dupsTested: 6,
          dupsDropped: 0,
          inputStages: [
            {
              stage: 'IXSCAN',
              nReturned: 3,
              executionTimeMillisEstimate: 0,
              works: 3,
              advanced: 3,
              needTime: 0,
              needYield: 0,
              saveState: 0,
              restoreState: 0,
              isEOF: 0,
              keyPattern: { A: 1, B: 1 },
              indexName: 'ix_A_B',
              isMultiKey: false,
              multiKeyPaths: { A: [], B: [] },
              isUnique: false,
              isSparse: false,
              isPartial: false,
              indexVersion: 2,
              direction: 'forward',
              indexBounds: { A: [ '["a", "a"]' ], B: [ '[MinKey, MaxKey]' ] },
              keysExamined: 3,
              seeks: 1,
              dupsTested: 0,
              dupsDropped: 0
            },
            {
              stage: 'IXSCAN',
              nReturned: 2,
              executionTimeMillisEstimate: 0,
              works: 3,
              advanced: 2,
              needTime: 0,
              needYield: 0,
              saveState: 0,
              restoreState: 0,
              isEOF: 1,
              keyPattern: { A: 1, B: 1 },
              indexName: 'ix_A_B',
              isMultiKey: false,
              multiKeyPaths: { A: [], B: [] },
              isUnique: false,
              isSparse: false,
              isPartial: false,
              indexVersion: 2,
              direction: 'forward',
              indexBounds: { A: [ '["b", "b"]' ], B: [ '[MinKey, MaxKey]' ] },
              keysExamined: 2,
              seeks: 1,
              dupsTested: 0,
              dupsDropped: 0
            },
            {
              stage: 'IXSCAN',
              nReturned: 1,
              executionTimeMillisEstimate: 0,
              works: 1,
              advanced: 1,
              needTime: 0,
              needYield: 0,
              saveState: 0,
              restoreState: 0,
              isEOF: 0,
              keyPattern: { A: 1, B: 1 },
              indexName: 'ix_A_B',
              isMultiKey: false,
              multiKeyPaths: { A: [], B: [] },
              isUnique: false,
              isSparse: false,
              isPartial: false,
              indexVersion: 2,
              direction: 'forward',
              indexBounds: { A: [ '["c", "c"]' ], B: [ '[MinKey, MaxKey]' ] },
              keysExamined: 1,
              seeks: 1,
              dupsTested: 0,
              dupsDropped: 0
            }
          ]
        }
      }
    }
  },
  ...
}

In these statistics, the LIMIT stage works the FETCH stage 13 times to obtain 5 documents.

The FETCH stage, in turn, keeps working the SORT_MERGE stage until it has received 5 sorted outputs. For each one, it uses the recordId to access the underlying storage and read the document (the fetch). Its work count is 12. LIMIT's count is one higher than its child's because of the additional call that checks whether the number of remaining results has reached 0.

The SORT_MERGE stage produces 5 sorted outputs by working its child IXSCAN stages.

The IXSCAN was split (exploded) into 3 index ranges:

{ A: [ '[a, a]' ], B: [ '[MinKey, MaxKey]' ] }
{ A: [ '[b, b]' ], B: [ '[MinKey, MaxKey]' ] }
{ A: [ '[c, c]' ], B: [ '[MinKey, MaxKey]' ] }

Because the sort requirement sort({"B": 1}) is ascending, each index scan runs forward. Each scan can be worked anywhere from 1 to 5 times, since all 5 results could come from a single index range.

Merge sort in the SORT_MERGE stage

Let’s see why, in the execution statistics above, the IXSCANs were worked 3, 2, and 1 times respectively.

The SORT_MERGE stage maintains a priority queue (_merging) ordered by its operator() comparator. Every time a new value is added to the queue, it is compared against the top value.

Which value ranks higher is determined by the sort pattern. The sort pattern may combine several fields with different directions, such as sort({"B": 1, "C": -1}). The field values are compared using the query's collation to determine the final order.

doWork() works the child stages (IXSCANs) one at a time and stores each output in the merge list (_mergingData). It then pushes the output into the priority queue (_merging), where it is compared according to the sort pattern, and returns NEED_TIME so that the upper stage calls it again.

On a later call, it returns the top value (id) of the priority queue to the upper stage, removes it from the queue and the list, and puts the child stage that produced that value into the child queue (_noResultToMerge).

In summary:

doWork():
  if the child queue is not empty:
    pop a child (tell that IXSCAN to do work)
    if it produced a result:
      remove it from the child queue
      push the result into the sort queue (ordered by operator())
      return NEED_TIME (needs to be called again)
    else:
      handle the error, then return FAILURE, IS_EOF, NEED_YIELD, NEED_TIME, etc.
  if the child queue is empty:
    pop the top value of the sort queue and return it
    append the child that produced it to the end of the child queue
    return ADVANCED

In other words, driven by the upper stage, it merges the outputs of the lower index scans and returns sorted results in order.

Here is a walkthrough of the processing.

As shown above, the IXSCAN stage is split, and the SORT_MERGE stage merge-sorts their outputs.

Initially, all child IXSCAN stages are placed in the child queue (_noResultToMerge). They are worked one at a time in that order, and their outputs are pushed into the merge list (_mergingData) and the priority queue (_merging) (1). The priority queue re-orders itself according to the sort pattern every time a value is pushed. (_mergingData is omitted from the figures.)

Once every child in _noResultToMerge has been worked and the queue is empty (4), the top value of _merging, 97, is returned to the upper stage, and IXSCAN(a), which produced it, is put back into _noResultToMerge so it can produce its next output (5).

_noResultToMerge is empty again (6), so the top value of _merging, 98, is returned (7), and IXSCAN(b) is worked next, pushing 99 into _merging (8).

_noResultToMerge is empty again, so the top value of _merging, 99, is returned (9). IXSCAN(b) is worked next, but it has nothing left to produce (the child IXSCAN(b) stage returns IS_EOF).

The top value of _merging, 100, is returned, and IXSCAN(a), which produced it, is put into _noResultToMerge (10).

IXSCAN(a) is worked, emptying _noResultToMerge and adding 101 to _merging (11). Then the top value of _merging, 101, is returned and IXSCAN(a) is put into _noResultToMerge (12). At this point all 5 results have been returned to the upper stage, and the SORT_MERGE stage is done.

The SORT_MERGE stage ran doWork 12 times in total. Its children were worked as follows: IXSCAN(a) 3 times, IXSCAN(b) 2 times, and IXSCAN(c) once. This matches the works counts in the execution statistics.

As this shows, the work count of each stage varies with the exploded index ranges, the sort pattern, and the actual distribution of field values.

Summary

• The SORT_MERGE stage drives its child IXSCAN stages so that as little data as possible is read. It is also efficient because no separate sort cost is incurred.
• As the name suggests, it follows the merge sort algorithm, but it does not actually split and sort subsets itself. It only merges subsets that are already sorted (the outputs of index scans) while preserving their order.
• It can appear when
• the index scan range can be split (exploded), and
• the output order of the index scans matches the sort requirement.
• The number of exploded index scan ranges is limited to 200. You can raise this with the internalQueryMaxScansToExplode parameter, but query execution may then require a larger working area. If such requests arrive at scale, the system can run short of memory.