SERVER-44377 generate correct plan for indexed inequalities to null

3 files changed, 171 insertions, 54 deletions

diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index 3afc1f82587..a947c02d631 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -78,8 +78,14 @@ void assertOILIsAscendingLocally(const vector<Interval>& intervals, size_t idx)
 }
 
 // Tightness rules are shared for $lt, $lte, $gt, $gte.
-IndexBoundsBuilder::BoundsTightness getInequalityPredicateTightness(const BSONElement& dataElt,
+IndexBoundsBuilder::BoundsTightness getInequalityPredicateTightness(const Interval& interval,
+                                                                    const BSONElement& dataElt,
                                                                     const IndexEntry& index) {
+    if (interval.isNull()) {
+        // Any time the bounds are empty, we consider them to be exact.
+        return IndexBoundsBuilder::EXACT;
+    }
+
     return Indexability::isExactBoundsGenerating(dataElt) ? IndexBoundsBuilder::EXACT
                                                           : IndexBoundsBuilder::INEXACT_FETCH;
 }
@@ -139,7 +145,9 @@ void makeNullEqualityBounds(const IndexEntry& index,
 }
 
 bool isEqualityOrInNull(MatchExpression* me) {
-    if (MatchExpression::EQ == me->matchType()) {
+    // Because of type-bracketing, {$gte: null} and {$lte: null} are equivalent to {$eq: null}.
+    if (MatchExpression::EQ == me->matchType() || MatchExpression::GTE == me->matchType() ||
+        MatchExpression::LTE == me->matchType()) {
         return static_cast<ComparisonMatchExpression*>(me)->getData().type() == BSONType::jstNULL;
     }
 
@@ -439,8 +447,10 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
             *tightnessOut = IndexBoundsBuilder::EXACT;
         }
 
-        // If this invariant would fail, we would otherwise return incorrect query results.
-        invariant(*tightnessOut == IndexBoundsBuilder::EXACT);
+        // If this invariant would fail, we would return incorrect query results. The invariant is
+        // intentionally commented out because the risk of having it crash the server outweighs the
+        // benefit of picking up a subtle correctness issue on a stable version.
+        // invariant(*tightnessOut == IndexBoundsBuilder::EXACT);
 
         // If the index is multikey on this path, it doesn't matter what the tightness of the child
         // is, we must return INEXACT_FETCH. Consider a multikey index on 'a' with document
@@ -508,6 +518,13 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
             return;
         }
 
+        if (BSONType::jstNULL == dataElt.type()) {
+            // Because of type-bracketing, $lte null is equivalent to $eq null. An equality to null
+            // query is special. It should return both undefined and null values.
+            makeNullEqualityBounds(index, isHashed, oilOut, tightnessOut);
+            return;
+        }
+
         BSONObjBuilder bob;
         // Use -infinity for one-sided numerical bounds
         if (dataElt.isNumber()) {
@@ -518,10 +535,12 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
         CollationIndexKey::collationAwareIndexKeyAppend(dataElt, index.collator, &bob);
         BSONObj dataObj = bob.obj();
         verify(dataObj.isOwned());
-        oilOut->intervals.push_back(makeRangeInterval(
-            dataObj, IndexBounds::makeBoundInclusionFromBoundBools(typeMatch(dataObj), true)));
 
-        *tightnessOut = getInequalityPredicateTightness(dataElt, index);
+        const Interval interval = makeRangeInterval(
+            dataObj, IndexBounds::makeBoundInclusionFromBoundBools(typeMatch(dataObj), true));
+        oilOut->intervals.push_back(interval);
+
+        *tightnessOut = getInequalityPredicateTightness(interval, dataElt, index);
     } else if (MatchExpression::LT == expr->matchType()) {
         const LTMatchExpression* node = static_cast<const LTMatchExpression*>(expr);
         BSONElement dataElt = node->getData();
@@ -559,7 +578,7 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
             oilOut->intervals.push_back(interval);
         }
 
-        *tightnessOut = getInequalityPredicateTightness(dataElt, index);
+        *tightnessOut = getInequalityPredicateTightness(interval, dataElt, index);
     } else if (MatchExpression::GT == expr->matchType()) {
         const GTMatchExpression* node = static_cast<const GTMatchExpression*>(expr);
         BSONElement dataElt = node->getData();
@@ -595,8 +614,7 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
         if (!interval.isNull()) {
             oilOut->intervals.push_back(interval);
         }
-
-        *tightnessOut = getInequalityPredicateTightness(dataElt, index);
+        *tightnessOut = getInequalityPredicateTightness(interval, dataElt, index);
     } else if (MatchExpression::GTE == expr->matchType()) {
         const GTEMatchExpression* node = static_cast<const GTEMatchExpression*>(expr);
         BSONElement dataElt = node->getData();
@@ -617,6 +635,13 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
             return;
         }
 
