SERVER-52618

3 files changed, 147 insertions, 7 deletions

diff --git a/jstests/core/hashed_partial_and_sparse_index.js b/jstests/core/hashed_partial_and_sparse_index.js
new file mode 100644
index 00000000000..2e412ce1b0c
--- /dev/null
+++ b/jstests/core/hashed_partial_and_sparse_index.js
@@ -0,0 +1,93 @@
+/**
+ * Tests to verify that the queries return correct results in the presence of partial hashed
+ * index and sparse index.
+ * @tags: [
+ *   requires_fcv_42,
+ * ]
+ */
+(function() {
+"use strict";
+
+load("jstests/aggregation/extras/utils.js");  // For arrayEq().
+load("jstests/libs/analyze_plan.js");         // For assertStagesForExplainOfCommand().
+
+const coll = db.hashed_partial_index;
+coll.drop();
+assert.commandWorked(coll.insert({}));
+assert.commandWorked(coll.insert({a: null}));
+assert.commandWorked(coll.insert({a: 1}));
+assert.commandWorked(coll.insert({b: 4}));
+assert.commandWorked(coll.insert({a: 1, b: 6}));
+
+/**
+ * Runs explain() operation on 'cmdObj' and verifies that all the stages in 'expectedStages' are
+ * present exactly once in the plan returned. When 'stagesNotExpected' array is passed, also
+ * verifies that none of those stages are present in the explain() plan.
+ */
+function assertStagesForExplainOfCommand({coll, cmdObj, expectedStages, stagesNotExpected}) {
+    const plan = assert.commandWorked(coll.runCommand({explain: cmdObj}));
+    const winningPlan = plan.queryPlanner.winningPlan;
+    for (let expectedStage of expectedStages) {
+        assert(planHasStage(coll.getDB(), winningPlan, expectedStage),
+               "Could not find stage " + expectedStage + ". Plan: " + tojson(plan));
+    }
+    for (let stage of (stagesNotExpected || [])) {
+        assert(!planHasStage(coll.getDB(), winningPlan, stage),
+               "Found stage " + stage + " when not expected. Plan: " + tojson(plan));
+    }
+    return plan;
+}
+
+/**
+ * Runs find command with the 'filter' and validates that the output returned matches
+ * 'expectedOutput'. Also runs explain() command on the same find command and validates that all
+ * the 'expectedStages' are present in the plan returned.
+ */
+function validateFindCmdOutputAndPlan({filter, expectedStages, expectedOutput}) {
+    const cmdObj = {find: coll.getName(), filter: filter, projection: {_id: 0}};
+    if (expectedOutput) {
+        const res = assert.commandWorked(coll.runCommand(cmdObj));
+        const ouputArray = new DBCommandCursor(coll.getDB(), res).toArray();
+
+        // We ignore the order since hashed index order is not predictable.
+        assert(arrayEq(expectedOutput, ouputArray), ouputArray);
+    }
+    assertStagesForExplainOfCommand({coll: coll, cmdObj: cmdObj, expectedStages: expectedStages});
+}
+
+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"]});
+
+    // 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"]
+    });
+}
+
+/**
+ * Test sparse indexes with hashed prefix.
+ */
+testSparseHashedIndex({a: "hashed"});
+
+/**
+ * Tests for partial indexes.
+ */
+assert.commandWorked(coll.dropIndexes());
+assert.commandWorked(coll.createIndex({b: "hashed"}, {partialFilterExpression: {b: {$gt: 5}}}));
+
+// Verify that index is not used if the query predicate doesn't match the
+// 'partialFilterExpression'.
+validateFindCmdOutputAndPlan({filter: {b: 4}, expectedStages: ["COLLSCAN"]});
+
+// Verify that index is used if the query predicate matches the 'partialFilterExpression'.
+validateFindCmdOutputAndPlan(
+    {filter: {b: 6}, expectedOutput: [{a: 1, b: 6}], expectedStages: ["IXSCAN", "FETCH"]});
+})();
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index 685e1485cc9..60e83488d8a 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -526,6 +526,10 @@ bool QueryPlannerIXSelect::_compatible(const BSONElement& keyPatternElt,
         // above.
         MONGO_UNREACHABLE;
     } else if (IndexNames::HASHED == indexedFieldType) {
+        if (index.sparse && !nodeIsSupportedBySparseIndex(node, isChildOfElemMatchValue)) {
+            return false;
+        }
+
         if (ComparisonMatchExpressionBase::isEquality(exprtype)) {
             return true;
         }
@@ -600,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
@@ -613,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 e1018a87944..cf30e1fc452 100644
--- a/src/mongo/db/query/planner_ixselect_test.cpp
+++ b/src/mongo/db/query/planner_ixselect_test.cpp
@@ -1290,6 +1290,34 @@ TEST(QueryPlannerIXSelectTest, HashedIndexShouldNotBeRelevantForNotEqualsNullPre
     testRateIndices("{a: {$ne: null}}", "", kSimpleCollator, {entry}, "a,a", expectedIndices);
 }
 
+TEST(QueryPlannerIXSelectTest, HashedSparseIndexShouldNotBeRelevantForNotEqualsNullPredicate) {
+    auto entry = buildSimpleIndexEntry(BSON("a"
+                                            << "hashed"));
+    entry.type = IndexType::INDEX_HASHED;
+    entry.sparse = true;
+    std::set<size_t> expectedIndices = {};
+    testRateIndices("{a: {$ne: null}}", "", 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, HashedSparseIndexShouldNotBeRelevantForInWithNull) {
+    auto entry = buildSimpleIndexEntry(BSON("a"
+                                            << "hashed"));
+    entry.type = IndexType::INDEX_HASHED;
+    entry.sparse = true;
+    std::set<size_t> expectedIndices = {};
+    // A non-null value must be included as well to prevent rewrite to {$eq: null}.
+    testRateIndices("{a: {$in: [1, null]}}", "", kSimpleCollator, {entry}, "a", expectedIndices);
+}
+
 /*
  * Will compare 'keyPatterns' with 'entries'. As part of comparing, it will sort both of them.
  */