SERVER-47382 Support inequalities on arrays with $not on indexed collection

6 files changed, 48 insertions, 39 deletions

diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h
index 6e702768d82..ba2ac275e9d 100644
--- a/src/mongo/db/matcher/expression.h
+++ b/src/mongo/db/matcher/expression.h
@@ -454,6 +454,14 @@ public:
         return false;
     }
 
+    virtual bool isGTMinKey() const {
+        return false;
+    }
+
+    virtual bool isLTMaxKey() const {
+        return false;
+    }
+
     virtual void acceptVisitor(MatchExpressionMutableVisitor* visitor) = 0;
     virtual void acceptVisitor(MatchExpressionConstVisitor* visitor) const = 0;
 
diff --git a/src/mongo/db/matcher/expression_leaf.h b/src/mongo/db/matcher/expression_leaf.h
index 2f4dabdf965..5420c91ca55 100644
--- a/src/mongo/db/matcher/expression_leaf.h
+++ b/src/mongo/db/matcher/expression_leaf.h
@@ -299,6 +299,10 @@ public:
     void acceptVisitor(MatchExpressionConstVisitor* visitor) const final {
         visitor->visit(this);
     }
+
+    bool isLTMaxKey() const final {
+        return _rhs.type() == BSONType::MaxKey;
+    }
 };
 
 class GTMatchExpression final : public ComparisonMatchExpression {
@@ -336,6 +340,10 @@ public:
     void acceptVisitor(MatchExpressionConstVisitor* visitor) const final {
         visitor->visit(this);
     }
+
+    bool isGTMinKey() const final {
+        return _rhs.type() == BSONType::MinKey;
+    }
 };
 
 class GTEMatchExpression final : public ComparisonMatchExpression {
diff --git a/src/mongo/db/query/canonical_query_encoder.cpp b/src/mongo/db/query/canonical_query_encoder.cpp
index fede266acc1..487a8ad2198 100644
--- a/src/mongo/db/query/canonical_query_encoder.cpp
+++ b/src/mongo/db/query/canonical_query_encoder.cpp
@@ -414,6 +414,15 @@ void encodeKeyForMatch(const MatchExpression* tree, StringBuilder* keyBuilder) {
         }
     }
 
