summaryrefslogtreecommitdiff
path: root/src/mongo/db/query
diff options
context:
space:
mode:
Diffstat (limited to 'src/mongo/db/query')
-rw-r--r--src/mongo/db/query/canonical_query.cpp8
-rw-r--r--src/mongo/db/query/canonical_query_test.cpp2
-rw-r--r--src/mongo/db/query/plan_cache_test.cpp23
-rw-r--r--src/mongo/db/query/plan_enumerator.cpp426
-rw-r--r--src/mongo/db/query/plan_enumerator.h72
-rw-r--r--src/mongo/db/query/query_planner.cpp43
-rw-r--r--src/mongo/db/query/query_planner_array_test.cpp407
-rw-r--r--src/mongo/db/query/query_planner_test.cpp280
8 files changed, 948 insertions, 313 deletions
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index 50bacf795b4..4ef22584133 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -33,6 +33,7 @@
#include "mongo/db/query/canonical_query.h"
#include "mongo/db/jsobj.h"
+#include "mongo/db/matcher/expression_array.h"
#include "mongo/db/namespace_string.h"
#include "mongo/db/operation_context.h"
#include "mongo/db/query/collation/collator_factory_interface.h"
@@ -335,6 +336,13 @@ MatchExpression* CanonicalQuery::normalizeTree(MatchExpression* root) {
// normalizeTree(...) takes ownership of 'child', and then
// transfers ownership of its return value to 'nme'.
nme->resetChild(normalizeTree(child));
+ } else if (MatchExpression::ELEM_MATCH_OBJECT == root->matchType()) {
+ // Normalize the rest of the tree hanging off this ELEM_MATCH_OBJECT node.
+ ElemMatchObjectMatchExpression* emome = static_cast<ElemMatchObjectMatchExpression*>(root);
+ auto child = emome->releaseChild();
+ // normalizeTree(...) takes ownership of 'child', and then
+ // transfers ownership of its return value to 'emome'.
+ emome->resetChild(std::unique_ptr<MatchExpression>(normalizeTree(child.release())));
} else if (MatchExpression::ELEM_MATCH_VALUE == root->matchType()) {
// Just normalize our children.
for (size_t i = 0; i < root->getChildVector()->size(); ++i) {
diff --git a/src/mongo/db/query/canonical_query_test.cpp b/src/mongo/db/query/canonical_query_test.cpp
index c7a1f2a05a2..292425167f7 100644
--- a/src/mongo/db/query/canonical_query_test.cpp
+++ b/src/mongo/db/query/canonical_query_test.cpp
@@ -521,6 +521,8 @@ TEST(CanonicalQueryTest, NormalizeQueryTree) {
// $in with 0 or more than 1 argument is not modified.
testNormalizeQuery("{a: {$in: []}}", "{a: {$in: []}}");
testNormalizeQuery("{a: {$in: [/./, 3]}}", "{a: {$in: [/./, 3]}}");
+ // Child of $elemMatch object expression is normalized.
+ testNormalizeQuery("{a: {$elemMatch: {$or: [{b: 1}]}}}", "{a: {$elemMatch: {b: 1}}}");
}
TEST(CanonicalQueryTest, NormalizeWithInPreservesTags) {
diff --git a/src/mongo/db/query/plan_cache_test.cpp b/src/mongo/db/query/plan_cache_test.cpp
index fd77c971357..752afe99fa2 100644
--- a/src/mongo/db/query/plan_cache_test.cpp
+++ b/src/mongo/db/query/plan_cache_test.cpp
@@ -1292,6 +1292,29 @@ TEST_F(CachePlanSelectionTest, ContainedOr) {
"]}}}}");
}
+TEST_F(CachePlanSelectionTest, ContainedOrAndIntersection) {
+ bool oldEnableHashIntersection = internalQueryPlannerEnableHashIntersection.load();
+ ON_BLOCK_EXIT([oldEnableHashIntersection] {
+ internalQueryPlannerEnableHashIntersection.store(oldEnableHashIntersection);
+ });
+ internalQueryPlannerEnableHashIntersection.store(true);
+ params.options = QueryPlannerParams::INCLUDE_COLLSCAN | QueryPlannerParams::INDEX_INTERSECTION;
+ addIndex(BSON("a" << 1 << "b" << 1), "a_1_b_1");
+ addIndex(BSON("c" << 1), "c_1");
+ BSONObj query = fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}");
+ runQuery(query);
+ assertPlanCacheRecoversSolution(
+ query,
+ "{fetch: {filter: null, node: {andHash: {nodes: ["
+ "{or: {nodes: ["
+ "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, "
+ "true]]}}},"
+ "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}]}},"
+ "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', "
+ "'MaxKey', true, true]]}}}"
+ "]}}}}");
+}
+
/**
* Test functions for computeKey. Cache keys are intentionally obfuscated and are
* meaningful only within the current lifetime of the server process. Users should treat plan
diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index 66c79e266c1..e85214cbaf5 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -288,20 +288,7 @@ std::string PlanEnumerator::dumpMemo() {
}
string PlanEnumerator::NodeAssignment::toString() const {
- if (NULL != pred) {
- mongoutils::str::stream ss;
- ss << "predicate\n";
- ss << "\tfirst indices: [";
- for (size_t i = 0; i < pred->indexes.size(); ++i) {
- ss << pred->indexes[i];
- if (i < pred->indexes.size() - 1)
- ss << ", ";
- }
- ss << "]\n";
- ss << "\tpred: " << pred->expr->toString();
- ss << "\tindexToAssign: " << pred->indexToAssign;
- return ss;
- } else if (NULL != andAssignment) {
+ if (NULL != andAssignment) {
mongoutils::str::stream ss;
ss << "AND enumstate counter " << andAssignment->counter;
for (size_t i = 0; i < andAssignment->choices.size(); ++i) {
@@ -396,69 +383,7 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) {
childContext.elemMatchExpr = context.elemMatchExpr;
childContext.outsidePreds = context.outsidePreds;
- if (Indexability::nodeCanUseIndexOnOwnField(node)) {
- // We only get here if our parent is an OR, an array operator, or we're the root.
-
- // If we have no index tag there are no indices we can use.
- if (NULL == node->getTag()) {
- return false;
- }
-
- RelevantTag* rt = static_cast<RelevantTag*>(node->getTag());
-
- size_t myMemoID;
- NodeAssignment* assign;
- allocateAssignment(node, &assign, &myMemoID);
-
- assign->pred.reset(new PredicateAssignment());
- assign->pred->expr = node;
-
- // 'expr' can use any index in 'first'.
- if (!rt->first.empty()) {
- assign->pred->indexes.swap(rt->first);
-
- for (auto index : assign->pred->indexes) {
- assign->pred->positions.push_back(0);
- assign->pred->orPushdowns.push_back(
- getOrPushdowns(index, childContext.outsidePreds));
- }
- }
-
- // 'expr' can use an index in 'notFirst' if an outside predicate can be combined with this
- // node and use the first position in the index.
- for (auto index : rt->notFirst) {
- auto orPushdowns = getOrPushdowns(index, childContext.outsidePreds);
- for (const auto& orPushdown : orPushdowns) {
- IndexTag* indexTag = static_cast<IndexTag*>(orPushdown.second.tagData.get());
- if (indexTag->pos == 0) {
- const auto indexEntry = (*_indices)[index];
- assign->pred->indexes.push_back(index);
- assign->pred->positions.push_back(getPosition(indexEntry, rt->path));
- assign->pred->orPushdowns.push_back(std::move(orPushdowns));
- break;
- }
- }
- }
-
- return !assign->pred->indexes.empty();
- } else if (Indexability::isBoundsGeneratingNot(node)) {
- 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()) {
+ 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) {
@@ -510,7 +435,9 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) {
assign->arrayAssignment.reset(aa.release());
return true;
- } else if (MatchExpression::AND == node->matchType()) {
+ } else if (Indexability::nodeCanUseIndexOnOwnField(node) ||
+ Indexability::isBoundsGeneratingNot(node) ||
+ (MatchExpression::AND == node->matchType())) {
// Map from idx id to children that have a pred over it.
// TODO: The index intersection logic could be simplified if we could iterate over these
@@ -701,12 +628,16 @@ bool PlanEnumerator::enumerateMandatoryIndex(const IndexToPredMap& idxToFirst,
if (compIt != idxToNotFirst.end()) {
// Assign any predicates on the non-leading index fields to 'indexAssign' that
// don't violate the intersecting or compounding rules for multikey indexes.
- assignMultikeySafePredicates(compIt->second, &indexAssign);
+ // We do not currently try to assign outside predicates to mandatory indexes.
+ const unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds{};
+ assignMultikeySafePredicates(compIt->second, outsidePreds, &indexAssign);
}
} else {
// Assign any predicates on the leading index field to 'indexAssign' that don't
// violate the intersecting rules for multikey indexes.
- assignMultikeySafePredicates(predsOverLeadingField, &indexAssign);
+ // We do not currently try to assign outside predicates to mandatory indexes.
+ const unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds{};
+ assignMultikeySafePredicates(predsOverLeadingField, outsidePreds, &indexAssign);
// Assign the mandatory predicate to 'thisIndex'. Due to how keys are generated for
// 2dsphere indexes, it is always safe to assign a predicate on a distinct path to
@@ -730,7 +661,9 @@ bool PlanEnumerator::enumerateMandatoryIndex(const IndexToPredMap& idxToFirst,
// Assign any predicates on the non-leading index fields to 'indexAssign' that
// don't violate the intersecting or compounding rules for multikey indexes.
- assignMultikeySafePredicates(predsOverNonLeadingFields, &indexAssign);
+ // We do not currently try to assign outside predicates to mandatory indexes.
+ assignMultikeySafePredicates(
+ predsOverNonLeadingFields, outsidePreds, &indexAssign);
}
}
} else if (thisIndex.multikey) {
@@ -812,75 +745,45 @@ bool PlanEnumerator::enumerateMandatoryIndex(const IndexToPredMap& idxToFirst,
// Output the assignments for this index.
AndEnumerableState state;
- state.assignments.push_back(indexAssign);
+ state.assignments.push_back(std::move(indexAssign));
andAssignment->choices.push_back(std::move(state));
}
return andAssignment->choices.size() > 0;
}
-std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> PlanEnumerator::getOrPushdowns(
- IndexID index, const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds) {
- std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> orPushdowns;
- const auto indexEntry = (*_indices)[index];
-
- // TODO SERVER-27904: Determine whether we can combine bounds.
- if (indexEntry.multikey) {
- return orPushdowns;
- }
+void PlanEnumerator::assignPredicate(
+ const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
+ MatchExpression* pred,
+ size_t position,
+ OneIndexAssignment* indexAssignment) {
+ if (outsidePreds.find(pred) != outsidePreds.end()) {
+ OrPushdownTag::Destination dest;
+ dest.route = outsidePreds.at(pred);
- for (const auto& pred : outsidePreds) {
- RelevantTag* relevantTag = static_cast<RelevantTag*>(pred.first->getTag());
- const auto& first = relevantTag->first;
- const auto& notFirst = relevantTag->notFirst;
- if ((std::find(first.begin(), first.end(), index) != first.end()) ||
- (std::find(notFirst.begin(), notFirst.end(), index) != notFirst.end())) {
- OrPushdownTag::Destination dest;
- dest.route = pred.second;
-
- // The index is not multikey, so we can combine bounds.
- const bool canCombineBounds = true;
-
- dest.tagData = stdx::make_unique<IndexTag>(
- index, getPosition(indexEntry, relevantTag->path), canCombineBounds);
- orPushdowns.emplace_back(pred.first, std::move(dest));
- }
+ // This method should only be called if we can combine bounds.
+ const bool canCombineBounds = true;
+ dest.tagData =
+ stdx::make_unique<IndexTag>(indexAssignment->index, position, canCombineBounds);
+ indexAssignment->orPushdowns.emplace_back(pred, std::move(dest));
+ } else {
+ indexAssignment->preds.push_back(pred);
+ indexAssignment->positions.push_back(position);
}
- return orPushdowns;
}
void PlanEnumerator::enumerateOneIndex(
- const IndexToPredMap& idxToFirst,
- const IndexToPredMap& idxToNotFirst,
+ IndexToPredMap idxToFirst,
+ IndexToPredMap idxToNotFirst,
const vector<MemoID>& subnodes,
- const unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds,
+ const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
AndAssignment* andAssignment) {
- // In the simplest case, an AndAssignment picks indices like a PredicateAssignment. To
- // be indexed we must only pick one index
- //
- // Complications:
- //
- // Some of our child predicates cannot be answered without an index. As such, the
- // indices that those predicates require must always be outputted. We store these
- // mandatory index assignments in 'mandatoryIndices'.
- //
- // Some of our children may not be predicates. We may have ORs (or array operators) as
- // children. If one of these subtrees provides an index, the AND is indexed. We store
- // these subtree choices in 'subnodes'.
- //
- // With the above two cases out of the way, we can focus on the remaining case: what to
- // do with our children that are leaf predicates.
- //
- // Guiding principles for index assignment to leaf predicates:
- //
- // 1. If we assign an index to {x:{$gt: 5}} we should assign the same index to
- // {x:{$lt: 50}}. That is, an index assignment should include all predicates
- // over its leading field.
- //
- // 2. If we have the index {a:1, b:1} and we assign it to {a: 5} we should assign it
- // to {b:7}, since with a predicate over the first field of the compound index,
- // the second field can be bounded as well. We may only assign indices to predicates
- // if all fields to the left of the index field are constrained.
+ // Each choice in the 'andAssignment' will consist of a single subnode to index (an OR or array
+ // operator) or a OneIndexAssignment. When creating a OneIndexAssignment, we ensure that at
+ // least one predicate can fulfill the first position in the key pattern, then we assign all
+ // predicates that can use the key pattern to the index. However, if the index is multikey,
+ // certain predicates cannot be combined/compounded. We determine which predicates can be
+ // combined/compounded using path-level multikey info, if available.
// First, add the state of using each subnode.
for (size_t i = 0; i < subnodes.size(); ++i) {
@@ -889,7 +792,31 @@ void PlanEnumerator::enumerateOneIndex(
andAssignment->choices.push_back(std::move(aes));
}
- // For each FIRST, we assign nodes to it.
+ // Next we create OneIndexAssignments.
+
+ // If there are any 'outsidePreds', then we are in a contained OR, and the 'outsidePreds' are
+ // AND-related to the contained OR and can be pushed inside of it. Add all of the 'outsidePreds'
+ // to 'idxToFirst' and 'idxToNotFirst'. We will treat them as normal predicates that can be
+ // assigned to the index, but we will ensure that any OneIndexAssignment contains some
+ // predicates from the current node.
+ for (const auto& pred : outsidePreds) {
+ invariant(pred.first->getTag());
+ RelevantTag* relevantTag = static_cast<RelevantTag*>(pred.first->getTag());
+ for (auto index : relevantTag->first) {
+ if (idxToFirst.find(index) != idxToFirst.end() ||
+ idxToNotFirst.find(index) != idxToNotFirst.end()) {
+ idxToFirst[index].push_back(pred.first);
+ }
+ }
+ for (auto index : relevantTag->notFirst) {
+ if (idxToFirst.find(index) != idxToFirst.end() ||
+ idxToNotFirst.find(index) != idxToNotFirst.end()) {
+ idxToNotFirst[index].push_back(pred.first);
+ }
+ }
+ }
+
+ // For each FIRST, we assign predicates to it.
for (IndexToPredMap::const_iterator it = idxToFirst.begin(); it != idxToFirst.end(); ++it) {
const IndexEntry& thisIndex = (*_indices)[it->first];
@@ -909,20 +836,24 @@ void PlanEnumerator::enumerateOneIndex(
for (const auto& firstAssignment : possibleFirstAssignments) {
OneIndexAssignment indexAssign;
indexAssign.index = it->first;
- indexAssign.preds = firstAssignment;
- indexAssign.positions.resize(indexAssign.preds.size(), 0);
+
+ for (auto pred : firstAssignment) {
+ assignPredicate(outsidePreds, pred, 0, &indexAssign);
+ }
auto compIt = idxToNotFirst.find(indexAssign.index);
if (compIt != idxToNotFirst.end()) {
// Assign any predicates on the non-leading index fields to 'indexAssign' that
// don't violate the intersecting and compounding rules for multikey indexes.
- assignMultikeySafePredicates(compIt->second, &indexAssign);
+ assignMultikeySafePredicates(compIt->second, outsidePreds, &indexAssign);
}
- AndEnumerableState state;
- state.assignments.push_back(indexAssign);
- // TODO SERVER-27904: Use outsidePreds to get orPushdowns.
- andAssignment->choices.push_back(std::move(state));
+ // Do not output this assignment if it consists only of outside predicates.
+ if (!indexAssign.preds.empty()) {
+ AndEnumerableState state;
+ state.assignments.push_back(std::move(indexAssign));
+ andAssignment->choices.push_back(std::move(state));
+ }
}
} else if (thisIndex.multikey) {
// We don't have path-level information about what causes 'thisIndex' to be multikey.
@@ -934,29 +865,34 @@ void PlanEnumerator::enumerateOneIndex(
OneIndexAssignment indexAssign;
indexAssign.index = it->first;
- indexAssign.preds.push_back(pred);
- indexAssign.positions.push_back(0);
+ assignPredicate(outsidePreds, pred, 0, &indexAssign);
// If there are any preds that could possibly be compounded with this
// index...
IndexToPredMap::const_iterator compIt = idxToNotFirst.find(indexAssign.index);
if (compIt != idxToNotFirst.end()) {
const vector<MatchExpression*>& couldCompound = compIt->second;
- vector<MatchExpression*> tryCompound;
+ vector<MatchExpression*> toCompound;
+ vector<MatchExpression*> assigned = indexAssign.preds;
+ for (const auto& orPushdown : indexAssign.orPushdowns) {
+ assigned.push_back(orPushdown.first);
+ }
+
+ // ...select the predicates that are safe to compound and compound them.
+ getMultikeyCompoundablePreds(assigned, couldCompound, &toCompound);
- // ...select the predicates that are safe to compound and try to
- // compound them.
- getMultikeyCompoundablePreds(indexAssign.preds, couldCompound, &tryCompound);
- if (tryCompound.size()) {
- compound(tryCompound, thisIndex, &indexAssign);
+ for (auto pred : toCompound) {
+ assignPredicate(
+ outsidePreds, pred, getPosition(thisIndex, pred), &indexAssign);
}
}
- // Output the assignment.
- AndEnumerableState state;
- state.assignments.push_back(indexAssign);
- // TODO SERVER-27904: Use outsidePreds to get orPushdowns.
- andAssignment->choices.push_back(std::move(state));
+ // Do not output this assignment if it consists only of outside predicates.
+ if (!indexAssign.preds.empty()) {
+ AndEnumerableState state;
+ state.assignments.push_back(std::move(indexAssign));
+ andAssignment->choices.push_back(std::move(state));
+ }
}
} else {
// The assignment we're filling out.
@@ -967,48 +903,26 @@ void PlanEnumerator::enumerateOneIndex(
// The index isn't multikey. Assign all preds to it. The planner will
// intersect the bounds.
- indexAssign.preds = it->second;
-
- // Since everything in assign.preds prefixes the index, they all go
- // at position '0' in the index, the first position.
- indexAssign.positions.resize(indexAssign.preds.size(), 0);
+ for (auto pred : it->second) {
+ assignPredicate(outsidePreds, pred, 0, &indexAssign);
+ }
// Find everything that could use assign.index but isn't a pred over
// the first field of that index.
IndexToPredMap::const_iterator compIt = idxToNotFirst.find(indexAssign.index);
if (compIt != idxToNotFirst.end()) {
- compound(compIt->second, thisIndex, &indexAssign);
+ for (auto pred : compIt->second) {
+ assignPredicate(outsidePreds, pred, getPosition(thisIndex, pred), &indexAssign);
+ }
}
// Output the assignment.
+ invariant(!indexAssign.preds.empty());
AndEnumerableState state;
- state.assignments.push_back(indexAssign);
- state.orPushdowns = getOrPushdowns(indexAssign.index, outsidePreds);
+ state.assignments.push_back(std::move(indexAssign));
andAssignment->choices.push_back(std::move(state));
}
}
-
- // If an outside predicate can fulfill the first position in the index, we can use it.
- for (const auto& index : idxToNotFirst) {
- if (idxToFirst.find(index.first) != idxToFirst.end()) {
- continue;
- }
- auto orPushdowns = getOrPushdowns(index.first, outsidePreds);
- for (const auto& orPushdown : orPushdowns) {
- IndexTag* indexTag = static_cast<IndexTag*>(orPushdown.second.tagData.get());
- if (indexTag->pos == 0) {
- OneIndexAssignment indexAssign;
- indexAssign.index = index.first;
- const IndexEntry& indexEntry = (*_indices)[index.first];
- compound(index.second, indexEntry, &indexAssign);
- AndEnumerableState state;
- state.assignments.push_back(indexAssign);
- state.orPushdowns = std::move(orPushdowns);
- andAssignment->choices.push_back(std::move(state));
- break;
- }
- }
- }
}
void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
@@ -1077,7 +991,7 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
oneAssign.positions.resize(kMaxSelfIntersections);
}
AndEnumerableState state;
- state.assignments.push_back(oneAssign);
+ state.assignments.push_back(std::move(oneAssign));
andAssignment->choices.push_back(std::move(state));
continue;
}
@@ -1085,7 +999,7 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
// Output (subnode, firstAssign) pairs.
for (size_t i = 0; i < subnodes.size(); ++i) {
AndEnumerableState indexAndSubnode;
- indexAndSubnode.assignments.push_back(oneAssign);
+ indexAndSubnode.assignments.push_back(std::move(oneAssign));
indexAndSubnode.subnodesToIndex.push_back(subnodes[i]);
andAssignment->choices.push_back(std::move(indexAndSubnode));
// Limit n^2.
@@ -1252,8 +1166,8 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
// We're done with this particular pair of indices; output
// the resulting assignments.
AndEnumerableState state;
- state.assignments.push_back(firstAssign);
- state.assignments.push_back(secondAssign);
+ state.assignments.push_back(std::move(firstAssign));
+ state.assignments.push_back(std::move(secondAssign));
andAssignment->choices.push_back(std::move(state));
}
}
@@ -1278,32 +1192,33 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
void PlanEnumerator::getIndexedPreds(MatchExpression* node,
PrepMemoContext context,
vector<MatchExpression*>* indexedPreds) {
- for (size_t i = 0; i < node->numChildren(); ++i) {
- MatchExpression* child = node->getChild(i);
- if (Indexability::nodeCanUseIndexOnOwnField(child)) {
- RelevantTag* rt = static_cast<RelevantTag*>(child->getTag());
- if (context.elemMatchExpr) {
- // If we're in an $elemMatch context, store the
- // innermost parent $elemMatch, as well as the
- // inner path prefix.
- rt->elemMatchExpr = context.elemMatchExpr;
- rt->pathPrefix = getPathPrefix(child->path().toString());
- } else {
- // We're not an $elemMatch context, so we should store
- // the prefix of the full path.
- rt->pathPrefix = getPathPrefix(rt->path);
- }
+ if (Indexability::nodeCanUseIndexOnOwnField(node)) {
+ RelevantTag* rt = static_cast<RelevantTag*>(node->getTag());
+ if (context.elemMatchExpr) {
+ // If we're in an $elemMatch context, store the
+ // innermost parent $elemMatch, as well as the
+ // inner path prefix.
+ rt->elemMatchExpr = context.elemMatchExpr;
+ rt->pathPrefix = getPathPrefix(node->path().toString());
+ } else {
+ // We're not an $elemMatch context, so we should store
+ // the prefix of the full path.
+ rt->pathPrefix = getPathPrefix(rt->path);
+ }
- // Output this as a pred that can use the index.
- indexedPreds->push_back(child);
- } else if (Indexability::isBoundsGeneratingNot(child)) {
- getIndexedPreds(child, context, indexedPreds);
- } else if (MatchExpression::ELEM_MATCH_OBJECT == child->matchType()) {
- PrepMemoContext childContext;
- childContext.elemMatchExpr = child;
- getIndexedPreds(child, childContext, indexedPreds);
- } else if (MatchExpression::AND == child->matchType()) {
- getIndexedPreds(child, context, indexedPreds);
+ // Output this as a pred that can use the index.
+ indexedPreds->push_back(node);
+ } else if (Indexability::isBoundsGeneratingNot(node)) {
+ getIndexedPreds(node->getChild(0), context, indexedPreds);
+ } else if (MatchExpression::ELEM_MATCH_OBJECT == node->matchType()) {
+ PrepMemoContext childContext;
+ childContext.elemMatchExpr = node;
+ for (size_t i = 0; i < node->numChildren(); ++i) {
+ getIndexedPreds(node->getChild(i), childContext, indexedPreds);
+ }
+ } else if (MatchExpression::AND == node->matchType()) {
+ for (size_t i = 0; i < node->numChildren(); ++i) {
+ getIndexedPreds(node->getChild(i), context, indexedPreds);
}
}
}
@@ -1422,8 +1337,10 @@ void PlanEnumerator::getMultikeyCompoundablePreds(const vector<MatchExpression*>
}
}
-void PlanEnumerator::assignMultikeySafePredicates(const std::vector<MatchExpression*>& couldAssign,
- OneIndexAssignment* indexAssignment) {
+void PlanEnumerator::assignMultikeySafePredicates(
+ const std::vector<MatchExpression*>& couldAssign,
+ const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
+ OneIndexAssignment* indexAssignment) {
invariant(indexAssignment);
invariant(indexAssignment->preds.size() == indexAssignment->positions.size());
@@ -1458,6 +1375,19 @@ void PlanEnumerator::assignMultikeySafePredicates(const std::vector<MatchExpress
}
}
+ // Update 'used' with all outside predicates already assigned to 'thisIndex';
+ for (const auto& orPushdown : indexAssignment->orPushdowns) {
+ invariant(orPushdown.first->getTag());
+ RelevantTag* rt = static_cast<RelevantTag*>(orPushdown.first->getTag());
+
+ // Any outside predicates already assigned to 'thisIndex' were assigned in the first
+ // position.
+ const size_t position = 0;
+ const bool shouldHaveAssigned =
+ canAssignPredToIndex(rt, thisIndex.multikeyPaths[position], &used);
+ invariant(shouldHaveAssigned);
+ }
+
size_t posInIdx = 0;
for (const auto keyElem : thisIndex.keyPattern) {
@@ -1474,8 +1404,7 @@ void PlanEnumerator::assignMultikeySafePredicates(const std::vector<MatchExpress
if (thisIndex.multikeyPaths[posInIdx].empty()) {
// We can always intersect or compound the bounds when no prefix of the queried path
// causes the index to be multikey.
- indexAssignment->preds.push_back(couldAssignPred);
- indexAssignment->positions.push_back(posInIdx);
+ assignPredicate(outsidePreds, couldAssignPred, posInIdx, indexAssignment);
continue;
}
@@ -1485,8 +1414,7 @@ void PlanEnumerator::assignMultikeySafePredicates(const std::vector<MatchExpress
canAssignPredToIndex(rt, thisIndex.multikeyPaths[posInIdx], &used);
if (shouldAssign) {
- indexAssignment->preds.push_back(couldAssignPred);
- indexAssignment->positions.push_back(posInIdx);
+ assignPredicate(outsidePreds, couldAssignPred, posInIdx, indexAssignment);
}
}
@@ -1536,10 +1464,12 @@ bool PlanEnumerator::alreadyCompounded(const set<MatchExpression*>& ixisectAssig
return false;
}
-size_t PlanEnumerator::getPosition(const IndexEntry& indexEntry, const std::string& path) {
+size_t PlanEnumerator::getPosition(const IndexEntry& indexEntry, MatchExpression* predicate) {
+ invariant(predicate->getTag());
+ RelevantTag* relevantTag = static_cast<RelevantTag*>(predicate->getTag());
size_t position = 0;
for (auto&& element : indexEntry.keyPattern) {
- if (element.fieldName() == path) {
+ if (element.fieldName() == relevantTag->path) {
return position;
}
++position;
@@ -1594,25 +1524,7 @@ void PlanEnumerator::tagMemo(size_t id) {
NodeAssignment* assign = _memo[id];
verify(NULL != assign);
- if (NULL != assign->pred) {
- PredicateAssignment* pa = assign->pred.get();
- verify(NULL == pa->expr->getTag());
- verify(pa->indexToAssign < pa->indexes.size());
- auto index = pa->indexes[pa->indexToAssign];
- auto position = pa->positions[pa->indexToAssign];
- const bool canCombineBounds = true;
- pa->expr->setTag(new IndexTag(index, position, canCombineBounds));
-
- // Add all OrPushdownTags for this index assignment.
- for (const auto& orPushdown : pa->orPushdowns[pa->indexToAssign]) {
- auto expr = orPushdown.first;
- if (!expr->getTag()) {
- expr->setTag(new OrPushdownTag());
- }
- OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(expr->getTag());
- orPushdownTag->addDestination(orPushdown.second.clone());
- }
- } else if (NULL != assign->orAssignment) {
+ if (NULL != assign->orAssignment) {
OrAssignment* oa = assign->orAssignment.get();
for (size_t i = 0; i < oa->subnodes.size(); ++i) {
tagMemo(oa->subnodes[i]);
@@ -1644,16 +1556,16 @@ void PlanEnumerator::tagMemo(size_t id) {
new IndexTag(assign.index, assign.positions[j], assign.canCombineBounds));
}
}
- }
- // Add all OrPushdownTags for this index assignment.
- for (const auto& orPushdown : aes.orPushdowns) {
- auto expr = orPushdown.first;
- if (!expr->getTag()) {
- expr->setTag(new OrPushdownTag());
+ // Add all OrPushdownTags for this index assignment.
+ for (const auto& orPushdown : assign.orPushdowns) {
+ auto expr = orPushdown.first;
+ if (!expr->getTag()) {
+ expr->setTag(new OrPushdownTag());
+ }
+ OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(expr->getTag());
+ orPushdownTag->addDestination(orPushdown.second.clone());
}
- OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(expr->getTag());
- orPushdownTag->addDestination(orPushdown.second.clone());
}
} else {
verify(0);
@@ -1664,15 +1576,7 @@ bool PlanEnumerator::nextMemo(size_t id) {
NodeAssignment* assign = _memo[id];
verify(NULL != assign);
- if (NULL != assign->pred) {
- PredicateAssignment* pa = assign->pred.get();
- pa->indexToAssign++;
- if (pa->indexToAssign >= pa->indexes.size()) {
- pa->indexToAssign = 0;
- return true;
- }
- return false;
- } else if (NULL != assign->orAssignment) {
+ if (NULL != assign->orAssignment) {
OrAssignment* oa = assign->orAssignment.get();
// Limit the number of OR enumerations
diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h
index 456464845b4..97a7549e6ad 100644
--- a/src/mongo/db/query/plan_enumerator.h
+++ b/src/mongo/db/query/plan_enumerator.h
@@ -167,11 +167,6 @@ private:
* The PlanEnumerator is interested in matching predicates and indices. Predicates
* are leaf nodes in the parse tree. {x:5}, {x: {$geoWithin:...}} are both predicates.
*
- * When we have simple predicates, like {x:5}, the task is easy: any indices prefixed
- * with 'x' can be used to answer the predicate. This is where the PredicateAssignment
- * is used.
- *
- * With logical operators, things are more complicated. Let's start with OR, the simplest.
* Since the output of an OR is the union of its results, each of its children must be
* indexed for the entire OR to be indexed. If each subtree of an OR is indexable, the
* OR is as well.
@@ -179,26 +174,11 @@ private:
* For an AND to be indexed, only one of its children must be indexed. AND is an
* intersection of its children, so each of its children describes a superset of the
* produced results.
+ *
+ * Leaf predicates are also given AND assignments, since they may index outside predicates that
+ * have been pushed down through OR nodes.
*/
- struct PredicateAssignment {
- PredicateAssignment() : indexToAssign(0) {}
-
- std::vector<IndexID> indexes;
- // Not owned here.
- MatchExpression* expr;
-
- // The position of 'expr' in each index key pattern.
- std::vector<size_t> positions;
-
- // Enumeration state. The current index in 'indexes', 'positions', and 'orPushdowns'.
- size_t indexToAssign;
-
- // The expressions that should receive an OrPushdownTag for each index.
- std::vector<std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>>>
- orPushdowns;
- };
-
struct OrAssignment {
OrAssignment() : counter(0) {}
@@ -224,14 +204,14 @@ private:
// multiple predicates are assigned to the same position of a multikey index, then the
// access planner should generate a self-intersection plan.
bool canCombineBounds = true;
+
+ // The expressions that should receive an OrPushdownTag when this assignment is made.
+ std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> orPushdowns;
};
struct AndEnumerableState {
std::vector<OneIndexAssignment> assignments;
std::vector<MemoID> subnodesToIndex;
-
- // The expressions that should receive an OrPushdownTag when this assignment is made.
- std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> orPushdowns;
};
struct AndAssignment {
@@ -253,7 +233,6 @@ private:
* Associates indices with predicates.
*/
struct NodeAssignment {
- std::unique_ptr<PredicateAssignment> pred;
std::unique_ptr<OrAssignment> orAssignment;
std::unique_ptr<AndAssignment> andAssignment;
std::unique_ptr<ArrayAssignment> arrayAssignment;
@@ -384,11 +363,18 @@ private:
* (b) a shared prefix of the paths X and Y inside the innermost $elemMatch causes the
* index to be multikey.
*
+ * If a predicate in 'couldAssign' is also in 'outsidePreds', then it is assumed to be an
+ * outside predicate that was pushed down through an OR. Instead of adding it to
+ * indexAssignment->preds, we add it to indexAssignment->orPushdowns. We create its
+ * OrPushdownTag using the route specified in 'outsidePreds'.
+ *
* This function should only be called if the index has path-level multikey information.
* Otherwise, getMultikeyCompoundablePreds() and compound() should be used instead.
*/
- void assignMultikeySafePredicates(const std::vector<MatchExpression*>& couldAssign,
- OneIndexAssignment* indexAssignment);
+ void assignMultikeySafePredicates(
+ const std::vector<MatchExpression*>& couldAssign,
+ const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
+ OneIndexAssignment* indexAssignment);
/**
* 'andAssignment' contains assignments that we've already committed to outputting,
@@ -431,10 +417,10 @@ private:
* and idxToNotFirst (and the sub-trees in 'subnodes'). Outputs the assignments into
* 'andAssignment'. The predicates in 'outsidePreds' are considered for OrPushdownTags.
*/
- void enumerateOneIndex(const IndexToPredMap& idxToFirst,
- const IndexToPredMap& idxToNotFirst,
+ void enumerateOneIndex(IndexToPredMap idxToFirst,
+ IndexToPredMap idxToNotFirst,
const std::vector<MemoID>& subnodes,
- const unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds,
+ const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
AndAssignment* andAssignment);
/**
@@ -460,17 +446,23 @@ private:
OneIndexAssignment* assign);
/**
- * Returns the position of 'path' in the key pattern for 'indexEntry'. It is illegal to call
- * this if 'path' is not present in the key pattern.
+ * Returns the position that 'predicate' can use in the key pattern for 'indexEntry'. It is
+ * illegal to call this if 'predicate' does not have a RelevantTag, or it cannot use the index.
*/
- size_t getPosition(const IndexEntry& indexEntry, const std::string& path);
+ size_t getPosition(const IndexEntry& indexEntry, MatchExpression* predicate);
- /*
- * Finds all predicates in 'outsidePreds' for which 'index' is relevant, and constructs
- * OrPushdownTag::Destinations for those predicates.
+ /**
+ * Adds 'pred' to 'indexAssignment', using 'position' as its position in the index. If 'pred' is
+ * in 'outsidePreds', then it is assumed to be an outside predicate that was pushed down through
+ * an OR. Instead of adding it to indexAssignment->preds, we add it to
+ * indexAssignment->orPushdowns. We create its OrPushdownTag using the route specified in
+ * 'outsidePreds'. 'pred' must be able to use the index and be multikey-safe to add to
+ * 'indexAssignment'.
*/
- std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> getOrPushdowns(
- IndexID index, const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds);
+ void assignPredicate(const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
+ MatchExpression* pred,
+ size_t position,
+ OneIndexAssignment* indexAssignment);
/**
* Return the memo entry for 'node'. Does some sanity checking to ensure that a memo entry
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 6d39ffe6934..0eb4b574820 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -299,6 +299,21 @@ Status QueryPlanner::cacheDataFromTaggedTree(const MatchExpression* const tagged
} else if (taggedTree->getTag() &&
taggedTree->getTag()->getType() == MatchExpression::TagData::Type::OrPushdownTag) {
OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(taggedTree->getTag());
+
+ if (orPushdownTag->getIndexTag()) {
+ const IndexTag* itag = static_cast<const IndexTag*>(orPushdownTag->getIndexTag());
+
+ if (is2DIndex(relevantIndices[itag->index].keyPattern)) {
+ return Status(ErrorCodes::BadValue, "can't cache '2d' index");
+ }
+
+ std::unique_ptr<IndexEntry> indexEntry =
+ stdx::make_unique<IndexEntry>(relevantIndices[itag->index]);
+ indexTree->entry.reset(indexEntry.release());
+ indexTree->index_pos = itag->pos;
+ indexTree->canCombineBounds = itag->canCombineBounds;
+ }
+
for (const auto& dest : orPushdownTag->getDestinations()) {
PlanCacheIndexTree::OrPushdown orPushdown;
orPushdown.route = dest.route;
@@ -355,16 +370,7 @@ Status QueryPlanner::tagAccordingToCache(MatchExpression* filter,
}
}
- if (NULL != indexTree->entry.get()) {
- map<StringData, size_t>::const_iterator got = indexMap.find(indexTree->entry->name);
- if (got == indexMap.end()) {
- mongoutils::str::stream ss;
- ss << "Did not find index with name: " << indexTree->entry->name;
- return Status(ErrorCodes::BadValue, ss);
- }
- filter->setTag(
- new IndexTag(got->second, indexTree->index_pos, indexTree->canCombineBounds));
- } else if (!indexTree->orPushdowns.empty()) {
+ if (!indexTree->orPushdowns.empty()) {
filter->setTag(new OrPushdownTag());
OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(filter->getTag());
for (const auto& orPushdown : indexTree->orPushdowns) {
@@ -382,6 +388,23 @@ Status QueryPlanner::tagAccordingToCache(MatchExpression* filter,
}
}
+ if (indexTree->entry.get()) {
+ map<StringData, size_t>::const_iterator got = indexMap.find(indexTree->entry->name);
+ if (got == indexMap.end()) {
+ mongoutils::str::stream ss;
+ ss << "Did not find index with name: " << indexTree->entry->name;
+ return Status(ErrorCodes::BadValue, ss);
+ }
+ if (filter->getTag()) {
+ OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(filter->getTag());
+ orPushdownTag->setIndexTag(
+ new IndexTag(got->second, indexTree->index_pos, indexTree->canCombineBounds));
+ } else {
+ filter->setTag(
+ new IndexTag(got->second, indexTree->index_pos, indexTree->canCombineBounds));
+ }
+ }
+
return Status::OK();
}
diff --git a/src/mongo/db/query/query_planner_array_test.cpp b/src/mongo/db/query/query_planner_array_test.cpp
index 0595e2f5ac7..87882799331 100644
--- a/src/mongo/db/query/query_planner_array_test.cpp
+++ b/src/mongo/db/query/query_planner_array_test.cpp
@@ -337,7 +337,7 @@ TEST_F(QueryPlannerTest, ElemMatchIndexedNestedOr) {
assertSolutionExists("{cscan: {dir: 1}}");
assertSolutionExists(
"{fetch: {filter: {$and: [{foo:1},"
- "{bar:{$elemMatch:{$or:[{baz:2}]}}}]}, "
+ "{bar:{$elemMatch:{baz:2}}}]}, "
"node: {ixscan: {pattern: {'bar.baz': 1}, "
"bounds: {'bar.baz': [[2,2,true,true]]}}}}}");
}
@@ -371,7 +371,7 @@ TEST_F(QueryPlannerTest, ElemMatchIndexedNestedOrMultikey) {
assertSolutionExists("{cscan: {dir: 1}}");
assertSolutionExists(
"{fetch: {filter: {$and: [{foo:1},"
- "{bar: {$elemMatch: {$or: [{$and: [{baz:2}, {z:3}]}]}}}]},"
+ "{bar: {$elemMatch: {$and: [{baz:2}, {z:3}]}}}]},"
"node: {ixscan: {pattern: {'bar.baz': 1, 'bar.z': 1}, "
"bounds: {'bar.baz': [[2,2,true,true]],"
"'bar.z': [[3,3,true,true]]}}}}}");
@@ -1651,4 +1651,407 @@ TEST_F(QueryPlannerTest, ContainedOrElemMatchPredicateIsLeadingFieldIndexInterse
assertSolutionExists("{cscan: {dir: 1}}}}");
}
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineLeadingFields) {
+ const bool multikey = true;
+ addIndex(BSON("a.b" << 1), multikey);
+ addIndex(BSON("a.c" << 1), multikey);
+
+ runQuery(
+ fromjson("{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: 6}]}]}}}"));
+ assertNumSolutions(3);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: "
+ "6}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[-Infinity, 10, true, true]]}}},"
+ "{ixscan: {pattern: {'a.c': 1}, bounds: {'a.c': [[6, 6, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: "
+ "6}]}]}}}, node: "
+ "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[0, Infinity, true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineLeadingFields) {
+ MultikeyPaths multikeyPaths{{0U}};
+ addIndex(BSON("a.b" << 1), multikeyPaths);
+ addIndex(BSON("a.c" << 1), multikeyPaths);
+
+ runQuery(
+ fromjson("{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: 6}]}]}}}"));
+ assertNumSolutions(3);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{$and: [{b: {$lte: 10}}, "
+ "{b: {$gte: 0}}]}, {c: 6}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[0, 10, true, true]]}}},"
+ "{ixscan: {pattern: {'a.c': 1}, bounds: {'a.c': [[6, 6, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: "
+ "6}]}]}}}, node: "
+ "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[0, Infinity, true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineLeadingFields) {
+ MultikeyPaths multikeyPaths{{0U}};
+ addIndex(BSON("a.b" << 1), multikeyPaths);
+ addIndex(BSON("a.c" << 1), multikeyPaths);
+
+ runQuery(
+ fromjson("{$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {$or: [{b: {$lte: "
+ "10}}, {c: 6}]}}}]}"));
+ assertNumSolutions(3);
+ assertSolutionExists(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {$or: [{b: "
+ "{$lte: 10}}, {c: 6}]}}}]}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[-Infinity, 10, true, true]]}}},"
+ "{ixscan: {pattern: {'a.c': 1}, bounds: {'a.c': [[6, 6, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {$or: [{b: "
+ "{$lte: 10}}, {c: 6}]}}}]}, node: "
+ "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[0, Infinity, true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCompoundFields) {
+ const bool multikey = true;
+ addIndex(BSON("a.b" << 1 << "a.c" << 1), multikey);
+ addIndex(BSON("a.d" << 1), multikey);
+
+ runQuery(fromjson("{a: {$elemMatch: {$and: [{b: 5}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+ assertNumSolutions(3);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {$or: [{$and: [{b: 5}, {c: 6}]}, {d: "
+ "7}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+ "[[6, 6, true, true]]}}},"
+ "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {$or: [{c: 6}, {d: 7}]}]}}}, node: "
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+ "[['MinKey', 'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCompoundFields) {
+ const bool multikey = true;
+ addIndex(BSON("a.b" << 1 << "a.c" << 1), multikey);
+ addIndex(BSON("a.d" << 1), multikey);
+
+ runQuery(fromjson(
+ "{$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {$or: [{c: 6}, {d: 7}]}}}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {$or: [{c: 6}, {d: "
+ "7}]}}}]}, node: "
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+ "[['MinKey', 'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundFields) {
+ MultikeyPaths multikeyPaths1{{0U}, {0U}};
+ MultikeyPaths multikeyPaths2{{0U}};
+ addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths1);
+ addIndex(BSON("a.d" << 1), multikeyPaths2);
+
+ runQuery(fromjson("{a: {$elemMatch: {$and: [{b: 5}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+ assertNumSolutions(3);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {$or: [{$and: [{b: 5}, {c: 6}]}, {d: "
+ "7}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+ "[[6, 6, true, true]]}}},"
+ "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {$or: [{c: 6}, {d: 7}]}]}}}, node: "
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+ "[['MinKey', 'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCompoundFields) {
+ MultikeyPaths multikeyPaths1{{0U}, {0U}};
+ MultikeyPaths multikeyPaths2{{0U}};
+ addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths1);
+ addIndex(BSON("a.d" << 1), multikeyPaths2);
+
+ runQuery(fromjson(
+ "{$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {$or: [{c: 6}, {d: 7}]}}}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {$or: [{c: 6}, {d: "
+ "7}]}}}]}, node: "
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+ "[['MinKey', 'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineLeadingOutsidePreds) {
+ const bool multikey = true;
+ addIndex(BSON("a.b" << 1 << "a.c" << 1), multikey);
+ addIndex(BSON("a.d" << 1), multikey);
+
+ runQuery(fromjson(
+ "{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+ assertNumSolutions(5);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+ "[{b: {$lte: 10}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[-Infinity, 10, true, true]], "
+ "'a.c': [[6, 6, true, true]]}}},"
+ "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+ "[{b: {$gte: 0}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[0, Infinity, true, true]], "
+ "'a.c': [[6, 6, true, true]]}}},"
+ "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, "
+ "{d: 7}]}]}}}, node: "
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[-Infinity, 10, true, true]], "
+ "'a.c': [['MinKey', 'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, "
+ "{d: 7}]}]}}}, node: "
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[0, Infinity, true, true]], "
+ "'a.c': [['MinKey', 'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineLeadingOutsidePreds) {
+ MultikeyPaths multikeyPaths1{{0U}, {0U}};
+ MultikeyPaths multikeyPaths2{{0U}};
+ addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths1);
+ addIndex(BSON("a.d" << 1), multikeyPaths2);
+
+ runQuery(fromjson(
+ "{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+ assertNumSolutions(3);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+ "[{b: {$lte: 10}}, {b: {$gte: 0}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[0, 10, true, true]], 'a.c': "
+ "[[6, 6, true, true]]}}},"
+ "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, "
+ "{d: 7}]}]}}}, node: "
+ "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[0, 10, true, true]], 'a.c': "
+ "[['MinKey', 'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineLeadingOutsidePreds) {
+ MultikeyPaths multikeyPaths{{0U}, {}};
+ addIndex(BSON("a.b" << 1 << "c" << 1), multikeyPaths);
+ addIndex(BSON("d" << 1));
+
+ runQuery(
+ fromjson("{$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: 10}}}}, "
+ "{$or: [{c: 6}, {d: 7}]}]}"));
+ assertNumSolutions(5);
+ assertSolutionExists(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+ "10}}}}]}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1, c: 1}, bounds: {'a.b': [[-Infinity, 10, true, true]], c: "
+ "[[6, 6, true, true]]}}},"
+ "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+ "10}}}}]}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.b': 1, c: 1}, bounds: {'a.b': [[0, Infinity, true, true]], c: [[6, "
+ "6, true, true]]}}},"
+ "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+ "10}}}}, {$or: [{c: 6}, {d: 7}]}]}, node: "
+ "{ixscan: {pattern: {'a.b': 1, c: 1}, bounds: {'a.b': [[-Infinity, 10, true, true]], c: "
+ "[['MinKey', 'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+ "10}}}}, {$or: [{c: 6}, {d: 7}]}]}, node: "
+ "{ixscan: {pattern: {'a.b': 1, c: 1}, bounds: {'a.b': [[0, Infinity, true, true]], c: "
+ "[['MinKey', 'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineTrailingOutsidePreds) {
+ const bool multikey = true;
+ addIndex(BSON("a.c" << 1 << "a.b" << 1), multikey);
+ addIndex(BSON("a.d" << 1), multikey);
+
+ runQuery(fromjson(
+ "{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+ assertNumSolutions(2);
+ std::vector<std::string> alternates;
+ alternates.push_back(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+ "[{b: {$gte: 0}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+ "[[0, Infinity, true, true]]}}},"
+ "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+ "]}}}}");
+ alternates.push_back(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+ "[{b: {$lte: 10}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+ "[[-Infinity, 10, true, true]]}}},"
+ "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertHasOneSolutionOf(alternates);
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineTrailingOutsidePreds) {
+ MultikeyPaths multikeyPaths1{{0U}, {0U}};
+ MultikeyPaths multikeyPaths2{{0U}};
+ addIndex(BSON("a.c" << 1 << "a.b" << 1), multikeyPaths1);
+ addIndex(BSON("a.d" << 1), multikeyPaths2);
+
+ runQuery(fromjson(
+ "{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+ "[{b: {$gte: 0}}, {b: {$lte: 10}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+ "[[0, 10, true, true]]}}},"
+ "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineTrailingOutsidePreds) {
+ MultikeyPaths multikeyPaths{{}, {0U}};
+ addIndex(BSON("c" << 1 << "a.b" << 1), multikeyPaths);
+ addIndex(BSON("d" << 1));
+
+ runQuery(
+ fromjson("{$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: 10}}}}, "
+ "{$or: [{c: 6}, {d: 7}]}]}"));
+ assertNumSolutions(2);
+ std::vector<std::string> alternates;
+ alternates.push_back(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+ "10}}}}]}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {c: 1, 'a.b': 1}, bounds: {c: [[6, 6, true, true]], 'a.b': [[0, "
+ "Infinity, true, true]]}}},"
+ "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ alternates.push_back(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+ "10}}}}]}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {c: 1, 'a.b': 1}, bounds: {c: [[6, 6, true, true]], 'a.b': "
+ "[[-Infinity, 10, true, true]]}}},"
+ "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertHasOneSolutionOf(alternates);
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCompoundTrailingOutsidePreds) {
+ const bool multikey = true;
+ addIndex(BSON("a.d" << 1 << "a.c" << 1 << "a.b" << 1), multikey);
+ addIndex(BSON("a.e" << 1), multikey);
+
+ runQuery(fromjson("{a: {$elemMatch: {$and: [{b: 5}, {c: 6}, {$or: [{d: 7}, {e: 8}]}]}}}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {c: 6}, {$or: [{$and: [{b: 5}, {c: 6}, "
+ "{d: 7}]}, {e: 8}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.d': 1, 'a.c': 1, 'a.b': 1}, bounds: {'a.d': [[7, 7, true, true]], "
+ "'a.c': [[6, 6, true, true]], 'a.b': [[5, 5, true, true]]}}},"
+ "{ixscan: {pattern: {'a.e': 1}, bounds: {'a.e': [[8, 8, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCompoundTrailingOutsidePreds) {
+ const bool multikey = true;
+ addIndex(BSON("d" << 1 << "a.c" << 1 << "a.b" << 1), multikey);
+ addIndex(BSON("e" << 1));
+
+ runQuery(fromjson(
+ "{$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}, {$or: [{d: 7}, {e: 8}]}]}"));
+ assertNumSolutions(2);
+ std::vector<std::string> alternates;
+ alternates.push_back(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}]}, node: "
+ "{or: {nodes: ["
+ "{ixscan: {pattern: {d: 1, 'a.c': 1, 'a.b': 1}, bounds: {d: [[7, 7, true, true]], 'a.c': "
+ "[[6, 6, true, true]], 'a.b': [['MinKey', 'MaxKey', true, true]]}}},"
+ "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+ "]}}}}");
+ alternates.push_back(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}]}, node: "
+ "{or: {nodes: ["
+ "{ixscan: {pattern: {d: 1, 'a.c': 1, 'a.b': 1}, bounds: {d: [[7, 7, true, true]], 'a.c': "
+ "[['MinKey', 'MaxKey', true, true]], 'a.b': [[5, 5, true, true]]}}},"
+ "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+ "]}}}}");
+ assertHasOneSolutionOf(alternates);
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundTrailingOutsidePreds) {
+ MultikeyPaths multikeyPaths1{{0U}, {0U}, {0U}};
+ MultikeyPaths multikeyPaths2{{0U}};
+ addIndex(BSON("a.d" << 1 << "a.c" << 1 << "a.b" << 1), multikeyPaths1);
+ addIndex(BSON("a.e" << 1), multikeyPaths2);
+
+ runQuery(fromjson("{a: {$elemMatch: {$and: [{b: 5}, {c: 6}, {$or: [{d: 7}, {e: 8}]}]}}}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {c: 6}, {$or: [{$and: [{b: 5}, {c: 6}, "
+ "{d: 7}]}, {e: 8}]}]}}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.d': 1, 'a.c': 1, 'a.b': 1}, bounds: {'a.d': [[7, 7, true, true]], "
+ "'a.c': [[6, 6, true, true]], 'a.b': [[5, 5, true, true]]}}},"
+ "{ixscan: {pattern: {'a.e': 1}, bounds: {'a.e': [[8, 8, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCompoundTrailingOutsidePreds) {
+ MultikeyPaths multikeyPaths{{}, {0U}, {0U}};
+ addIndex(BSON("d" << 1 << "a.c" << 1 << "a.b" << 1), multikeyPaths);
+ addIndex(BSON("e" << 1));
+
+ runQuery(fromjson(
+ "{$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}, {$or: [{d: 7}, {e: 8}]}]}"));
+ assertNumSolutions(2);
+ // When we have path-level multikey info, we ensure that predicates are assigned in order of
+ // index position.
+ assertSolutionExists(
+ "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}]}, node: "
+ "{or: {nodes: ["
+ "{ixscan: {pattern: {d: 1, 'a.c': 1, 'a.b': 1}, bounds: {d: [[7, 7, true, true]], 'a.c': "
+ "[[6, 6, true, true]], 'a.b': [['MinKey', 'MaxKey', true, true]]}}},"
+ "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
} // namespace
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 3e433b450fa..de3607bf0af 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -4989,4 +4989,284 @@ TEST_F(QueryPlannerTest, ContainedOrNotPredicateIsLeadingFieldInBothBranchesInde
assertSolutionExists("{cscan: {dir: 1}}}}");
}
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineLeadingFields) {
+ const bool multikey = true;
+ addIndex(BSON("a" << 1), multikey);
+ addIndex(BSON("b" << 1));
+
+ runQuery(fromjson("{$and: [{a: {$gte: 0}}, {$or: [{a: {$lte: 10}}, {b: 6}]}]}"));
+ assertNumSolutions(3);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {a: 1}, bounds: {a: [[-Infinity, 10, true, true]]}}},"
+ "{ixscan: {pattern: {b: 1}, bounds: {b: [[6, 6, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {$or: [{a: {$lte: 10}}, {b: 6}]}, node: "
+ "{ixscan: {pattern: {a: 1}, bounds: {a: [[0, Infinity, true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineLeadingFields) {
+ MultikeyPaths multikeyPaths{{0U}};
+ addIndex(BSON("a" << 1), multikeyPaths);
+ addIndex(BSON("b" << 1));
+
+ runQuery(fromjson("{$and: [{a: {$gte: 0}}, {$or: [{a: {$lte: 10}}, {b: 6}]}]}"));
+ assertNumSolutions(3);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {a: 1}, bounds: {a: [[-Infinity, 10, true, true]]}}},"
+ "{ixscan: {pattern: {b: 1}, bounds: {b: [[6, 6, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {$or: [{a: {$lte: 10}}, {b: 6}]}, node: "
+ "{ixscan: {pattern: {a: 1}, bounds: {a: [[0, Infinity, true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineLeadingFields) {
+ MultikeyPaths multikeyPaths{{}, {0U}};
+ addIndex(BSON("a" << 1 << "c" << 1), multikeyPaths);
+ addIndex(BSON("b" << 1));
+
+ runQuery(fromjson("{$and: [{a: {$gte: 0}}, {$or: [{a: {$lte: 10}}, {b: 6}]}]}"));
+ assertNumSolutions(3);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[0, 10, true, true]]}}},"
+ "{ixscan: {pattern: {b: 1}, bounds: {b: [[6, 6, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: {$or: [{a: {$lte: 10}}, {b: 6}]}, node: "
+ "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[0, Infinity, true, true]], c: [['MinKey', "
+ "'MaxKey', true, true]]}}}"
+ "}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCompoundFields) {
+ const bool multikey = true;
+ addIndex(BSON("b" << 1 << "a" << 1), multikey);
+ addIndex(BSON("c" << 1));
+
+ runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {a: 5}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, "
+ "true]]}}},"
+ "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCompoundFields) {
+ const bool multikey = true;
+ addIndex(BSON("a.c" << 1 << "a.b" << 1), multikey);
+ addIndex(BSON("d" << 1));
+
+ runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{'a.c': 6}, {d: 7}]}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+ "[['MinKey', 'MaxKey', true, true]]}}},"
+ "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundFields) {
+ MultikeyPaths multikeyPaths{{0U}, {0U}};
+ addIndex(BSON("b" << 1 << "a" << 1), multikeyPaths);
+ addIndex(BSON("c" << 1));
+
+ runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {a: 5}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, "
+ "true]]}}},"
+ "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundDottedFields) {
+ MultikeyPaths multikeyPaths{{1U}, {1U}};
+ addIndex(BSON("a.c" << 1 << "a.b" << 1), multikeyPaths);
+ addIndex(BSON("d" << 1));
+
+ runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{'a.c': 6}, {d: 7}]}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+ "[[5, 5, true, true]]}}},"
+ "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCompoundFields) {
+ MultikeyPaths multikeyPaths{{0U}, {0U}};
+ addIndex(BSON("a.c" << 1 << "a.b" << 1), multikeyPaths);
+ addIndex(BSON("d" << 1));
+
+ runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{'a.c': 6}, {d: 7}]}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+ "[['MinKey', 'MaxKey', true, true]]}}},"
+ "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineTrailingFields) {
+ const bool multikey = true;
+ addIndex(BSON("b" << 1 << "a" << 1), multikey);
+ addIndex(BSON("c" << 1));
+
+ runQuery(
+ fromjson("{$and: [{a: {$gte: 0}}, {$or: [{$and: [{a: {$lte: 10}}, {b: 6}]}, {c: 7}]}]}"));
+ assertNumSolutions(2);
+ std::vector<std::string> alternates;
+ alternates.push_back(
+ "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[-Infinity, 10, "
+ "true, true]]}}},"
+ "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ alternates.push_back(
+ "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[0, Infinity, "
+ "true, true]]}}},"
+ "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertHasOneSolutionOf(alternates);
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineTrailingFields) {
+ MultikeyPaths multikeyPaths{{}, {0U}};
+ addIndex(BSON("b" << 1 << "a" << 1), multikeyPaths);
+ addIndex(BSON("c" << 1));
+
+ runQuery(
+ fromjson("{$and: [{a: {$gte: 0}}, {$or: [{$and: [{a: {$lte: 10}}, {b: 6}]}, {c: 7}]}]}"));
+ assertNumSolutions(2);
+ std::vector<std::string> alternates;
+ alternates.push_back(
+ "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[-Infinity, 10, "
+ "true, true]]}}},"
+ "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ alternates.push_back(
+ "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[0, Infinity, "
+ "true, true]]}}},"
+ "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertHasOneSolutionOf(alternates);
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineTrailingFields) {
+ MultikeyPaths multikeyPaths{{0U}, {}};
+ addIndex(BSON("b" << 1 << "a" << 1), multikeyPaths);
+ addIndex(BSON("c" << 1));
+
+ runQuery(
+ fromjson("{$and: [{a: {$gte: 0}}, {$or: [{$and: [{a: {$lte: 10}}, {b: 6}]}, {c: 7}]}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[0, 10, true, "
+ "true]]}}},"
+ "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCompoundTrailingFields) {
+ const bool multikey = true;
+ addIndex(BSON("b" << 1 << "a" << 1 << "c" << 1), multikey);
+ addIndex(BSON("d" << 1));
+
+ runQuery(fromjson("{$and: [{a: 5}, {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {a: 5}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {b: 1, a: 1, c: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, "
+ "true]], c: [[7, 7, true, true]]}}},"
+ "{ixscan: {pattern: {d: 1}, bounds: {d: [[8, 8, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCompoundTrailingFields) {
+ const bool multikey = true;
+ addIndex(BSON("d" << 1 << "a.b" << 1 << "a.c" << 1), multikey);
+ addIndex(BSON("e" << 1));
+
+ runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{$and: [{'a.c': 6}, {d: 7}]}, {e: 8}]}]}"));
+ assertNumSolutions(2);
+ std::vector<std::string> alternates;
+ alternates.push_back(
+ "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {d: 1, 'a.b': 1, 'a.c': 1}, bounds: {d: [[7, 7, true, true]], 'a.b': "
+ "[['MinKey', 'MaxKey', true, true]], 'a.c': [[6, 6, true, true]]}}},"
+ "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+ "]}}}}");
+ alternates.push_back(
+ "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {d: 1, 'a.b': 1, 'a.c': 1}, bounds: {d: [[7, 7, true, true]], 'a.b': "
+ "[[5, 5, true, true]], 'a.c': [['MinKey', 'MaxKey', true, true]]}}},"
+ "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+ "]}}}}");
+ assertHasOneSolutionOf(alternates);
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundTrailingFields) {
+ MultikeyPaths multikeyPaths{{}, {0U}, {}};
+ addIndex(BSON("b" << 1 << "a" << 1 << "c" << 1), multikeyPaths);
+ addIndex(BSON("d" << 1));
+
+ runQuery(fromjson("{$and: [{a: 5}, {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}]}"));
+ assertNumSolutions(2);
+ assertSolutionExists(
+ "{fetch: {filter: {a: 5}, node: {or: {nodes: ["
+ "{ixscan: {pattern: {b: 1, a: 1, c: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, "
+ "true]], c: [[7, 7, true, true]]}}},"
+ "{ixscan: {pattern: {d: 1}, bounds: {d: [[8, 8, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCompoundTrailingFields) {
+ MultikeyPaths multikeyPaths{{}, {0U}, {0U}};
+ addIndex(BSON("d" << 1 << "a.b" << 1 << "a.c" << 1), multikeyPaths);
+ addIndex(BSON("e" << 1));
+
+ runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{$and: [{'a.c': 6}, {d: 7}]}, {e: 8}]}]}"));
+ assertNumSolutions(2);
+ // When we have path-level multikey info, we ensure that predicates are assigned in order of
+ // index position.
+ assertSolutionExists(
+ "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+ "{fetch: {filter: {'a.c': 6}, node: {ixscan: {pattern: {d: 1, 'a.b': 1, 'a.c': 1}, bounds: "
+ "{d: [[7, 7, true, true]], 'a.b': [[5, 5, true, true]], 'a.c': [['MinKey', 'MaxKey', true, "
+ "true]]}}}}},"
+ "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+ "]}}}}");
+ assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
} // namespace
View Lorry Controller Status