SERVER-31898 Allow multikey indexes to provide sorts in certain cases

7 files changed, 389 insertions, 59 deletions

diff --git a/jstests/aggregation/group_conversion_to_distinct_scan.js b/jstests/aggregation/group_conversion_to_distinct_scan.js
index 226dea6f584..47cf5005a09 100644
--- a/jstests/aggregation/group_conversion_to_distinct_scan.js
+++ b/jstests/aggregation/group_conversion_to_distinct_scan.js
@@ -300,18 +300,32 @@ explain = coll.explain().aggregate(pipeline);
 assert.eq(null, getAggPlanStage(explain, "DISTINCT_SCAN"), explain);
 
 //
-// Verify that we _do not_ attempt a DISTINCT_SCAN to satisfy a sort on a multikey field, even
-// when the field we are grouping by is not multikey.
+// Verify that we use a DISTINCT_SCAN to satisfy a sort on a multikey field if the bounds
+// are [minKey, maxKey].
 //
 pipeline = [{$sort: {aa: 1, mkB: 1}}, {$group: {_id: "$aa", accum: {$first: "$mkB"}}}];
 assertResultsMatchWithAndWithoutHintandIndexes(
     pipeline, [{_id: null, accum: null}, {_id: 1, accum: [1, 3]}, {_id: 2, accum: []}]);
 explain = coll.explain().aggregate(pipeline);
-assert.eq(null, getAggPlanStage(explain, "DISTINCT_SCAN"), tojson(explain));
+assert.neq(null, getAggPlanStage(explain, "DISTINCT_SCAN"), explain);
+assert.eq({aa: 1, mkB: 1, c: 1}, getAggPlanStage(explain, "DISTINCT_SCAN").keyPattern);
+assert.neq(null, getAggPlanStage(explain, "FETCH"));
+assert.eq(null, getAggPlanStage(explain, "SORT"));
 
 //
-// Verify that with dotted paths we _do not_ attempt a DISTINCT_SCAN to satisfy a sort on a
-// multikey field, even when the field we are grouping by is not multikey.
+// Verify that we _do not_ attempt a DISTINCT_SCAN because "mkB" is multikey, and we don't use
+// DISTINCT_SCAN for a compound group key.
+//
+pipeline = [{$sort: {aa: 1, mkB: 1}}, {$group: {_id: {aa: "$aa", mkB: "$mkB"}}}];
+assertResultsMatchWithAndWithoutHintandIndexes(
+    pipeline,
+    [{_id: {aa: 1, mkB: [1, 3]}}, {_id: {}}, {_id: {aa: 1, mkB: 2}}, {_id: {aa: 2, mkB: []}}]);
+explain = coll.explain().aggregate(pipeline);
+assert.eq(null, getAggPlanStage(explain, "DISTINCT_SCAN"), explain);
+
+//
+// Verify that with dotted paths we use a DISTINCT_SCAN to satisfy a sort on a multikey field if the
+// bounds are [minKey, maxKey].
 //
 pipeline =
     [{$sort: {"foo.a": 1, "mkFoo.b": 1}}, {$group: {_id: "$foo.a", accum: {$first: "$mkFoo.b"}}}];
@@ -319,6 +333,58 @@ assertResultsMatchWithAndWithoutHintandIndexes(
     pipeline,
     [{_id: null, accum: null}, {_id: 1, accum: 1}, {_id: 2, accum: 2}, {_id: 3, accum: [4, 3]}]);
 explain = coll.explain().aggregate(pipeline);