+        if (BSONType::jstNULL == dataElt.type()) {
+            // Because of type-bracketing, $lte null is equivalent to $eq null. An equality to null
+            // query is special. It should return both undefined and null values.
+            makeNullEqualityBounds(index, isHashed, oilOut, tightnessOut);
+            return;
+        }
+
         BSONObjBuilder bob;
         CollationIndexKey::collationAwareIndexKeyAppend(dataElt, index.collator, &bob);
         if (dataElt.isNumber()) {
@@ -627,10 +652,11 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
         BSONObj dataObj = bob.obj();
         verify(dataObj.isOwned());
 
-        oilOut->intervals.push_back(makeRangeInterval(
-            dataObj, IndexBounds::makeBoundInclusionFromBoundBools(true, typeMatch(dataObj))));
+        const Interval interval = makeRangeInterval(
+            dataObj, IndexBounds::makeBoundInclusionFromBoundBools(true, typeMatch(dataObj)));
+        oilOut->intervals.push_back(interval);
 
-        *tightnessOut = getInequalityPredicateTightness(dataElt, index);
+        *tightnessOut = getInequalityPredicateTightness(interval, dataElt, index);
     } else if (MatchExpression::REGEX == expr->matchType()) {
         const RegexMatchExpression* rme = static_cast<const RegexMatchExpression*>(expr);
         translateRegex(rme, index, oilOut, tightnessOut);
diff --git a/src/mongo/db/query/index_bounds_builder_test.cpp b/src/mongo/db/query/index_bounds_builder_test.cpp
index c6aae09515f..e977b419167 100644
--- a/src/mongo/db/query/index_bounds_builder_test.cpp
+++ b/src/mongo/db/query/index_bounds_builder_test.cpp
@@ -2174,22 +2174,29 @@ void assertBoundsRepresentNotEqualsNull(const OrderedIntervalList& oil) {
     }
 }
 
