SERVER-14718 index negations below elemMatch value

5 files changed, 136 insertions, 24 deletions

diff --git a/src/mongo/db/matcher/expression_array.h b/src/mongo/db/matcher/expression_array.h
index 872f3d82b46..f543f33b712 100644
--- a/src/mongo/db/matcher/expression_array.h
+++ b/src/mongo/db/matcher/expression_array.h
@@ -123,6 +123,8 @@ namespace mongo {
 
         virtual void toBSON(BSONObjBuilder* out) const;
 
+        virtual std::vector<MatchExpression*>* getChildVector() { return &_subs; }
+
         virtual size_t numChildren() const { return _subs.size(); }
 
         virtual MatchExpression* getChild( size_t i ) const { return _subs[i]; }
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index ec81c5ffc66..b143f59e150 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -29,6 +29,7 @@
 #include "mongo/db/query/canonical_query.h"
 
 #include "mongo/db/jsobj.h"
+#include "mongo/db/matcher/expression_array.h"
 #include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/query/query_planner_common.h"
 
@@ -624,6 +625,12 @@ namespace mongo {
             // transfers ownership of its return value to 'nme'.
             nme->resetChild(normalizeTree(child));
         }
+        else if (MatchExpression::ELEM_MATCH_VALUE == root->matchType()) {
+            // Just normalize our children.
+            for (size_t i = 0; i < root->getChildVector()->size(); ++i) {
+                (*root->getChildVector())[i] = normalizeTree(root->getChild(i));
+            }
+        }
 
         return root;
     }
diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index d9e423f9e07..af8621090cd 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -266,6 +266,9 @@ namespace mongo {
             *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
         }
         else if (MatchExpression::NOT == expr->matchType()) {
+            // A NOT is indexed by virtue of its child. If we're here then the NOT's child
+            // must be a kind of node for which we can index negations. It can't be things like
+            // $mod, $regex, or $type.
             MatchExpression* child = expr->getChild(0);
 
             // If we have a NOT -> EXISTS, we must handle separately.
@@ -277,32 +280,20 @@ namespace mongo {
                 bob.appendNull("");
                 BSONObj dataObj = bob.obj();
                 oilOut->intervals.push_back(makeRangeInterval(dataObj, true, true));
-                
+
                 *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
                 return;
             }
-            else if (Indexability::nodeCanUseIndexOnOwnField(child)) {
-                // We have a NOT of a bounds-generating expression. Get the
-                // 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
-                // being because we have some deficiencies in tree normalization (see SERVER-12735).
-                //
-                // For example, we will get here if there is an index {a: 1}
-                // and the query is {a: {$elemMatch: {$not: {$gte: 6}}}}.
-                oilOut->intervals.push_back(allValues());
+
+            translate(child, 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;
             }
         }
diff --git a/src/mongo/db/query/indexability.h b/src/mongo/db/query/indexability.h
index 7791d4fad8b..7ab8007b0bf 100644
--- a/src/mongo/db/query/indexability.h
+++ b/src/mongo/db/query/indexability.h
@@ -71,11 +71,36 @@ namespace mongo {
             // considered "indexable" all children of the ELEM_MATCH_VALUE
             // must be "indexable" type expressions as well.
             for (size_t i = 0; i < me->numChildren(); i++) {
-                if (!isIndexOnOwnFieldTypeNode(me->getChild(i))) {
+                MatchExpression* child = me->getChild(i);
+
+                // Special case for NOT: If the child is a NOT, then it's the thing below
+                // the NOT that we care about.
+                if (MatchExpression::NOT == child->matchType()) {
+                    MatchExpression* notChild = child->getChild(0);
+
+                    if (MatchExpression::MOD == notChild->matchType() ||
+                        MatchExpression::REGEX == notChild->matchType() ||
+                        MatchExpression::TYPE_OPERATOR == notChild->matchType()) {
+                        // We can't index negations of this kind of expression node.
+                        return false;
+                    }
+
+                    // It's the child of the NOT that we check for indexability.
+                    if (!isIndexOnOwnFieldTypeNode(notChild)) {
+                        return false;
+                    }
+
+                    // Special handling for NOT has already been done; don't fall through.
+                    continue;
+                }
+
+                if (!isIndexOnOwnFieldTypeNode(child)) {
                     return false;
                 }
             }
 
+            // The entire ELEM_MATCH_VALUE is indexable since every one of its children
+            // is indexable.
             return true;
         }
 
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 85ef2db6a92..93b87844da6 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -3952,6 +3952,93 @@ namespace {
                                 "{ixscan: {pattern: {'a.b.endDate': 1}}}]}}}}");
     }
 
+    // SERVER-14718
+    TEST_F(QueryPlannerTest, NegationBelowElemMatchValue) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+        // true means multikey
+        addIndex(BSON("a" << 1), true);
+
+        runQuery(fromjson("{a: {$elemMatch: {$ne: 2}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {filter: {a:{$elemMatch:{$ne:2}}}, node: "
+                                "{ixscan: {filter: null, pattern: {a: 1}, bounds: "
+                                    "{a: [['MinKey',2,true,false], [2,'MaxKey',false,true]]}}}}}");
+    }
+
+    // SERVER-14718
+    TEST_F(QueryPlannerTest, AndWithNegationBelowElemMatchValue) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+        // true means multikey
+        addIndex(BSON("a" << 1), true);
+        addIndex(BSON("b" << 1), true);
+
+        runQuery(fromjson("{b: 10, a: {$elemMatch: {$not: {$gt: 4}}}}"));
+
+        // One solution using index on 'b' and one using index on 'a'.
+        assertNumSolutions(2U);
+        assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {b: 1}}}}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {a: 1}, bounds: {a: "
+                                    "[['MinKey',4,true,true],[Infinity,'MaxKey',false,true]]}}}}}");
+    }
+
+    // SERVER-14718
+    TEST_F(QueryPlannerTest, AndWithNegationBelowElemMatchValue2) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+        // true means multikey
+        addIndex(BSON("a" << 1), true);
+
+        runQuery(fromjson("{b: 10, a: {$elemMatch: {$not: {$gt: 4}, $gt: 2}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {a: 1}, bounds: "
+                                "{a: [[2, 4, false, true]]}}}}}");
+    }
+
+    // SERVER-14718
+    TEST_F(QueryPlannerTest, NegationBelowElemMatchValueBelowElemMatchObject) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+        // true means multikey
+        addIndex(BSON("a.b" << 1), true);
+
+        runQuery(fromjson("{a: {$elemMatch: {b: {$elemMatch: {$ne: 4}}}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {'a.b': 1}, bounds: "
+                                "{'a.b': [['MinKey',4,true,false],[4,'MaxKey',false,true]]}}}}}");
+    }
+
+    // SERVER-14718
+    TEST_F(QueryPlannerTest, NegationBelowElemMatchValueBelowOrBelowAnd) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+        // true means multikey
+        addIndex(BSON("a" << 1), true);
+        addIndex(BSON("b" << 1));
+
+        runQuery(fromjson("{c: 3, $or: [{a: {$elemMatch: {$ne: 4, $ne: 3}}}, {b: 5}]}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {filter: {c:3}, node: {or: {nodes: ["
+                                "{fetch: {node: {ixscan: {filter: null, pattern: {a: 1}, bounds: "
+                                    "{a: [['MinKey',3,true,false],"
+                                         "[3,4,false,false],"
+                                         "[4,'MaxKey',false,true]]}}}}}, "
+                                "{ixscan: {filter: null, pattern: {b: 1}, bounds: "
+                                    "{b: [[5,5,true,true]]}}}]}}}}");
+    }
+
+    // SERVER-14718
+    TEST_F(QueryPlannerTest, CantIndexNegationBelowElemMatchValue) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+        // true means multikey
+        addIndex(BSON("a" << 1), true);
+
+        runQuery(fromjson("{a: {$elemMatch: {$not: {$mod: [2, 0]}}}}"));
+
+        // There are no indexed solutions, because negations of $mod are not indexable.
+        assertNumSolutions(0);
+    }
+
     //
     // QueryPlannerParams option tests
     //