+    // If the query predicate is minKey or maxKey it can't use the same plan as other GT/LT
+    // queries. If the index is multikey and the query involves one of these values, it needs
+    // to use INEXACT_FETCH and the bounds can't be inverted. Therefore these need their own
+    // shape.
+    if (tree->isGTMinKey())
+        *keyBuilder << "min";
+    else if (tree->isLTMaxKey())
+        *keyBuilder << "max";
+
     // Traverse child nodes.
     // Enclose children in [].
     if (tree->numChildren() > 0) {
diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index dc826b1ebdb..98386d60579 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -568,12 +568,12 @@ void IndexBoundsBuilder::_translatePredicate(const MatchExpression* expr,
             *tightnessOut = IndexBoundsBuilder::EXACT;
         }
 
-        // This disables indexed negation of array inequality.
-        // TODO: SERVER-45233 Perform correct behavior here once indexed array inequality without
-        // negation's semantics are correctly determined and implemented.
-        massert(ErrorCodes::InternalError,
-                "Indexed negation of array inequality not supported.",
-                *tightnessOut == IndexBoundsBuilder::EXACT);
+        // Generally speaking inverting bounds can only be done for exact bounds. Any looser bounds
+        // (like INEXACT_FETCH) would signal that inversion would be mistakenly excluding some
+        // values. One exception is for collation, whose index bounds are tracked as INEXACT_FETCH,
+        // but only because the index data is different than the user data, not because the range
+        // is imprecise.
+        invariant(*tightnessOut == IndexBoundsBuilder::EXACT || index.collator);
 
         // 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
diff --git a/src/mongo/db/query/index_bounds_builder_test.cpp b/src/mongo/db/query/index_bounds_builder_test.cpp
index 7ec1beb9f37..2d3ca2d0ac5 100644
--- a/src/mongo/db/query/index_bounds_builder_test.cpp
+++ b/src/mongo/db/query/index_bounds_builder_test.cpp
@@ -492,32 +492,6 @@ TEST_F(IndexBoundsBuilderTest, TranslateGtMinKey) {
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
-TEST_F(IndexBoundsBuilderTest, DontCrashOnNegationOfArrayInequality) {
-    BSONObj keyPattern = BSON("a" << 1);
-    auto testIndex = IndexEntry(keyPattern,
-                                IndexNames::nameToType(IndexNames::findPluginName(keyPattern)),
-                                true,  // multikey
-                                {},
-                                {},
-                                false,  // sparse
-                                false,  // unique
-                                IndexEntry::Identifier{"test_foo"},
-                                nullptr,  // filterExpr
-                                BSONObj(),
-                                nullptr,
-                                nullptr);
-
-    BSONObj obj = fromjson("{a: {$not: {$lt: [\"here\", {}, false]}}}");
-    auto expr = MatchExpression::optimize(parseMatchExpression(obj));
-    BSONElement elt = obj.firstElement();
-    OrderedIntervalList oil;
-    IndexBoundsBuilder::BoundsTightness tightness;
-    // TODO: SERVER-45233 This should succeed rather than throwing code.
-    ASSERT_THROWS_CODE(IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness),
-                       DBException,
-                       ErrorCodes::InternalError);
-}
-
 // Nothing can be greater than MaxKey so the resulting index bounds would be a useless empty range.
 TEST_F(IndexBoundsBuilderTest, TranslateGtMaxKeyDoesNotGenerateBounds) {
     auto testIndex = buildSimpleIndexEntry();
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index 642074fea09..47e1df683f5 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -55,11 +55,13 @@ namespace {
 
 namespace wcp = ::mongo::wildcard_planning;
 
-// Can't index negations of {$eq: <Array>} or {$in: [<Array>, ...]}. Note that we could
-// use the index in principle, though we would need to generate special bounds.
-bool isEqualsArrayOrNotInArray(const MatchExpression* me) {
+// Can't index negations of {$eq: <Array>}, {$lt: <Array>}, {$gt: <Array>}, {$lte: <Array>}, {$gte:
+// <Array>}, or {$in: [<Array>, ...]}. Note that we could use the index in principle, though we
+// would need to generate special bounds.
+bool isComparisonWithArrayPred(const MatchExpression* me) {
     const auto type = me->matchType();
-    if (type == MatchExpression::EQ) {
+    if (type == MatchExpression::EQ || type == MatchExpression::LT || type == MatchExpression::GT ||
+        type == MatchExpression::LTE || type == MatchExpression::GTE) {
         return static_cast<const ComparisonMatchExpression*>(me)->getData().type() ==
             BSONType::Array;
     } else if (type == MatchExpression::MATCH_IN) {
@@ -68,7 +70,6 @@ bool isEqualsArrayOrNotInArray(const MatchExpression* me) {
             return elt.type() == BSONType::Array;
         });
     }
-
     return false;
 }
 
@@ -444,7 +445,16 @@ bool QueryPlannerIXSelect::_compatible(const BSONElement& keyPatternElt,
                 return false;
             }
 
-            if (isEqualsArrayOrNotInArray(child)) {
+            // Comparisons with arrays have strange enough semantics that inverting the bounds
+            // within a $not has many complex special cases. We avoid indexing these queries, even
+            // though it is sometimes possible to build useful bounds.
+            if (isComparisonWithArrayPred(child)) {
+                return false;
+            }
+
+            // $gt and $lt to MinKey/MaxKey must build inexact bounds if the index is multikey and
+            // therefore cannot be inverted safely in a $not.
+            if (index.multikey && (child->isGTMinKey() || child->isLTMaxKey())) {
                 return false;
             }
 
@@ -623,7 +633,7 @@ bool QueryPlannerIXSelect::nodeIsSupportedBySparseIndex(const MatchExpression* q
 
 bool QueryPlannerIXSelect::logicalNodeMayBeSupportedByAnIndex(const MatchExpression* queryExpr) {
     return !(queryExpr->matchType() == MatchExpression::NOT &&
-             isEqualsArrayOrNotInArray(queryExpr->getChild(0)));
+             isComparisonWithArrayPred(queryExpr->getChild(0)));
 }
 
 bool QueryPlannerIXSelect::nodeIsSupportedByWildcardIndex(const MatchExpression* queryExpr) {