SERVER-27646 Build index bounds for {$ne: null} predicates

1 files changed, 38 insertions, 9 deletions

diff --git a/src/mongo/db/query/planner_ixselect.h b/src/mongo/db/query/planner_ixselect.h
index 1a92dd33d6c..8e2f526b3c1 100644
--- a/src/mongo/db/query/planner_ixselect.h
+++ b/src/mongo/db/query/planner_ixselect.h
@@ -28,6 +28,7 @@
 
 #pragma once
 
+#include "mongo/db/matcher/expression_array.h"
 #include "mongo/db/query/canonical_query.h"
 #include "mongo/db/query/index_entry.h"
 #include "mongo/db/query/query_solution.h"
@@ -62,18 +63,21 @@ public:
                                     std::vector<IndexEntry>* out);
 
     /**
-     * Return true if the index key pattern field 'elt' (which belongs to 'index') can be used
-     * to answer the predicate 'node'.
+     * Return true if the index key pattern field 'keyPatternElt' (which belongs to 'index' and is
+     * at position 'keyPatternIndex' in the index's keyPattern) can be used to answer the predicate
+     * 'node'. When 'node' is a sub-tree of a larger MatchExpression, 'fullPathToNode' is the path
+     * traversed to get to this node, otherwise it is empty.
      *
      * For example, {field: "hashed"} can only be used with sets of equalities.
      *              {field: "2d"} can only be used with some geo predicates.
      *              {field: "2dsphere"} can only be used with some other geo predicates.
      */
-    static bool compatible(const BSONElement& elt,
+    static bool compatible(const BSONElement& keyPatternElt,
                            const IndexEntry& index,
+                           std::size_t keyPatternIndex,
                            MatchExpression* node,
-                           const CollatorInterface* collator,
-                           bool elemMatchChild = false);
+                           StringData fullPathToNode,
+                           const CollatorInterface* collator);
 
     /**
      * Determine how useful all of our relevant 'indices' are to all predicates in the subtree
@@ -129,13 +133,33 @@ public:
     static void stripUnneededAssignments(MatchExpression* node,
                                          const std::vector<IndexEntry>& indices);
 
+private:
     /**
-     * Returns true if the indexed field has any multikey components. Illegal to call unless
-     * 'indexedField' is present in the key pattern for 'index'.
+     * Used to keep track of if any $elemMatch predicates were encountered when walking a
+     * MatchExpression tree. The presence of an outer $elemMatch can impact whether an index is
+     * applicable for an inner MatchExpression. For example, the NOT expression in
+     * {a: {$elemMatch: {b: {$ne: null}}} can only use an "a.b" index if that path is not multikey
+     * on "a.b". Because of the $elemMatch, it's okay to use the "a.b" index if the path is multikey
+     * on "a".
      */
-    static bool indexedFieldHasMultikeyComponents(StringData indexedField, const IndexEntry& index);
+    struct ElemMatchContext {
+        ArrayMatchingMatchExpression* innermostParentElemMatch{nullptr};
+        StringData fullPathToParentElemMatch{""_sd};
+    };
 
-private:
+    static bool _compatible(const BSONElement& keyPatternElt,
+                            const IndexEntry& index,
+                            std::size_t keyPatternIndex,
+                            MatchExpression* node,
+                            StringData fullPathToNode,
+                            const CollatorInterface* collator,
+                            const ElemMatchContext& elemMatchContext);
+
+    static void _rateIndices(MatchExpression* node,
+                             std::string prefix,
+                             const std::vector<IndexEntry>& indices,
+                             const CollatorInterface* collator,
+                             const ElemMatchContext& elemMatchContext);
     /**
      * Amend the RelevantTag lists for all predicates in the subtree rooted at 'node' to remove
      * invalid assignments to text indexes.
@@ -222,6 +246,11 @@ private:
      */
     static void stripInvalidAssignmentsToPartialIndices(MatchExpression* node,
                                                         const std::vector<IndexEntry>& indices);
+
+    static bool notEqualsNullCanUseIndex(const IndexEntry& index,
+                                         const BSONElement& keyPatternElt,
+                                         std::size_t keyPatternIndex,
+                                         const ElemMatchContext& elemMatchContext);
 };
 
 }  // namespace mongo