diff options
author | Hari Khalsa <hkhalsa@10gen.com> | 2014-04-24 15:27:18 -0400 |
---|---|---|
committer | Dan Pasette <dan@mongodb.com> | 2014-05-15 18:48:11 -0400 |
commit | faaffb7477e70be293f0e1141f4fff28ffaa2771 (patch) | |
tree | 44188e137f02e7feb5d895fcde1ee1c48878f725 | |
parent | 826903317459a630d3e0cd57653d65567a2144e3 (diff) | |
download | mongo-faaffb7477e70be293f0e1141f4fff28ffaa2771.tar.gz |
SERVER-13714 fix enumeration of non-top-level indexed negations
(cherry picked from commit 38711ac013df44b1bc928f868ee45a9ac93b3ffb)
-rw-r--r-- | src/mongo/db/query/plan_enumerator.cpp | 52 | ||||
-rw-r--r-- | src/mongo/db/query/plan_enumerator.h | 6 | ||||
-rw-r--r-- | src/mongo/db/query/query_planner_test.cpp | 30 |
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)); |