Update upstream source from tag 'upstream/6.0.0'master

Update to upstream version '6.0.0'
with Debian dir 5604a80ec1c96ca76f25f40d78e6ef855abec322

1 files changed, 33 insertions, 111 deletions

diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index 3c027bde140..01e13b5f058 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -108,38 +108,13 @@ Interval makeNullPointInterval(bool isHashed) {
     return isHashed ? kHashedNullInterval : IndexBoundsBuilder::kNullPointInterval;
 }
 
-/**
- * This helper updates the query bounds tightness for the limited set of conditions where we see a
- * null query that can be covered.
- */
-void updateTightnessForNullQuery(const IndexEntry& index,
-                                 IndexBoundsBuilder::BoundsTightness* tightnessOut) {
-    if (index.sparse || index.type == IndexType::INDEX_HASHED) {
-        // Sparse indexes and hashed indexes require a FETCH stage with a filter for null queries.
-        *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
-        return;
-    }
-
-    if (index.multikey) {
-        // If we have a simple equality null query and our index is multikey, we cannot cover the
-        // query. This is because null intervals are translated into the null and undefined point
-        // intervals, and the undefined point interval includes entries for []. In the case of a
-        // single null interval, [] should not match.
-        *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
-        return;
-    }
-
-    // The query may be fully covered by the index if the projection allows it, since the case above
-    // about the empty array can only become an issue if there is an empty array present, which
-    // would mark the index as multikey.
-    *tightnessOut = IndexBoundsBuilder::EXACT_MAYBE_COVERED;
-}
-
 void makeNullEqualityBounds(const IndexEntry& index,
                             bool isHashed,
                             OrderedIntervalList* oil,
                             IndexBoundsBuilder::BoundsTightness* tightnessOut) {
-    updateTightnessForNullQuery(index, tightnessOut);
+    // An equality to null predicate cannot be covered because the index does not distinguish
+    // between the lack of a value and the literal value null.
+    *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
 
     // There are two values that could possibly be equal to null in an index: undefined and null.
     oil->intervals.push_back(makeUndefinedPointInterval(isHashed));
@@ -279,10 +254,7 @@ bool IndexBoundsBuilder::canUseCoveredMatching(const MatchExpression* expr,
     IndexBoundsBuilder::BoundsTightness tightness;
     OrderedIntervalList oil;
     translate(expr, BSONElement{}, index, &oil, &tightness, /* iet::Builder */ nullptr);
-    // We have additional tightness values (MAYBE_COVERED), but we cannot generally cover those
-    // cases unless we have an appropriate projection.
-    return tightness == IndexBoundsBuilder::INEXACT_COVERED ||
-        tightness == IndexBoundsBuilder::EXACT;
+    return tightness >= IndexBoundsBuilder::INEXACT_COVERED;
 }
 
 // static
@@ -432,61 +404,6 @@ const Interval IndexBoundsBuilder::kNullPointInterval =
 const Interval IndexBoundsBuilder::kEmptyArrayPointInterval =
     IndexBoundsBuilder::makePointInterval(kEmptyArrayElementObj);
 
-bool detectIfEntireNullIntervalMatchesPredicate(const InMatchExpression* ime,
-                                                const IndexEntry& index) {
-    if (!ime->hasNull()) {
-        // This isn't a null query.
-        return false;
-    }
-
-    if (index.sparse || (IndexType::INDEX_HASHED == index.type)) {
-        // Sparse indexes and hashed indexes still require a FETCH stage with a filter for null
-        // queries.
-        return false;
-    }
-
-    // Given the context of having a null $in query with eligible indexes, we may be able to cover
-    // some combinations of intervals that we could not cover individually.
-    if (index.multikey) {
-        // If the path has multiple components and we have a multikey index, we still need a FETCH
-        // in order to defend against cases where we have a multikey index on "a". These documents
-        // will generate null index keys: {"a.b": null} and {a: [1,2,3]}. However, a query like
-        // {"a.b": {$in: [null, []]}} should not match {a: [1, 2, 3]}.
-        // TODO SERVER-71021: it may be possible to cover more cases here.
-        if (ime->fieldRef()->numParts() > 1) {
-            return false;
-        }
-
-        // We must have an equality to an empty array for this null query to be covered, otherwise,
-        // because we generate both null and undefined point intervals for a null query, and because
-        // a multikey index reuses the same entry for [] and undefined, we will not be able to cover
-        // the query.
-        if (!ime->hasEmptyArray()) {
-            return false;
-        }
-    }
-
-    return true;
-}
-
-void IndexBoundsBuilder::_mergeTightness(const BoundsTightness& tightness,
-                                         BoundsTightness& tightnessOut) {
-    // There is a special case where we may have a covered null query (EXACT_MAYBE_COVERED) and a
-    // regex with inexact bounds that doesn't need a FETCH (INEXACT_COVERED). In this case, we want
-    // to update the tightness to INEXACT_MAYBE_COVERED, to indicate that we need to check if the
-    // projection allows us to cover the query, but ensure that we will have a filter on the index
-    // if it turns out we can.
-    if (((tightness == BoundsTightness::EXACT_MAYBE_COVERED) &&
-         (tightnessOut == BoundsTightness::INEXACT_COVERED)) ||
-        ((tightness == BoundsTightness::INEXACT_COVERED) &&
-         (tightnessOut == BoundsTightness::EXACT_MAYBE_COVERED))) {
-        tightnessOut = BoundsTightness::INEXACT_MAYBE_COVERED;
-    } else if (tightness < tightnessOut) {
-        // Otherwise, fallback to picking the new tightness if it is looser than the old tightness.
-        tightnessOut = tightness;
-    }
-}
-
 void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
                                              const BSONElement& elt,
                                              const IndexEntry& index,
@@ -1038,45 +955,51 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
         });
 
         const InMatchExpression* ime = static_cast<const InMatchExpression*>(expr);