+assert.neq(null, getAggPlanStage(explain, "DISTINCT_SCAN"));
+assert.eq(
+    {"foo.a": 1, "mkFoo.b": 1}, getAggPlanStage(explain, "DISTINCT_SCAN").keyPattern, explain);
+assert.neq(null, getAggPlanStage(explain, "FETCH"));
+assert.eq(null, getAggPlanStage(explain, "SORT"));
+
+//
+// Verify that we _do not_ attempt a DISTINCT_SCAN to satisfy a sort on a multikey field if
+// the bounds are not [minKey, maxKey].
+//
+pipeline = [
+    {$match: {mkB: {$ne: 9999}}},
+    {$sort: {aa: 1, mkB: 1}},
+    {$group: {_id: "$aa", accum: {$first: "$mkB"}}}
+];
+assertResultsMatchWithAndWithoutHintandIndexes(
+    pipeline, [{_id: 1, accum: [1, 3]}, {_id: null, accum: null}, {_id: 2, accum: []}]);
+explain = coll.explain().aggregate(pipeline);
+assert.eq(null, getAggPlanStage(explain, "DISTINCT_SCAN"), explain);
+
+pipeline = [
+    {$match: {mkB: {$gt: -5}}},
+    {$sort: {aa: 1, mkB: 1}},
+    {$group: {_id: "$aa", accum: {$first: "$mkB"}}}
+];
+assertResultsMatchWithAndWithoutHintandIndexes(pipeline, [{_id: 1, accum: [1, 3]}]);
+explain = coll.explain().aggregate(pipeline);
+assert.eq(null, getAggPlanStage(explain, "DISTINCT_SCAN"), explain);
+
+pipeline = [
+    {$match: {aa: {$ne: 9999}}},
+    {$sort: {aa: 1, mkB: 1}},
+    {$group: {_id: "$aa", accum: {$first: "$mkB"}}}
+];
+assertResultsMatchWithAndWithoutHintandIndexes(
+    pipeline, [{_id: 1, accum: [1, 3]}, {_id: null, accum: null}, {_id: 2, accum: []}]);
+explain = coll.explain().aggregate(pipeline);
+assert.neq(null, getAggPlanStage(explain, "DISTINCT_SCAN"), explain);
+
+//
+// Verify that with dotted paths we _do not_ attempt a DISTINCT_SCAN to satisfy a sort on a
+// multikey field if the bounds are not [minKey, maxKey].
+//
+pipeline = [
+    {$match: {"mkFoo.b": {$ne: 20000}}},
+    {$sort: {"foo.a": 1, "mkFoo.b": 1}},
+    {$group: {_id: "$foo.a", accum: {$first: "$mkFoo.b"}}}
+];
+assertResultsMatchWithAndWithoutHintandIndexes(
+    pipeline,
+    [{_id: null, accum: null}, {_id: 1, accum: 1}, {_id: 2, accum: 2}, {_id: 3, accum: [4, 3]}]);
+explain = coll.explain().aggregate(pipeline);
 assert.eq(null, getAggPlanStage(explain, "DISTINCT_SCAN"), explain);
 
 //
diff --git a/jstests/core/sort_array.js b/jstests/core/sort_array.js
index bd30bcb169f..a5b4347d45d 100644
--- a/jstests/core/sort_array.js
+++ b/jstests/core/sort_array.js
@@ -1,4 +1,4 @@
-// @tags: [does_not_support_stepdowns, requires_non_retryable_writes]
+// @tags: [does_not_support_stepdowns, requires_non_retryable_writes, requires_fcv_44]
 
 /**
  * Tests for sorting documents by fields that contain arrays.
@@ -13,9 +13,10 @@ let coll = db.jstests_array_sort;
 /**
  * Runs a $match-$sort-$project query as both a find and then an aggregate. Asserts that the
  * result set, after being converted to an array, is equal to 'expected'. Also asserts that the
- * find plan uses the SORT stage and the agg plan uses the "$sort" agg stage.
+ * find plan either uses the SORT stage and the agg plan uses the "$sort" agg stage or does not use
+ * either dependent on the value of expectBlockingSort.
  */
