SERVER-13732 Index access plan for contained OR should consider top-level predicates

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;