SERVER-42291 generate correct bounds for $nin null queries

(cherry picked from commit bf8fcb05e020e8eb7b99a3ca7667e0d5a289c873)

4 files changed, 257 insertions, 7 deletions

diff --git a/jstests/core/null_query_semantics.js b/jstests/core/null_query_semantics.js
index bdce5bc8f85..7aa7a2a585f 100644
--- a/jstests/core/null_query_semantics.js
+++ b/jstests/core/null_query_semantics.js
@@ -63,6 +63,63 @@
             assert(resultsEq(projectResults, extractAValues(expected)), tojson(projectResults));
         }());
 
+        // Test the semantics of the query {a: {$nin: [null, <number>]}}.
+        (function testNotInNullQuery() {
+            const query = {a: {$nin: [null, 4]}};
+            const noProjectResults = coll.find(query).toArray();
+            const expected = [
+                {_id: "a_empty_subobject", a: {}},
+                {_id: "a_subobject_b_not_null", a: {b: "hi"}},
+                {_id: "a_subobject_b_null", a: {b: null}},
+                {_id: "a_subobject_b_undefined", a: {b: undefined}},
+            ];
+
+            // TODO: SERVER-21929: $in may (or may not) miss fields with value "undefined".
+            const expectedWithUndefined = expected.concat([
+                {_id: "a_undefined", a: undefined},
+            ]);
+            assert(resultsEq(noProjectResults, expected) ||
+                       resultsEq(noProjectResults, expectedWithUndefined),
+                   noProjectResults);
+
+            const projectResults = coll.find(query, projectToOnlyA).toArray();
+            assert(resultsEq(projectResults, extractAValues(expected)) ||
+                       resultsEq(projectResults, extractAValues(expectedWithUndefined)),
+                   projectResults);
+        }());
+
+        (function testNotInNullAndRegexQuery() {
+            // While $nin: [null, ...] can be indexed, $nin: [<regex>] cannot. Ensure that we get
+            // the correct results in this case.
+            const query = {a: {$nin: [null, /^hi.*/]}};
+            const noProjectResults = coll.find(query).toArray();
+            const expected = [
+                {_id: "a_empty_subobject", a: {}},
+                {_id: "a_empty_subobject", a: 4},
+                {_id: "a_subobject_b_not_null", a: {b: "hi"}},
+                {_id: "a_subobject_b_null", a: {b: null}},
+                {_id: "a_subobject_b_undefined", a: {b: undefined}},
+
+                // TODO: SERVER-21929: $in may (or may not) miss fields with value "undefined".
+                {_id: "a_undefined", a: undefined},
+            ];
+            assert(resultsEq(noProjectResults, expected), tojson(noProjectResults));
+
+            const projectResults = coll.find(query, projectToOnlyA).toArray();
+            assert(resultsEq(projectResults, extractAValues(expected)), tojson(projectResults));
+        }());
+
+        (function testExistsFalse() {
+            const noProjectResults = coll.find({a: {$exists: false}}).toArray();
+            const expected = [
+                {_id: "no_a"},
+            ];
+            assert(resultsEq(noProjectResults, expected), tojson(noProjectResults));
+
+            const projectResults = coll.find({a: {$exists: false}}, projectToOnlyA).toArray();
+            assert(resultsEq(projectResults, extractAValues(expected)), tojson(projectResults));
+        }());
+
         // Test the semantics of the query {"a.b": {$eq: null}}.
         (function testDottedEqualsNull() {
             const noProjectResults = coll.find({"a.b": {$eq: null}}).toArray();
@@ -94,6 +151,22 @@
             assert(resultsEq(projectResults, [{a: {b: "hi"}}]), tojson(projectResults));
         }());
 
+        (function testDottedExistsFalse() {
+            const noProjectResults = coll.find({"a.b": {$exists: false}}).toArray();
+            const expected = [
+                {_id: "no_a"},
+                {_id: "a_empty_subobject", a: {}},
+                {_id: "a_null", a: null},
+                {_id: "a_number", a: 4},
+                {_id: "a_undefined", a: undefined},
+            ];
+            assert(resultsEq(noProjectResults, expected), tojson(noProjectResults));
+
+            const projectResults =
+                coll.find({"a.b": {$exists: false}}, projectToOnlyADotB).toArray();
+            assert(resultsEq(projectResults, [{}, {a: {}}, {}, {}, {}]), tojson(projectResults));
+        }());
+
         // Test similar queries, but with an $elemMatch. These queries should have no results since
         // an $elemMatch requires an array.
         (function testElemMatchQueriesWithNoArrays() {
@@ -185,6 +258,76 @@
             assert(resultsEq(projectResults, extractAValues(expected)), tojson(projectResults));
         }());
 
