SERVER-36465 Support {$ne: null} queries with non-multikey sparse and wildcard indexes

1 files changed, 42 insertions, 5 deletions

diff --git a/src/mongo/db/query/planner_wildcard_helpers.cpp b/src/mongo/db/query/planner_wildcard_helpers.cpp
index 23335b81741..d928fc47638 100644
--- a/src/mongo/db/query/planner_wildcard_helpers.cpp
+++ b/src/mongo/db/query/planner_wildcard_helpers.cpp
@@ -41,6 +41,21 @@ namespace mongo {
 namespace wildcard_planning {
 namespace {
 /**
+ * Returns an OIL that called 'name', with just the interval [{}, []).
+ */
+OrderedIntervalList getAllObjectsOIL(const std::string& name) {
+    OrderedIntervalList oil(name);
+    BSONObjBuilder bob;
+    bob.appendMinForType("", BSONType::Object);
+    bob.appendMaxForType("", BSONType::Object);
+    oil.intervals.push_back(IndexBoundsBuilder::makeRangeInterval(
+        bob.obj(), BoundInclusion::kExcludeBothStartAndEndKeys));
+
+    return oil;
+}
+
+
+/**
  * Compares the path 'fieldNameOrArrayIndexPath' to 'staticComparisonPath', ignoring any array
  * indices present in the former if they are not present in the latter. The 'multikeyPathComponents'
  * set contains the path positions that are known to be arrays; only numerical path components that
@@ -178,8 +193,9 @@ std::set<FieldRef> generateFieldNameOrArrayIndexPathSet(const std::set<std::size
     return paths;
 }
 
-BoundsTightness applyWildcardIndexScanBoundsTightness(const IndexEntry& index,
-                                                      BoundsTightness tightnessIn) {
+BoundsTightness translateWildcardIndexBoundsAndTightness(const IndexEntry& index,
+                                                         BoundsTightness tightnessIn,
+                                                         OrderedIntervalList* oil) {
     // This method should only ever be called for a $** IndexEntry. We expect to be called during
     // planning, *before* finishWildcardIndexScanNode has been invoked. The IndexEntry should thus
     // only have a single keyPattern field and multikeyPath entry, but this is sufficient to
@@ -187,10 +203,24 @@ BoundsTightness applyWildcardIndexScanBoundsTightness(const IndexEntry& index,
     invariant(index.type == IndexType::INDEX_WILDCARD);
     invariant(index.keyPattern.nFields() == 1);
     invariant(index.multikeyPaths.size() == 1);
+    invariant(oil);
+
+    auto* intervals = &oil->intervals;
 
-    // If the tightness is already INEXACT_FETCH, any further changes are redundant.
-    if (tightnessIn == BoundsTightness::INEXACT_FETCH) {
-        return tightnessIn;
+    // If our bounds include any objects -- that is, anything in the range [{}, []) -- then we will
+    // need to use "subpath bounds", and include the additional interval ["path.","path/") on
+    // "$_path".
+    if (requiresSubpathBounds(*oil) && !intervals->front().isMinToMax()) {
+        // If we require subpath bounds (and aren't already using bounds from MinKey to MaxKey),
+        // then we must use [MinKey, MaxKey] bounds for the value.  For example, say our value
+        // bounds are [[MinKey, undefined), (null, MaxKey]] (the bounds generated by a {$ne: null}
+        // query). Our result set should include documents such as {a: {b: null}}. However, the
+        // index key for this object will be {"": "a.b", "": null}. This means if we were to use
+        // the original bounds, we would miss this document. We therefore expand the value bounds
+        // to included everything. We must also adjust the tightness to be inexact, to avoid false
+        // positives.
+        *intervals = {IndexBoundsBuilder::allValues()};
+        return BoundsTightness::INEXACT_FETCH;
     }
 
     // If the query passes through any array indices, we must always fetch and filter the documents.
@@ -245,5 +275,12 @@ bool validateNumericPathComponents(const MultikeyPaths& multikeyPaths,
     return arrayIndices[0] >= includePath->numParts();
 }
 
+bool requiresSubpathBounds(const OrderedIntervalList& oil) {
+    // For intersectize() to work, the OILs' names must match.
+    OrderedIntervalList allObjects = getAllObjectsOIL(oil.name);
+    IndexBoundsBuilder::intersectize(oil, &allObjects);
+    return !allObjects.intervals.empty();
+}
+
 }  // namespace wildcard_planning
 }  // namespace mongo