+const std::vector<BSONObj> kNeNullQueries = {BSON("a" << BSON("$ne" << BSONNULL)),
+                                             BSON("a" << BSON("$not" << BSON("$lte" << BSONNULL))),
+                                             BSON("a" << BSON("$not" << BSON("$gte" << BSONNULL)))};
+
 TEST(IndexBoundsBuilderTest, TranslateNotEqualToNullShouldBuildExactBoundsIfIndexIsNotMultiKey) {
     BSONObj indexPattern = BSON("a" << 1);
     auto testIndex = buildSimpleIndexEntry(indexPattern);
 
-    BSONObj obj = BSON("a" << BSON("$ne" << BSONNULL));
-    auto expr = parseMatchExpression(obj);
+    for (BSONObj obj : kNeNullQueries) {
+        // It's necessary to call optimize since the $not will have a singleton $and child, which
+        // IndexBoundsBuilder::translate cannot handle.
+        auto expr = MatchExpression::optimize(parseMatchExpression(obj));
 
-    OrderedIntervalList oil;
-    IndexBoundsBuilder::BoundsTightness tightness;
-    IndexBoundsBuilder::translate(
-        expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(
+            expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
 
-    // Bounds should be [MinKey, undefined), (null, MaxKey].
-    ASSERT_EQUALS(oil.name, "a");
-    ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
-    assertBoundsRepresentNotEqualsNull(oil);
+        // Bounds should be [MinKey, undefined), (null, MaxKey].
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+        assertBoundsRepresentNotEqualsNull(oil);
+    }
 }
 
 TEST(IndexBoundsBuilderTest,
@@ -2198,36 +2205,42 @@ TEST(IndexBoundsBuilderTest,
     auto testIndex = buildSimpleIndexEntry(indexPattern);
     testIndex.multikeyPaths = {{}, {0}};  // "a" is not multi-key, but "b" is.
 
-    BSONObj obj = BSON("a" << BSON("$ne" << BSONNULL));
-    auto expr = parseMatchExpression(obj);
+    for (BSONObj obj : kNeNullQueries) {
+        // It's necessary to call optimize since the $not will have a singleton $and child, which
+        // IndexBoundsBuilder::translate cannot handle.
+        auto expr = MatchExpression::optimize(parseMatchExpression(obj));
 
-    OrderedIntervalList oil;
-    IndexBoundsBuilder::BoundsTightness tightness;
-    IndexBoundsBuilder::translate(
-        expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(
+            expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
 
-    // Bounds should be [MinKey, undefined), (null, MaxKey].
-    ASSERT_EQUALS(oil.name, "a");
-    ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
-    assertBoundsRepresentNotEqualsNull(oil);
+        // Bounds should be [MinKey, undefined), (null, MaxKey].
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+        assertBoundsRepresentNotEqualsNull(oil);
+    }
 }
 
 TEST(IndexBoundsBuilderTest, TranslateNotEqualToNullShouldBuildExactBoundsOnReverseIndex) {
     BSONObj indexPattern = BSON("a" << -1);
     auto testIndex = buildSimpleIndexEntry(indexPattern);
 
-    BSONObj obj = BSON("a" << BSON("$ne" << BSONNULL));
-    auto expr = parseMatchExpression(obj);
+    for (BSONObj obj : kNeNullQueries) {
+        // It's necessary to call optimize since the $not will have a singleton $and child, which
+        // IndexBoundsBuilder::translate cannot handle.
+        auto expr = MatchExpression::optimize(parseMatchExpression(obj));
 
-    OrderedIntervalList oil;
-    IndexBoundsBuilder::BoundsTightness tightness;
-    IndexBoundsBuilder::translate(
-        expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(
+            expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
 
-    // Bounds should be [MinKey, undefined), (null, MaxKey].
-    ASSERT_EQUALS(oil.name, "a");
-    ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
-    assertBoundsRepresentNotEqualsNull(oil);
+        // Bounds should be [MinKey, undefined), (null, MaxKey].
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+        assertBoundsRepresentNotEqualsNull(oil);
+    }
 }
 
 TEST(IndexBoundsBuilderTest, TranslateNotEqualToNullShouldBuildInexactBoundsIfIndexIsMultiKey) {
@@ -2235,17 +2248,95 @@ TEST(IndexBoundsBuilderTest, TranslateNotEqualToNullShouldBuildInexactBoundsIfIn
     auto testIndex = buildSimpleIndexEntry(indexPattern);
     testIndex.multikey = true;
 
-    BSONObj matchObj = BSON("a" << BSON("$ne" << BSONNULL));
-    auto expr = parseMatchExpression(matchObj);
+    for (BSONObj obj : kNeNullQueries) {
+        // It's necessary to call optimize since the $not will have a singleton $and child, which
+        // IndexBoundsBuilder::translate cannot handle.
+        auto expr = MatchExpression::optimize(parseMatchExpression(obj));
 
-    OrderedIntervalList oil;
-    IndexBoundsBuilder::BoundsTightness tightness;
-    IndexBoundsBuilder::translate(
-        expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(
+            expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
 
-    ASSERT_EQUALS(oil.name, "a");
-    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
-    assertBoundsRepresentNotEqualsNull(oil);
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+        assertBoundsRepresentNotEqualsNull(oil);
+    }
+}
+
+TEST(IndexBoundsBuilderTest, TranslateInequalityToNullShouldProduceExactEmptyBounds) {
+    BSONObj indexPattern = BSON("a" << 1);
+    auto testIndex = buildSimpleIndexEntry(indexPattern);
+
+    const std::vector<BSONObj> inequalities = {BSON("a" << BSON("$lt" << BSONNULL)),
+                                               BSON("a" << BSON("$gt" << BSONNULL))};
+
+    for (BSONObj obj : inequalities) {
+        // It's necessary to call optimize since the $not will have a singleton $and child, which
+        // IndexBoundsBuilder::translate cannot handle.
+        auto expr = parseMatchExpression(obj);
+
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(
+            expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
+
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+        ASSERT(oil.intervals.empty());
+    }
+}
+
+TEST(IndexBoundsBuilderTest, TranslateNotInequalityToNullShouldProduceExactFullBounds) {
+    BSONObj indexPattern = BSON("a" << 1);
+    auto testIndex = buildSimpleIndexEntry(indexPattern);
+
+    const std::vector<BSONObj> inequalities = {
+        BSON("a" << BSON("$not" << BSON("$lt" << BSONNULL))),
+        BSON("a" << BSON("$not" << BSON("$gt" << BSONNULL)))};
+
+    for (BSONObj obj : inequalities) {
+        // It's necessary to call optimize since the $not will have a singleton $and child, which
+        // IndexBoundsBuilder::translate cannot handle.
+        auto expr = MatchExpression::optimize(parseMatchExpression(obj));
+
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(
+            expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
+
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+        ASSERT_EQ(oil.intervals.size(), 1U);
+        ASSERT(oil.intervals.front().isMinToMax());
+    }
+}
+
+TEST(IndexBoundsBuilderTest,
+     TranslateNotInequalityToNullOnMultiKeyIndexShouldProduceInexactFullBounds) {
+    BSONObj indexPattern = BSON("a" << 1);
+    auto testIndex = buildSimpleIndexEntry(indexPattern);
+    testIndex.multikey = true;
+
+    const std::vector<BSONObj> inequalities = {
+        BSON("a" << BSON("$not" << BSON("$lt" << BSONNULL))),
+        BSON("a" << BSON("$not" << BSON("$gt" << BSONNULL)))};
+
+    for (BSONObj obj : inequalities) {
+        // It's necessary to call optimize since the $not will have a singleton $and child, which
+        // IndexBoundsBuilder::translate cannot handle.
+        auto expr = MatchExpression::optimize(parseMatchExpression(obj));
+
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(
+            expr.get(), indexPattern.firstElement(), testIndex, &oil, &tightness);
+
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+        ASSERT_EQ(oil.intervals.size(), 1U);
+        ASSERT(oil.intervals.front().isMinToMax());
+    }
 }
 
 TEST(IndexBoundsBuilderTest,
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 4a182e5a27e..7c44f4c1ccb 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -2789,13 +2789,13 @@ TEST_F(QueryPlannerTest, SparseIndexCanSupportGTEOrLTENull) {
     assertNumSolutions(1U);
     assertSolutionExists(
         "{fetch: {filter: {i: {$gte: null}}, node: {ixscan: {pattern: "
-        "{i: 1}, bounds: {i: [[null,null,true,true]]}}}}}");
+        "{i: 1}, bounds: {i: [[undefined,undefined,true,true], [null,null,true,true]]}}}}}");
 
     runQuery(fromjson("{i: {$lte: null}}"));
     assertNumSolutions(1U);
     assertSolutionExists(
         "{fetch: {filter: {i: {$lte: null}}, node: {ixscan: {pattern: "
-        "{i: 1}, bounds: {i: [[null,null,true,true]]}}}}}");
+        "{i: 1}, bounds: {i: [[undefined,undefined,true,true], [null,null,true,true]]}}}}}");
 }
 
 //