SERVER-51718 Disallow sparse, hashed indexes from being considered for answering $exists: false queries

(cherry picked from commit daa74ba2f414534e736f408b40d62aef869b06cc)

4 files changed, 119 insertions, 42 deletions

diff --git a/jstests/core/hashed_partial_and_sparse_index.js b/jstests/core/hashed_partial_and_sparse_index.js
index d42ddfc8f86..2bba4787a36 100644
--- a/jstests/core/hashed_partial_and_sparse_index.js
+++ b/jstests/core/hashed_partial_and_sparse_index.js
@@ -36,24 +36,45 @@ function validateFindCmdOutputAndPlan({filter, expectedStages, expectedOutput})
     assertStagesForExplainOfCommand({coll: coll, cmdObj: cmdObj, expectedStages: expectedStages});
 }
 
-/**
- * Tests for sparse indexes.
- */
-assert.commandWorked(coll.createIndex({a: 1, b: "hashed", c: -1}, {sparse: true}));
+function testSparseHashedIndex(indexSpec) {
+    assert.commandWorked(coll.dropIndexes());
+    assert.commandWorked(coll.createIndex(indexSpec, {sparse: true}));
 
-// Verify index not used for null/missing queries with sparse index.
-validateFindCmdOutputAndPlan({filter: {a: null}, expectedStages: ["COLLSCAN"]});
-validateFindCmdOutputAndPlan({filter: {a: {$exists: false}}, expectedStages: ["COLLSCAN"]});
+    // Verify index not used for null/missing queries with sparse index.
+    validateFindCmdOutputAndPlan({filter: {a: null}, expectedStages: ["COLLSCAN"]});
+    validateFindCmdOutputAndPlan({filter: {a: {$exists: false}}, expectedStages: ["COLLSCAN"]});
 
-// Verify index can be used for non-null queries with sparse index.
-validateFindCmdOutputAndPlan({
-    filter: {a: {$exists: true}},
-    expectedOutput: [{a: null}, {a: 1}, {a: 1, b: 6}],
-    expectedStages: ["IXSCAN", "FETCH"]
-});
+    // Verify index can be used for non-null queries with sparse index.
+    validateFindCmdOutputAndPlan({
+        filter: {a: {$exists: true}},
+        expectedOutput: [{a: null}, {a: 1}, {a: 1, b: 6}],
+        expectedStages: ["IXSCAN", "FETCH"]
+    });
+
+    validateFindCmdOutputAndPlan({
+        filter: {a: 1, b: 6},
+        expectedOutput: [{a: 1, b: 6}],
+        expectedStages: ["IXSCAN", "FETCH"]
+    });
+
+    // Test {$exists: false} when hashed field is not a prefix and index is sparse.
+    validateFindCmdOutputAndPlan({
+        filter: {a: {$exists: false}},
+        expectedOutput: [{b: 4}, {}],
+        expectedStages: ["COLLSCAN"],
+        stagesNotExpected: ["IXSCAN"]
+    });
+}
+
+/**
+ * Tests sparse indexes with non-hashed prefix.
+ */
+testSparseHashedIndex({a: 1, b: "hashed", c: -1});
 
