SERVER-13066 allow negations to use multikey indices

(cherry picked from commit 7aa932a23fd1c429d7b3d8cbd96d865526c149c9)

3 files changed, 59 insertions, 14 deletions

diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index 53e965bd987..71367e21488 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -274,6 +274,15 @@ namespace mongo {
                 // bounds of the NOT's child and then complement them.
                 translate(expr->getChild(0), elt, index, oilOut, tightnessOut);
                 oilOut->complement();
+
+                // If the index is multikey, it doesn't matter what the tightness
+                // of the child is, we must return INEXACT_FETCH. Consider a multikey
+                // index on 'a' with document {a: [1, 2, 3]} and query {a: {$ne: 3}}.
+                // If we treated the bounds [MinKey, 3), (3, MaxKey] as exact, then
+                // we would erroneously return the document!
+                if (index.multikey) {
+                    *tightnessOut = INEXACT_FETCH;
+                }
             }
             else {
                 // TODO: In the future we shouldn't need this. We handle this case for the time
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index 20a0ef48aaa..2500648d854 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -163,32 +163,31 @@ namespace mongo {
             // There are restrictions on when we can use the index if
             // the expression is a NOT.
             if (exprtype == MatchExpression::NOT) {
-                // Don't allow indexed NOT on special index types
-                // such as geo or text indices.
+                // Don't allow indexed NOT on special index types such as geo or text indices.
                 if (INDEX_BTREE != index.type) {
                     return false;
                 }
 
-                // Prevent negated preds from using sparse or
-                // multikey indices. We do so for sparse indices because
-                // we will fail to return the documents which do not contain
-                // the indexed fields.
-                //
-                // We avoid multikey indices because of the semantics of
-                // negations on multikey fields. For example, with multikey
-                // index {a:1}, the document {a: [1,2,3]} does *not* match
-                // the query {a: {$ne: 3}}. We'd mess this up if we used
-                // an index scan over [MinKey, 3) and (3, MaxKey] without
-                // a filter.
-                if (index.sparse || index.multikey) {
+                // Prevent negated preds from using sparse indices. Doing so would cause us to
+                // miss documents which do not contain the indexed fields.
+                if (index.sparse) {
                     return false;
                 }
+
                 // Can't index negations of MOD or REGEX
                 MatchExpression::MatchType childtype = node->getChild(0)->matchType();
                 if (MatchExpression::REGEX == childtype ||
                     MatchExpression::MOD == childtype) {
                     return false;
                 }
+
+                // If it's a negated $in, it can't have any REGEX's inside.
+                if (MatchExpression::MATCH_IN == childtype) {
+                    InMatchExpression* ime = static_cast<InMatchExpression*>(node->getChild(0));
+                    if (ime->getData().numRegexes() != 0) {
+                        return false;
+                    }
+                }
             }
 
             // We can only index EQ using text indices.  This is an artificial limitation imposed by
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index ba5a4565977..71ea89f9f06 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -2243,6 +2243,43 @@ namespace {
                                  "a: [['MinKey',1,true,false], [1,'MaxKey',false,true]]}}}}}");
     }
 
+    TEST_F(QueryPlannerTest, NEOnMultikeyIndex) {
+        // true means multikey
+        addIndex(BSON("a" << 1), true);
+        runQuery(fromjson("{a: {$ne: 3}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: {a:{$ne:3}}, node: {ixscan: {pattern: {a:1}, "
+                                 "bounds: {a: [['MinKey',3,true,false],"
+                                              "[3,'MaxKey',false,true]]}}}}}");
+    }
+
+    // In general, a negated $nin can make use of an index.
+    TEST_F(QueryPlannerTest, NinUsesMultikeyIndex) {
+        // true means multikey
+        addIndex(BSON("a" << 1), true);
+        runQuery(fromjson("{a: {$nin: [4, 10]}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: {a:{$nin:[4,10]}}, node: {ixscan: {pattern: {a:1}, "
+                                "bounds: {a: [['MinKey',4,true,false],"
+                                             "[4,10,false,false],"
+                                             "[10,'MaxKey',false,true]]}}}}}");
+    }
+
+    // But it can't if the $nin contains a regex because regex bounds can't
+    // be complemented.
+    TEST_F(QueryPlannerTest, NinCantUseMultikeyIndex) {
+        // true means multikey
+        addIndex(BSON("a" << 1), true);
+        runQuery(fromjson("{a: {$nin: [4, /foobar/]}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+    }
+
     //
     // 2D geo negation
     // The filter b != 1 is embedded in the geoNear2d node.