+        // Test the semantics of the query {a: {$nin: [null, <number>]}}.
+        (function testNotInNullQuery() {
+            const query = {a: {$nin: [null, 75]}};
+            const noProjectResults = coll.find(query).toArray();
+            const expected = [
+                {_id: "a_empty_subobject", a: {}},
+                {_id: "a_number", a: 4},
+                {_id: "a_subobject_b_not_null", a: {b: "hi"}},
+                {_id: "a_subobject_b_null", a: {b: null}},
+                {_id: "a_subobject_b_undefined", a: {b: undefined}},
+
+                {_id: "a_double_array", a: [[]]},
+                {_id: "a_empty_array", a: []},
+                {_id: "a_object_array_all_b_nulls", a: [{b: null}, {b: undefined}, {b: null}, {}]},
+                {_id: "a_object_array_no_b_nulls", a: [{b: 1}, {b: 3}, {b: "string"}]},
+                {_id: "a_object_array_some_b_nulls", a: [{b: null}, {b: 3}, {b: null}]},
+                {_id: "a_object_array_some_b_undefined", a: [{b: undefined}, {b: 3}]},
+                {_id: "a_object_array_some_b_missing", a: [{b: 3}, {}]},
+                {_id: "a_value_array_no_nulls", a: [1, "string", 4]},
+            ];
+
+            // TODO: SERVER-21929: $in may (or may not) miss fields with value "undefined".
+            const expectedWithUndefined = expected.concat([
+                {_id: "a_undefined", a: undefined},
+                {_id: "a_value_array_with_undefined", a: [1, "string", undefined, 4]},
+            ]);
+            assert(resultsEq(noProjectResults, expected) ||
+                       resultsEq(noProjectResults, expectedWithUndefined),
+                   noProjectResults);
+
+            const projectResults = coll.find(query, projectToOnlyA).toArray();
+            assert(resultsEq(projectResults, extractAValues(expected)) ||
+                       resultsEq(projectResults, extractAValues(expectedWithUndefined)),
+                   projectResults);
+        }());
+
+        (function testNotInNullAndRegexQuery() {
+            const query = {a: {$nin: [null, /^str.*/]}};
+            const noProjectResults = coll.find(query).toArray();
+            const expected = [
+                {_id: "a_empty_subobject", a: {}},
+                {_id: "a_number", a: 4},
+                {_id: "a_subobject_b_not_null", a: {b: "hi"}},
+                {_id: "a_subobject_b_null", a: {b: null}},
+                {_id: "a_subobject_b_undefined", a: {b: undefined}},
+
+                {_id: "a_double_array", a: [[]]},
+                {_id: "a_empty_array", a: []},
+                {_id: "a_object_array_all_b_nulls", a: [{b: null}, {b: undefined}, {b: null}, {}]},
+                {_id: "a_object_array_no_b_nulls", a: [{b: 1}, {b: 3}, {b: "string"}]},
+                {_id: "a_object_array_some_b_nulls", a: [{b: null}, {b: 3}, {b: null}]},
+                {_id: "a_object_array_some_b_undefined", a: [{b: undefined}, {b: 3}]},
+                {_id: "a_object_array_some_b_missing", a: [{b: 3}, {}]},
+            ];
+
+            // TODO: SERVER-21929: $in may (or may not) miss fields with value "undefined".
+            const expectedWithUndefined = expected.concat([
+                {_id: "a_undefined", a: undefined},
+            ]);
+
+            assert(resultsEq(noProjectResults, expected) ||
+                       resultsEq(noProjectResults, expectedWithUndefined),
+                   noProjectResults);
+
+            const projectResults = coll.find(query, projectToOnlyA).toArray();
+            assert(resultsEq(projectResults, extractAValues(expected)) ||
+                       resultsEq(projectResults, extractAValues(expectedWithUndefined)),
+                   projectResults);
+        }());
+
         // Test the results of similar queries with an $elemMatch.
         (function testElemMatchValue() {
             // Test $elemMatch with equality to null.
@@ -299,6 +442,65 @@
                    tojson(projectResults));
         }());
 
