SERVER-12532 negated predicates can use an index

14 files changed, 551 insertions, 33 deletions

diff --git a/src/mongo/db/matcher/expression_tree.h b/src/mongo/db/matcher/expression_tree.h
index 95536faaa84..9105b0d2b79 100644
--- a/src/mongo/db/matcher/expression_tree.h
+++ b/src/mongo/db/matcher/expression_tree.h
@@ -175,8 +175,12 @@ namespace mongo {
 
         virtual MatchExpression* getChild( size_t i ) const { return _exp.get(); }
 
+        MatchExpression* releaseChild(void) { return _exp.release(); }
+
+        void resetChild( MatchExpression* newChild) { _exp.reset(newChild); }
+
     private:
-        boost::scoped_ptr<MatchExpression> _exp;
+        std::auto_ptr<MatchExpression> _exp;
     };
 
 }
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index 99e1fb02f1a..64e82db7678 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -315,7 +315,7 @@ namespace mongo {
 
     // static
     MatchExpression* CanonicalQuery::normalizeTree(MatchExpression* root) {
-        // root->isLogical() is true now.  We care about AND and OR.  Negations currently scare us.
+        // root->isLogical() is true now.  We care about AND, OR, and NOT. NOR currently scares us.
         if (MatchExpression::AND == root->matchType() || MatchExpression::OR == root->matchType()) {
             // We could have AND of AND of AND.  Make sure we clean up our children before merging
             // them.
@@ -359,6 +359,14 @@ namespace mongo {
                 return ret;
             }
         }
+        else if (MatchExpression::NOT == root->matchType()) {
+            // Normalize the rest of the tree hanging off this NOT node.
+            NotMatchExpression* nme = static_cast<NotMatchExpression*>(root);
+            MatchExpression* child = nme->releaseChild();
+            // normalizeTree(...) takes ownership of 'child', and then
+            // transfers ownership of its return value to 'nme'.
+            nme->resetChild(normalizeTree(child));
+        }
 
         return root;
     }
diff --git a/src/mongo/db/query/index_bounds.cpp b/src/mongo/db/query/index_bounds.cpp
index e024cf09f33..c6199b1d351 100644
--- a/src/mongo/db/query/index_bounds.cpp
+++ b/src/mongo/db/query/index_bounds.cpp
@@ -75,6 +75,62 @@ namespace mongo {
         return ss;
     }
 
+    // static
+    void OrderedIntervalList::complement() {
+        BSONObjBuilder minBob;
+        minBob.appendMinKey("");
+        BSONObj minObj = minBob.obj();
+
+        // We complement by scanning the entire range of BSON values
+        // from MinKey to MaxKey. The value from which we must begin
+        // the next complemented interval is kept in 'curBoundary'.
+        BSONElement curBoundary = minObj.firstElement();
+
+        // If 'curInclusive' is true, then 'curBoundary' is
+        // included in one of the original intervals, and hence
+        // should not be included in the complement (and vice-versa
+        // if 'curInclusive' is false).
+        bool curInclusive = false;
+
+        // We will build up a list of intervals that represents
+        // the inversion of those in the OIL.
+        vector<Interval> newIntervals;
+        for (size_t j = 0; j < intervals.size(); ++j) {
+            Interval curInt = intervals[j];
+            if (0 != curInt.start.woCompare(curBoundary) ||
+                (!curInclusive && !curInt.startInclusive)) {
+                // Make a new interval from 'curBoundary' to
+                // the start of 'curInterval'.
+                BSONObjBuilder intBob;
+                intBob.append(curBoundary);
+                intBob.append(curInt.start);
+                Interval newInt(intBob.obj(), !curInclusive, !curInt.startInclusive);
+                newIntervals.push_back(newInt);
+            }
+
+            // Reset the boundary for the next iteration.
+            curBoundary = curInt.end;
+            curInclusive = curInt.endInclusive;
+        }
+
+        // We may have to add a final interval which ends in MaxKey.
+        BSONObjBuilder maxBob;
+        maxBob.appendMaxKey("");
+        BSONObj maxObj = maxBob.obj();
+        BSONElement maxKey = maxObj.firstElement();
+        if (0 != maxKey.woCompare(curBoundary) || !curInclusive) {
+            BSONObjBuilder intBob;
+            intBob.append(curBoundary);
+            intBob.append(maxKey);
+            Interval newInt(intBob.obj(), !curInclusive, true);
+            newIntervals.push_back(newInt);
+        }
+
+        // Replace the old list of intervals with the new one.
+        intervals.clear();
+        intervals.insert(intervals.end(), newIntervals.begin(), newIntervals.end());
+    }
+
     string IndexBounds::toString() const {
         mongoutils::str::stream ss;
         if (isSimpleRange) {
diff --git a/src/mongo/db/query/index_bounds.h b/src/mongo/db/query/index_bounds.h
index 0d554a007e5..3a0e4fec3e9 100644
--- a/src/mongo/db/query/index_bounds.h
+++ b/src/mongo/db/query/index_bounds.h
@@ -51,6 +51,19 @@ namespace mongo {
 
         bool isValidFor(int expectedOrientation) const;
         std::string toString() const;
+
+        /**
+         * Complements the OIL. Used by the index bounds builder in order
+         * to create index bounds for $not predicates.
+         *
+         * Assumes the OIL is increasing, and therefore must be called prior to
+         * alignBounds(...).
+         *
+         * Example:
+         *   The complement of [3, 6), [8, 10] is [MinKey, 3), [6, 8), (20, MaxKey],
+         *   where this OIL has direction==1.
+         */
+        void complement();
     };
 
     /**
diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index b6bd05d6a91..bb03d5cf15a 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -254,10 +254,22 @@ namespace mongo {
             *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
         }
         else if (MatchExpression::NOT == expr->matchType()) {
-            // TODO: We could look at the child of 'expr', compute bounds, and take
-            // the complement.
-            oilOut->intervals.push_back(allValues());
-            *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
+            if (Indexability::nodeCanUseIndexOnOwnField(expr->getChild(0))) {
+                // 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();
+            }
+            else {
+                // XXX: 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());
+                *tightnessOut = INEXACT_FETCH;
+            }
         }
         else if (MatchExpression::EQ == expr->matchType()) {
             const EqualityMatchExpression* node = static_cast<const EqualityMatchExpression*>(expr);
diff --git a/src/mongo/db/query/index_bounds_builder_test.cpp b/src/mongo/db/query/index_bounds_builder_test.cpp
index 7712daad4e5..4be2f4dea22 100644
--- a/src/mongo/db/query/index_bounds_builder_test.cpp
+++ b/src/mongo/db/query/index_bounds_builder_test.cpp
@@ -989,4 +989,66 @@ namespace {
         ASSERT(!testSingleInterval(bounds));
     }
 
+    //
+    // Complementing bounds for negations
+    //
+
+    /**
+     * Get a BSONObj which represents the interval from
+     * MinKey to 'end'.
+     */
+    BSONObj minKeyIntObj(int end) {
+        BSONObjBuilder bob;
+        bob.appendMinKey("");
+        bob.appendNumber("", end);
+        return bob.obj();
+    }
+
+    /**
+     * Get a BSONObj which represents the interval from
+     * 'start' to MaxKey.
+     */
+    BSONObj maxKeyIntObj(int start) {
+        BSONObjBuilder bob;
+        bob.appendNumber("", start);
+        bob.appendMaxKey("");
+        return bob.obj();
+    }
+
+    // Expected oil: [MinKey, 3), (3, MaxKey]
+    TEST(IndexBoundsBuilderTest, SimpleNE) {
+        IndexEntry testIndex = IndexEntry(BSONObj());
+        BSONObj obj = BSON("a" << BSON("$ne" << 3));
+        auto_ptr<MatchExpression> expr(parseMatchExpression(obj));
+        BSONElement elt = obj.firstElement();
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(oil.intervals.size(), 2U);
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare(
+            Interval(minKeyIntObj(3), true, false)));
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[1].compare(
+            Interval(maxKeyIntObj(3), false, true)));
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+    }
+
+    TEST(IndexBoundsBuilderTest, IntersectWithNE) {
+        IndexEntry testIndex = IndexEntry(BSONObj());
+        vector<BSONObj> toIntersect;
+        toIntersect.push_back(fromjson("{a: {$gt: 1}}"));
+        toIntersect.push_back(fromjson("{a: {$ne: 2}}}"));
+        toIntersect.push_back(fromjson("{a: {$lte: 6}}"));
+        OrderedIntervalList oil;
+        IndexBoundsBuilder::BoundsTightness tightness;
+        testTranslateAndIntersect(toIntersect, &oil, &tightness);
+        ASSERT_EQUALS(oil.name, "a");
+        ASSERT_EQUALS(oil.intervals.size(), 2U);
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare(
+            Interval(BSON("" << 1 << "" << 2), false, false)));
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[1].compare(
+            Interval(BSON("" << 2 << "" << 6), false, true)));
+        ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+    }
+
 }  // namespace