-function testAggAndFindSort({filter, sort, project, hint, expected}) {
+function testAggAndFindSort({filter, sort, project, hint, expected, expectBlockingSort}) {
     let cursor = coll.find(filter, project).sort(sort);
     assert.eq(cursor.toArray(), expected);
     if (hint) {
@@ -24,7 +25,11 @@ function testAggAndFindSort({filter, sort, project, hint, expected}) {
         assert.eq(cursor.toArray(), expected);
     }
     let explain = coll.find(filter, project).sort(sort).explain();
-    assert(planHasStage(db, explain, "SORT"));
+    if (expectBlockingSort) {
+        assert(planHasStage(db, explain, "SORT"));
+    } else {
+        assert(!planHasStage(db, explain, "SORT"));
+    }
 
     let pipeline = [
         {$_internalInhibitOptimization: {}},
@@ -55,7 +60,8 @@ testAggAndFindSort({
     filter: {a: {$gte: 2}},
     sort: {a: 1},
     project: {_id: 1, a: 1},
-    expected: [{_id: 1, a: [8, 4, -1]}, {_id: 0, a: [3, 0, 1]}]
+    expected: [{_id: 1, a: [8, 4, -1]}, {_id: 0, a: [3, 0, 1]}],
+    expectBlockingSort: true
 });
 
 assert.commandWorked(coll.remove({}));
@@ -67,33 +73,41 @@ testAggAndFindSort({
     filter: {a: {$gte: 2}},
     sort: {a: -1},
     project: {_id: 1, a: 1},
-    expected: [{_id: 1, a: [0, 4, -1]}, {_id: 0, a: [3, 0, 1]}]
+    expected: [{_id: 1, a: [0, 4, -1]}, {_id: 0, a: [3, 0, 1]}],
+    expectBlockingSort: true
 });
 
 assert.commandWorked(coll.remove({}));
-assert.commandWorked(coll.insert({_id: 0, a: [3, 0, 1]}));
-assert.commandWorked(coll.insert({_id: 1, a: [8, 4, -1]}));
 assert.commandWorked(coll.createIndex({a: 1}));
+assert.commandWorked(coll.insert({_id: 0, a: [3, 0, 1]}));
+assert.commandWorked(coll.insert({_id: 1, a: [0, 4, -1]}));
 
-// Ascending sort, in the presence of an index. The multikey index should not be used to provide
-// the sort.
+// Descending sort, in the presence of an index.
 testAggAndFindSort({
     filter: {a: {$gte: 2}},
-    sort: {a: 1},
+    sort: {a: -1},
     project: {_id: 1, a: 1},
-    expected: [{_id: 1, a: [8, 4, -1]}, {_id: 0, a: [3, 0, 1]}]
+    expected: [{_id: 1, a: [0, 4, -1]}, {_id: 0, a: [3, 0, 1]}],
+    expectBlockingSort: true
 });
 
-assert.commandWorked(coll.remove({}));
-assert.commandWorked(coll.insert({_id: 0, a: [3, 0, 1]}));
-assert.commandWorked(coll.insert({_id: 1, a: [0, 4, -1]}));
-
-// Descending sort, in the presence of an index.
+// Descending sort, in the presence of an index with [minKey, maxKey] bounds has a non-blocking
+// sort.
 testAggAndFindSort({
-    filter: {a: {$gte: 2}},
+    filter: {},
     sort: {a: -1},
     project: {_id: 1, a: 1},
-    expected: [{_id: 1, a: [0, 4, -1]}, {_id: 0, a: [3, 0, 1]}]
+    expected: [{_id: 1, a: [0, 4, -1]}, {_id: 0, a: [3, 0, 1]}],
+    expectBlockingSort: false
+});
+
+// Ascending sort, in the presence of an index with [minKey, maxKey] bounds has a non-blocking sort.
+testAggAndFindSort({
+    filter: {},
+    sort: {a: 1},
+    project: {_id: 1, a: 1},
+    expected: [{_id: 1, a: [0, 4, -1]}, {_id: 0, a: [3, 0, 1]}],
+    expectBlockingSort: false
 });
 
 assert.commandWorked(coll.remove({}));
@@ -102,21 +116,90 @@ assert.commandWorked(coll.insert({_id: 1, x: [{y: 1, z: 7}, {y: 0, z: [8, 6]}]})
 
 // Compound mixed ascending/descending sorts, without an index. Sort key for doc with _id: 0 is
 // {'': 0, '': 9}. Sort key for doc with _id: 1 is {'': 0, '': 8}.
-testAggAndFindSort(
-    {filter: {}, sort: {"x.y": 1, "x.z": -1}, project: {_id: 1}, expected: [{_id: 0}, {_id: 1}]});
+testAggAndFindSort({
+    filter: {},
+    sort: {"x.y": 1, "x.z": -1},
+    project: {_id: 1},
+    expected: [{_id: 0}, {_id: 1}],
+    expectBlockingSort: true
+});
 
 // Sort key for doc with _id: 0 is {'': 4, '': 7}. Sort key for doc with _id: 1 is {'': 1, '':
 // 7}.
-testAggAndFindSort(
-    {filter: {}, sort: {"x.y": -1, "x.z": 1}, project: {_id: 1}, expected: [{_id: 0}, {_id: 1}]});
+testAggAndFindSort({
+    filter: {},
+    sort: {"x.y": -1, "x.z": 1},
+    project: {_id: 1},
+    expected: [{_id: 0}, {_id: 1}],
+    expectBlockingSort: true
+});
 
 assert.commandWorked(coll.createIndex({"x.y": 1, "x.z": -1}));
 
-// Compound mixed ascending/descending sorts, with an index.
-testAggAndFindSort(
-    {filter: {}, sort: {"x.y": 1, "x.z": -1}, project: {_id: 1}, expected: [{_id: 0}, {_id: 1}]});
+// Compound mixed ascending/descending sorts, with an index. Ascending and Descending sorts in the
+// presence of an index with all fields having [minKey, maxKey] bounds has a non-blocking sort.
+testAggAndFindSort({
+    filter: {},
+    sort: {"x.y": 1, "x.z": -1},
+    project: {_id: 1},
+    expected: [{_id: 0}, {_id: 1}],
+    expectBlockingSort: false
+});
+testAggAndFindSort({
+    filter: {},
+    sort: {"x.y": -1, "x.z": 1},
+    project: {_id: 1},
+    expected: [{_id: 0}, {_id: 1}],
+    expectBlockingSort: false
+});
+// Since there are bounds on "x.y", and since "x.y" shares a prefix with "x.z", this index cannot
+// provide the sort.
+testAggAndFindSort({
+    filter: {"x.y": 1},
+    sort: {"x.z": -1},
+    project: {_id: 1},
+    expected: [{_id: 0}, {_id: 1}],
+    expectBlockingSort: true
+});
+
+// Since there are bounds on "x.y" this index cannot provide the sort.
+testAggAndFindSort({
+    filter: {"x.y": 1},
+    sort: {"x.y": -1},
+    project: {_id: 1},
+    expected: [{_id: 0}, {_id: 1}],
+    expectBlockingSort: true
+});
+
+// Since there are bounds on "x.y" and "x.z", this index cannot provide the sort.
+testAggAndFindSort({
+    filter: {"x.y": 1, "x.z": 1},
+    sort: {"x.y": -1, "x.z": -1},
+    project: {_id: 1},
+    expected: [],
+    expectBlockingSort: true
+});
+
+assert.commandWorked(coll.createIndex({"x.y": 1, "x": -1}));
+
+// Since there are bounds on 'x.y', and since 'x.y' shares a prefix with 'x', the index cannot
+// provide a sort on the multikey field 'x'.
+testAggAndFindSort({
+    filter: {"x.y": 1},
+    sort: {"x": -1},
+    project: {_id: 1},
+    expected: [{_id: 0}, {_id: 1}],
+    expectBlockingSort: true
+});
+
+// Since multikey index,'d', has no shared prefixes with 'e', the index can provide a sort on the
+// multikey field 'e'.
+coll.drop();
+assert.commandWorked(coll.insert({_id: 0, d: 3, e: [1, 2, 3]}));
+assert.commandWorked(coll.insert({_id: 1, d: [0, 4, -1], e: 4}));
+assert.commandWorked(coll.createIndex({d: 1, e: 1}));
 testAggAndFindSort(
-    {filter: {}, sort: {"x.y": -1, "x.z": 1}, project: {_id: 1}, expected: [{_id: 0}, {_id: 1}]});
+    {filter: {d: 1}, sort: {e: 1}, project: {_id: 1}, expected: [], expectBlockingSort: false});
 
 // Test that a multikey index can provide a sort over a non-multikey field.
 coll.drop();
@@ -140,8 +223,13 @@ assert.commandWorked(
 assert.commandWorked(
     coll.insert({_id: 1, a: 2, b: {c: 2}, d: [{e: {f: 2, g: [5, 4, 3]}}, {e: {g: [2, 1, 0]}}]}));
 
-testAggAndFindSort(
-    {filter: {}, sort: {"d.e.g": 1}, project: {_id: 1}, expected: [{_id: 1}, {_id: 0}]});
+testAggAndFindSort({
+    filter: {},
+    sort: {"d.e.g": 1},
+    project: {_id: 1},
+    expected: [{_id: 1}, {_id: 0}],
+    expectBlockingSort: true
+});
 
 // Test a sort over the trailing field of a compound index, where the two fields of the index
 // share a path prefix. This is designed as a regression test for SERVER-31858.
@@ -154,7 +242,8 @@ testAggAndFindSort({
     filter: {"a.b": 1},
     project: {_id: 1},
     sort: {"a.c": 1},
-    expected: [{_id: 0}, {_id: 1}, {_id: 2}]
+    expected: [{_id: 0}, {_id: 1}, {_id: 2}],
+    expectBlockingSort: true
 });
 
 // Test that an indexed and unindexed sort return the same thing for a path "a.x" which
@@ -163,17 +252,28 @@ coll.drop();
 assert.commandWorked(coll.insert({_id: 0, a: [{x: 2}]}));
 assert.commandWorked(coll.insert({_id: 1, a: [{x: 1}]}));
 assert.commandWorked(coll.insert({_id: 2, a: [{x: 3}]}));
-testAggAndFindSort(
-    {filter: {}, project: {_id: 1}, sort: {"a.x": 1}, expected: [{_id: 1}, {_id: 0}, {_id: 2}]});
+testAggAndFindSort({
+    filter: {},
+    project: {_id: 1},
+    sort: {"a.x": 1},
+    expected: [{_id: 1}, {_id: 0}, {_id: 2}],
+    expectBlockingSort: true
+});
 assert.commandWorked(coll.createIndex({"a.x": 1}));
-testAggAndFindSort(
-    {filter: {}, project: {_id: 1}, sort: {"a.x": 1}, expected: [{_id: 1}, {_id: 0}, {_id: 2}]});
+testAggAndFindSort({
+    filter: {},
+    project: {_id: 1},
+    sort: {"a.x": 1},
+    expected: [{_id: 1}, {_id: 0}, {_id: 2}],
+    expectBlockingSort: false
+});
 testAggAndFindSort({
     filter: {},
     project: {_id: 1},
     sort: {"a.x": 1},
     hint: {"a.x": 1},
-    expected: [{_id: 1}, {_id: 0}, {_id: 2}]
+    expected: [{_id: 1}, {_id: 0}, {_id: 2}],
+    expectBlockingSort: false
 });
 
 // Now repeat the test with multiple entries along the path "a.x".
@@ -181,16 +281,28 @@ coll.drop();
 assert.commandWorked(coll.insert({_id: 0, a: [{x: 2}, {x: 3}]}));
 assert.commandWorked(coll.insert({_id: 1, a: [{x: 1}, {x: 4}]}));
 assert.commandWorked(coll.insert({_id: 2, a: [{x: 3}, {x: 4}]}));
-testAggAndFindSort(
-    {filter: {}, project: {_id: 1}, sort: {"a.x": 1}, expected: [{_id: 1}, {_id: 0}, {_id: 2}]});
+testAggAndFindSort({
+    filter: {},
+    project: {_id: 1},
+    sort: {"a.x": 1},
+    expected: [{_id: 1}, {_id: 0}, {_id: 2}],
+    expectBlockingSort: true
+});
 assert.commandWorked(coll.createIndex({"a.x": 1}));
-testAggAndFindSort(
-    {filter: {}, project: {_id: 1}, sort: {"a.x": 1}, expected: [{_id: 1}, {_id: 0}, {_id: 2}]});
+// Sort with an index on "a.x".
+testAggAndFindSort({
+    filter: {},
+    project: {_id: 1},
+    sort: {"a.x": 1},
+    expected: [{_id: 1}, {_id: 0}, {_id: 2}],
+    expectBlockingSort: false
+});
 testAggAndFindSort({
     filter: {},
     project: {_id: 1},
     sort: {"a.x": 1},
     hint: {"a.x": 1},
-    expected: [{_id: 1}, {_id: 0}, {_id: 2}]
+    expected: [{_id: 1}, {_id: 0}, {_id: 2}],
+    expectBlockingSort: false
 });
 }());
diff --git a/src/mongo/db/query/index_bounds.cpp b/src/mongo/db/query/index_bounds.cpp
index bea6a10f75a..fb638d39727 100644
--- a/src/mongo/db/query/index_bounds.cpp
+++ b/src/mongo/db/query/index_bounds.cpp
@@ -240,6 +240,10 @@ Interval::Direction OrderedIntervalList::computeDirection() const {
                    : Interval::Direction::kDirectionDescending;
 }
 
+bool OrderedIntervalList::isMinToMax() const {
+    return intervals.size() == 1 && intervals[0].isMinToMax();
+}
+
 // static
 void OrderedIntervalList::complement() {
     BSONObjBuilder minBob;
diff --git a/src/mongo/db/query/index_bounds.h b/src/mongo/db/query/index_bounds.h
index 513e22335f1..c1964415edd 100644
--- a/src/mongo/db/query/index_bounds.h
+++ b/src/mongo/db/query/index_bounds.h
@@ -84,6 +84,11 @@ struct OrderedIntervalList {
     OrderedIntervalList reverseClone() const;
 
     Interval::Direction computeDirection() const;
+
+    /**
+     * Returns true if this OIL represents a single [MinKey, MaxKey] bound.
+     */
+    bool isMinToMax() const;
 };
 
 /**
diff --git a/src/mongo/db/query/query_planner_array_test.cpp b/src/mongo/db/query/query_planner_array_test.cpp
index 857ef98613b..2e5361a2000 100644
--- a/src/mongo/db/query/query_planner_array_test.cpp
+++ b/src/mongo/db/query/query_planner_array_test.cpp
@@ -2419,6 +2419,71 @@ TEST_F(QueryPlannerTest, CanExplodeMultikeyIndexScanForSortWhenSortFieldsAreNotM
         "bounds: {a: [[2,2,true,true]], 'b.c': [['MinKey','MaxKey',true,true]]}}}]}}}}");
 }
 
+TEST_F(QueryPlannerTest, MultikeyIndexScanWithMinKeyMaxKeyBoundsCanProvideSort) {
+    params.options &= ~QueryPlannerParams::INCLUDE_COLLSCAN;
+    MultikeyPaths multikeyPaths{{0U}};
+    addIndex(BSON("a" << 1), multikeyPaths);
+    runQueryAsCommand(fromjson("{sort: {a: 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1}, bounds: {a: "
+        "[['MinKey','MaxKey',true,true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, MultikeyIndexScanWithBoundsOnIndexWithoutSharedPrefixCanProvideSort) {
+    params.options &= ~QueryPlannerParams::INCLUDE_COLLSCAN;
+    MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQueryAsCommand(fromjson("{filter: {b : {$gte: 3}}, sort: {a: 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: {b: {$gte: 3}}, node: {ixscan: {pattern: {a: 1, b: 1}, bounds: {a: "
+        "[['MinKey','MaxKey',true,true]], b: [['MinKey','MaxKey',true,true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest,
+       MultikeyIndexScanWithBoundsOnIndexWithoutSharedPrefixCanProvideSortDifferentIndex) {
+    params.options &= ~QueryPlannerParams::INCLUDE_COLLSCAN;
+    MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQueryAsCommand(fromjson("{filter: {a : {$eq: 3}}, sort: {b: 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, bounds: {a: "
+        "[[3,3,true,true]], b: [['MinKey','MaxKey',true,true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest,
+       MultikeyIndexScanWithFilterAndSortOnFieldsThatSharePrefixCannotProvideSort) {
+    params.options &= ~QueryPlannerParams::INCLUDE_COLLSCAN;
+    MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("a" << 1 << "a.b" << 1), multikeyPaths);
+    runQueryAsCommand(fromjson("{filter: {a : {$gte: 3}}, sort: {'a.b': 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{sort: {pattern: {'a.b': 1}, limit: 0, node: {sortKeyGen: {node: "
+        "{fetch: {filter: null, node: {ixscan: {pattern: {a: 1, 'a.b': 1}, filter: null, bounds: "
+        "{a: [[3, Infinity, true,true]], 'a.b': [['MinKey','MaxKey',true,true]]}}}}}}}}}");
+}
+
+TEST_F(QueryPlannerTest,
+       MultikeyIndexScanWithFilterAndSortOnFieldsThatSharePrefixCannotProvideSortDifferentIndex) {
+    params.options &= ~QueryPlannerParams::INCLUDE_COLLSCAN;
+    MultikeyPaths multikeyPaths{{0U, 1U}, {0U}};
+    addIndex(BSON("a.b" << 1 << "a" << 1), multikeyPaths);
+    runQueryAsCommand(fromjson("{filter: {'a.b' : {$gte: 3}}, sort: {a: 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{sort: {pattern: {a: 1}, limit: 0, node: {sortKeyGen: {node: "
+        "{fetch: {filter: null, node: {ixscan: {pattern: {'a.b': 1, a: 1}, filter: null, bounds: "
+        "{'a.b': [[3, Infinity, true,true]], a: [['MinKey','MaxKey',true,true]]}}}}}}}}}");
+}
+
 TEST_F(QueryPlannerTest, ElemMatchValueNENull) {
     addIndex(BSON("a" << 1));
     runQuery(fromjson("{a: {$elemMatch: {$ne: null}}}"));
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index 319c498f77e..eef289d4d7a 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -37,6 +37,7 @@
 #include "mongo/bson/bsontypes.h"
 #include "mongo/bson/mutable/document.h"
 #include "mongo/bson/simple_bsonelement_comparator.h"
+#include "mongo/db/field_ref.h"
 #include "mongo/db/index_names.h"
 #include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/query/collation/collation_index_key.h"
@@ -696,6 +697,70 @@ std::set<StringData> getMultikeyFields(const BSONObj& keyPattern,
     return multikeyFields;
 }
 
+/**
+ * Returns true if the index scan described by 'multikeyFields' and 'bounds' can legally provide the
+ * 'sortSpec', or false if the sort cannot be provided. A multikey index cannot provide a sort if
+ * either of the following is true: 1) the sort spec includes a multikey field that has bounds other
+ * than [minKey, maxKey], 2) there are bounds other than [minKey, maxKey] over a multikey field
+ * which share a path prefix with a component of the sort pattern. These cases are further explained
+ * in SERVER-31898.
+ */
+bool confirmBoundsProvideSortGivenMultikeyness(const BSONObj& sortSpec,
+                                               const IndexBounds& bounds,
+                                               const std::set<StringData>& multikeyFields) {
+    // Forwardize the bounds to correctly apply checks to descending sorts and well as ascending
+    // sorts.
+    const auto ascendingBounds = bounds.forwardize();
+    const auto& fields = ascendingBounds.fields;
+    for (auto&& sortPatternComponent : sortSpec) {
+        if (multikeyFields.count(sortPatternComponent.fieldNameStringData()) == 0) {
+            // If this component of the sort pattern (which must be one of the components of
+            // the index spec) is not multikey, we don't need additional checks.
+            continue;
+        }
+
+        // Bail out if the bounds are specified as a simple range. As a future improvement, we could
+        // extend this optimization to allow simple multikey scans to provide a sort.
+        if (ascendingBounds.isSimpleRange) {
+            return false;
+        }
+
+        // Checks if the current 'sortPatternComponent' has [MinKey, MaxKey].
+        const auto name = sortPatternComponent.fieldNameStringData();
+        for (auto&& intervalList : fields) {
+            if (name == intervalList.name && !intervalList.isMinToMax()) {
+                return false;
+            }
+        }
+
+        // Checks if there is a shared path prefix between the bounds and the sort pattern of
+        // multikey fields.
+        FieldRef refName(name);
+        for (const auto& intervalList : fields) {
+            // Ignores the prefix if the bounds are [MinKey, MaxKey] or if the field is not
+            // multikey.
+            if (intervalList.isMinToMax() ||
+                (multikeyFields.find(intervalList.name) == multikeyFields.end())) {
+                continue;
+            }
+
+            FieldRef boundsPath(intervalList.name);
+            const auto commonPrefixSize = boundsPath.commonPrefixSize(refName);
+            // The interval list name and the sort pattern name will never be equal at this point.
+            // This is because if they are equal and do not have [minKey, maxKey] bounds, we would
+            // already have bailed out of the function. If they do have [minKey, maxKey] bounds,
+            // they will be skipped in the check for [minKey, maxKey] bounds above.
+            invariant(refName != boundsPath);
+            // Checks if there's a common prefix between the interval list name and the sort pattern
+            // name.
+            if (commonPrefixSize > 0) {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
 
 /**
  * Populates 'sortsOut' with the sort orders provided by an index scan over 'index', with the given
@@ -816,22 +881,14 @@ void computeSortsForScan(const IndexEntry& index,
         }
     }
 
-    // We cannot provide a sort which involves a multikey field. Prune such sort orders, if the
-    // index is multikey.
     if (index.multikey) {
         for (auto sortsIt = sortsOut->begin(); sortsIt != sortsOut->end();) {
-            bool foundMultikeyField = false;
-            for (auto&& elt : *sortsIt) {
-                if (multikeyFields.find(elt.fieldNameStringData()) != multikeyFields.end()) {
-                    foundMultikeyField = true;
-                    break;
-                }
-            }
-
-            if (foundMultikeyField) {
-                sortsIt = sortsOut->erase(sortsIt);
-            } else {
+            // Erase this sort from 'sortsOut' if it is not compatible with multikey fields in the
+            // index.
+            if (confirmBoundsProvideSortGivenMultikeyness(*sortsIt, bounds, multikeyFields)) {
                 ++sortsIt;
+            } else {
+                sortsIt = sortsOut->erase(sortsIt);
             }
         }
     }
diff --git a/src/mongo/db/query/query_solution_test.cpp b/src/mongo/db/query/query_solution_test.cpp
index 5ec327bec97..97b14fec0ce 100644
--- a/src/mongo/db/query/query_solution_test.cpp
+++ b/src/mongo/db/query/query_solution_test.cpp
@@ -943,7 +943,6 @@ TEST(QuerySolutionTest, NonSimpleRangeAllEqualExcludesFieldWithMultikeyComponent
     }
 
     node.computeProperties();
-
     ASSERT_EQUALS(node.getSort().size(), 4U);
     ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1)));
     ASSERT(node.getSort().count(BSON("a" << 1)));
@@ -951,4 +950,26 @@ TEST(QuerySolutionTest, NonSimpleRangeAllEqualExcludesFieldWithMultikeyComponent
     ASSERT(node.getSort().count(BSON("e" << 1)));
 }
 
+TEST(QuerySolutionTest, SharedPrefixMultikeyNonMinMaxBoundsDoesNotProvideAnySorts) {
+    IndexScanNode node{buildSimpleIndexEntry(BSON("c.x" << 1 << "c.z" << 1))};
+
+    node.index.multikey = true;
+    node.index.multikeyPaths = MultikeyPaths{{1U}, {1U}};
+
+    {
+        OrderedIntervalList oil{};
+        oil.name = "c.x";
+        oil.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1)));
+        node.bounds.fields.push_back(oil);
+    }
+    {
+        OrderedIntervalList oil{};
+        oil.name = "c.z";
+        oil.intervals.push_back(IndexBoundsBuilder::allValues());
+        node.bounds.fields.push_back(oil);
+    }
+
+    node.computeProperties();
+    ASSERT_EQUALS(node.getSort().size(), 0U);
+}
 }  // namespace