+        // Test the semantics of the query {a.b: {$nin: [null, <number>]}}.
+        (function testDottedNotInNullQuery() {
+            const query = {"a.b": {$nin: [null, 75]}};
+            const noProjectResults = coll.find(query).toArray();
+            const expected = [
+                {_id: "a_subobject_b_not_null", a: {b: "hi"}},
+                {_id: "a_double_array", a: [[]]},
+                {_id: "a_empty_array", a: []},
+                {_id: "a_object_array_no_b_nulls", a: [{b: 1}, {b: 3}, {b: "string"}]},
+                {_id: "a_value_array_all_nulls", a: [null, null]},
+                {_id: "a_value_array_no_nulls", a: [1, "string", 4]},
+                {_id: "a_value_array_with_null", a: [1, "string", null, 4]},
+                {_id: "a_value_array_with_undefined", a: [1, "string", undefined, 4]},
+            ];
+
+            // TODO: SERVER-21929: $in may (or may not) miss fields with value "undefined".
+            const expectedWithUndefined = expected.concat([
+                {_id: "a_object_array_some_b_undefined", a: [{b: undefined}, {b: 3}]},
+                {_id: "a_subobject_b_undefined", a: {b: undefined}},
+            ]);
+            assert(resultsEq(noProjectResults, expected) ||
+                       resultsEq(noProjectResults, expectedWithUndefined),
+                   noProjectResults);
+
+            const projectResults = coll.find(query, projectToOnlyA).toArray();
+            assert(resultsEq(projectResults, extractAValues(expected)) ||
+                       resultsEq(projectResults, extractAValues(expectedWithUndefined)),
+                   projectResults);
+        }());
+
+        // Test the semantics of the query {a.b: {$nin: [null, <regex>]}}.
+        (function testDottedNotInNullAndRegexQuery() {
+            const query = {"a.b": {$nin: [null, /^str.*/]}};
+            const noProjectResults = coll.find(query).toArray();
+            const expected = [
+                {_id: "a_subobject_b_not_null", a: {b: "hi"}},
+                {_id: "a_double_array", a: [[]]},
+                {_id: "a_empty_array", a: []},
+                {_id: "a_value_array_all_nulls", a: [null, null]},
+                {_id: "a_value_array_no_nulls", a: [1, "string", 4]},
+                {_id: "a_value_array_with_null", a: [1, "string", null, 4]},
+                {_id: "a_value_array_with_undefined", a: [1, "string", undefined, 4]},
+            ];
+
+            // TODO: SERVER-21929: $in may (or may not) miss fields with value "undefined".
+            const expectedWithUndefined = expected.concat([
+                {_id: "a_object_array_some_b_undefined", a: [{b: undefined}, {b: 3}]},
+                {_id: "a_subobject_b_undefined", a: {b: undefined}},
+            ]);
+            assert(resultsEq(noProjectResults, expected) ||
+                       resultsEq(noProjectResults, expectedWithUndefined),
+                   noProjectResults);
+
+            const projectResults = coll.find(query, projectToOnlyA).toArray();
+            assert(resultsEq(projectResults, extractAValues(expected)) ||
+                       resultsEq(projectResults, extractAValues(expectedWithUndefined)),
+                   projectResults);
+        }());
+
         // Test the results of similar dotted queries with an $elemMatch. These should have no
         // results since none of our documents have an array at the path "a.b".
         (function testDottedElemMatchValue() {
diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index bd3c92c38fc..3afc1f82587 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -137,6 +137,20 @@ void makeNullEqualityBounds(const IndexEntry& index,
     // Just to be sure, make sure the bounds are in the right order if the hash values are opposite.
     IndexBoundsBuilder::unionize(oil);
 }
+
+bool isEqualityOrInNull(MatchExpression* me) {
+    if (MatchExpression::EQ == me->matchType()) {
+        return static_cast<ComparisonMatchExpression*>(me)->getData().type() == BSONType::jstNULL;
+    }
+
+    if (me->matchType() == MatchExpression::MATCH_IN) {
+        const InMatchExpression* in = static_cast<const InMatchExpression*>(me);
+        return in->hasNull();
+    }
+
+    return false;
+}
+
 }  // namespace
 
 string IndexBoundsBuilder::simpleRegex(const char* regex,
@@ -421,11 +435,11 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
         // Until the index distinguishes between missing values and literal null values, we cannot
         // build exact bounds for equality predicates on the literal value null. However, we _can_
         // build exact bounds for the inverse, for example the query {a: {$ne: null}}.
-        if (MatchExpression::EQ == child->matchType() &&
-            static_cast<ComparisonMatchExpression*>(child)->getData().type() == BSONType::jstNULL) {
+        if (isEqualityOrInNull(child)) {
             *tightnessOut = IndexBoundsBuilder::EXACT;
         }
 
+        // If this invariant would fail, we would otherwise return incorrect query results.
         invariant(*tightnessOut == IndexBoundsBuilder::EXACT);
 
         // If the index is multikey on this path, it doesn't matter what the tightness of the child
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index 77f662a4701..c35bb3cbdfb 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -440,8 +440,9 @@ 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.
-            if (isNotEqualsNull &&
-                !notEqualsNullCanUseIndex(index, keyPatternElt, keyPatternIdx, elemMatchContext)) {
+            const bool canUseIndexForNeNull =
+                notEqualsNullCanUseIndex(index, keyPatternElt, keyPatternIdx, elemMatchContext);
+            if (isNotEqualsNull && !canUseIndexForNeNull) {
                 return false;
             }
 
@@ -451,6 +452,12 @@ bool QueryPlannerIXSelect::_compatible(const BSONElement& keyPatternElt,
                 if (!ime->getRegexes().empty()) {
                     return false;
                 }
+
+                // If we can't use the index for $ne to null, then we cannot use it for the
+                // case {$nin: [null, <...>]}.
+                if (!canUseIndexForNeNull && ime->hasNull()) {
+                    return false;
+                }
             }
         }
 
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 3c38b272fd1..8d944b29eb9 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -3325,6 +3325,20 @@ TEST_F(QueryPlannerTest, NENull) {
         "[['MinKey',undefined,true,false],[null,'MaxKey',false,true]]}}}}}");
 }
 
+TEST_F(QueryPlannerTest, NinNull) {
+    addIndex(BSON("a" << 1));
+    runQuery(fromjson("{a: {$nin: [null, 4]}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1}}");
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {ixscan: {pattern: {a:1}, "
+        "bounds: {a: [['MinKey',undefined,true,false],"
+        "[null,4,false,false],"
+        "[4,'MaxKey',false,true]]}}}}}");
+}
+
+
 TEST_F(QueryPlannerTest, NENullWithSort) {
     addIndex(BSON("a" << 1));
     runQuerySortProj(fromjson("{a: {$ne: null}}"), BSON("a" << 1), BSONObj());
@@ -3375,7 +3389,7 @@ TEST_F(QueryPlannerTest, NENullWithSortAndProjection) {
 
 // In general, a negated $nin can make use of an index.
 TEST_F(QueryPlannerTest, NinUsesMultikeyIndex) {
-    // true means multikey
+    // 'true' means multikey.
     addIndex(BSON("a" << 1), true);
     runQuery(fromjson("{a: {$nin: [4, 10]}}"));
 
@@ -3390,8 +3404,8 @@ TEST_F(QueryPlannerTest, NinUsesMultikeyIndex) {
 
 // But it can't if the $nin contains a regex because regex bounds can't
 // be complemented.
-TEST_F(QueryPlannerTest, NinCantUseMultikeyIndex) {
-    // true means multikey
+TEST_F(QueryPlannerTest, NinWithRegexCantUseMultikeyIndex) {
+    // 'true' means multikey.
     addIndex(BSON("a" << 1), true);
     runQuery(fromjson("{a: {$nin: [4, /foobar/]}}"));
 
@@ -3399,6 +3413,19 @@ TEST_F(QueryPlannerTest, NinCantUseMultikeyIndex) {
     assertSolutionExists("{cscan: {dir: 1}}");
 }
 
+// Or if it contains a null, because null is "equal" to undefined, and undefined can represent an
+// empty array. Therefore negating the bounds [undefined, null], would lead to the query missing
+// values for empty array.
+TEST_F(QueryPlannerTest, NinWithNullCantUseMultikeyIndex) {
+    // 'true' means multikey.
+    addIndex(BSON("a" << 1), true);
+    runQuery(fromjson("{a: {$nin: [4, null]}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists("{cscan: {dir: 1}}");
+}
+
+
 //
 // Multikey indices
 //