+
         *tightnessOut = IndexBoundsBuilder::EXACT;
 
         // Create our various intervals.
 
         IndexBoundsBuilder::BoundsTightness tightness;
-        // We check if the $in predicate satisfies conditions to be a covered null predicate on the
-        // basis of indexes, null intervals, and array intervals.
-        const bool entireNullIntervalMatchesPredicate =
-            detectIfEntireNullIntervalMatchesPredicate(ime, index);
+        bool arrayOrNullPresent = false;
         for (auto&& equality : ime->getEqualities()) {
-            // First, we generate the bounds the same way that we would do for an individual
-            // equality. This will set tightness to the value it should be if this equality is being
-            // considered in isolation.
-            IndexBoundsBuilder::translateEquality(equality, index, isHashed, oilOut, &tightness);
-            if (entireNullIntervalMatchesPredicate &&
-                (BSONType::jstNULL == equality.type() ||
-                 (BSONType::Array == equality.type() && equality.Obj().isEmpty()))) {
-                // We may have a covered null query. In this case, we update both empty array and
-                // null interval tightness to EXACT_MAYBE_COVERED, as individually they would have a
-                // tightness of INEXACT_FETCH. However, we already know we will be able to cover
-                // these intervals together if we have appropriate projections. Note that any other
-                // intervals that cannot be covered may still require the query to use a FETCH.
-                tightness = IndexBoundsBuilder::EXACT_MAYBE_COVERED;
+            translateEquality(equality, index, isHashed, oilOut, &tightness);
+            // The ordering invariant of oil has been violated by the call to translateEquality.
+            arrayOrNullPresent = arrayOrNullPresent || equality.type() == BSONType::jstNULL ||
+                equality.type() == BSONType::Array;
+            if (tightness != IndexBoundsBuilder::EXACT) {
+                *tightnessOut = tightness;
             }
-            IndexBoundsBuilder::_mergeTightness(tightness, *tightnessOut);
         }
 
         for (auto&& regex : ime->getRegexes()) {
             translateRegex(regex.get(), index, oilOut, &tightness);
-            IndexBoundsBuilder::_mergeTightness(tightness, *tightnessOut);
+            if (tightness != IndexBoundsBuilder::EXACT) {
+                *tightnessOut = tightness;
+            }
+        }
+
+        if (ime->hasNull()) {
+            // A null index key does not always match a null query value so we must fetch the
+            // doc and run a full comparison.  See SERVER-4529.
+            // TODO: Do we already set the tightnessOut by calling translateEquality?
+            *tightnessOut = INEXACT_FETCH;
+        }
+
+        if (ime->hasEmptyArray()) {
+            // Empty arrays are indexed as undefined.
+            BSONObjBuilder undefinedBob;
+            undefinedBob.appendUndefined("");
+            oilOut->intervals.push_back(makePointInterval(undefinedBob.obj()));
+            *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
         }
 
         // Equalities are already sorted and deduped so unionize is unneccesary if no regexes
         // are present. Hashed indexes may also cause the bounds to be out-of-order.
-        // Arrays and nulls introduce multiple elements that necessitate a sort and deduping.
-        if (ime->hasNonScalarOrNonEmptyValues() || index.type == IndexType::INDEX_HASHED) {
+        // Arrays and nulls introduce multiple elements that neccesitate a sort and deduping.
+        if (!ime->getRegexes().empty() || index.type == IndexType::INDEX_HASHED ||
+            arrayOrNullPresent)
             unionize(oilOut);
-        }
-
     } else if (MatchExpression::GEO == expr->matchType()) {
         const GeoMatchExpression* gme = static_cast<const GeoMatchExpression*>(expr);
         if ("2dsphere" == elt.valueStringDataSafe()) {
@@ -1392,7 +1315,6 @@ void IndexBoundsBuilder::translateEquality(const BSONElement& data,
     }
 
     std::sort(oil->intervals.begin(), oil->intervals.end(), IntervalComparison);
-
     *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
 }