-validateFindCmdOutputAndPlan(
-    {filter: {a: 1, b: 6}, expectedOutput: [{a: 1, b: 6}], expectedStages: ["IXSCAN", "FETCH"]});
+/**
+ * Test sparse indexes with hashed prefix.
+ */
+testSparseHashedIndex({a: "hashed", b: 1});
 
 /**
  * Tests for partial indexes.
@@ -70,4 +91,4 @@ validateFindCmdOutputAndPlan(
     validateFindCmdOutputAndPlan(
         {filter: {b: 6}, expectedOutput: [{a: 1, b: 6}], expectedStages: ["IXSCAN", "FETCH"]});
 });
-})();
\ No newline at end of file
+})();
diff --git a/jstests/core/single_field_hashed_index.js b/jstests/core/single_field_hashed_index.js
index 6f4fa090aea..af1067d5e2a 100644
--- a/jstests/core/single_field_hashed_index.js
+++ b/jstests/core/single_field_hashed_index.js
@@ -2,7 +2,11 @@
  * Tests the basic behaviours and properties of single-field hashed indexes.
  * Cannot implicitly shard accessed collections because of extra shard key index in sharded
  * collection.
- * @tags: [assumes_no_implicit_index_creation, requires_fastcount]
+ * @tags: [
+ *   assumes_no_implicit_index_creation,
+ *   requires_fastcount,
+ *   requires_fcv_44,
+ * ]
  */
 (function() {
 "use strict";
@@ -62,6 +66,10 @@ assert(isIxscan(db, explain.queryPlanner.winningPlan), "not using hashed index")
 explain = t.find({$and: [{a: {$in: [1, 2]}}, {a: {$gt: 1}}]}).explain();
 assert(isIxscan(db, explain.queryPlanner.winningPlan), "not using hashed index");
 
+// Non-sparse hashed index can be used to satisfy {$exists: false}.
+explain = t.find({a: {$exists: false}}).explain();
+assert(isIxscan(db, explain.queryPlanner.winningPlan), explain);
+
 // Test creation of index based on hash of _id index.
 const indexSpec2 = {
     '_id': "hashed"
@@ -81,6 +89,10 @@ const sparseIndex = {
 assert.commandWorked(t.createIndex(sparseIndex, {"sparse": true}));
 assert.eq(t.getIndexes().length, 4, "sparse index didn't get created");
 
+// Sparse hashed indexes cannot be used to satisfy {$exists: false}.
+explain = t.find({b: {$exists: false}}).explain();
+assert(!isIxscan(db, explain.queryPlanner.winningPlan), explain);
+
 // Test sparse index has smaller total items on after inserts.
 for (let i = 0; i < 10; i++) {
     assert.commandWorked(t.insert({b: i}));
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index ab23b567ad8..1444ac64dda 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -422,26 +422,11 @@ bool QueryPlannerIXSelect::_compatible(const BSONElement& keyPatternElt,
                 return false;
             }
 
+            // The type being INDEX_WILDCARD implies that the index is sparse.
+            invariant(index.sparse || index.type != INDEX_WILDCARD);
+
             const auto* child = node->getChild(0);
             const MatchExpression::MatchType childtype = child->matchType();
-            const bool isNotEqualsNull =
-                (childtype == MatchExpression::EQ &&
-                 static_cast<const ComparisonMatchExpression*>(child)->getData().type() ==
-                     BSONType::jstNULL);
-
-            // The type being INDEX_WILDCARD implies that the index is sparse.
-            invariant(!(index.type == INDEX_WILDCARD && !index.sparse));
-
-            // Prevent negated predicates from using sparse indices. Doing so would cause us to
-            // miss documents which do not contain the indexed fields. The only case where we may
-            // use a sparse index for a negation is when the query is {$ne: null}. This is due to
-            // the behavior of {$eq: null} matching documents where the field does not exist OR the
-            // field is equal to literal null. The negation of {$eq: null} therefore matches
-            // documents where the field does exist AND the field is not equal to literal
-            // null. Since the field must exist, it is safe to use a sparse index.
-            if (index.sparse && !isNotEqualsNull) {
-                return false;
-            }
 
             // Can't index negations of MOD, REGEX, TYPE_OPERATOR, or ELEM_MATCH_VALUE.
             if (MatchExpression::REGEX == childtype || MatchExpression::MOD == childtype ||
@@ -456,6 +441,10 @@ bool QueryPlannerIXSelect::_compatible(const BSONElement& keyPatternElt,
 
             // Most of the time we can't use a multikey index for a $ne: null query, however there
             // are a few exceptions around $elemMatch.
+            const bool isNotEqualsNull =
+                (childtype == MatchExpression::EQ &&
+                 static_cast<const ComparisonMatchExpression*>(child)->getData().type() ==
+                     BSONType::jstNULL);
             const bool canUseIndexForNeNull =
                 notEqualsNullCanUseIndex(index, keyPatternElt, keyPatternIdx, elemMatchContext);
             if (isNotEqualsNull && !canUseIndexForNeNull) {
@@ -541,6 +530,10 @@ bool QueryPlannerIXSelect::_compatible(const BSONElement& keyPatternElt,
         // above.
         MONGO_UNREACHABLE;
     } else if (IndexNames::HASHED == indexedFieldType) {
+        if (index.sparse && !nodeIsSupportedBySparseIndex(node, isChildOfElemMatchValue)) {
+            return false;
+        }
+
         return nodeIsSupportedByHashedIndex(node);
     } else if (IndexNames::GEO_2DSPHERE == indexedFieldType) {
         if (exprtype == MatchExpression::GEO) {
@@ -611,11 +604,6 @@ bool QueryPlannerIXSelect::nodeIsSupportedBySparseIndex(const MatchExpression* q
     // cannot answer), so this function only needs to check if the query performs an equality to
     // null.
 
-    // Equality to null inside an $elemMatch implies a match on literal 'null'.
-    if (isInElemMatch) {
-        return true;
-    }
-
     // Otherwise, we can't use a sparse index for $eq (or $lte, or $gte) with a null element.
     //
     // We can use a sparse index for $_internalExprEq with a null element. Expression language
@@ -624,10 +612,30 @@ bool QueryPlannerIXSelect::nodeIsSupportedBySparseIndex(const MatchExpression* q
     const auto typ = queryExpr->matchType();
     if (typ == MatchExpression::EQ) {
         const auto* queryExprEquality = static_cast<const EqualityMatchExpression*>(queryExpr);
-        return !queryExprEquality->getData().isNull();
+        // Equality to null inside an $elemMatch implies a match on literal 'null'.
+        return isInElemMatch || !queryExprEquality->getData().isNull();
     } else if (queryExpr->matchType() == MatchExpression::MATCH_IN) {
         const auto* queryExprIn = static_cast<const InMatchExpression*>(queryExpr);
-        return !queryExprIn->hasNull();
+        // Equality to null inside an $elemMatch implies a match on literal 'null'.
+        return isInElemMatch || !queryExprIn->hasNull();
+    } else if (queryExpr->matchType() == MatchExpression::NOT) {
+        const auto* child = queryExpr->getChild(0);
+        const MatchExpression::MatchType childtype = child->matchType();
+        const bool isNotEqualsNull =
+            (childtype == MatchExpression::EQ &&
+             static_cast<const ComparisonMatchExpression*>(child)->getData().type() ==
+                 BSONType::jstNULL);
+
+        // Prevent negated predicates from using sparse indices. Doing so would cause us to
+        // miss documents which do not contain the indexed fields. The only case where we may
+        // use a sparse index for a negation is when the query is {$ne: null}. This is due to
+        // the behavior of {$eq: null} matching documents where the field does not exist OR the
+        // field is equal to literal null. The negation of {$eq: null} therefore matches
+        // documents where the field does exist AND the field is not equal to literal
+        // null. Since the field must exist, it is safe to use a sparse index.
+        if (!isNotEqualsNull) {
+            return false;
+        }
     }
 
     return true;
diff --git a/src/mongo/db/query/planner_ixselect_test.cpp b/src/mongo/db/query/planner_ixselect_test.cpp
index 84ba3f704d0..53848037cf3 100644
--- a/src/mongo/db/query/planner_ixselect_test.cpp
+++ b/src/mongo/db/query/planner_ixselect_test.cpp
@@ -1291,6 +1291,42 @@ TEST(QueryPlannerIXSelectTest, HashedIndexShouldNotBeRelevantForNotEqualsNullPre
     testRateIndices("{a: {$ne: null}}", "", kSimpleCollator, {entry}, "a,a", expectedIndices);
 }
 
+TEST(QueryPlannerIXSelectTest, HashedSparseIndexShouldNotBeRelevantForExistsFalse) {
+    auto entry = buildSimpleIndexEntry(BSON("a"
+                                            << "hashed"));
+    entry.type = IndexType::INDEX_HASHED;
+    entry.sparse = true;
+    std::set<size_t> expectedIndices = {};
+    testRateIndices("{a: {$exists: false}}", "", kSimpleCollator, {entry}, "a,a", expectedIndices);
+}
+
+TEST(QueryPlannerIXSelectTest, HashedSparseIndexShouldNotBeRelevantForEqualsNull) {
+    auto entry = buildSimpleIndexEntry(BSON("a"
+                                            << "hashed"));
+    entry.type = IndexType::INDEX_HASHED;
+    entry.sparse = true;
+    std::set<size_t> expectedIndices = {};
+    testRateIndices("{a: {$eq: null}}", "", kSimpleCollator, {entry}, "a", expectedIndices);
+}
+
+TEST(QueryPlannerIXSelectTest, HashedNonSparseIndexShouldBeRelevantForExistsFalse) {
+    auto entry = buildSimpleIndexEntry(BSON("a"
+                                            << "hashed"));
+    entry.type = IndexType::INDEX_HASHED;
+    entry.sparse = false;
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$exists: false}}", "", kSimpleCollator, {entry}, "a,a", expectedIndices);
+}
+
+TEST(QueryPlannerIXSelectTest, HashedSparseIndexShouldBeRelevantForExistsTrue) {
+    auto entry = buildSimpleIndexEntry(BSON("a"
+                                            << "hashed"));
+    entry.type = IndexType::INDEX_HASHED;
+    entry.sparse = true;
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$exists: true}}", "", kSimpleCollator, {entry}, "a", expectedIndices);
+}
+
 /*
  * Will compare 'keyPatterns' with 'entries'. As part of comparing, it will sort both of them.
  */