diff --git a/src/mongo/db/query/index_bounds_test.cpp b/src/mongo/db/query/index_bounds_test.cpp
index a7687e5b10a..25503c74c34 100644
--- a/src/mongo/db/query/index_bounds_test.cpp
+++ b/src/mongo/db/query/index_bounds_test.cpp
@@ -119,6 +119,135 @@ namespace {
     }
 
     //
+    // Tests for OrderedIntervalList::complement()
+    //
+
+    /**
+     * Get a BSONObj which represents the interval from
+     * MinKey to 'end'.
+     */
+    BSONObj minKeyIntObj(int end) {
+        BSONObjBuilder bob;
+        bob.appendMinKey("");
+        bob.appendNumber("", end);
+        return bob.obj();
+    }
+
+    /**
+     * Get a BSONObj which represents the interval from
+     * 'start' to MaxKey.
+     */
+    BSONObj maxKeyIntObj(int start) {
+        BSONObjBuilder bob;
+        bob.appendNumber("", start);
+        bob.appendMaxKey("");
+        return bob.obj();
+    }
+
+    /**
+     * Get a BSONObj which represents the interval
+     * [MinKey, MaxKey].
+     */
+    BSONObj allValues() {
+        BSONObjBuilder bob;
+        bob.appendMinKey("");
+        bob.appendMaxKey("");
+        return bob.obj();
+    }
+
+    /**
+     * Test that if we complement the OIL twice,
+     * we get back the original OIL.
+     */
+     void testDoubleComplement(const OrderedIntervalList* oil) {
+         OrderedIntervalList clone;
+         for (size_t i = 0; i < oil->intervals.size(); ++i) {
+             clone.intervals.push_back(oil->intervals[i]);
+         }
+
+         clone.complement();
+         clone.complement();
+
+         ASSERT_EQUALS(oil->intervals.size(), clone.intervals.size());
+         for (size_t i = 0; i < oil->intervals.size(); ++i) {
+             ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                oil->intervals[i].compare(clone.intervals[i]));
+         }
+     }
+
+    // Complement of empty is [MinKey, MaxKey]
+    TEST(IndexBoundsTest, ComplementEmptyOil) {
+        OrderedIntervalList oil;
+        testDoubleComplement(&oil);
+        oil.complement();
+        ASSERT_EQUALS(oil.intervals.size(), 1U);
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare(
+            Interval(allValues(), true, true)));
+    }
+
+    // Complement of [MinKey, MaxKey] is empty
+    TEST(IndexBoundsTest, ComplementAllValues) {
+        OrderedIntervalList oil;
+        oil.intervals.push_back(Interval(allValues(), true, true));
+        testDoubleComplement(&oil);
+        oil.complement();
+        ASSERT_EQUALS(oil.intervals.size(), 0U);
+    }
+
+    // Complement of [MinKey, 3), [5, MaxKey) is
+    // [3, 5), [MaxKey, MaxKey].
+    TEST(IndexBoundsTest, ComplementRanges) {
+        OrderedIntervalList oil;
+        oil.intervals.push_back(Interval(minKeyIntObj(3), true, false));
+        oil.intervals.push_back(Interval(maxKeyIntObj(5), true, false));
+        testDoubleComplement(&oil);
+        oil.complement();
+        ASSERT_EQUALS(oil.intervals.size(), 2U);
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare(
+            Interval(BSON("" << 3 << "" << 5), true, false)));
+
+        // Make the interval [MaxKey, MaxKey].
+        BSONObjBuilder bob;
+        bob.appendMaxKey("");
+        bob.appendMaxKey("");
+        BSONObj maxKeyInt = bob.obj();
+
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[1].compare(
+            Interval(maxKeyInt, true, true)));
+    }
+
+    // Complement of (MinKey, 3), (3, MaxKey) is
+    // [MinKey, MinKey], [3, 3], [MaxKey, MaxKey].
+    TEST(IndexBoundsTest, ComplementRanges2) {
+        OrderedIntervalList oil;
+        oil.intervals.push_back(Interval(minKeyIntObj(3), false, false));
+        oil.intervals.push_back(Interval(maxKeyIntObj(3), false, false));
+        testDoubleComplement(&oil);
+        oil.complement();
+        ASSERT_EQUALS(oil.intervals.size(), 3U);
+
+        // First interval is [MinKey, MinKey]
+        BSONObjBuilder minBob;
+        minBob.appendMinKey("");
+        minBob.appendMinKey("");
+        BSONObj minObj = minBob.obj();
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare(
+            Interval(minObj, true, true)));
+
+        // Second is [3, 3]
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[1].compare(
+            Interval(BSON("" << 3 << "" << 3), true, true)));
+
+        // Third is [MaxKey, MaxKey]
+        BSONObjBuilder maxBob;
+        maxBob.appendMaxKey("");
+        maxBob.appendMaxKey("");
+        BSONObj maxObj = maxBob.obj();
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[2].compare(
+            Interval(maxObj, true, true)));
+    }
+
+    //
     // Iteration over
     //
 
