diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/mongo/db/exec/subplan.cpp | 2 | ||||
| -rw-r--r-- | src/mongo/db/matcher/expression.h | 2 | ||||
| -rw-r--r-- | src/mongo/db/matcher/expression_tree.h | 12 | ||||
| -rw-r--r-- | src/mongo/db/query/index_tag.cpp | 238 | ||||
| -rw-r--r-- | src/mongo/db/query/index_tag.h | 135 | ||||
| -rw-r--r-- | src/mongo/db/query/plan_cache.cpp | 16 | ||||
| -rw-r--r-- | src/mongo/db/query/plan_cache.h | 15 | ||||
| -rw-r--r-- | src/mongo/db/query/plan_cache_test.cpp | 15 | ||||
| -rw-r--r-- | src/mongo/db/query/plan_enumerator.cpp | 283 | ||||
| -rw-r--r-- | src/mongo/db/query/plan_enumerator.h | 59 | ||||
| -rw-r--r-- | src/mongo/db/query/planner_access.h | 3 | ||||
| -rw-r--r-- | src/mongo/db/query/query_planner.cpp | 45 | ||||
| -rw-r--r-- | src/mongo/db/query/query_planner_array_test.cpp | 198 | ||||
| -rw-r--r-- | src/mongo/db/query/query_planner_geo_test.cpp | 60 | ||||
| -rw-r--r-- | src/mongo/db/query/query_planner_test.cpp | 627 | ||||
| -rw-r--r-- | src/mongo/db/query/query_planner_text_test.cpp | 11 |
16 files changed, 1613 insertions, 108 deletions
diff --git a/src/mongo/db/exec/subplan.cpp b/src/mongo/db/exec/subplan.cpp index d7cbaed6db2..3c7122f3fe1 100644 --- a/src/mongo/db/exec/subplan.cpp +++ b/src/mongo/db/exec/subplan.cpp @@ -388,7 +388,7 @@ Status SubplanStage::choosePlanForSubqueries(PlanYieldPolicy* yieldPolicy) { } // Must do this before using the planner functionality. - sortUsingTags(_orExpression.get()); + prepareForAccessPlanning(_orExpression.get()); // Use the cached index assignments to build solnRoot. Takes ownership of '_orExpression'. QuerySolutionNode* solnRoot = QueryPlannerAccess::buildIndexedDataAccess( diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h index 95c0c8a3a9c..2f2b5a494a8 100644 --- a/src/mongo/db/matcher/expression.h +++ b/src/mongo/db/matcher/expression.h @@ -213,9 +213,11 @@ public: class TagData { public: + enum class Type { IndexTag, RelevantTag, OrPushdownTag }; virtual ~TagData() {} virtual void debugString(StringBuilder* builder) const = 0; virtual TagData* clone() const = 0; + virtual Type getType() const = 0; }; /** diff --git a/src/mongo/db/matcher/expression_tree.h b/src/mongo/db/matcher/expression_tree.h index 1e751f0f98c..d444f5b3ddc 100644 --- a/src/mongo/db/matcher/expression_tree.h +++ b/src/mongo/db/matcher/expression_tree.h @@ -65,12 +65,24 @@ public: return _expressions[i]; } + /* + * Replaces the ith child with nullptr, and releases ownership of the child. + */ virtual std::unique_ptr<MatchExpression> releaseChild(size_t i) { auto child = std::unique_ptr<MatchExpression>(_expressions[i]); _expressions[i] = nullptr; return child; } + /* + * Removes the ith child, and releases ownership of the child. + */ + virtual std::unique_ptr<MatchExpression> removeChild(size_t i) { + auto child = std::unique_ptr<MatchExpression>(_expressions[i]); + _expressions.erase(_expressions.begin() + i); + return child; + } + virtual std::vector<MatchExpression*>* getChildVector() { return &_expressions; } diff --git a/src/mongo/db/query/index_tag.cpp b/src/mongo/db/query/index_tag.cpp index c1dceec6b02..ad598152b78 100644 --- a/src/mongo/db/query/index_tag.cpp +++ b/src/mongo/db/query/index_tag.cpp @@ -28,33 +28,19 @@ #include "mongo/db/query/index_tag.h" +#include "mongo/db/matcher/expression_array.h" +#include "mongo/db/matcher/expression_tree.h" #include "mongo/db/query/indexability.h" +#include "mongo/platform/unordered_map.h" #include <algorithm> #include <limits> namespace mongo { -// TODO: Move out of the enumerator and into the planner. +using TagType = MatchExpression::TagData::Type; -const size_t IndexTag::kNoIndex = std::numeric_limits<size_t>::max(); - -void tagForSort(MatchExpression* tree) { - if (!Indexability::nodeCanUseIndexOnOwnField(tree)) { - size_t myTagValue = IndexTag::kNoIndex; - for (size_t i = 0; i < tree->numChildren(); ++i) { - MatchExpression* child = tree->getChild(i); - tagForSort(child); - IndexTag* childTag = static_cast<IndexTag*>(child->getTag()); - if (NULL != childTag) { - myTagValue = std::min(myTagValue, childTag->index); - } - } - if (myTagValue != IndexTag::kNoIndex) { - tree->setTag(new IndexTag(myTagValue)); - } - } -} +namespace { bool TagComparison(const MatchExpression* lhs, const MatchExpression* rhs) { IndexTag* lhsTag = static_cast<IndexTag*>(lhs->getTag()); @@ -100,6 +86,8 @@ bool TagComparison(const MatchExpression* lhs, const MatchExpression* rhs) { return lhs->matchType() < rhs->matchType(); } +// Sorts the tree using its IndexTag(s). Nodes that use the same index will sort so that they are +// adjacent to one another. void sortUsingTags(MatchExpression* tree) { for (size_t i = 0; i < tree->numChildren(); ++i) { sortUsingTags(tree->getChild(i)); @@ -110,4 +98,216 @@ void sortUsingTags(MatchExpression* tree) { } } +// Attaches 'node' to 'target'. If 'target' is an AND, adds 'node' as a child of 'target'. +// Otherwise, creates an AND that is a child of 'targetParent' at position 'targetPosition', and +// adds 'target' and 'node' as its children. Tags 'node' with 'tagData'. +void attachNode(MatchExpression* node, + MatchExpression* target, + OrMatchExpression* targetParent, + size_t targetPosition, + std::unique_ptr<MatchExpression::TagData> tagData) { + auto clone = node->shallowClone(); + if (clone->matchType() == MatchExpression::NOT) { + IndexTag* indexTag = static_cast<IndexTag*>(tagData.get()); + clone->setTag(new IndexTag(indexTag->index)); + clone->getChild(0)->setTag(tagData.release()); + } else { + clone->setTag(tagData.release()); + } + + if (MatchExpression::AND == target->matchType()) { + AndMatchExpression* andNode = static_cast<AndMatchExpression*>(target); + andNode->add(clone.release()); + } else { + std::unique_ptr<AndMatchExpression> andNode = stdx::make_unique<AndMatchExpression>(); + IndexTag* indexTag = static_cast<IndexTag*>(clone->getTag()); + andNode->setTag(new IndexTag(indexTag->index)); + andNode->add(target); + andNode->add(clone.release()); + targetParent->getChildVector()->operator[](targetPosition) = andNode.release(); + } +} + +// Partitions destinations according to the first element of the destination's route. Trims the +// first element off of each destination's route. +unordered_map<size_t, std::vector<OrPushdownTag::Destination>> partitionChildDestinations( + std::vector<OrPushdownTag::Destination> destinations) { + unordered_map<size_t, std::vector<OrPushdownTag::Destination>> childDestinations; + for (auto&& dest : destinations) { + invariant(!dest.route.empty()); + auto index = dest.route.front(); + dest.route.pop_front(); + childDestinations[index].push_back(std::move(dest)); + } + return childDestinations; +} + +// Finds the node within 'tree' that is an indexed OR, if one exists. +MatchExpression* getIndexedOr(MatchExpression* tree) { + if (MatchExpression::OR == tree->matchType() && tree->getTag()) { + return tree; + } + for (size_t i = 0; i < tree->numChildren(); ++i) { + if (auto indexedOrChild = getIndexedOr(tree->getChild(i))) { + return indexedOrChild; + } + } + return nullptr; +} + +// Pushes down 'node' along the routes in 'target' specified in 'destinations'. Each value in the +// route is the index of a child in an indexed OR. Returns true if 'node' is moved to every indexed +// descendant of 'target'. +bool pushdownNode(MatchExpression* node, + MatchExpression* target, + std::vector<OrPushdownTag::Destination> destinations) { + if (MatchExpression::OR == target->matchType()) { + OrMatchExpression* orNode = static_cast<OrMatchExpression*>(target); + bool moveToAllChildren = true; + auto childDestinationsMap = partitionChildDestinations(std::move(destinations)); + for (size_t i = 0; i < orNode->numChildren(); ++i) { + auto childDestinations = childDestinationsMap.find(i); + if (childDestinations == childDestinationsMap.end()) { + + // This child was not specified by any route in 'destinations'. + moveToAllChildren = false; + } else { + invariant(!childDestinations->second.empty()); + if (childDestinations->second[0].route.empty()) { + + // There should only be one destination if we have reached the end of a route. + // Otherwise, we started with duplicate routes. + invariant(childDestinations->second.size() == 1); + + // We have reached the position at which to attach 'node'. + attachNode(node, + orNode->getChild(i), + orNode, + i, + std::move(childDestinations->second[0].tagData)); + } else { + + // This child was specified by a non-trivial route in destinations, so we recur. + moveToAllChildren = pushdownNode(node, + orNode->getChild(i), + std::move(childDestinations->second)) && + moveToAllChildren; + } + } + } + return moveToAllChildren; + } + + if (MatchExpression::AND == target->matchType()) { + auto indexedOr = getIndexedOr(target); + invariant(indexedOr); + return pushdownNode(node, indexedOr, std::move(destinations)); + } + + MONGO_UNREACHABLE; +} + +// Populates 'out' with all descendants of 'node' that have OrPushdownTags, assuming the initial +// input is an ELEM_MATCH_OBJECT. +void getElemMatchOrPushdownDescendants(MatchExpression* node, std::vector<MatchExpression*>* out) { + if (node->getTag() && node->getTag()->getType() == TagType::OrPushdownTag) { + out->push_back(node); + } else if (node->matchType() == MatchExpression::ELEM_MATCH_OBJECT || + node->matchType() == MatchExpression::AND) { + for (size_t i = 0; i < node->numChildren(); ++i) { + getElemMatchOrPushdownDescendants(node->getChild(i), out); + } + } +} + +// Finds all the nodes in the tree with OrPushdownTags and copies them to the Destinations specified +// in the OrPushdownTag, tagging them with the TagData in the Destination. Removes the node from its +// current location if possible. +void resolveOrPushdowns(MatchExpression* tree) { + if (tree->numChildren() == 0) { + return; + } + if (MatchExpression::AND == tree->matchType()) { + AndMatchExpression* andNode = static_cast<AndMatchExpression*>(tree); + MatchExpression* indexedOr = getIndexedOr(andNode); + + for (size_t i = 0; i < andNode->numChildren(); ++i) { + auto child = andNode->getChild(i); + if (child->getTag() && child->getTag()->getType() == TagType::OrPushdownTag) { + invariant(indexedOr); + OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(child->getTag()); + auto destinations = orPushdownTag->releaseDestinations(); + auto indexTag = orPushdownTag->releaseIndexTag(); + child->setTag(nullptr); + if (pushdownNode(child, indexedOr, std::move(destinations)) && !indexTag) { + + // indexedOr can completely satisfy the predicate specified in child, so we can + // trim it. We could remove the child even if it had an index tag for this + // position, but that could make the index tagging of the tree wrong. + auto ownedChild = andNode->removeChild(i); + + // We removed child i, so decrement the child index. + --i; + } else { + child->setTag(indexTag.release()); + } + } else if (child->matchType() == MatchExpression::NOT && child->getChild(0)->getTag() && + child->getChild(0)->getTag()->getType() == TagType::OrPushdownTag) { + invariant(indexedOr); + OrPushdownTag* orPushdownTag = + static_cast<OrPushdownTag*>(child->getChild(0)->getTag()); + auto destinations = orPushdownTag->releaseDestinations(); + auto indexTag = orPushdownTag->releaseIndexTag(); + child->getChild(0)->setTag(nullptr); + + // Push down the NOT and its child. + if (pushdownNode(child, indexedOr, std::move(destinations)) && !indexTag) { + + // indexedOr can completely satisfy the predicate specified in child, so we can + // trim it. We could remove the child even if it had an index tag for this + // position, but that could make the index tagging of the tree wrong. + auto ownedChild = andNode->removeChild(i); + + // We removed child i, so decrement the child index. + --i; + } else { + child->getChild(0)->setTag(indexTag.release()); + } + } else if (child->matchType() == MatchExpression::ELEM_MATCH_OBJECT) { + + // Push down all descendants of child with OrPushdownTags. + std::vector<MatchExpression*> orPushdownDescendants; + getElemMatchOrPushdownDescendants(child, &orPushdownDescendants); + if (!orPushdownDescendants.empty()) { + invariant(indexedOr); + } + for (auto descendant : orPushdownDescendants) { + OrPushdownTag* orPushdownTag = + static_cast<OrPushdownTag*>(descendant->getTag()); + auto destinations = orPushdownTag->releaseDestinations(); + auto indexTag = orPushdownTag->releaseIndexTag(); + descendant->setTag(nullptr); + pushdownNode(descendant, indexedOr, std::move(destinations)); + descendant->setTag(indexTag.release()); + + // We cannot trim descendants of an $elemMatch object, since the filter must + // be applied in its entirety. + } + } + } + } + for (size_t i = 0; i < tree->numChildren(); ++i) { + resolveOrPushdowns(tree->getChild(i)); + } +} + +} // namespace + +const size_t IndexTag::kNoIndex = std::numeric_limits<size_t>::max(); + +void prepareForAccessPlanning(MatchExpression* tree) { + resolveOrPushdowns(tree); + sortUsingTags(tree); +} + } // namespace mongo diff --git a/src/mongo/db/query/index_tag.h b/src/mongo/db/query/index_tag.h index 7808b082d0f..b234fb1670f 100644 --- a/src/mongo/db/query/index_tag.h +++ b/src/mongo/db/query/index_tag.h @@ -28,6 +28,7 @@ #pragma once +#include <deque> #include <vector> #include "mongo/bson/util/builder.h" @@ -64,6 +65,10 @@ public: return new IndexTag(index, pos, canCombineBounds); } + virtual Type getType() const { + return Type::IndexTag; + } + // What index should we try to use for this leaf? size_t index = kNoIndex; @@ -130,21 +135,131 @@ public: ret->notFirst = notFirst; return ret; } + + virtual Type getType() const { + return Type::RelevantTag; + } }; /** - * Tags each node of the tree with the lowest numbered index that the sub-tree rooted at that - * node uses. - * - * Nodes that satisfy Indexability::nodeCanUseIndexOnOwnField are already tagged if there - * exists an index that that node can use. + * An OrPushdownTag indicates that this node is a predicate that can be used inside of a sibling + * indexed OR. */ -void tagForSort(MatchExpression* tree); +class OrPushdownTag final : public MatchExpression::TagData { +public: + /** + * A destination to which this predicate should be pushed down, consisting of a route through + * the sibling indexed OR, and the tag the predicate should receive after it is pushed down. + */ + struct Destination { -/** - * Sorts the tree using its IndexTag(s). Nodes that use the same index are adjacent to one - * another. + Destination clone() const { + Destination clone; + clone.route = route; + clone.tagData.reset(tagData->clone()); + return clone; + } + + void debugString(StringBuilder* builder) const { + *builder << " || Move to "; + bool firstPosition = true; + for (auto position : route) { + if (!firstPosition) { + *builder << ","; + } + firstPosition = false; + *builder << position; + } + tagData->debugString(builder); + } + + /** + * The route along which the predicate should be pushed down. This starts at the + * indexed OR sibling of the predicate. Each value in 'route' is the index of a child in + * an indexed OR. + * For example, if the MatchExpression tree is: + * AND + * / \ + * {a: 5} OR + * / \ + * AND {e: 9} + * / \ + * {b: 6} OR + * / \ + * {c: 7} {d: 8} + * and the predicate is {a: 5}, then the path {0, 1} means {a: 5} should be + * AND-combined with {d: 8}. + */ + std::deque<size_t> route; + + // The TagData that the predicate should be tagged with after it is pushed down. + std::unique_ptr<MatchExpression::TagData> tagData; + }; + + void debugString(StringBuilder* builder) const override { + if (_indexTag) { + _indexTag->debugString(builder); + } + for (const auto& dest : _destinations) { + dest.debugString(builder); + } + } + + MatchExpression::TagData* clone() const override { + std::unique_ptr<OrPushdownTag> clone = stdx::make_unique<OrPushdownTag>(); + for (const auto& dest : _destinations) { + clone->addDestination(dest.clone()); + } + if (_indexTag) { + clone->setIndexTag(_indexTag->clone()); + } + return clone.release(); + } + + Type getType() const override { + return Type::OrPushdownTag; + } + + void addDestination(Destination dest) { + _destinations.push_back(std::move(dest)); + } + + const std::vector<Destination>& getDestinations() const { + return _destinations; + } + + /** + * Releases ownership of the destinations. + */ + std::vector<Destination> releaseDestinations() { + std::vector<Destination> destinations; + destinations.swap(_destinations); + return destinations; + } + + void setIndexTag(MatchExpression::TagData* indexTag) { + _indexTag.reset(indexTag); + } + + const MatchExpression::TagData* getIndexTag() const { + return _indexTag.get(); + } + + std::unique_ptr<MatchExpression::TagData> releaseIndexTag() { + return std::move(_indexTag); + } + +private: + std::vector<Destination> _destinations; + + // The index tag the predicate should receive at its current position in the tree. + std::unique_ptr<MatchExpression::TagData> _indexTag; +}; + +/* + * Reorders the nodes according to their tags as needed for access planning. 'tree' should be a + * tagged MatchExpression tree in canonical order. */ -void sortUsingTags(MatchExpression* tree); +void prepareForAccessPlanning(MatchExpression* tree); } // namespace mongo diff --git a/src/mongo/db/query/plan_cache.cpp b/src/mongo/db/query/plan_cache.cpp index 4f926e70664..debb7c80fdf 100644 --- a/src/mongo/db/query/plan_cache.cpp +++ b/src/mongo/db/query/plan_cache.cpp @@ -411,6 +411,7 @@ PlanCacheIndexTree* PlanCacheIndexTree::clone() const { root->setIndexEntry(*entry.get()); root->canCombineBounds = canCombineBounds; } + root->orPushdowns = orPushdowns; for (std::vector<PlanCacheIndexTree*>::const_iterator it = children.begin(); it != children.end(); @@ -435,9 +436,22 @@ std::string PlanCacheIndexTree::toString(int indents) const { } else { result << std::string(3 * indents, '-') << "Leaf "; if (NULL != entry.get()) { - result << entry->keyPattern.toString() << ", pos: " << index_pos << ", can combine? " + result << entry->name << ", pos: " << index_pos << ", can combine? " << canCombineBounds; } + for (const auto& orPushdown : orPushdowns) { + result << "Move to "; + bool firstPosition = true; + for (auto position : orPushdown.route) { + if (!firstPosition) { + result << ","; + } + firstPosition = false; + result << position; + } + result << ": " << orPushdown.indexName << ", pos: " << orPushdown.position + << ", can combine? " << orPushdown.canCombineBounds << ". "; + } result << '\n'; } return result.str(); diff --git a/src/mongo/db/query/plan_cache.h b/src/mongo/db/query/plan_cache.h index 16aaff994a2..31a09fe6aaa 100644 --- a/src/mongo/db/query/plan_cache.h +++ b/src/mongo/db/query/plan_cache.h @@ -86,6 +86,19 @@ typedef std::string PlanID; * This is done by QueryPlanner::tagAccordingToCache. */ struct PlanCacheIndexTree { + + /** + * An OrPushdown is the cached version of an OrPushdownTag::Destination. It indicates that this + * node is a predicate that can be used inside of a sibling indexed OR, to tighten index bounds + * or satisfy the first field in the index. + */ + struct OrPushdown { + std::string indexName; + size_t position; + bool canCombineBounds; + std::deque<size_t> route; + }; + PlanCacheIndexTree() : entry(nullptr), index_pos(0), canCombineBounds(true) {} ~PlanCacheIndexTree() { @@ -123,6 +136,8 @@ struct PlanCacheIndexTree { // and is used to ensure that bounds are correctly intersected and/or compounded when a query is // planned from the plan cache. bool canCombineBounds; + + std::vector<OrPushdown> orPushdowns; }; /** diff --git a/src/mongo/db/query/plan_cache_test.cpp b/src/mongo/db/query/plan_cache_test.cpp index b4d8f0f9ef0..fd77c971357 100644 --- a/src/mongo/db/query/plan_cache_test.cpp +++ b/src/mongo/db/query/plan_cache_test.cpp @@ -1277,6 +1277,21 @@ TEST_F(CachePlanSelectionTest, MatchingCollation) { "{fetch: {node: {ixscan: {pattern: {x: 1}}}}}"); } +TEST_F(CachePlanSelectionTest, ContainedOr) { + addIndex(BSON("b" << 1 << "a" << 1), "b_1_a_1"); + addIndex(BSON("c" << 1 << "a" << 1), "c_1_a_1"); + BSONObj query = fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}"); + runQuery(query); + assertPlanCacheRecoversSolution( + query, + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, " + "true]]}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 5, 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 789cd405607..66c79e266c1 100644 --- a/src/mongo/db/query/plan_enumerator.cpp +++ b/src/mongo/db/query/plan_enumerator.cpp @@ -214,6 +214,40 @@ bool canAssignPredToIndex(const RelevantTag* rt, return true; } +/** + * Tags each node of the tree with the lowest numbered index that the sub-tree rooted at that + * node uses. + * + * Nodes that satisfy Indexability::nodeCanUseIndexOnOwnField are already tagged if there + * exists an index that that node can use. + */ +void tagForSort(MatchExpression* tree) { + if (!Indexability::nodeCanUseIndexOnOwnField(tree)) { + size_t myTagValue = IndexTag::kNoIndex; + for (size_t i = 0; i < tree->numChildren(); ++i) { + MatchExpression* child = tree->getChild(i); + tagForSort(child); + if (child->getTag() && + child->getTag()->getType() == MatchExpression::TagData::Type::IndexTag) { + IndexTag* childTag = static_cast<IndexTag*>(child->getTag()); + myTagValue = std::min(myTagValue, childTag->index); + } else if (child->getTag() && + child->getTag()->getType() == + MatchExpression::TagData::Type::OrPushdownTag) { + OrPushdownTag* childTag = static_cast<OrPushdownTag*>(child->getTag()); + if (childTag->getIndexTag()) { + const IndexTag* indexTag = + static_cast<const IndexTag*>(childTag->getIndexTag()); + myTagValue = std::min(myTagValue, indexTag->index); + } + } + } + if (myTagValue != IndexTag::kNoIndex) { + tree->setTag(new IndexTag(myTagValue)); + } + } +} + } // namespace @@ -258,9 +292,9 @@ string PlanEnumerator::NodeAssignment::toString() const { mongoutils::str::stream ss; ss << "predicate\n"; ss << "\tfirst indices: ["; - for (size_t i = 0; i < pred->first.size(); ++i) { - ss << pred->first[i]; - if (i < pred->first.size() - 1) + for (size_t i = 0; i < pred->indexes.size(); ++i) { + ss << pred->indexes[i]; + if (i < pred->indexes.size() - 1) ss << ", "; } ss << "]\n"; @@ -360,6 +394,8 @@ void PlanEnumerator::allocateAssignment(MatchExpression* expr, bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) { PrepMemoContext childContext; 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. @@ -369,23 +405,42 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) { } RelevantTag* rt = static_cast<RelevantTag*>(node->getTag()); - // In order to definitely use an index it must be prefixed with our field. - // We don't consider notFirst indices here because we must be AND-related to a node - // that uses the first spot in that index, and we currently do not know that - // unless we're in an AND node. - if (0 == rt->first.size()) { - return false; - } - // We know we can use an index, so grab a memo spot. size_t myMemoID; NodeAssignment* assign; allocateAssignment(node, &assign, &myMemoID); assign->pred.reset(new PredicateAssignment()); assign->pred->expr = node; - assign->pred->first.swap(rt->first); - return true; + + // '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. @@ -406,7 +461,14 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) { } 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) { - if (!prepMemo(node->getChild(i), childContext)) { + + // Extend the path through the indexed ORs of each outside predicate. + auto childContextCopy = childContext; + for (auto& pred : childContextCopy.outsidePreds) { + pred.second.push_back(i); + } + + if (!prepMemo(node->getChild(i), childContextCopy)) { return false; } } @@ -478,7 +540,13 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) { // mandatory preds to 'indexedPreds'. Adding the mandatory preds directly to // 'indexedPreds' would lead to problems such as pulling a predicate beneath an OR // into a set joined by an AND. - if (!partitionPreds(node, childContext, &indexedPreds, &subnodes, &mandatorySubnodes)) { + getIndexedPreds(node, childContext, &indexedPreds); + // Pass in the indexed predicates as outside predicates when prepping the subnodes. + auto childContextCopy = childContext; + for (auto pred : indexedPreds) { + childContextCopy.outsidePreds[pred] = std::deque<size_t>(); + } + if (!prepSubNodes(node, childContextCopy, &subnodes, &mandatorySubnodes)) { return false; } @@ -537,11 +605,11 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) { } // If none of our children can use indices, bail out. - if (idxToFirst.empty() && (subnodes.size() == 0) && (mandatorySubnodes.size() == 0)) { + if (idxToFirst.empty() && idxToNotFirst.empty() && (subnodes.size() == 0) && + (mandatorySubnodes.size() == 0)) { return false; } - // At least one child can use an index, so we can create a memo entry. AndAssignment* andAssignment = new AndAssignment(); size_t myMemoID; @@ -555,7 +623,7 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) { if (1 == mandatorySubnodes.size()) { AndEnumerableState aes; aes.subnodesToIndex.push_back(mandatorySubnodes[0]); - andAssignment->choices.push_back(aes); + andAssignment->choices.push_back(std::move(aes)); return true; } @@ -566,13 +634,14 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) { idxToFirst, idxToNotFirst, mandatoryPred, mandatoryIndices, andAssignment); } - enumerateOneIndex(idxToFirst, idxToNotFirst, subnodes, andAssignment); + enumerateOneIndex( + idxToFirst, idxToNotFirst, subnodes, childContext.outsidePreds, andAssignment); if (_ixisect) { enumerateAndIntersect(idxToFirst, idxToNotFirst, subnodes, andAssignment); } - return true; + return !andAssignment->choices.empty(); } // Don't know what the node is at this point. @@ -744,16 +813,48 @@ bool PlanEnumerator::enumerateMandatoryIndex(const IndexToPredMap& idxToFirst, // Output the assignments for this index. AndEnumerableState state; state.assignments.push_back(indexAssign); - andAssignment->choices.push_back(state); + andAssignment->choices.push_back(std::move(state)); } return andAssignment->choices.size() > 0; } -void PlanEnumerator::enumerateOneIndex(const IndexToPredMap& idxToFirst, - const IndexToPredMap& idxToNotFirst, - const vector<MemoID>& subnodes, - AndAssignment* andAssignment) { +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; + } + + 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)); + } + } + return orPushdowns; +} + +void PlanEnumerator::enumerateOneIndex( + const IndexToPredMap& idxToFirst, + const IndexToPredMap& idxToNotFirst, + const vector<MemoID>& subnodes, + 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 // @@ -785,7 +886,7 @@ void PlanEnumerator::enumerateOneIndex(const IndexToPredMap& idxToFirst, for (size_t i = 0; i < subnodes.size(); ++i) { AndEnumerableState aes; aes.subnodesToIndex.push_back(subnodes[i]); - andAssignment->choices.push_back(aes); + andAssignment->choices.push_back(std::move(aes)); } // For each FIRST, we assign nodes to it. @@ -820,7 +921,8 @@ void PlanEnumerator::enumerateOneIndex(const IndexToPredMap& idxToFirst, AndEnumerableState state; state.assignments.push_back(indexAssign); - andAssignment->choices.push_back(state); + // TODO SERVER-27904: Use outsidePreds to get orPushdowns. + 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. @@ -853,7 +955,8 @@ void PlanEnumerator::enumerateOneIndex(const IndexToPredMap& idxToFirst, // Output the assignment. AndEnumerableState state; state.assignments.push_back(indexAssign); - andAssignment->choices.push_back(state); + // TODO SERVER-27904: Use outsidePreds to get orPushdowns. + andAssignment->choices.push_back(std::move(state)); } } else { // The assignment we're filling out. @@ -880,7 +983,30 @@ void PlanEnumerator::enumerateOneIndex(const IndexToPredMap& idxToFirst, // Output the assignment. AndEnumerableState state; state.assignments.push_back(indexAssign); - andAssignment->choices.push_back(state); + state.orPushdowns = getOrPushdowns(indexAssign.index, outsidePreds); + 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; + } } } } @@ -952,7 +1078,7 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst, } AndEnumerableState state; state.assignments.push_back(oneAssign); - andAssignment->choices.push_back(state); + andAssignment->choices.push_back(std::move(state)); continue; } @@ -961,7 +1087,7 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst, AndEnumerableState indexAndSubnode; indexAndSubnode.assignments.push_back(oneAssign); indexAndSubnode.subnodesToIndex.push_back(subnodes[i]); - andAssignment->choices.push_back(indexAndSubnode); + andAssignment->choices.push_back(std::move(indexAndSubnode)); // Limit n^2. if (andAssignment->choices.size() - sizeBefore > _intersectLimit) { return; @@ -1128,7 +1254,7 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst, AndEnumerableState state; state.assignments.push_back(firstAssign); state.assignments.push_back(secondAssign); - andAssignment->choices.push_back(state); + andAssignment->choices.push_back(std::move(state)); } } @@ -1144,21 +1270,19 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst, AndEnumerableState state; state.subnodesToIndex.push_back(subnodes[i]); state.subnodesToIndex.push_back(subnodes[j]); - andAssignment->choices.push_back(state); + andAssignment->choices.push_back(std::move(state)); } } } -bool PlanEnumerator::partitionPreds(MatchExpression* node, - PrepMemoContext context, - vector<MatchExpression*>* indexOut, - vector<MemoID>* subnodesOut, - vector<MemoID>* mandatorySubnodes) { +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 (NULL != context.elemMatchExpr) { + if (context.elemMatchExpr) { // If we're in an $elemMatch context, store the // innermost parent $elemMatch, as well as the // inner path prefix. @@ -1171,20 +1295,27 @@ bool PlanEnumerator::partitionPreds(MatchExpression* node, } // Output this as a pred that can use the index. - indexOut->push_back(child); + indexedPreds->push_back(child); } else if (Indexability::isBoundsGeneratingNot(child)) { - partitionPreds(child, context, indexOut, subnodesOut, mandatorySubnodes); + getIndexedPreds(child, context, indexedPreds); } else if (MatchExpression::ELEM_MATCH_OBJECT == child->matchType()) { PrepMemoContext childContext; childContext.elemMatchExpr = child; - partitionPreds(child, childContext, indexOut, subnodesOut, mandatorySubnodes); + getIndexedPreds(child, childContext, indexedPreds); } else if (MatchExpression::AND == child->matchType()) { - partitionPreds(child, context, indexOut, subnodesOut, mandatorySubnodes); - } else { - bool mandatory = expressionRequiresIndex(child); + getIndexedPreds(child, context, indexedPreds); + } + } +} - // Recursively prepMemo for the subnode. We fall through - // to this case for logical nodes other than AND (e.g. OR). +bool PlanEnumerator::prepSubNodes(MatchExpression* node, + PrepMemoContext context, + vector<MemoID>* subnodesOut, + vector<MemoID>* mandatorySubnodes) { + for (size_t i = 0; i < node->numChildren(); ++i) { + MatchExpression* child = node->getChild(i); + if (MatchExpression::OR == child->matchType()) { + bool mandatory = expressionRequiresIndex(child); if (prepMemo(child, context)) { size_t childID = memoIDForNode(child); @@ -1199,6 +1330,13 @@ bool PlanEnumerator::partitionPreds(MatchExpression* node, // that the entire AND cannot be indexed either. return false; } + } else if (MatchExpression::ELEM_MATCH_OBJECT == child->matchType()) { + PrepMemoContext childContext; + childContext.elemMatchExpr = child; + childContext.outsidePreds = context.outsidePreds; + prepSubNodes(child, childContext, subnodesOut, mandatorySubnodes); + } else if (MatchExpression::AND == child->matchType()) { + prepSubNodes(child, context, subnodesOut, mandatorySubnodes); } } @@ -1398,6 +1536,17 @@ bool PlanEnumerator::alreadyCompounded(const set<MatchExpression*>& ixisectAssig return false; } +size_t PlanEnumerator::getPosition(const IndexEntry& indexEntry, const std::string& path) { + size_t position = 0; + for (auto&& element : indexEntry.keyPattern) { + if (element.fieldName() == path) { + return position; + } + ++position; + } + MONGO_UNREACHABLE; +} + void PlanEnumerator::compound(const vector<MatchExpression*>& tryCompound, const IndexEntry& thisIndex, OneIndexAssignment* assign) { @@ -1448,8 +1597,21 @@ void PlanEnumerator::tagMemo(size_t id) { if (NULL != assign->pred) { PredicateAssignment* pa = assign->pred.get(); verify(NULL == pa->expr->getTag()); - verify(pa->indexToAssign < pa->first.size()); - pa->expr->setTag(new IndexTag(pa->first[pa->indexToAssign])); + 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) { OrAssignment* oa = assign->orAssignment.get(); for (size_t i = 0; i < oa->subnodes.size(); ++i) { @@ -1473,10 +1635,25 @@ void PlanEnumerator::tagMemo(size_t id) { for (size_t j = 0; j < assign.preds.size(); ++j) { MatchExpression* pred = assign.preds[j]; - verify(NULL == pred->getTag()); - pred->setTag( - new IndexTag(assign.index, assign.positions[j], assign.canCombineBounds)); + if (pred->getTag()) { + OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(pred->getTag()); + orPushdownTag->setIndexTag( + new IndexTag(assign.index, assign.positions[j], assign.canCombineBounds)); + } else { + pred->setTag( + 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()); } + OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(expr->getTag()); + orPushdownTag->addDestination(orPushdown.second.clone()); } } else { verify(0); @@ -1490,7 +1667,7 @@ bool PlanEnumerator::nextMemo(size_t id) { if (NULL != assign->pred) { PredicateAssignment* pa = assign->pred.get(); pa->indexToAssign++; - if (pa->indexToAssign >= pa->first.size()) { + if (pa->indexToAssign >= pa->indexes.size()) { pa->indexToAssign = 0; return true; } diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h index a84cc909d58..456464845b4 100644 --- a/src/mongo/db/query/plan_enumerator.h +++ b/src/mongo/db/query/plan_enumerator.h @@ -128,6 +128,10 @@ private: struct PrepMemoContext { PrepMemoContext() : elemMatchExpr(NULL) {} MatchExpression* elemMatchExpr; + + // Maps from indexable predicates that can be pushed into the current node to the route + // through ORs that they have taken to get to this node. + unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds; }; /** @@ -180,14 +184,19 @@ private: struct PredicateAssignment { PredicateAssignment() : indexToAssign(0) {} - std::vector<IndexID> first; + std::vector<IndexID> indexes; // Not owned here. MatchExpression* expr; - // Enumeration state. An indexed predicate's possible states are the indices that the - // predicate can directly use (the 'first' indices). As such this value ranges from 0 - // to first.size()-1 inclusive. + // 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 { @@ -220,6 +229,9 @@ private: 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 { @@ -268,19 +280,24 @@ private: * context information is stashed in the tags so that we don't lose * information due to flattening. * - * Nodes that cannot be deeply traversed are returned via the output - * vectors 'subnodesOut' and 'mandatorySubnodes'. Subnodes are "mandatory" - * if they *must* use an index (TEXT and GEO). - * * Does not take ownership of arguments. * * Returns false if the AND cannot be indexed. Otherwise returns true. */ - bool partitionPreds(MatchExpression* node, - PrepMemoContext context, - std::vector<MatchExpression*>* indexOut, - std::vector<MemoID>* subnodesOut, - std::vector<MemoID>* mandatorySubnodes); + void getIndexedPreds(MatchExpression* node, + PrepMemoContext context, + std::vector<MatchExpression*>* indexOut); + + /** + * Recursively traverse 'node', with OR nodes as the base case. The OR nodes are not + * explored--instead we call prepMemo() on the OR subnode, and add its assignment to the output. + * Subnodes are "mandatory" if they *must* use an index (TEXT and GEO). + * Returns a boolean indicating whether all mandatory subnodes can be indexed. + */ + bool prepSubNodes(MatchExpression* node, + PrepMemoContext context, + std::vector<MemoID>* subnodesOut, + std::vector<MemoID>* mandatorySubnodes); /** * Finds a set of predicates that can be safely compounded with the set @@ -412,11 +429,12 @@ private: /** * Generate one-index-at-once assignments given the predicate/index structure in idxToFirst * and idxToNotFirst (and the sub-trees in 'subnodes'). Outputs the assignments into - * 'andAssignment'. + * 'andAssignment'. The predicates in 'outsidePreds' are considered for OrPushdownTags. */ void enumerateOneIndex(const IndexToPredMap& idxToFirst, const IndexToPredMap& idxToNotFirst, const std::vector<MemoID>& subnodes, + const unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds, AndAssignment* andAssignment); /** @@ -442,6 +460,19 @@ 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. + */ + size_t getPosition(const IndexEntry& indexEntry, const std::string& path); + + /* + * Finds all predicates in 'outsidePreds' for which 'index' is relevant, and constructs + * OrPushdownTag::Destinations for those predicates. + */ + std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> getOrPushdowns( + IndexID index, const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds); + + /** * Return the memo entry for 'node'. Does some sanity checking to ensure that a memo entry * actually exists. */ diff --git a/src/mongo/db/query/planner_access.h b/src/mongo/db/query/planner_access.h index a5844f4fa58..85cafd30608 100644 --- a/src/mongo/db/query/planner_access.h +++ b/src/mongo/db/query/planner_access.h @@ -294,9 +294,6 @@ public: * facilitate grouping of index scans. As such, the processing for AND and OR is * almost identical. * - * See tagForSort and sortUsingTags in index_tag.h for details on ordering the children - * of OR and AND. - * * Does not take ownership of 'root' but may remove children from it. */ static bool processIndexScans(const CanonicalQuery& query, diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp index b19a6bf0e5f..6d39ffe6934 100644 --- a/src/mongo/db/query/query_planner.cpp +++ b/src/mongo/db/query/query_planner.cpp @@ -272,7 +272,8 @@ Status QueryPlanner::cacheDataFromTaggedTree(const MatchExpression* const tagged unique_ptr<PlanCacheIndexTree> indexTree(new PlanCacheIndexTree()); - if (NULL != taggedTree->getTag()) { + if (taggedTree->getTag() && + taggedTree->getTag()->getType() == MatchExpression::TagData::Type::IndexTag) { IndexTag* itag = static_cast<IndexTag*>(taggedTree->getTag()); if (itag->index >= relevantIndices.size()) { mongoutils::str::stream ss; @@ -295,6 +296,18 @@ Status QueryPlanner::cacheDataFromTaggedTree(const MatchExpression* const tagged indexTree->entry.reset(ientry); indexTree->index_pos = itag->pos; indexTree->canCombineBounds = itag->canCombineBounds; + } else if (taggedTree->getTag() && + taggedTree->getTag()->getType() == MatchExpression::TagData::Type::OrPushdownTag) { + OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(taggedTree->getTag()); + for (const auto& dest : orPushdownTag->getDestinations()) { + PlanCacheIndexTree::OrPushdown orPushdown; + orPushdown.route = dest.route; + IndexTag* indexTag = static_cast<IndexTag*>(dest.tagData.get()); + orPushdown.indexName = relevantIndices[indexTag->index].name; + orPushdown.position = indexTag->pos; + orPushdown.canCombineBounds = indexTag->canCombineBounds; + indexTree->orPushdowns.push_back(std::move(orPushdown)); + } } for (size_t i = 0; i < taggedTree->numChildren(); ++i) { @@ -351,6 +364,22 @@ Status QueryPlanner::tagAccordingToCache(MatchExpression* filter, } filter->setTag( new IndexTag(got->second, indexTree->index_pos, indexTree->canCombineBounds)); + } else if (!indexTree->orPushdowns.empty()) { + filter->setTag(new OrPushdownTag()); + OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(filter->getTag()); + for (const auto& orPushdown : indexTree->orPushdowns) { + auto index = indexMap.find(orPushdown.indexName); + if (index == indexMap.end()) { + return Status(ErrorCodes::BadValue, + str::stream() << "Did not find index with name: " + << orPushdown.indexName); + } + OrPushdownTag::Destination dest; + dest.route = orPushdown.route; + dest.tagData = stdx::make_unique<IndexTag>( + index->second, orPushdown.position, orPushdown.canCombineBounds); + orPushdownTag->addDestination(std::move(dest)); + } } return Status::OK(); @@ -420,8 +449,8 @@ Status QueryPlanner::planFromCache(const CanonicalQuery& query, return s; } - // The planner requires a defined sort order. - sortUsingTags(clone.get()); + // The MatchExpression tree is in canonical order. We must order the nodes for access planning. + prepareForAccessPlanning(clone.get()); LOG(5) << "Tagged tree:" << endl << redact(clone->toString()); @@ -783,9 +812,9 @@ Status QueryPlanner::plan(const CanonicalQuery& query, LOG(5) << "About to build solntree from tagged tree:" << endl << redact(rawTree->toString()); - // Store the plan cache index tree before sorting using index tags, so that the - // PlanCacheIndexTree has the same sort as the MatchExpression used to generate the plan - // cache key. + // Store the plan cache index tree before calling prepareForAccessingPlanning(), so that + // the PlanCacheIndexTree has the same sort as the MatchExpression used to generate the + // plan cache key. std::unique_ptr<MatchExpression> clone(rawTree->shallowClone()); PlanCacheIndexTree* cacheData; Status indexTreeStatus = @@ -795,7 +824,9 @@ Status QueryPlanner::plan(const CanonicalQuery& query, } unique_ptr<PlanCacheIndexTree> autoData(cacheData); - sortUsingTags(rawTree); + // We have already cached the tree in canonical order, so now we can order the nodes for + // access planning. + prepareForAccessPlanning(rawTree); // This can fail if enumeration makes a mistake. QuerySolutionNode* solnRoot = QueryPlannerAccess::buildIndexedDataAccess( diff --git a/src/mongo/db/query/query_planner_array_test.cpp b/src/mongo/db/query/query_planner_array_test.cpp index 0cd00755d52..a4e4c38998a 100644 --- a/src/mongo/db/query/query_planner_array_test.cpp +++ b/src/mongo/db/query/query_planner_array_test.cpp @@ -1453,4 +1453,202 @@ TEST_F(QueryPlannerTest, CannotCoverNonMultikeyDottedField) { "bounds: {'a.y':[[1,1,true,true]],'b.z':[[2,2,true,true]]}}}}}}}"); } +TEST_F(QueryPlannerTest, ContainedOrElemMatchValue) { + addIndex(BSON("b" << 1 << "a" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: {$elemMatch: {$eq: 5}}}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{or: {nodes: [" + "{fetch: {filter: {a: {$elemMatch: {$eq: 5}}}, node: {ixscan: {pattern: {b: 1, a: 1}, " + "bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, true]]}}}}}," + "{fetch: {filter: {a: {$elemMatch: {$eq: 5}}}, node: {ixscan: {pattern: {c: 1, a: 1}, " + "bounds: {c: [[7, 7, true, true]], a: [[5, 5, true, true]]}}}}}" + "]}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrElemMatchObject) { + addIndex(BSON("c" << 1 << "a.b" << 1)); + addIndex(BSON("d" << 1 << "a.b" << 1)); + + runQuery(fromjson("{$and: [{a: {$elemMatch: {b: 5}}}, {$or: [{c: 6}, {d: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: {a: {$elemMatch: {b: 5}}}, node: {or: {nodes: [" + "{ixscan: {pattern: {c: 1, 'a.b': 1}, bounds: {c: [[6, 6, true, true]], 'a.b': [[5, 5, " + "true, true]]}}}," + "{ixscan: {pattern: {d: 1, 'a.b': 1}, bounds: {d: [[7, 7, true, true]], 'a.b': [[5, 5, " + "true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrElemMatchObjectMultiplePredicates) { + addIndex(BSON("d" << 1 << "a.b" << 1)); + addIndex(BSON("e" << 1 << "a.c" << 1)); + + runQuery(fromjson("{$and: [{a: {$elemMatch: {b: 5, c: 6}}}, {$or: [{d: 7}, {e: 8}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: {a: {$elemMatch: {b: 5, c: 6}}}, node: {or: {nodes: [" + "{ixscan: {pattern: {d: 1, 'a.b': 1}, bounds: {d: [[7, 7, true, true]], 'a.b': [[5, 5, " + "true, true]]}}}," + "{ixscan: {pattern: {e: 1, 'a.c': 1}, bounds: {e: [[8, 8, true, true]], 'a.c': [[6, 6, " + "true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrNestedElemMatchObject) { + addIndex(BSON("d" << 1 << "a.b.c" << 1)); + addIndex(BSON("e" << 1 << "a.b.c" << 1)); + + runQuery(fromjson( + "{$and: [{a: {$elemMatch: {b: {$elemMatch: {c: 5}}}}}, {$or: [{d: 6}, {e: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: {a: {$elemMatch: {b: {$elemMatch: {c: 5}}}}}, node: {or: {nodes: [" + "{ixscan: {pattern: {d: 1, 'a.b.c': 1}, bounds: {d: [[6, 6, true, true]], 'a.b.c': [[5, 5, " + "true, true]]}}}," + "{ixscan: {pattern: {e: 1, 'a.b.c': 1}, bounds: {e: [[7, 7, true, true]], 'a.b.c': [[5, 5, " + "true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrMoveToElemMatchValue) { + addIndex(BSON("b" << 1 << "a" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: {$elemMatch: {$eq: 6}}}, {c: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{fetch: {filter: {b: {$elemMatch: {$eq: 6}}}, node: {ixscan: {pattern: {b: 1, a: 1}, " + "bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, true]]}}}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrMoveToElemMatchObject) { + addIndex(BSON("b.c" << 1 << "a" << 1)); + addIndex(BSON("d" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: {$elemMatch: {c: 6}}}, {d: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{fetch: {filter: {b: {$elemMatch: {c: 6}}}, node: {ixscan: {pattern: {'b.c': 1, a: 1}, " + "bounds: {'b.c': [[6, 6, true, true]], a: [[5, 5, true, true]]}}}}}," + "{ixscan: {pattern: {d: 1, a: 1}, bounds: {d: [[7, 7, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrMoveToElemMatchObjectMultiplePredicates) { + addIndex(BSON("b.c" << 1 << "a" << 1 << "b.d" << 1)); + addIndex(BSON("e" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: {$elemMatch: {c: 6, d: 7}}}, {e: 8}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{fetch: {filter: {b: {$elemMatch: {c: 6, d: 7}}}, node: {ixscan: {pattern: {'b.c': 1, a: " + "1, 'b.d': 1}, bounds: {'b.c': [[6, 6, true, true]], a: [[5, 5, true, true]], 'b.d': [[7, " + "7, true, true]]}}}}}," + "{ixscan: {pattern: {e: 1, a: 1}, bounds: {e: [[8, 8, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrMoveToNestedElemMatchObject) { + addIndex(BSON("b.c.d" << 1 << "a" << 1)); + addIndex(BSON("e" << 1 << "a" << 1)); + + runQuery(fromjson( + "{$and: [{a: 5}, {$or: [{b: {$elemMatch: {c: {$elemMatch: {d: 6}}}}}, {e: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{fetch: {filter: {b: {$elemMatch: {c: {$elemMatch: {d: 6}}}}}, node: {ixscan: {pattern: " + "{'b.c.d': 1, a: 1}, bounds: {'b.c.d': [[6, 6, true, true]], a: [[5, 5, true, true]]}}}}}," + "{ixscan: {pattern: {e: 1, a: 1}, bounds: {e: [[7, 7, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrInElemMatch) { + addIndex(BSON("a.c" << 1 << "a.b" << 1)); + addIndex(BSON("a.d" << 1 << "a.b" << 1)); + + runQuery(fromjson("{a: {$elemMatch: {$and: [{b: 5}, {$or: [{c: 6}, {d: 7}]}]}}}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: {a: {$elemMatch: {$and: [{$or: [{$and: [{c: 6}, {b: 5}]}, {$and: [{d: " + "7}, {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: {'a.d': 1, 'a.b': 1}, bounds: {'a.d': [[7, 7, true, true]], 'a.b': " + "[[5, 5, true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrInAndInElemMatch) { + addIndex(BSON("b.d" << 1 << "b.c" << 1)); + addIndex(BSON("b.e" << 1 << "b.c" << 1)); + + runQuery( + fromjson("{$and: [{a: 5}, {b: {$elemMatch: {$and: [{c: 5}, {$or: [{d: 6}, {e: 7}]}]}}}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: {$and: [{a: 5}, {b: {$elemMatch: {$and: [{c: 5}, {$or: [{$and: [{d: 6}, " + "{c: 5}]}, {$and: [{e: 7}, {c: 5}]}]}]}}}]}, " + "node: {or: {nodes: [" + "{ixscan: {pattern: {'b.d': 1, 'b.c': 1}, bounds: {'b.d': [[6, 6, true, true]], 'b.c': " + "[[5, 5, true, true]]}}}," + "{ixscan: {pattern: {'b.e': 1, 'b.c': 1}, bounds: {'b.e': [[7, 7, true, true]], 'b.c': " + "[[5, 5, true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrElemMatchPredicateIsLeadingFieldIndexIntersection) { + params.options = QueryPlannerParams::INCLUDE_COLLSCAN | QueryPlannerParams::INDEX_INTERSECTION; + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("c" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(4); + assertSolutionExists( + "{fetch: {filter: {a: 5}, node: {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]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{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]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + } // namespace diff --git a/src/mongo/db/query/query_planner_geo_test.cpp b/src/mongo/db/query/query_planner_geo_test.cpp index 9e087444079..96b71acdb3d 100644 --- a/src/mongo/db/query/query_planner_geo_test.cpp +++ b/src/mongo/db/query/query_planner_geo_test.cpp @@ -239,6 +239,66 @@ TEST_F(QueryPlannerTest, Multikey2DSphereGeoNearReverseCompound) { "bounds: {x: [[1, 1, true, true]], a: [['MinKey', 'MaxKey', true, true]]}}}"); } +TEST_F(QueryPlannerTest, 2DNonNearContainedOr) { + addIndex(BSON("x" << 1 << "a" + << "2d")); + addIndex(BSON("y" << 1)); + runQuery( + fromjson("{$and: [{x: 1}, {$or: [{a: {$within: {$polygon: [[0, 0], [0, 1], [1, 0], [0, " + "0]]}}}, {y: 1}]}]}")); + + assertNumSolutions(3U); + assertSolutionExists( + "{fetch: {filter: {x: 1}, node: {or: {nodes: [" + "{ixscan: {pattern: {x: 1, a: '2d'}, bounds: {x: [[1, 1, true, true]]}}}," + "{ixscan: {pattern: {y: 1}, bounds: {y: [[1, 1, true, true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{a: {$within: {$polygon: [[0, 0], [0, 1], [1, 0], [0, 0]]}}}, {y: " + "1}]}, node: " + "{ixscan: {pattern: {x: 1, a: '2d'}, bounds: {x: [[1, 1, true, true]], a: [['MinKey', " + "'MaxKey', true, true]]}}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, 2DSphereV1NonNearContainedOr) { + addIndex(BSON("x" << 1 << "a" + << "2dsphere"), + BSON("2dsphereIndexVersion" << 1)); + addIndex(BSON("y" << 1)); + runQuery( + fromjson("{$and: [{x: 1}, {$or: [{a: {$geoWithin: {$geometry: {type: 'Polygon', " + "coordinates: [[[0, 0], [0, 1], [1, 0], [0, 0]]]}}}}, {y: 1}]}]}")); + + assertNumSolutions(3U); + assertSolutionExists( + "{fetch: {filter: {x: 1}, node: {or: {nodes: [" + "{fetch: {filter: {a: {$geoWithin: {$geometry: {type: 'Polygon', coordinates: [[[0, 0], " + "[0, 1], [1, 0], [0, 0]]]}}}}, node: {ixscan: {pattern: {x: 1, a: '2dsphere'}, bounds: {x: " + "[[1, 1, true, true]]}}}}}," + "{ixscan: {pattern: {y: 1}, bounds: {y: [[1, 1, true, true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{a: {$geoWithin: {$geometry: {type: 'Polygon', coordinates: [[[0, " + "0], [0, 1], [1, 0], [0, 0]]]}}}}, {y: 1}]}, node: " + "{ixscan: {pattern: {x: 1, a: '2dsphere'}, bounds: {x: [[1, 1, true, true]], a: " + "[['MinKey', 'MaxKey', true, true]]}}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, 2DSphereV2NonNearContainedOr) { + addIndex(BSON("x" << 1 << "a" + << "2dsphere"), + BSON("2dsphereIndexVersion" << 2)); + addIndex(BSON("y" << 1)); + runQuery( + fromjson("{$and: [{x: 1}, {$or: [{a: {$geoWithin: {$geometry: {type: 'Polygon', " + "coordinates: [[[0, 0], [0, 1], [1, 0], [0, 0]]]}}}}, {y: 1}]}]}")); + + assertNumSolutions(1U); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + TEST_F(QueryPlannerTest, NearNoIndex) { addIndex(BSON("x" << 1)); runInvalidQuery(fromjson("{x:1, a: {$nearSphere: [0,0], $maxDistance: 0.31 }}")); diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp index 2efcc825f58..842a5964e4e 100644 --- a/src/mongo/db/query/query_planner_test.cpp +++ b/src/mongo/db/query/query_planner_test.cpp @@ -4365,4 +4365,631 @@ TEST_F(QueryPlannerTest, PlansForMultipleIndexesOnTheSameKeyPatternAreGenerated) assertSolutionExists("{cscan: {dir: 1}}}}"); } +TEST_F(QueryPlannerTest, ContainedOr) { + addIndex(BSON("b" << 1 << "a" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, " + "true]]}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrOneChildUsesPredicate) { + addIndex(BSON("b" << 1 << "a" << 1)); + 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, ContainedOrCombineWithAnd) { + addIndex(BSON("b" << 1 << "a" << 1)); + addIndex(BSON("c" << 1 << "d" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {$and: [{c: 7}, {d: 8}]}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, " + "true]]}}}," + "{ixscan: {pattern: {c: 1, d: 1, a: 1}, bounds: {c: [[7, 7, true, true]], d: [[8, 8, true, " + "true]], a: [[5, 5, true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, NestedContainedOr) { + addIndex(BSON("b" << 1 << "a" << 1)); + addIndex(BSON("d" << 1 << "a" << 1)); + addIndex(BSON("e" << 1 << "a" << 1)); + + runQuery( + fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {$and: [{c: 7}, {$or: [{d: 8}, {e: 9}]}]}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, " + "true]]}}}," + "{fetch: {filter: {c: 7}, node: {or: {nodes: [" + "{ixscan: {pattern: {d: 1, a: 1}, bounds: {d: [[8, 8, true, true]], a: [[5, 5, true, " + "true]]}}}," + "{ixscan: {pattern: {e: 1, a: 1}, bounds: {e: [[9, 9, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, NestedContainedOrOneChildUsesPredicate) { + addIndex(BSON("c" << 1 << "a" << 1)); + addIndex(BSON("d" << 1)); + addIndex(BSON("f" << 1)); + addIndex(BSON("g" << 1 << "a" << 1)); + + runQuery( + fromjson("{$and: [{a: 5}, {$or: [{$and: [{b: 6}, {$or: [{c: 7}, {d: 8}]}]}, " + "{$and: [{e: 9}, {$or: [{f: 10}, {g: 11}]}]}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: {a: 5}, node: {or: {nodes: [" + "{fetch: {filter: {b: 6}, node: {or: {nodes: [" + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 5, true, " + "true]]}}}," + "{ixscan: {pattern: {d: 1}, bounds: {d: [[8, 8, true, true]]}}}" + "]}}}}," + "{fetch: {filter: {e: 9}, node: {or: {nodes: [" + "{ixscan: {pattern: {f: 1}, bounds: {f: [[10, 10, true, true]]}}}," + "{ixscan: {pattern: {g: 1, a: 1}, bounds: {g: [[11, 11, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, DoublyContainedOr) { + addIndex(BSON("b" << 1 << "a" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + addIndex(BSON("d" << 1)); + + runQuery( + fromjson("{$and: [{$or: [{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}, {d: 8}]}, {e: 9}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: {e: 9}, node: {or: {nodes: [" + "{or: {nodes: [" + "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, " + "true]]}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 5, true, " + "true]]}}}]}}," + "{ixscan: {pattern: {d: 1}, bounds: {d: [[8, 8, true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrNotNextInIndex) { + addIndex(BSON("b" << 1 << "d" << 1 << "a" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {b: 1, d: 1, a: 1}, bounds: {b: [[6, 6, true, true]], d: [['MinKey', " + "'MaxKey', true, true]], a: [[5, 5, true, true]]}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrMultiplePredicates) { + addIndex(BSON("c" << 1 << "a" << 1 << "b" << 1)); + addIndex(BSON("d" << 1 << "b" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {b: 6}, {$or: [{c: 7}, {d: 8}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {c: 1, a: 1, b: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 5, true, " + "true]], b: [[6, 6, true, true]]}}}," + "{ixscan: {pattern: {d: 1, b: 1, a: 1}, bounds: {d: [[8, 8, true, true]], b: [[6, 6, true, " + "true]], a: [[5, 5, true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrIntersect) { + addIndex(BSON("b" << 1 << "a" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + + runQuery( + fromjson("{$and: [{a: {$gte: 5}}, {$or: [{b: 6}, {$and: [{c: 7}, {a: {$lte: 8}}]}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, Infinity, " + "true, true]]}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 8, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrNot) { + addIndex(BSON("b" << 1 << "a" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{$nor: [{a: 5}]}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [['MinKey', 5, " + "true, false], [5, 'MaxKey', false, true]]}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [['MinKey', 5, " + "true, false], [5, 'MaxKey', false, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrMoveToNot) { + addIndex(BSON("b" << 1 << "a" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{$nor: [{b: 6}]}, {c: 7}]}]}")); + assertNumSolutions(2); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [['MinKey', 6, true, false], [6, 'MaxKey', " + "false, true]], a: [[5, 5, true, true]]}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrPredicateIsLeadingFieldInIndex) { + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("a" << 1 << "c" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(4); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]]}}}," + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[5, 5, true, true]], c: [[7, 7, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[5, 5, true, true]], c: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrPredicateIsLeadingFieldAndTrailingField) { + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(3); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]]}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[5, 5, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrPredicateIsLeadingFieldForOneOrBranch) { + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("c" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(3); + assertSolutionExists( + "{fetch: {filter: {a: 5}, node: {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]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrPredicatesAreLeadingFields) { + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("a" << 1 << "c" << 1)); + + runQuery(fromjson("{$and: [{a: {$gte: 0}}, {a: {$lte: 10}}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(4); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[0, 10, true, true]], b: [[6, 6, true, " + "true]]}}}," + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[0, 10, true, true]], c: [[7, 7, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[0, 10, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[0, 10, true, true]], c: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrOnePredicateIsLeadingField) { + addIndex(BSON("a" << 1 << "b" << 1 << "c" << 1)); + addIndex(BSON("a" << 1 << "b" << 1 << "d" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {b: 6}, {$or: [{c: 7}, {d: 8}]}]}")); + assertNumSolutions(4); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1, c: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]], c: [[7, 7, true, true]]}}}," + "{ixscan: {pattern: {a: 1, b: 1, d: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]], d: [[8, 8, true, true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{c: 7}, {d: 8}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1, c: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]], c: [['MinKey', 'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{c: 7}, {d: 8}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1, d: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]], d: [['MinKey', 'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrCombineLeadingFields) { + addIndex(BSON("a" << 1)); + addIndex(BSON("b" << 1 << "a" << 1)); + + runQuery(fromjson("{$and: [{a: {$gte: 0}}, {$or: [{a: {$lte: 10}}, {b: 6}]}]}")); + assertNumSolutions(3); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1}, bounds: {a: [[0, 10, true, true]]}}}," + "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[0, Infinity, " + "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, ContainedOrPredicateIsLeadingFieldMoveToAnd) { + addIndex(BSON("a" << 1 << "b" << 1 << "c" << 1)); + addIndex(BSON("a" << 1 << "d" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}]}")); + assertNumSolutions(4); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1, c: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]], c: [[7, 7, true, true]]}}}," + "{ixscan: {pattern: {a: 1, d: 1}, bounds: {a: [[5, 5, true, true]], d: [[8, 8, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1, c: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', " + "'MaxKey', true, true]], c: [['MinKey', 'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}, node: " + "{ixscan: {pattern: {a: 1, d: 1}, bounds: {a: [[5, 5, true, true]], d: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrPredicateIsLeadingFieldMoveToAndWithFilter) { + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("a" << 1 << "d" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}]}")); + assertNumSolutions(4); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{fetch: {filter: {c: 7}, node: {ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, " + "true]], b: [[6, 6, true, " + "true]]}}}}}," + "{ixscan: {pattern: {a: 1, d: 1}, bounds: {a: [[5, 5, true, true]], d: [[8, 8, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}, node: " + "{ixscan: {pattern: {a: 1, d: 1}, bounds: {a: [[5, 5, true, true]], d: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrPredicatesAreLeadingFieldsMoveToAnd) { + addIndex(BSON("a" << 1 << "b" << 1 << "c" << 1)); + addIndex(BSON("a" << 1 << "d" << 1)); + + runQuery(fromjson( + "{$and: [{a: {$gte: 0}}, {a: {$lte: 10}}, {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}]}")); + assertNumSolutions(4); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1, c: 1}, bounds: {a: [[0, 10, true, true]], b: [[6, 6, " + "true, true]], c: [[7, 7, true, true]]}}}," + "{ixscan: {pattern: {a: 1, d: 1}, bounds: {a: [[0, 10, true, true]], d: [[8, 8, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1, c: 1}, bounds: {a: [[0, 10, true, true]], b: [['MinKey', " + "'MaxKey', true, true]], c: [['MinKey', 'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}, node: " + "{ixscan: {pattern: {a: 1, d: 1}, bounds: {a: [[0, 10, true, true]], d: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrOnePredicateIsLeadingFieldMoveToAnd) { + addIndex(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1)); + addIndex(BSON("a" << 1 << "b" << 1 << "e" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {b: 6}, {$or: [{$and: [{c: 7}, {d: 8}]}, {e: 9}]}]}")); + assertNumSolutions(4); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1, c: 1, d: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, " + "true, true]], c: [[7, 7, true, true]], d: [[8, 8, true, true]]}}}," + "{ixscan: {pattern: {a: 1, b: 1, e: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]], e: [[9, 9, true, true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{$and: [{c: 7}, {d: 8}]}, {e: 9}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1, c: 1, d: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, " + "true, true]], c: [['MinKey', 'MaxKey', true, true]], d: [['MinKey', 'MaxKey', true, " + "true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{$and: [{c: 7}, {d: 8}]}, {e: 9}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1, e: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]], e: [['MinKey', 'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrCombineLeadingFieldsMoveToAnd) { + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("c" << 1 << "a" << 1)); + + runQuery( + fromjson("{$and: [{a: {$gte: 0}}, {$or: [{$and: [{a: {$lte: 10}}, {b: 6}]}, {c: 7}]}]}")); + assertNumSolutions(3); + assertSolutionExists( + "{fetch: {filter: null, node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[0, 10, true, true]], b: [[6, 6, true, " + "true]]}}}," + "{ixscan: {pattern: {c: 1, a: 1}, bounds: {c: [[7, 7, true, true]], a: [[0, Infinity, " + "true, true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{$and: [{a: {$lte: 10}}, {b: 6}]}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[0, Infinity, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrPredicateIsLeadingFieldIndexIntersection) { + params.options = QueryPlannerParams::INCLUDE_COLLSCAN | QueryPlannerParams::INDEX_INTERSECTION; + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("c" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(4); + assertSolutionExists( + "{fetch: {filter: {a: 5}, node: {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]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{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]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrPredicateIsLeadingFieldInBothBranchesIndexIntersection) { + params.options = QueryPlannerParams::INCLUDE_COLLSCAN | QueryPlannerParams::INDEX_INTERSECTION; + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("a" << 1 << "c" << 1)); + + runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(6); + assertSolutionExists( + "{fetch: {node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, " + "true]]}}}," + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[5, 5, true, true]], c: [[7, 7, true, " + "true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[5, 5, true, true]], c: [['MinKey', " + "'MaxKey', true, true]]}}}" + "}}"); + // The AND_HASH stage is not really needed, since the predicate {a: 5} is covered by the indexed + // OR. + assertSolutionExists( + "{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: {a: 1, c: 1}, bounds: {a: [[5, 5, true, true]], c: [[7, 7, true, " + "true]]}}}]}}," + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', " + "'MaxKey', true, true]]}}}" + "]}}}}"); + assertSolutionExists( + "{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: {a: 1, c: 1}, bounds: {a: [[5, 5, true, true]], c: [[7, 7, true, " + "true]]}}}]}}," + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[5, 5, true, true]], c: [['MinKey', " + "'MaxKey', true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrNotPredicateIsLeadingFieldIndexIntersection) { + params.options = QueryPlannerParams::INCLUDE_COLLSCAN | QueryPlannerParams::INDEX_INTERSECTION; + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("c" << 1)); + + runQuery(fromjson("{$and: [{$nor: [{a: 5}]}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(4); + // The filter is {$not: {a: 5}}, but there is no way to write a BSON expression that will parse + // to that MatchExpression. + assertSolutionExists( + "{fetch: {node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], b: [[6, 6, true, " + "true]]}}}," + "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], b: [['MinKey', 'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: null, node: {andHash: {nodes: [" + "{or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], b: [[6, 6, true, true]]}}}," + "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}]}}," + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], b: [['MinKey', 'MaxKey', true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + +TEST_F(QueryPlannerTest, ContainedOrNotPredicateIsLeadingFieldInBothBranchesIndexIntersection) { + params.options = QueryPlannerParams::INCLUDE_COLLSCAN | QueryPlannerParams::INDEX_INTERSECTION; + addIndex(BSON("a" << 1 << "b" << 1)); + addIndex(BSON("a" << 1 << "c" << 1)); + + runQuery(fromjson("{$and: [{$nor: [{a: 5}]}, {$or: [{b: 6}, {c: 7}]}]}")); + assertNumSolutions(6); + // The filter is {$not: {a: 5}}, but there is no way to write a BSON expression that will parse + // to that MatchExpression. + assertSolutionExists( + "{fetch: {node: {or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], b: [[6, 6, true, " + "true]]}}}," + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], c: [[7, 7, true, true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], b: [['MinKey', 'MaxKey', true, true]]}}}" + "}}"); + assertSolutionExists( + "{fetch: {filter: {$or: [{b: 6}, {c: 7}]}, node: " + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], c: [['MinKey', 'MaxKey', true, true]]}}}" + "}}"); + // The AND_HASH stage is not really needed, since the predicate {a: 5} is covered by the indexed + // OR. + assertSolutionExists( + "{fetch: {filter: null, node: {andHash: {nodes: [" + "{or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], b: [[6, 6, true, true]]}}}," + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], c: [[7, 7, true, true]]}}}]}}," + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], b: [['MinKey', 'MaxKey', true, true]]}}}" + "]}}}}"); + assertSolutionExists( + "{fetch: {filter: null, node: {andHash: {nodes: [" + "{or: {nodes: [" + "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], b: [[6, 6, true, true]]}}}," + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], c: [[7, 7, true, true]]}}}]}}," + "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [['MinKey', 5, true, false], [5, 'MaxKey', " + "false, true]], c: [['MinKey', 'MaxKey', true, true]]}}}" + "]}}}}"); + assertSolutionExists("{cscan: {dir: 1}}}}"); +} + } // namespace diff --git a/src/mongo/db/query/query_planner_text_test.cpp b/src/mongo/db/query/query_planner_text_test.cpp index 5050653292a..c3ccb700618 100644 --- a/src/mongo/db/query/query_planner_text_test.cpp +++ b/src/mongo/db/query/query_planner_text_test.cpp @@ -107,6 +107,17 @@ TEST_F(QueryPlannerTest, HaveBadPrefixOnTextIndex) { runInvalidQuery(fromjson("{$or: [{a:1}, {$text: {$search: 'blah'}}]}")); } +// Outside predicates are not yet pushed into contained ORs for text indexes. +TEST_F(QueryPlannerTest, PrefixOnTextIndexIsOutsidePred) { + params.options = QueryPlannerParams::NO_TABLE_SCAN; + addIndex(BSON("a" << 1 << "_fts" + << "text" + << "_ftsx" + << 1)); + addIndex(BSON("b" << 1)); + runInvalidQuery(fromjson("{$and: [{a: 5}, {$or: [{$text: {$search: 'blah'}}, {b: 6}]}]}")); +} + // There can be more than one prefix, but they all require points. TEST_F(QueryPlannerTest, ManyPrefixTextIndex) { params.options = QueryPlannerParams::NO_TABLE_SCAN; |