SERVER-3173 use path-level multikey metadata to generate covered plans if possible

This allows queries using a multikey index which project out
the array fields to avoid collection access.

3 files changed, 114 insertions, 6 deletions

diff --git a/src/mongo/db/query/query_planner_array_test.cpp b/src/mongo/db/query/query_planner_array_test.cpp
index 3bc52263b13..0cd00755d52 100644
--- a/src/mongo/db/query/query_planner_array_test.cpp
+++ b/src/mongo/db/query/query_planner_array_test.cpp
@@ -1413,4 +1413,44 @@ TEST_F(QueryPlannerTest, CannotCompoundBoundsWhenSharedPrefixInsideElemMatchIsMu
         "bounds: {'a.b.c': [[2, 2, true, true]], 'a.b.d': [['MinKey', 'MaxKey', true, true]]}}}}}");
 }
 
+TEST_F(QueryPlannerTest, CanMakeCoveredPlanForNonArrayLeadingFieldWithPathLevelMultikeyInfo) {
+    MultikeyPaths multikeyPaths{{}, {0U}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQueryAsCommand(
+        fromjson("{find: 'testns', filter: {a: 1, b: 2}, projection: {_id: 0, a: 1}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{proj: {spec: {_id: 0, a: 1}, node: {cscan: {dir: 1}}}}");
+    assertSolutionExists(
+        "{proj: {spec: {_id: 0, a: 1}, node: {ixscan: {pattern: {a: 1, b: 1},"
+        "filter: null, bounds: {a: [[1,1,true,true]], b: [[2,2,true,true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanMakeCoveredPlanForNonArrayTrailingFieldWithPathLevelMultikeyInfo) {
+    MultikeyPaths multikeyPaths{{1U}, {}, {1U}};
+    addIndex(BSON("a.z" << 1 << "b" << 1 << "c.z" << 1), multikeyPaths);
+    runQueryAsCommand(fromjson(
+        "{find: 'testns', filter: {'a.z': 1, 'c.z': 2, b: 3}, projection: {_id: 0, b: 1}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{proj: {spec: {_id: 0, b: 1}, node: {cscan: {dir: 1}}}}");
+    assertSolutionExists(
+        "{proj: {spec: {_id:0,b:1}, node: {ixscan: {pattern: {'a.z':1,b:1,'c.z':1}, filter: null,"
+        "bounds: {'a.z':[[1,1,true,true]],b:[[3,3,true,true]],'c.z':[[2,2,true,true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CannotCoverNonMultikeyDottedField) {
+    MultikeyPaths multikeyPaths{{}, {0U}};
+    addIndex(BSON("a.y" << 1 << "b.z" << 1), multikeyPaths);
+    runQueryAsCommand(
+        fromjson("{find: 'testns', filter: {'a.y': 1, 'b.z': 2}, projection: {_id: 0, 'a.y': 1}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{proj: {spec: {_id:0,'a.y':1}, node: {cscan: {dir: 1}}}}");
+    assertSolutionExists(
+        "{proj: {spec: {_id:0,'a.y':1}, node: {fetch: {filter: null, node: {ixscan:"
+        "{pattern: {'a.y':1,'b.z':1}, filter: null,"
+        "bounds: {'a.y':[[1,1,true,true]],'b.z':[[2,2,true,true]]}}}}}}}");
+}
+
 }  // namespace
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index aa2426954c4..191924eda68 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -538,9 +538,9 @@ void IndexScanNode::appendToString(mongoutils::str::stream* ss, int indent) cons
 }
 
 bool IndexScanNode::hasField(const string& field) const {
-    // There is no covering in a multikey index because you don't know whether or not the field
-    // in the key was extracted from an array in the original document.
-    if (index.multikey) {
+    // The index is multikey but does not have any path-level multikeyness information. Such indexes
+    // can never provide covering.
+    if (index.multikey && index.multikeyPaths.empty()) {
         return false;
     }
 
@@ -559,11 +559,17 @@ bool IndexScanNode::hasField(const string& field) const {
         }
     }
 
-    BSONObjIterator it(index.keyPattern);
-    while (it.more()) {
-        if (field == it.next().fieldName()) {
+    size_t keyPatternFieldIndex = 0;
+    for (auto&& elt : index.keyPattern) {
+        // The index can provide this field if the requested path appears in the index key pattern,
+        // and that path has no multikey components. We can't cover a field that has multikey
+        // components because the index keys contain individual array elements, and we can't
+        // reconstitute the array from the index keys in the right order.
+        if (field == elt.fieldName() &&
+            (!index.multikey || index.multikeyPaths[keyPatternFieldIndex].empty())) {
             return true;
         }
+        ++keyPatternFieldIndex;
     }
     return false;
 }
diff --git a/src/mongo/db/query/query_solution_test.cpp b/src/mongo/db/query/query_solution_test.cpp
index b1f8bc18e4b..fe9749d49c3 100644
--- a/src/mongo/db/query/query_solution_test.cpp
+++ b/src/mongo/db/query/query_solution_test.cpp
@@ -768,4 +768,66 @@ TEST(QuerySolutionTest, ExclusionProjectionTruncatesSort) {
     ASSERT(proj.getSort().count(BSON("a" << 1)));
 }
 
+TEST(QuerySolutionTest, NonMultikeyIndexWithoutPathLevelInfoCanCoverItsFields) {
+    auto node = stdx::make_unique<IndexScanNode>(IndexEntry(BSON("a" << 1 << "b.c.d" << 1)));
+    node->index.multikey = false;
+    node->index.multikeyPaths = MultikeyPaths{};
+    ASSERT_TRUE(node->hasField("a"));
+    ASSERT_TRUE(node->hasField("b.c.d"));
+    ASSERT_FALSE(node->hasField("b.c"));
+    ASSERT_FALSE(node->hasField("b"));
+    ASSERT_FALSE(node->hasField("e"));
+}
+
+TEST(QuerySolutionTest, NonMultikeyIndexWithPathLevelInfoCanCoverItsFields) {
+    auto node = stdx::make_unique<IndexScanNode>(IndexEntry(BSON("a" << 1 << "b.c.d" << 1)));
+    node->index.multikey = false;
+    node->index.multikeyPaths = MultikeyPaths{{}, {}};
+    ASSERT_TRUE(node->hasField("a"));
+    ASSERT_TRUE(node->hasField("b.c.d"));
+    ASSERT_FALSE(node->hasField("b.c"));
+    ASSERT_FALSE(node->hasField("b"));
+    ASSERT_FALSE(node->hasField("e"));
+}
+
+TEST(QuerySolutionTest, MultikeyIndexWithoutPathLevelInfoCannotCoverAnyFields) {
+    auto node = stdx::make_unique<IndexScanNode>(IndexEntry(BSON("a" << 1 << "b.c.d" << 1)));
+    node->index.multikey = true;
+    node->index.multikeyPaths = MultikeyPaths{};
+    ASSERT_FALSE(node->hasField("a"));
+    ASSERT_FALSE(node->hasField("b.c.d"));
+    ASSERT_FALSE(node->hasField("b.c"));
+    ASSERT_FALSE(node->hasField("b"));
+    ASSERT_FALSE(node->hasField("e"));
+}
+
+TEST(QuerySolutionTest, MultikeyIndexWithPathLevelInfoCanCoverNonMultikeyFields) {
+    auto node =
+        stdx::make_unique<IndexScanNode>(IndexEntry(BSON("a" << 1 << "b" << 1 << "c" << 1)));
+
+    // Add metadata indicating that "b" is multikey.
+    node->index.multikey = true;
+    node->index.multikeyPaths = MultikeyPaths{{}, {0U}, {}};
+
+    ASSERT_TRUE(node->hasField("a"));
+    ASSERT_FALSE(node->hasField("b"));
+    ASSERT_FALSE(node->hasField("b.c"));
+    ASSERT_TRUE(node->hasField("c"));
+}
+
+TEST(QuerySolutionTest, MultikeyIndexCannotCoverFieldWithAnyMultikeyPathComponent) {
+    auto node =
+        stdx::make_unique<IndexScanNode>(IndexEntry(BSON("a" << 1 << "b.c.d" << 1 << "e" << 1)));
+
+    // Add metadata indicating that "b.c" is multikey.
+    node->index.multikey = true;
+    node->index.multikeyPaths = MultikeyPaths{{}, {1U}, {}};
+
+    ASSERT_TRUE(node->hasField("a"));
+    ASSERT_FALSE(node->hasField("b"));
+    ASSERT_FALSE(node->hasField("b.c"));
+    ASSERT_FALSE(node->hasField("b.c.d"));
+    ASSERT_TRUE(node->hasField("e"));
+}
+
 }  // namespace