diff --git a/src/mongo/db/query/indexability.h b/src/mongo/db/query/indexability.h
index b7668122971..6f25bda0469 100644
--- a/src/mongo/db/query/indexability.h
+++ b/src/mongo/db/query/indexability.h
@@ -82,7 +82,24 @@ namespace mongo {
         static bool arrayUsesIndexOnChildren(const MatchExpression* me) {
             return me->isArray() && (MatchExpression::ELEM_MATCH_OBJECT == me->matchType()
                                      || MatchExpression::ALL == me->matchType());
-        };
+        }
+
+        /**
+         * Returns true if 'me' is a NOT, and the child of the NOT can use
+         * an index on its own field.
+         */
+        static bool isBoundsGeneratingNot(const MatchExpression* me) {
+            return MatchExpression::NOT == me->matchType() &&
+                   nodeCanUseIndexOnOwnField(me->getChild(0));
+        }
+
+        /**
+         * Returns true if either 'me' is a bounds generating NOT,
+         * or 'me' can use an index on its own field.
+         */
+        static bool isBoundsGenerating(const MatchExpression* me) {
+            return isBoundsGeneratingNot(me) || nodeCanUseIndexOnOwnField(me);
+        }
     };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/interval.h b/src/mongo/db/query/interval.h
index 1b8e381bc17..eb20d12275d 100644
--- a/src/mongo/db/query/interval.h
+++ b/src/mongo/db/query/interval.h
@@ -81,7 +81,7 @@ namespace mongo {
          * The interval's extremities are closed or not depending on whether
          * 'start'/'endIncluded' are true or not.
          */
-        Interval(BSONObj base, bool startIncluded, bool endInclued);
+        Interval(BSONObj base, bool startIncluded, bool endIncluded);
 
         /** Sets the current interval to the given values (see constructor) */
         void init(BSONObj base, bool startIncluded, bool endIncluded);
diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index 9e8798db014..d4593a70d6d 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -199,6 +199,9 @@ namespace mongo {
             assign->pred->first.swap(rt->first);
             return true;
         }
+        else if (Indexability::isBoundsGeneratingNot(node)) {
+            return prepMemo(node->getChild(0), childContext);
+        }
         else if (MatchExpression::OR == node->matchType()) {
             // For an OR to be indexed, all its children must be indexed.
             for (size_t i = 0; i < node->numChildren(); ++i) {
@@ -724,6 +727,9 @@ namespace mongo {
                 // Output this as a pred that can use the index.
                 indexOut->push_back(child);
             }
+            else if (Indexability::isBoundsGeneratingNot(child)) {
+                partitionPreds(child, context, indexOut, subnodesOut);
+            }
             else if (MatchExpression::ELEM_MATCH_OBJECT == child->matchType()) {
                 PrepMemoContext childContext;
                 childContext.elemMatchExpr = child;
diff --git a/src/mongo/db/query/planner_access.cpp b/src/mongo/db/query/planner_access.cpp
index b357a8c6031..46e1fa1b084 100644
--- a/src/mongo/db/query/planner_access.cpp
+++ b/src/mongo/db/query/planner_access.cpp
@@ -498,7 +498,8 @@ namespace mongo {
             // If there's a tag it must be valid.
             verify(IndexTag::kNoIndex != ixtag->index);
 
-            // If the child can't use an index on its own field, it's indexed by virtue of one of
+            // If the child can't use an index on its own field (and the child is not a negation
+            // of a bounds-generating expression), then it's indexed by virtue of one of
             // its children having an index.
             //
             // If the child is an $elemMatch, we try to merge its child predicates into the
@@ -506,7 +507,11 @@ namespace mongo {
             //
             // NOTE: If the child is logical, it could possibly collapse into a single ixscan.  we
             // ignore this for now.
-            if (!Indexability::nodeCanUseIndexOnOwnField(child)) {
+            if (!Indexability::isBoundsGenerating(child)) {
+                // If we're here, then the child is indexed by virtue of its children.
+                // In most cases this means that we recursively build indexed data
+                // access on 'child'.
+
                 if (MatchExpression::AND == root->matchType() &&
                     MatchExpression::ELEM_MATCH_OBJECT == child->matchType()) {
                     // We have an AND with an ELEM_MATCH_OBJECT child. The plan enumerator produces
@@ -618,6 +623,13 @@ namespace mongo {
             // If we're here, we now know that 'child' can use an index directly and the index is
             // over the child's field.
 
+            // If 'child' is a NOT, then the tag we're interested in is on the NOT's
+            // child node.
+            if (MatchExpression::NOT == child->matchType()) {
+                ixtag = static_cast<IndexTag*>(child->getChild(0)->getTag());
+                invariant(IndexTag::kNoIndex != ixtag->index);
+            }
+
             // If the child we're looking at uses a different index than the current index scan, add
             // the current index scan to the output as we're done with it.  The index scan created
             // by the child then becomes our new current index scan.  Note that the current scan
@@ -964,7 +976,7 @@ namespace mongo {
                                                             MatchExpression* root,
                                                             bool inArrayOperator,
                                                             const vector<IndexEntry>& indices) {
-        if (root->isLogical()) {
+        if (root->isLogical() && !Indexability::isBoundsGeneratingNot(root)) {
             if (MatchExpression::AND == root->matchType()) {
                 // Takes ownership of root.
                 return buildIndexedAnd(query, root, inArrayOperator, indices);
@@ -990,7 +1002,7 @@ namespace mongo {
                 // No index to use here, not in the context of logical operator, so we're SOL.
                 return NULL;
             }
-            else if (Indexability::nodeCanUseIndexOnOwnField(root)) {
+            else if (Indexability::isBoundsGenerating(root)) {
                 // Make an index scan over the tagged index #.
                 IndexTag* tag = static_cast<IndexTag*>(root->getTag());
 
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index 1430724f917..95b9926e418 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -77,9 +77,9 @@ namespace mongo {
     void QueryPlannerIXSelect::getFields(MatchExpression* node,
                                          string prefix,
                                          unordered_set<string>* out) {
-        // Do not traverse tree beyond negation node
+        // Do not traverse tree beyond a NOR negation node
         MatchExpression::MatchType exprtype = node->matchType();
-        if (exprtype == MatchExpression::NOT || exprtype == MatchExpression::NOR) {
+        if (exprtype == MatchExpression::NOR) {
             return;
         }
 
@@ -161,6 +161,31 @@ namespace mongo {
                 return false;
             }
 
+            // There are restrictions on when we can use the index if
+            // the expression is a NOT.
+            if (exprtype == MatchExpression::NOT) {
+                // 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) {
+                    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;
+                }
+            }
+
             // We can only index EQ using text indices.  This is an artificial limitation imposed by
             // FTSSpec::getIndexPrefix() which will fail if there is not an EQ predicate on each
             // index prefix field of the text index.
@@ -273,16 +298,23 @@ namespace mongo {
     void QueryPlannerIXSelect::rateIndices(MatchExpression* node,
                                            string prefix,
                                            const vector<IndexEntry>& indices) {
-        // Do not traverse tree beyond negation node
+        // Do not traverse tree beyond logical NOR node
         MatchExpression::MatchType exprtype = node->matchType();
-        if (exprtype == MatchExpression::NOT || exprtype == MatchExpression::NOR) {
+        if (exprtype == MatchExpression::NOR) {
             return;
         }
 
         // Every indexable node is tagged even when no compatible index is
         // available.
-        if (Indexability::nodeCanUseIndexOnOwnField(node)) {
-            string fullPath = prefix + node->path().toString();
+        if (Indexability::isBoundsGenerating(node)) {
+            string fullPath;
+            if (MatchExpression::NOT == node->matchType()) {
+                fullPath = prefix + node->getChild(0)->path().toString();
+            }
+            else {
+                fullPath = prefix + node->path().toString();
+            }
+
             verify(NULL == node->getTag());
             RelevantTag* rt = new RelevantTag();
             node->setTag(rt);
@@ -302,6 +334,14 @@ namespace mongo {
                     }
                 }
             }
+
+            // If this is a NOT, we have to clone the tag and attach
+            // it to the NOT's child.
+            if (MatchExpression::NOT == node->matchType()) {
+                RelevantTag* childRt = static_cast<RelevantTag*>(rt->clone());
+                childRt->path = rt->path;
+                node->getChild(0)->setTag(childRt);
+            }
         }
         else if (Indexability::arrayUsesIndexOnChildren(node)) {
             // See comment in getFields about all/elemMatch and paths.
diff --git a/src/mongo/db/query/planner_ixselect_test.cpp b/src/mongo/db/query/planner_ixselect_test.cpp
index 1ee2183e3da..041167771e8 100644
--- a/src/mongo/db/query/planner_ixselect_test.cpp
+++ b/src/mongo/db/query/planner_ixselect_test.cpp
@@ -136,8 +136,8 @@ namespace {
      * $ne, $nin, $nor
      */
     TEST(QueryPlannerIXSelectTest, GetFieldsNegation) {
-        testGetFields("{a: {$ne: 1}}", "", "");
-        testGetFields("{a: {$nin: [1]}}", "", "");
+        testGetFields("{a: {$ne: 1}}", "", "a");
+        testGetFields("{a: {$nin: [1]}}", "", "a");
         testGetFields("{$nor: [{a: 1}, {b: 1}]}", "", "");
         testGetFields("{$and: [{a: 1}, {a: {$ne: 2}}]}", "", "a");
     }
@@ -146,8 +146,8 @@ namespace {
      * Array negation test cases for getFields
      */
     TEST(QueryPlannerIXSelectTest, GetFieldsArrayNegation) {
-        testGetFields("{a: {$elemMatch: {b: {$ne: 1}}}}", "", "");
-        testGetFields("{a: {$all: [{$elemMatch: {b: {$ne: 1}}}]}}", "", "");
+        testGetFields("{a: {$elemMatch: {b: {$ne: 1}}}}", "", "a.b");
+        testGetFields("{a: {$all: [{$elemMatch: {b: {$ne: 1}}}]}}", "", "a.b");
     }
 
     /**
@@ -252,18 +252,18 @@ namespace {
      * Negation test cases for rateIndices().
      */
     TEST(QueryPlannerIXSelectTest, RateIndicesTaggedNodePathsNegation) {
-        testRateIndicesTaggedNodePaths("{a: {$ne: 1}}", "", "");
-        testRateIndicesTaggedNodePaths("{a: {$nin: [1]}}", "", "");
+        testRateIndicesTaggedNodePaths("{a: {$ne: 1}}", "", "a,a");
+        testRateIndicesTaggedNodePaths("{a: {$nin: [1]}}", "", "a,a");
         testRateIndicesTaggedNodePaths("{$nor: [{a: 1}, {b: 1}]}", "", "");
-        testRateIndicesTaggedNodePaths("{$and: [{a: 1}, {a: {$ne: 2}}]}", "", "a");
+        testRateIndicesTaggedNodePaths("{$and: [{a: 1}, {a: {$ne: 2}}]}", "", "a,a,a");
     }
 
     /**
      * Array negation test cases for rateIndices().
      */
     TEST(QueryPlannerIXSelectTest, RateIndicesTaggedNodePathArrayNegation) {
-        testRateIndicesTaggedNodePaths("{a: {$elemMatch: {b: {$ne: 1}}}}", "", "");
-        testRateIndicesTaggedNodePaths("{a: {$all: [{$elemMatch: {b: {$ne: 1}}}]}}", "", "");
+        testRateIndicesTaggedNodePaths("{a: {$elemMatch: {b: {$ne: 1}}}}", "", "a.b,a.b");
+        testRateIndicesTaggedNodePaths("{a: {$all: [{$elemMatch: {b: {$ne: 1}}}]}}", "", "a.b,a.b");
     }
 
 }  // namespace
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 82d2ed5e4a4..02a9af3dbab 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -1693,15 +1693,20 @@ namespace {
 
         assertNumSolutions(2U);
         assertSolutionExists("{sort: {pattern: {a: 1}, limit: 0, node: {cscan: {dir: 1}}}}");
-        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: 1}}}}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: 1}, "
+                                "bounds: {a: [['MinKey',1,true,false], "
+                                             "[1,'MaxKey',false,true]]}}}}}");
     }
 
     TEST_F(QueryPlannerTest, NegationTopLevel) {
         addIndex(BSON("a" << 1));
         runQuerySortProj(fromjson("{a: {$ne: 1}}"), BSONObj(), BSONObj());
 
-        assertNumSolutions(1U);
+        assertNumSolutions(2U);
         assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: {pattern: {a:1}, "
+                                "bounds: {a: [['MinKey',1,true,false], "
+                                             "[1,'MaxKey',false,true]]}}}}}");
     }
 
     TEST_F(QueryPlannerTest, NegationOr) {
@@ -1726,7 +1731,8 @@ namespace {
 
         assertNumSolutions(2U);
         assertSolutionExists("{cscan: {dir: 1}}");
-        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: 1}}}}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: 1},"
+                                "bounds: {a: [[1,1,true,true]]}}}}}");
     }
 
     TEST_F(QueryPlannerTest, NegationAndIndexOnEqualityAndNegationBranches) {
@@ -1736,18 +1742,171 @@ namespace {
 
         assertNumSolutions(3U);
         assertSolutionExists("{cscan: {dir: 1}}");
-        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: 1}}}}}");
-        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {b: 1}}}}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: 1}, "
+                                "bounds: {a: [[1,1,true,true]]}}}}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {b: 1}, "
+                                "bounds: {b: [[2,2,true,true]]}}}}}");
     }
 
-    TEST_F(QueryPlannerTest, NegationAndIndexOnInEquality) {
+    TEST_F(QueryPlannerTest, NegationAndIndexOnInequality) {
         addIndex(BSON("b" << 1));
         runQuerySortProj(fromjson("{$and: [{a: 1}, {b: {$ne: 1}}]}"), BSONObj(), BSONObj());
 
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: {a:1}, node: {ixscan: {pattern: {b:1}, "
+                                "bounds: {b: [['MinKey',1,true,false], "
+                                             "[1,'MaxKey',false,true]]}}}}}");
+    }
+
+    // Negated regexes don't use the index.
+    TEST_F(QueryPlannerTest, NegationRegexPrefix) {
+        addIndex(BSON("i" << 1));
+        runQuery(fromjson("{i: {$not: /^a/}}"));
+
         assertNumSolutions(1U);
         assertSolutionExists("{cscan: {dir: 1}}");
     }
 
+    // Negated mods don't use the index
+    TEST_F(QueryPlannerTest, NegationMod) {
+        addIndex(BSON("i" << 1));
+        runQuery(fromjson("{i: {$not: {$mod: [2, 1]}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+    }
+
+    // Negated $elemMatch object won't use the index
+    TEST_F(QueryPlannerTest, NegationElemMatchObject) {
+        addIndex(BSON("i.j" << 1));
+        runQuery(fromjson("{i: {$not: {$elemMatch: {j: 1}}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+    }
+
+    // Negated $elemMatch object won't use the index
+    TEST_F(QueryPlannerTest, NegationElemMatchObject2) {
+        addIndex(BSON("i.j" << 1));
+        runQuery(fromjson("{i: {$not: {$elemMatch: {j: {$ne: 1}}}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+    }
+
+    // If there is a negation that can't use the index,
+    // ANDed with a predicate that can use the index, then
+    // we can still use the index for the latter predicate.
+    TEST_F(QueryPlannerTest, NegationRegexWithIndexablePred) {
+        addIndex(BSON("i" << 1));
+        runQuery(fromjson("{$and: [{i: {$not: /o/}}, {i: 2}]}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {i:1}, "
+                                "bounds: {i: [[2,2,true,true]]}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, NegationCantUseSparseIndex) {
+        // false means not multikey, true means sparse
+        addIndex(BSON("i" << 1), false, true);
+        runQuery(fromjson("{i: {$ne: 4}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+    }
+
+    TEST_F(QueryPlannerTest, NegationCantUseSparseIndex2) {
+        // false means not multikey, true means sparse
+        addIndex(BSON("i" << 1 << "j" << 1), false, true);
+        runQuery(fromjson("{i: 4, j: {$ne: 5}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {i:1,j:1}, bounds: "
+                                "{i: [[4,4,true,true]], j: [['MinKey','MaxKey',true,true]]}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, NegatedRangeStrGT) {
+        addIndex(BSON("i" << 1));
+        runQuery(fromjson("{i: {$not: {$gt: 'a'}}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: {pattern: {i:1}, "
+                                "bounds: {i: [['MinKey','a',true,true], "
+                                             "[{},'MaxKey',true,true]]}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, NegatedRangeStrGTE) {
+        addIndex(BSON("i" << 1));
+        runQuery(fromjson("{i: {$not: {$gte: 'a'}}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: {pattern: {i:1}, "
+                                "bounds: {i: [['MinKey','a',true,false], "
+                                             "[{},'MaxKey',true,true]]}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, NegatedRangeIntGT) {
+        addIndex(BSON("i" << 1));
+        runQuery(fromjson("{i: {$not: {$gt: 5}}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: {pattern: {i:1}, "
+                                "bounds: {i: [['MinKey',5,true,true], "
+                                             "[Infinity,'MaxKey',false,true]]}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, NegatedRangeIntGTE) {
+        addIndex(BSON("i" << 1));
+        runQuery(fromjson("{i: {$not: {$gte: 5}}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: {pattern: {i:1}, "
+                                "bounds: {i: [['MinKey',5,true,false], "
+                                             "[Infinity,'MaxKey',false,true]]}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, TwoNegatedRanges) {
+        addIndex(BSON("i" << 1));
+        runQuery(fromjson("{$and: [{i: {$not: {$lte: 'b'}}}, "
+                                  "{i: {$not: {$gte: 'f'}}}]}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: {pattern: {i:1}, "
+                                "bounds: {i: [['MinKey','',true,false], "
+                                             "['b','f',false,false], "
+                                             "[{},'MaxKey',true,true]]}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, AndWithNestedNE) {
+        addIndex(BSON("a" << 1));
+        runQuery(fromjson("{a: {$gt: -1, $lt: 1, $ne: 0}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: {pattern: {a:1}, "
+                                "bounds: {a: [[-1,0,false,false], "
+                                             "[0,1,false,false]]}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, NegatePredOnCompoundIndex) {
+        addIndex(BSON("x" << 1 << "a" << 1));
+        runQuery(fromjson("{x: 1, a: {$ne: 1}, b: {$ne: 2}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {x:1,a:1}, bounds: "
+                                "{x: [[1,1,true,true]], "
+                                 "a: [['MinKey',1,true,false], [1,'MaxKey',false,true]]}}}}}");
+    }
+
     //
     // 2D geo negation
     // The filter b != 1 is embedded in the geoNear2d node.