SERVER-19402 Change find command semantics for sorting on an array field.

This eliminates the behavior in which the lowest-valued
in-bounds index key was chosen as the sort key. After this
change, we instead choose the lowest key overall, which may
or may not be in-bounds. This change prevents the sort order
from depending on either the query predicate or the
implementation details of the query planner.

Note that it is no longer correct for a multikey index to
provide a sort over an array field. However, a non-array
field of a multikey index can provide a sort when that index
has path-level multikeyness metadata.

1 files changed, 66 insertions, 0 deletions

diff --git a/src/mongo/db/query/query_solution_test.cpp b/src/mongo/db/query/query_solution_test.cpp
index fe9749d49c3..a3a76deaa43 100644
--- a/src/mongo/db/query/query_solution_test.cpp
+++ b/src/mongo/db/query/query_solution_test.cpp
@@ -830,4 +830,70 @@ TEST(QuerySolutionTest, MultikeyIndexCannotCoverFieldWithAnyMultikeyPathComponen
     ASSERT_TRUE(node->hasField("e"));
 }
 
+TEST(QuerySolutionTest, MultikeyIndexWithoutPathLevelInfoCannotProvideAnySorts) {
+    IndexScanNode node{IndexEntry(BSON("a" << 1 << "b" << 1 << "c" << 1))};
+    node.index.multikey = true;
+
+    {
+        OrderedIntervalList oil{};
+        oil.name = "a";
+        oil.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1)));
+        node.bounds.fields.push_back(oil);
+    }
+
+    for (auto&& name : {"b"_sd, "c"_sd}) {
+        OrderedIntervalList oil{};
+        oil.name = name.toString();
+        oil.intervals.push_back(IndexBoundsBuilder::makeRangeInterval(
+            BSON("" << 1 << "" << 2), BoundInclusion::kIncludeBothStartAndEndKeys));
+        node.bounds.fields.push_back(oil);
+    }
+
+    node.computeProperties();
+    ASSERT(node.getSort().empty());
+}
+
+TEST(QuerySolutionTest, SimpleRangeAllEqualExcludesFieldWithMultikeyComponent) {
+    IndexScanNode node{
+        IndexEntry(BSON("a" << 1 << "b" << 1 << "c.z" << 1 << "d" << 1 << "e" << 1))};
+    node.bounds.isSimpleRange = true;
+    node.bounds.startKey = BSON("a" << 1 << "b" << 1 << "c.z" << 1 << "d" << 1 << "e" << 1);
+    node.bounds.endKey = BSON("a" << 1 << "b" << 1 << "c.z" << 1 << "d" << 1 << "e" << 1);
+
+    // Add metadata indicating that "c.z" is multikey.
+    node.index.multikey = true;
+    node.index.multikeyPaths = MultikeyPaths{{}, {}, {1U}, {}, {}};
+
+    node.computeProperties();
+
+    ASSERT_EQUALS(node.getSort().size(), 4U);
+    ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1)));
+    ASSERT(node.getSort().count(BSON("a" << 1)));
+    ASSERT(node.getSort().count(BSON("d" << 1 << "e" << 1)));
+    ASSERT(node.getSort().count(BSON("e" << 1)));
+}
+
+TEST(QuerySolutionTest, NonSimpleRangeAllEqualExcludesFieldWithMultikeyComponent) {
+    IndexScanNode node{
+        IndexEntry(BSON("a" << 1 << "b" << 1 << "c.z" << 1 << "d" << 1 << "e" << 1))};
+    // Add metadata indicating that "c.z" is multikey.
+    node.index.multikey = true;
+    node.index.multikeyPaths = MultikeyPaths{{}, {}, {1U}, {}, {}};
+
+    for (auto&& name : {"a"_sd, "b"_sd, "c.z"_sd, "d"_sd, "e"_sd}) {
+        OrderedIntervalList oil{};
+        oil.name = name.toString();
+        oil.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1)));
+        node.bounds.fields.push_back(oil);
+    }
+
+    node.computeProperties();
+
+    ASSERT_EQUALS(node.getSort().size(), 4U);
+    ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1)));
+    ASSERT(node.getSort().count(BSON("a" << 1)));
+    ASSERT(node.getSort().count(BSON("d" << 1 << "e" << 1)));
+    ASSERT(node.getSort().count(BSON("e" << 1)));
+}
+
 }  // namespace