SERVER-25782 Allow SORT_MERGE plans even if some children are FETCH stages rather than IXSCAN stages

4 files changed, 287 insertions, 53 deletions

diff --git a/jstests/core/explode_for_sort_fetch.js b/jstests/core/explode_for_sort_fetch.js
new file mode 100644
index 00000000000..9e295080399
--- /dev/null
+++ b/jstests/core/explode_for_sort_fetch.js
@@ -0,0 +1,124 @@
+/**
+ * Tests explode for sort query planner behavior when the input query plan contains OR > FETCH >
+ * IXSCAN, OR > IXSCAN subtrees or a mix of both.
+ * @tags: [
+ * # Does not work with legacy shellWriteMode.
+ * requires_find_command
+ * ]
+ */
+(function() {
+"use strict";
+
+const testDB = db.getSiblingDB(jsTestName());
+assert.commandWorked(testDB.dropDatabase());
+const coll = testDB.explode_for_sort_fetch;
+
+// Executes a test case that creates indexes, inserts documents, issues a find query on a
+// collection and checks the results.
+function executeQueryTestCase(testCase) {
+    jsTestLog(tojson(testCase));
+
+    // Drop the collection.
+    coll.drop();
+
+    // Create indexes.
+    assert.commandWorked(coll.createIndexes(testCase.indexes));
+
+    // Insert some documents into the collection.
+    assert.commandWorked(coll.insert(testCase.inputDocuments));
+
+    // Issue a find query and compare results to expected.
+    assert.eq(coll.find(testCase.filter).sort(testCase.sort).toArray(),
+              testCase.expectedResults,
+              `Test case ${testCase.name}`);
+}
+
+const testCases = [
+    {
+        // Verifies that query produces correct results when the query plan passed to explode for
+        // sort contains subtree of shape OR > FETCH > IXSCAN. Attribute 'f' is fetched by the FETCH
+        // stage.
+        name: "ExplodeForSortIxscanFetchOr",
+        indexes: [{a: 1, b: 1, e: 1}, {c: -1, d: -1, e: -1}],
+        filter: {
+            $or: [
+                {a: {$in: [1, 2]}, b: {$in: [3, 4]}, f: 5},
+                {c: {$in: [1, 2]}, d: {$in: [3, 4]}, f: 5}
+            ]
+        },
+        sort: {e: 1},
+        inputDocuments: [
+            {_id: 3, a: 1, b: 3, f: 5, e: 3},
+            {_id: 4, a: 2, b: 4, f: 5, e: 4},
+            {_id: 8, a: 1, b: 4, f: 5, e: 8},
+            {_id: 1, a: 2, b: 3, f: 5, e: 1},
+            {_id: 0, a: 2, b: 3, f: 3, e: 0},
+            {_id: 7, c: 1, d: 3, f: 5, e: 7},
+            {_id: 6, c: 2, d: 4, f: 5, e: 6},
+            {_id: 2, c: 1, d: 4, f: 5, e: 2},
+            {_id: 5, c: 2, d: 3, f: 5, e: 5},
+            {_id: 9, c: 2, d: 3, f: 3, e: 9},
+        ],
+        expectedResults: [
+            {_id: 1, a: 2, b: 3, f: 5, e: 1},
+            {_id: 2, c: 1, d: 4, f: 5, e: 2},
+            {_id: 3, a: 1, b: 3, f: 5, e: 3},
+            {_id: 4, a: 2, b: 4, f: 5, e: 4},
+            {_id: 5, c: 2, d: 3, f: 5, e: 5},
+            {_id: 6, c: 2, d: 4, f: 5, e: 6},
+            {_id: 7, c: 1, d: 3, f: 5, e: 7},
+            {_id: 8, a: 1, b: 4, f: 5, e: 8},
+        ]
+    },
+    {
+        // Verifies that query produces correct results when the query plan passed to explode for
+        // sort contains a mix of subtrees of shape OR > FETCH > IXSCAN and OR > IXSCAN. Attribute
+        // 'f' is fetched by the FETCH stage.
+        name: "ExplodeForSortIxscanFetchOrMixedWithIxscanOr",
+        indexes: [{a: 1, b: 1, e: 1}, {c: -1, d: 1, e: -1}],
+        filter:
+            {$or: [{a: {$in: [1, 2]}, b: {$in: [3, 4]}, f: 5}, {c: {$in: [1, 2]}, d: {$in: [3]}}]},
+        sort: {e: 1},
+        inputDocuments: [
+            {_id: 3, a: 1, b: 3, f: 5, e: 3},
+            {_id: 4, a: 2, b: 4, f: 5, e: 4},
+            {_id: 8, a: 1, b: 4, f: 5, e: 8},
+            {_id: 1, a: 2, b: 3, f: 5, e: 1},
+            {_id: 0, a: 2, b: 3, f: 3, e: 0},
+            {_id: 7, c: 1, d: 3, f: 5, e: 7},
+            {_id: 5, c: 2, d: 3, f: 5, e: 5},
+            {_id: 9, c: 2, d: 3, f: 3, e: 9},
+        ],
+        expectedResults: [
+            {_id: 1, a: 2, b: 3, f: 5, e: 1},
+            {_id: 3, a: 1, b: 3, f: 5, e: 3},
+            {_id: 4, a: 2, b: 4, f: 5, e: 4},
+            {_id: 5, c: 2, d: 3, f: 5, e: 5},
+            {_id: 7, c: 1, d: 3, f: 5, e: 7},
+            {_id: 8, a: 1, b: 4, f: 5, e: 8},
+            {_id: 9, c: 2, d: 3, f: 3, e: 9},
+        ]
+    },
+    {
+        // Verifies that query produces correct results when the query plan passed to explode for
+        // sort contains a subtree of shape OR > IXSCAN.
+        name: "ExplodeForSortIxscanOr",
+        indexes: [{a: 1, b: 1, e: 1}, {c: -1, d: 1, e: -1}],
+        filter: {$or: [{a: {$in: [1, 2]}, b: 3}, {c: {$in: [1, 2]}, d: 3}]},
+        sort: {e: 1},
+        inputDocuments: [
+            {_id: 1, a: 1, b: 3, f: 5, e: 1},
+            {_id: 3, a: 2, b: 3, f: 5, e: 3},
+            {_id: 2, c: 1, d: 3, f: 5, e: 2},
+            {_id: 4, c: 2, d: 3, f: 5, e: 4},
+        ],
+        expectedResults: [
+            {_id: 1, a: 1, b: 3, f: 5, e: 1},
+            {_id: 2, c: 1, d: 3, f: 5, e: 2},
+            {_id: 3, a: 2, b: 3, f: 5, e: 3},
+            {_id: 4, c: 2, d: 3, f: 5, e: 4},
+        ]
+    },
+];
+testCases.forEach(executeQueryTestCase);
+}());
\ No newline at end of file
diff --git a/jstests/libs/parallelTester.js b/jstests/libs/parallelTester.js
index acec214a2b5..d3461adb73d 100644
--- a/jstests/libs/parallelTester.js
+++ b/jstests/libs/parallelTester.js
@@ -221,6 +221,7 @@ if (typeof _threadInject != "undefined") {
             var requires_find_command = [
                 "apply_ops_system_dot_views.js",
                 "explode_for_sort_collation.js",
+                "explode_for_sort_fetch.js",
                 "update_pipeline_shell_helpers.js",
                 "update_with_pipeline.js",
                 "views/dbref_projection.js",
diff --git a/src/mongo/db/query/planner_analysis.cpp b/src/mongo/db/query/planner_analysis.cpp
index 077b0d4dcf7..f5dd21a114b 100644
--- a/src/mongo/db/query/planner_analysis.cpp
+++ b/src/mongo/db/query/planner_analysis.cpp
@@ -73,6 +73,43 @@ void getLeafNodes(QuerySolutionNode* root, vector<QuerySolutionNode*>* leafNodes
 }
 
 /**
+ * Determines if the query solution node 'node' is a FETCH node with an IXSCAN child node.
+ */
+bool isFetchNodeWithIndexScanChild(const QuerySolutionNode* node) {
+    return (STAGE_FETCH == node->getType() && node->children.size() == 1 &&
+            STAGE_IXSCAN == node->children[0]->getType());
+}
+
+/**
+ * Walks the tree 'root' and outputs all nodes that can be considered for explosion for sort.
+ * Outputs FETCH nodes with an IXSCAN node as a child as well as singular IXSCAN leaves without a
+ * FETCH as a parent into 'explodableNodes'.
+ */
+void getExplodableNodes(QuerySolutionNode* root, vector<QuerySolutionNode*>* explodableNodes) {
+    if (STAGE_IXSCAN == root->getType() || isFetchNodeWithIndexScanChild(root)) {
+        explodableNodes->push_back(root);
+    } else {
+        for (auto&& childNode : root->children) {
+            getExplodableNodes(childNode, explodableNodes);
+        }
+    }
+}
+
+/**
+ * Returns the IXSCAN node from the tree 'node' that can be either a IXSCAN node or a FETCH node
+ * with an IXSCAN node as a child.
+ */
+const IndexScanNode* getIndexScanNode(const QuerySolutionNode* node) {
+    if (STAGE_IXSCAN == node->getType()) {
+        return static_cast<const IndexScanNode*>(node);
+    } else if (isFetchNodeWithIndexScanChild(node)) {
+        return static_cast<const IndexScanNode*>(node->children[0]);
+    }
+    MONGO_UNREACHABLE;
+    return nullptr;
+}
+
+/**
  * Returns true if every interval in 'oil' is a point, false otherwise.
  */
 bool isUnionOfPoints(const OrderedIntervalList& oil) {
@@ -115,16 +152,16 @@ bool structureOKForExplode(QuerySolutionNode* solnRoot, QuerySolutionNode** toRe
         return true;
     }
 
-    if (STAGE_FETCH == solnRoot->getType()) {
-        if (STAGE_IXSCAN == solnRoot->children[0]->getType()) {
-            *toReplace = solnRoot->children[0];
-            return true;
-        }
+    if (isFetchNodeWithIndexScanChild(solnRoot)) {
+        *toReplace = solnRoot->children[0];
+        return true;
     }
 
+    // If we have a STAGE_OR, we can explode only when all children are either IXSCANs or FETCHes
+    // that have an IXSCAN as a child.
     if (STAGE_OR == solnRoot->getType()) {
-        for (size_t i = 0; i < solnRoot->children.size(); ++i) {
-            if (STAGE_IXSCAN != solnRoot->children[i]->getType()) {
+        for (auto&& child : solnRoot->children) {
+            if (STAGE_IXSCAN != child->getType() && !isFetchNodeWithIndexScanChild(child)) {
                 return false;
             }
         }
@@ -184,9 +221,9 @@ void makeCartesianProduct(const IndexBounds& bounds,
 }
 
 /**
- * Take the provided index scan node 'isn'. Returns a list of index scans which are
- * logically equivalent to 'isn' if joined by a MergeSort through the out-parameter
- * 'explosionResult'. These index scan instances are owned by the caller.
+ * Takes the provided 'node', either an IndexScanNode or FetchNode with a direct child that is an
+ * IndexScanNode. Returns a list of nodes which are logically equivalent to 'node' if joined by a
+ * MergeSort through the out-parameter 'explosionResult'. These nodes are owned by the caller.
  *
  * fieldsToExplode is a count of how many fields in the scan's bounds are the union of point
  * intervals.  This is computed beforehand and provided as a small optimization.
@@ -194,18 +231,21 @@ void makeCartesianProduct(const IndexBounds& bounds,
  * Example:
  *
  * For the query find({a: {$in: [1,2]}}).sort({b: 1}) using the index {a:1, b:1}:
- * 'isn' will be scan with bounds a:[[1,1],[2,2]] & b: [MinKey, MaxKey]
+ * 'node' will be a scan with multi-interval bounds a: [[1, 1], [2, 2]], b: [MinKey, MaxKey]
  * 'sort' will be {b: 1}
  * 'fieldsToExplode' will be 1 (as only one field isUnionOfPoints).
  *
  * On return, 'explosionResult' will contain the following two scans:
- * a:[[1,1]], b:[MinKey, MaxKey]
- * a:[[2,2]], b:[MinKey, MaxKey]
+ * a: [[1, 1]], b: [MinKey, MaxKey]
+ * a: [[2, 2]], b: [MinKey, MaxKey]
  */
-void explodeScan(const IndexScanNode* isn,
+void explodeNode(const QuerySolutionNode* node,
                  const BSONObj& sort,
                  size_t fieldsToExplode,
                  vector<QuerySolutionNode*>* explosionResult) {
+    // Get the 'isn' from either the FetchNode or IndexScanNode.
+    const IndexScanNode* isn = getIndexScanNode(node);
+
     // Turn the compact bounds in 'isn' into a bunch of points...
     vector<PointPrefix> prefixForScans;
     makeCartesianProduct(isn->bounds, fieldsToExplode, &prefixForScans);
@@ -234,7 +274,23 @@ void explodeScan(const IndexScanNode* isn,
         for (size_t j = fieldsToExplode; j < isn->bounds.fields.size(); ++j) {
             child->bounds.fields[j] = isn->bounds.fields[j];
         }
-        explosionResult->push_back(child);
+
+        // If the explosion is on a FetchNode, make a copy and add the 'isn' as a child.
+        if (STAGE_FETCH == node->getType()) {
+            auto origFetchNode = static_cast<const FetchNode*>(node);
+            auto newFetchNode = std::make_unique<FetchNode>();
+
+            // Copy the FETCH's filter, if it exists.
+            if (origFetchNode->filter.get()) {
+                newFetchNode->filter = origFetchNode->filter->shallowClone();
+            }
+
+            // Add the 'child' IXSCAN under the FETCH stage, and the FETCH stage to the result set.
+            newFetchNode->children.push_back(child);
+            explosionResult->push_back(newFetchNode.release());
+        } else {
+            explosionResult->push_back(child);
+        }
     }
 }
 
@@ -530,31 +586,31 @@ BSONObj QueryPlannerAnalysis::getSortPattern(const BSONObj& indexKeyPattern) {
 bool QueryPlannerAnalysis::explodeForSort(const CanonicalQuery& query,
                                           const QueryPlannerParams& params,
                                           QuerySolutionNode** solnRoot) {
-    vector<QuerySolutionNode*> leafNodes;
+    vector<QuerySolutionNode*> explodableNodes;
 
     QuerySolutionNode* toReplace;
     if (!structureOKForExplode(*solnRoot, &toReplace)) {
         return false;
     }
 
-    getLeafNodes(*solnRoot, &leafNodes);
+    // Find explodable nodes in the subtree rooted at 'toReplace'.
+    getExplodableNodes(toReplace, &explodableNodes);
 
     const BSONObj& desiredSort = query.getQueryRequest().getSort();
 
     // How many scan leaves will result from our expansion?
     size_t totalNumScans = 0;
 
-    // The value of entry i is how many scans we want to blow up for leafNodes[i].
-    // We calculate this in the loop below and might as well reuse it if we blow up
-    // that scan.
+    // The value of entry i is how many scans we want to blow up for explodableNodes[i]. We
+    // calculate this in the loop below and might as well reuse it if we blow up that scan.
     vector<size_t> fieldsToExplode;
 
     // The sort order we're looking for has to possibly be provided by each of the index scans
     // upon explosion.
-    for (size_t i = 0; i < leafNodes.size(); ++i) {
+    for (auto&& explodableNode : explodableNodes) {
         // We can do this because structureOKForExplode is only true if the leaves are index
         // scans.
-        IndexScanNode* isn = static_cast<IndexScanNode*>(leafNodes[i]);
+        IndexScanNode* isn = const_cast<IndexScanNode*>(getIndexScanNode(explodableNode));
         const IndexBounds& bounds = isn->bounds;
 
         // Not a point interval prefix, can't try to rewrite.
@@ -662,9 +718,8 @@ bool QueryPlannerAnalysis::explodeForSort(const CanonicalQuery& query,
     // get our sort order via ixscan blow-up.
     MergeSortNode* merge = new MergeSortNode();
     merge->sort = desiredSort;
-    for (size_t i = 0; i < leafNodes.size(); ++i) {
-        IndexScanNode* isn = static_cast<IndexScanNode*>(leafNodes[i]);
-        explodeScan(isn, desiredSort, fieldsToExplode[i], &merge->children);
+    for (size_t i = 0; i < explodableNodes.size(); ++i) {
+        explodeNode(explodableNodes[i], desiredSort, fieldsToExplode[i], &merge->children);
     }
 
     merge->computeProperties();
diff --git a/src/mongo/db/query/query_planner_tree_test.cpp b/src/mongo/db/query/query_planner_tree_test.cpp
index 1b9017a8c13..d25d8bd7341 100644
--- a/src/mongo/db/query/query_planner_tree_test.cpp
+++ b/src/mongo/db/query/query_planner_tree_test.cpp
@@ -929,7 +929,7 @@ TEST_F(QueryPlannerTest, ExplodeOrForSort2) {
 }
 
 // SERVER-13754: an $or that can't be exploded, because one clause of the
-// $or does provide the sort, even after explosion.
+// $or doesn't provide the sort, even after explosion.
 TEST_F(QueryPlannerTest, CantExplodeOrForSort) {
     addIndex(BSON("a" << 1 << "b" << 1 << "c" << 1));
     addIndex(BSON("d" << 1 << "c" << 1));
@@ -947,45 +947,39 @@ TEST_F(QueryPlannerTest, CantExplodeOrForSort) {
         "{ixscan: {pattern: {d: 1, c: 1}}}]}}}}}}");
 }
 
-// SERVER-13754: too many scans in an $or explosion.
+// Verifies that the $or is not exploded due to too many ixscans in the explosion.
 TEST_F(QueryPlannerTest, TooManyToExplodeOr) {
-    addIndex(BSON("a" << 1 << "e" << 1));
-    addIndex(BSON("b" << 1 << "e" << 1));
-    addIndex(BSON("c" << 1 << "e" << 1));
-    addIndex(BSON("d" << 1 << "e" << 1));
-    runQuerySortProj(fromjson("{$or: [{a: {$in: [1,2,3,4,5,6]},"
-                              "b: {$in: [1,2,3,4,5,6]}},"
-                              "{c: {$in: [1,2,3,4,5,6]},"
-                              "d: {$in: [1,2,3,4,5,6]}}]}"),
+    addIndex(BSON("a" << 1 << "b" << 1 << "e" << 1));
+    addIndex(BSON("b" << 1 << "c" << 1 << "e" << 1));
+    // Both branches of the $or have 2 indexed predicates with an 11-element $in, which will
+    // generate a total of 2*(11^2)=242 scans when exploded. This exceeds the permitted limit of
+    // 200.
+    runQuerySortProj(fromjson("{$or: [{a: {$in: [1,2,3,4,5,6,7,8,9,10,11]},"
+                              "b: {$in: [1,2,3,4,5,6,7,8,9,10,11]},"
+                              "d: {$in: [1, 2]}},"
+                              "{c: {$in: [1,2,3,4,5,6,7,8,9,10,11]},"
+                              "b: {$in: [1,2,3,4,5,6,7,8,9,10,11]}}]}"),
                      BSON("e" << 1),
                      BSONObj());
 
     // We cap the # of ixscans we're willing to create, so we don't get explosion. Instead
-    // we get 5 different solutions which all use a blocking sort.
-    assertNumSolutions(5U);
+    // we get 3 different solutions which all use a blocking sort.
+    assertNumSolutions(3U);
     assertSolutionExists(
         "{sort: {pattern: {e: 1}, limit: 0, type: 'simple', node: "
         "{cscan: {dir: 1}}}}");
     assertSolutionExists(
-        "{sort: {pattern: {e: 1}, limit: 0, type: 'simple', node: "
-        "{or: {nodes: ["
-        "{fetch: {node: {ixscan: {pattern: {a: 1, e: 1}}}}},"
-        "{fetch: {node: {ixscan: {pattern: {c: 1, e: 1}}}}}]}}}}");
-    assertSolutionExists(
-        "{sort: {pattern: {e: 1}, limit: 0, type: 'simple', node: "
-        "{or: {nodes: ["
-        "{fetch: {node: {ixscan: {pattern: {b: 1, e: 1}}}}},"
-        "{fetch: {node: {ixscan: {pattern: {c: 1, e: 1}}}}}]}}}}");
-    assertSolutionExists(
-        "{sort: {pattern: {e: 1}, limit: 0, type: 'simple', node: "
+        "{fetch: {node: "
+        "{sort: {pattern: {e: 1}, limit: 0, type: 'default', node: "
         "{or: {nodes: ["
-        "{fetch: {node: {ixscan: {pattern: {a: 1, e: 1}}}}},"
-        "{fetch: {node: {ixscan: {pattern: {d: 1, e: 1}}}}}]}}}}");
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1, e: 1}}}}},"
+        "{ixscan: {pattern: {b: 1, c: 1, e: 1}}}]}}}}}}");
     assertSolutionExists(
-        "{sort: {pattern: {e: 1}, limit: 0, type: 'simple', node: "
+        "{fetch: {node: "
+        "{sort: {pattern: {e: 1}, limit: 0, type: 'default', node: "
         "{or: {nodes: ["
-        "{fetch: {node: {ixscan: {pattern: {b: 1, e: 1}}}}},"
-        "{fetch: {node: {ixscan: {pattern: {d: 1, e: 1}}}}}]}}}}");
+        "{ixscan: {pattern: {b: 1, c: 1, e: 1}}},"
+        "{fetch: {node: {ixscan: {pattern: {b: 1, c: 1, e: 1}}}}}]}}}}}}");
 }
 
 // SERVER-15696: Make sure explodeForSort copies filters on IXSCAN stages to all of the
@@ -1011,6 +1005,66 @@ TEST_F(QueryPlannerTest, ExplodeIxscanWithFilter) {
         "filter: {b: {$regex: 'foo', $options: 'i'}}}}]}}}}");
 }
 
+// Verifies that a OR > FETCH > IXSCAN plan is exploded for sort.
+TEST_F(QueryPlannerTest, ExplodeForSortIxscanFetchOr) {
+    addIndex(BSON("a" << 1 << "x" << 1));
+    addIndex(BSON("b" << 1 << "x" << 1));
+
+    // Field 'c' is not covered by an index and forces an introduction of a FETCH stage to form
+    // OR > FETCH > IXSCAN tree.
+    runQuerySortProj(fromjson("{$or: [{a: {$in: [1,2]}, c: 1}, {b: {$in: [3,4]}, c: 2}]}"),
+                     BSON("x" << 1),
+                     BSONObj());
+
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{sort: {pattern: {x: 1}, limit: 0, type: 'simple', node:"
+        "{cscan: {dir: 1}}}}}");
+    assertSolutionExists(
+        "{mergeSort: {nodes:"
+        "[{fetch: {filter: {c: 1}, node:"
+        "{ixscan: {bounds: {a: [[1,1,true,true]], x: [['MinKey','MaxKey',true,true]]},"
+        "pattern: {a:1, x:1}}}}},"
+        "{fetch: {filter: {c: 1}, node:"
+        "{ixscan: {bounds: {a: [[2,2,true,true]], x: [['MinKey','MaxKey',true,true]]},"
+        "pattern: {a:1, x:1}}}}},"
+        "{fetch: {filter: {c: 2}, node:"
+        "{ixscan: {bounds: {b: [[3,3,true,true]], x: [['MinKey','MaxKey',true,true]]},"
+        "pattern: {b:1, x:1}}}}},"
+        "{fetch: {filter: {c: 2}, node:"
+        "{ixscan: {bounds: {b: [[4,4,true,true]], x: [['MinKey','MaxKey',true,true]]},"
+        "pattern: {b:1, x:1}}}}}]}}");
+}
+
+// Verifies that a mix of OR > IXSCAN and OR > FETCH > IXSCAN plan structures is exploded for sort.
+TEST_F(QueryPlannerTest, ExplodeForSortIxscanFetchOrAndIxscanOr) {
+    addIndex(BSON("a" << 1 << "x" << 1));
+    addIndex(BSON("b" << 1 << "x" << 1));
+
+    // Field 'c' is not covered by an index and forces an introduction of a FETCH stage to form
+    // OR > FETCH > IXSCAN tree.
+    runQuerySortProj(
+        fromjson("{$or: [{a: {$in: [1,2]}, c: 1}, {b: {$in: [3,4]}}]}"), BSON("x" << 1), BSONObj());
+
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{sort: {pattern: {x: 1}, limit: 0, type: 'simple', node:"
+        "{cscan: {dir: 1}}}}}");
+    assertSolutionExists(
+        "{fetch: {node:"
+        "{mergeSort: {nodes:"
+        "[{fetch: {filter: {c: 1}, node:"
+        "{ixscan: {bounds: {a: [[1,1,true,true]], x: [['MinKey','MaxKey',true,true]]},"
+        "pattern: {a:1, x:1}}}}},"
+        "{fetch: {filter: {c: 1}, node:"
+        "{ixscan: {bounds: {a: [[2,2,true,true]], x: [['MinKey','MaxKey',true,true]]},"
+        "pattern: {a:1, x:1}}}}},"
+        "{ixscan: {bounds: {b: [[3,3,true,true]], x: [['MinKey','MaxKey',true,true]]},"
+        "pattern: {b:1, x:1}}},"
+        "{ixscan: {bounds: {b: [[4,4,true,true]], x: [['MinKey','MaxKey',true,true]]},"
+        "pattern: {b:1, x:1}}}]}}}}");
+}
+
 TEST_F(QueryPlannerTest, InWithSortAndLimitTrailingField) {
     addIndex(BSON("a" << 1 << "b" << -1 << "c" << 1));
     runQuerySortProjSkipNToReturn(fromjson("{a: {$in: [1, 2]}, b: {$gte: 0}}"),