SERVER-13714 fix enumeration of non-top-level indexed negations

(cherry picked from commit 38711ac013df44b1bc928f868ee45a9ac93b3ffb)

3 files changed, 78 insertions, 10 deletions

diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index 68ea028ed73..584dce000b7 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -87,7 +87,9 @@ namespace mongo {
 
     std::string PlanEnumerator::dumpMemo() {
         mongoutils::str::stream ss;
-        for (size_t i = 0; i < _memo.size(); ++i) {
+
+        // Note that this needs to be kept in sync with allocateAssignment which assigns memo IDs.
+        for (size_t i = 1; i < _memo.size(); ++i) {
             ss << "[Node #" << i << "]: " << _memo[i]->toString() << "\n";
         }
         return ss;
@@ -152,11 +154,22 @@ namespace mongo {
         }
     }
 
+    PlanEnumerator::MemoID PlanEnumerator::memoIDForNode(MatchExpression* node) {
+        unordered_map<MatchExpression*, MemoID>::iterator it = _nodeToId.find(node);
+
+        if (_nodeToId.end() == it) {
+            error() << "Trying to look up memo entry for node, none found.";
+            invariant(0);
+        }
+
+        return it->second;
+    }
+
     bool PlanEnumerator::getNext(MatchExpression** tree) {
         if (_done) { return false; }
 
         // Tag with our first solution.
-        tagMemo(_nodeToId[_root]);
+        tagMemo(memoIDForNode(_root));
 
         *tree = _root->shallowClone();
         tagForSort(*tree);
@@ -164,7 +177,7 @@ namespace mongo {
 
         _root->resetTag();
         QLOG() << "Enumerator: memo just before moving:" << endl << dumpMemo();
-        _done = nextMemo(_nodeToId[_root]);
+        _done = nextMemo(memoIDForNode(_root));
         return true;
     }
 
@@ -172,9 +185,14 @@ namespace mongo {
     // Structure creation
     //
 
-    void PlanEnumerator::allocateAssignment(MatchExpression* expr, NodeAssignment** assign,
+    void PlanEnumerator::allocateAssignment(MatchExpression* expr,
+                                            NodeAssignment** assign,
                                             MemoID* id) {
-        size_t newID = _memo.size();
+        // We start at 1 so that the lookup of any entries not explicitly allocated
+        // will refer to an invalid memo slot.
+        size_t newID = _memo.size() + 1;
+
+        // Shouldn't be anything there already.
         verify(_nodeToId.end() == _nodeToId.find(expr));
         _nodeToId[expr] = newID;
         verify(_memo.end() == _memo.find(newID));
@@ -211,7 +229,22 @@ namespace mongo {
             return true;
         }
         else if (Indexability::isBoundsGeneratingNot(node)) {
-            return prepMemo(node->getChild(0), childContext);
+            bool childIndexable = prepMemo(node->getChild(0), childContext);
+            // If the child isn't indexable then bail out now.
+            if (!childIndexable) {
+                return false;
+            }
+
+            // Our parent node, if any exists, will expect a memo entry keyed on 'node'.  As such we
+            // have the node ID for 'node' just point to the memo created for the child that
+            // actually generates the bounds.
+            size_t myMemoID;
+            NodeAssignment* assign;
+            allocateAssignment(node, &assign, &myMemoID);
+            OrAssignment* orAssignment = new OrAssignment();
+            orAssignment->subnodes.push_back(memoIDForNode(node->getChild(0)));
+            assign->orAssignment.reset(orAssignment);
+            return true;
         }
         else if (MatchExpression::OR == node->matchType()) {
             // For an OR to be indexed, all its children must be indexed.
@@ -228,7 +261,7 @@ namespace mongo {
 
             OrAssignment* orAssignment = new OrAssignment();
             for (size_t i = 0; i < node->numChildren(); ++i) {
-                orAssignment->subnodes.push_back(_nodeToId[node->getChild(i)]);
+                orAssignment->subnodes.push_back(memoIDForNode(node->getChild(i)));
             }
             assign->orAssignment.reset(orAssignment);
             return true;
@@ -245,7 +278,7 @@ namespace mongo {
             // For an OR to be indexed, all its children must be indexed.
             for (size_t i = 0; i < node->numChildren(); ++i) {
                 if (prepMemo(node->getChild(i), childContext)) {
-                    aa->subnodes.push_back(_nodeToId[node->getChild(i)]);
+                    aa->subnodes.push_back(memoIDForNode(node->getChild(i)));
                 }
             }
 
@@ -818,8 +851,7 @@ namespace mongo {
                 // and for array nodes other than ELEM_MATCH_OBJECT or
                 // ELEM_MATCH_VALUE (e.g. ALL).
                 if (prepMemo(child, context)) {
-                    verify(_nodeToId.end() != _nodeToId.find(child));
-                    size_t childID = _nodeToId[child];
+                    size_t childID = memoIDForNode(child);
 
                     // Output the subnode.
                     if (mandatory) {
diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h
index 7f2f60108c6..65fb9d7b290 100644
--- a/src/mongo/db/query/plan_enumerator.h
+++ b/src/mongo/db/query/plan_enumerator.h
@@ -372,6 +372,12 @@ namespace mongo {
                       const IndexEntry& thisIndex,
                       OneIndexAssignment* assign);
 
+        /**
+         * Return the memo entry for 'node'.  Does some sanity checking to ensure that a memo entry
+         * actually exists.
+         */
+        MemoID memoIDForNode(MatchExpression* node);
+
         std::string dumpMemo();
 
         // Map from expression to its MemoID.
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 5523675d9c5..58550e88a1f 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -216,6 +216,12 @@ namespace {
             return solns.size();
         }
 
+        void dumpSolutions() {
+            mongoutils::str::stream ost;
+            dumpSolutions(ost);
+            log() << string(ost);
+        }
+
         void dumpSolutions(mongoutils::str::stream& ost) const {
             for (vector<QuerySolution*>::const_iterator it = solns.begin();
                     it != solns.end();
@@ -759,6 +765,30 @@ namespace {
         assertSolutionExists("{cscan: {dir: 1}}");
     }
 
+    // SERVER-13714.  A non-top-level indexable negation exposed a bug in plan enumeration.
+    TEST_F(QueryPlannerTest, NonTopLevelIndexedNegation) {
+        addIndex(BSON("state" << 1));
+        addIndex(BSON("is_draft" << 1));
+        addIndex(BSON("published_date" << 1));
+        addIndex(BSON("newsroom_id" << 1));
+
+        BSONObj queryObj = fromjson("{$and:[{$or:[{is_draft:false},{creator_id:1}]},"
+                                           "{$or:[{state:3,is_draft:false},"
+                                                 "{published_date:{$ne:null}}]},"
+                                           "{newsroom_id:{$in:[1]}}]}");
+        runQuery(queryObj);
+    }
+
+    TEST_F(QueryPlannerTest, NonTopLevelIndexedNegationMinQuery) {
+        addIndex(BSON("state" << 1));
+        addIndex(BSON("is_draft" << 1));
+        addIndex(BSON("published_date" << 1));
+
+        // This is the min query to reproduce SERVER-13714
+        BSONObj queryObj = fromjson("{$or:[{state:1, is_draft:1}, {published_date:{$ne: 1}}]}");
+        runQuery(queryObj);
+    }
+
     // SERVER-12594: we don't yet collapse an OR of ANDs into a single ixscan.
     TEST_F(QueryPlannerTest, OrOfAnd) {
         addIndex(BSON("a" << 1));