SERVER-17854 Move partial idx selection logic to QueryPlannerIXSelect

Also replaces index_partial_queryplanner.js with unit test
query_planner_partialidx_test.cpp.

9 files changed, 601 insertions, 62 deletions

diff --git a/jstests/core/index_partial_queryplanner.js b/jstests/core/index_partial_queryplanner.js
deleted file mode 100644
index 1d4872b518d..00000000000
--- a/jstests/core/index_partial_queryplanner.js
+++ /dev/null
@@ -1,33 +0,0 @@
-// Query planner tests for partial indexes.
-// Will be converted to unit tests. See SERVER-18092.
-(function() {
-    "use strict";
-    var coll = db.index_partial_queryplanner;
-    coll.drop();
-
-    coll.ensureIndex({x: 1},
-        {partialFilterExpression: {a: {$lt: 5},
-                     b: {$lt: 5}}});
-
-    for(var i = 0; i < 10; i++) {
-        coll.insert({x: i, a: i, b: i});
-    }
-
-    function useIndex(filter) {
-        var query = coll.find(filter);
-        var ex = query.explain(true);
-
-        return ex.executionStats.totalDocsExamined <= 1 ||
-            ex.executionStats.totalDocsExamined == query.count();
-    }
-
-    assert(!useIndex({x: 7, a: 7}));
-    assert(!useIndex({x: 7, b: 7}));
-    assert(!useIndex({x: 7, a: 7, b: 7}));
-    assert(!useIndex({x: 7, a: 7, b: 7, c: 7}));
-
-    assert(!useIndex({x: 3, a: 3}));
-    assert(!useIndex({x: 3, b: 3}));
-    assert(useIndex({x: 3, a: 3, b: 3}));
-    assert(useIndex({x: 3, a: 3, b: 3, c: 3}));
-})();
diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript
index e899da3961b..68835f2492b 100644
--- a/src/mongo/db/query/SConscript
+++ b/src/mongo/db/query/SConscript
@@ -311,6 +311,16 @@ env.CppUnitTest(
     ],
 )
 
+env.CppUnitTest(
+    target="query_planner_partialidx_test",
+    source=[
+        "query_planner_partialidx_test.cpp"
+    ],
+    LIBDEPS=[
+        "query_planner_test_fixture",
+    ],
+)
+
 # $text pulls in a lot of stuff so we test it here.
 env.CppUnitTest(
     target="query_planner_text_test",
diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp
index a098175b112..765da9bd893 100644
--- a/src/mongo/db/query/get_executor.cpp
+++ b/src/mongo/db/query/get_executor.cpp
@@ -52,7 +52,6 @@
 #include "mongo/db/exec/update.h"
 #include "mongo/db/index_names.h"
 #include "mongo/db/index/index_descriptor.h"
-#include "mongo/db/matcher/expression_algo.h"
 #include "mongo/db/ops/update_lifecycle.h"
 #include "mongo/db/query/canonical_query.h"
 #include "mongo/db/query/explain.h"
@@ -117,20 +116,6 @@ void filterAllowedIndexEntries(const AllowedIndices& allowedIndices,
 namespace {
 // The body is below in the "count hack" section but getExecutor calls it.
 bool turnIxscanIntoCount(QuerySolution* soln);
-
-bool filteredIndexBad(const MatchExpression* filter, CanonicalQuery* query) {
-    if (!filter)
-        return false;
-
-    MatchExpression* queryPredicates = query->root();
-    if (!queryPredicates) {
-        // Index is filtered, but query has none.
-        // Impossible to use index.
-        return true;
-    }
-
-    return !expression::isSubsetOf(queryPredicates, filter);
-}
 }  // namespace
 
 
@@ -142,12 +127,7 @@ void fillOutPlannerParams(OperationContext* txn,
     IndexCatalog::IndexIterator ii = collection->getIndexCatalog()->getIndexIterator(txn, false);
     while (ii.more()) {
         const IndexDescriptor* desc = ii.next();
-
         IndexCatalogEntry* ice = ii.catalogEntry(desc);
-        if (filteredIndexBad(ice->getFilterExpression(), canonicalQuery)) {
-            continue;
-        }
-
         plannerParams->indices.push_back(IndexEntry(desc->keyPattern(),
                                                     desc->getAccessMethodName(),
                                                     desc->isMultikey(txn),
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index f1f133c8ee5..0b274c69ebf 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -34,6 +34,7 @@
 
 #include "mongo/db/geo/hash.h"
 #include "mongo/db/index_names.h"
+#include "mongo/db/matcher/expression_algo.h"
 #include "mongo/db/matcher/expression_array.h"
 #include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/matcher/expression_text.h"
@@ -365,6 +366,8 @@ void QueryPlannerIXSelect::stripInvalidAssignments(MatchExpression* node,
         MatchExpression::GEO_NEAR != node->matchType()) {
         stripInvalidAssignmentsTo2dsphereIndices(node, indices);
     }
+
+    stripInvalidAssignmentsToPartialIndices(node, indices);
 }
 
 namespace {
@@ -456,6 +459,72 @@ static void removeIndexRelevantTag(MatchExpression* node, size_t idx) {
     }
 }
 
+namespace {
+
+bool nodeIsNegationOrElemMatchObj(const MatchExpression* node) {
+    return (node->matchType() == MatchExpression::NOT ||
+            node->matchType() == MatchExpression::NOR ||
+            node->matchType() == MatchExpression::ELEM_MATCH_OBJECT);
+}
+
+void stripInvalidAssignmentsToPartialIndexNode(MatchExpression* node,
+                                               size_t idxNo,
+                                               const IndexEntry& idxEntry,
+                                               bool inNegationOrElemMatchObj) {
+    if (node->getTag()) {
+        removeIndexRelevantTag(node, idxNo);
+    }
+    inNegationOrElemMatchObj |= nodeIsNegationOrElemMatchObj(node);
+    for (size_t i = 0; i < node->numChildren(); ++i) {
+        // If 'node' is an OR and our current clause satisfies the filter expression, then we may be
+        // able to spare this clause from being stripped.  We only support such sparing if we're not
+        // in a negation or ELEM_MATCH_OBJECT, though:
+        // - If we're in a negation, then we're looking for documents that describe the inverse of
+        //   the current predicate.  For example, suppose we have an index with key pattern {a: 1}
+        //   and filter expression {a: {$gt: 0}}, and our OR is inside a negation and the current
+        //   clause we're evaluating is {a: 10}.  If we allow use of this index, then we'd end up
+        //   generating bounds corresponding to the predicate {a: {$ne: 10}}, which does not satisfy
+        //   the filter expression (note also that the match expression parser currently does not
+        //   generate trees with OR inside NOT, but we may consider changing it to allow this in the
+        //   future).
+        // - If we're in an ELEM_MATCH_OBJECT, then every predicate in the current clause has an
+        //   implicit prefix of the elemMatch's path, so it can't be compared outright to the filter
+        //   expression.  For example, suppose we have an index with key pattern {"a.b": 1} and
+        //   filter expression {f: 1}, and we are evaluating the first clause of the $or in the
+        //   query {a: {$elemMatch: {$or: [{b: 1, f: 1}, ...]}}}.  Even though {b: 1, f: 1}
+        //   satisfies the filter expression {f: 1}, the former is referring to fields "a.b" and
+        //   "a.f" while the latter is referring to field "f", so the clause does not actually
+        //   satisfy the filter expression and should not be spared.
+        if (!inNegationOrElemMatchObj && node->matchType() == MatchExpression::OR &&
+            expression::isSubsetOf(node->getChild(i), idxEntry.filterExpr)) {
+            continue;
+        }
+        stripInvalidAssignmentsToPartialIndexNode(
+            node->getChild(i), idxNo, idxEntry, inNegationOrElemMatchObj);
+    }
+}
+
+void stripInvalidAssignmentsToPartialIndexRoot(MatchExpression* root,
+                                               size_t idxNo,
+                                               const IndexEntry& idxEntry) {
+    if (expression::isSubsetOf(root, idxEntry.filterExpr)) {
+        return;
+    }
+    const bool inNegationOrElemMatchObj = nodeIsNegationOrElemMatchObj(root);
+    stripInvalidAssignmentsToPartialIndexNode(root, idxNo, idxEntry, inNegationOrElemMatchObj);
+}
+
+}  // namespace
+
+void QueryPlannerIXSelect::stripInvalidAssignmentsToPartialIndices(
+    MatchExpression* node, const vector<IndexEntry>& indices) {
+    for (size_t i = 0; i < indices.size(); ++i) {
+        if (indices[i].filterExpr) {
+            stripInvalidAssignmentsToPartialIndexRoot(node, i, indices[i]);
+        }
+    }
+}
+
 //
 // Text index quirks
 //
diff --git a/src/mongo/db/query/planner_ixselect.h b/src/mongo/db/query/planner_ixselect.h
index bbef9748d3a..b782e6d8560 100644
--- a/src/mongo/db/query/planner_ixselect.h
+++ b/src/mongo/db/query/planner_ixselect.h
@@ -177,6 +177,39 @@ private:
      */
     static void stripInvalidAssignmentsTo2dsphereIndices(MatchExpression* node,
                                                          const std::vector<IndexEntry>& indices);
+
+    /**
+     * This function strips RelevantTag assignments to partial indices, where the assignment is
+     * incompatible with the index's filter expression.
+     *
+     * For example, suppose there exists a partial index in 'indices' with key pattern {a: 1} and
+     * filter expression {f: {$exists: true}}.  If 'node' is {a: 1}, this function would strip the
+     * EQ predicate's assignment to the partial index (because if it did not, plans that use this
+     * index would miss documents that don't satisfy the filter expression).  On the other hand, if
+     * 'node' is {a: 1, f: 1}, then the partial index could be used, and so this function would not
+     * strip the assignment.
+     *
+     * Special note about OR clauses: if 'node' contains a leaf with an assignment to a partial
+     * index inside an OR, this function will look both inside and outside the OR clause in an
+     * attempt to find predicates that could satisfy the partial index, but these predicates must be
+     * wholly contained either inside or outside.
+     *
+     * To illustrate, given a partial index {a: 1} with filter expression {f: true, g: true}, the
+     * assignment of the "a" predicate would not be stripped for either of the following
+     * expressions:
+     * - {f: true, g: true, $or: [{a: 0}, {a: 1}]}
+     * - {$or: [{a: 1, f: true, g: true}, {_id: 1}]}
+     *
+     * However, the assignment of the "a" predicate would be stripped in the following expression:
+     * - {f: true, $or: [{a: 1, g: true}, {_id: 1}]}
+     *
+     * For the last case, the assignment is stripped is because the {f: true} predicate and the
+     * {g: true} predicate are both needed for the {a: 1} predicate to be compatible with the
+     * partial index, but the {f: true} predicate is outside the OR while the {g: true} predicate is
+     * contained within the OR.
+     */
+    static void stripInvalidAssignmentsToPartialIndices(MatchExpression* node,
+                                                        const std::vector<IndexEntry>& indices);
 };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 6b98e0fae79..bb5a163835c 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -35,6 +35,7 @@
 #include <vector>
 
 #include "mongo/client/dbclientinterface.h"  // For QueryOption_foobar
+#include "mongo/db/matcher/expression_algo.h"
 #include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/matcher/expression_text.h"
 #include "mongo/db/query/canonical_query.h"
@@ -814,15 +815,9 @@ Status QueryPlanner::plan(const CanonicalQuery& query,
         if (!usingIndexToSort) {
             for (size_t i = 0; i < params.indices.size(); ++i) {
                 const IndexEntry& index = params.indices[i];
-                // Only regular (non-plugin) indexes can be used to provide a sort.
-                if (index.type != INDEX_BTREE) {
-                    continue;
-                }
-                // Only non-sparse indexes can be used to provide a sort.
-                if (index.sparse) {
-                    continue;
-                }
-
+                // Only regular (non-plugin) indexes can be used to provide a sort, and only
+                // non-sparse indexes can be used to provide a sort.
+                //
                 // TODO: Sparse indexes can't normally provide a sort, because non-indexed
                 // documents could potentially be missing from the result set.  However, if the
                 // query predicate can be used to guarantee that all documents to be returned
@@ -834,6 +829,18 @@ Status QueryPlanner::plan(const CanonicalQuery& query,
                 // - Index {a: 1, b: "2dsphere"} (which is "geo-sparse", if
                 //   2dsphereIndexVersion=2) should be able to provide a sort for
                 //   find({b: GEO}).sort({a:1}).  SERVER-10801.
+                if (index.type != INDEX_BTREE) {
+                    continue;
+                }
+                if (index.sparse) {
+                    continue;
+                }
+
+                // Partial indexes can only be used to provide a sort only if the query predicate is
+                // compatible.
+                if (index.filterExpr && !expression::isSubsetOf(query.root(), index.filterExpr)) {
+                    continue;
+                }
 
                 const BSONObj kp = QueryPlannerAnalysis::getSortPattern(index.keyPattern);
                 if (providesSort(query, kp)) {
diff --git a/src/mongo/db/query/query_planner_partialidx_test.cpp b/src/mongo/db/query/query_planner_partialidx_test.cpp
new file mode 100644
index 00000000000..6f27939b10a
--- /dev/null
+++ b/src/mongo/db/query/query_planner_partialidx_test.cpp
@@ -0,0 +1,447 @@
+/**
+ *    Copyright (C) 2015 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/query/query_planner.h"
+#include "mongo/db/query/query_planner_test_fixture.h"
+
+namespace mongo {
+namespace {
+
+TEST_F(QueryPlannerTest, PartialIndexEq) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{a: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{a: 1}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {ixscan: "
+        "{filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[1, 1, true, true]]}}}}}");
+
+    runQuery(fromjson("{a: -1}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexNot) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{a: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{a: {$ne: 1}}"));
+    assertNumSolutions(0U);
+
+    runQuery(fromjson("{a: {$ne: -1}}"));
+    assertNumSolutions(0U);
+
+    runQuery(fromjson("{a: {$not: {$lte: 0}}}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexElemMatchObj) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{'a.b': {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{'a.b': 1}"), filterExpr.get());
+
+    // The following query could in theory use the partial index, but we don't support it right now.
+    runQuery(fromjson("{a: {$elemMatch: {b: 1}}}"));
+    assertNumSolutions(0U);
+
+    runQuery(fromjson("{a: {$elemMatch: {b: -1}}}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexElemMatchObjContainingOr) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{'a.b': {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{'a.b': 1}"), filterExpr.get());
+
+    // The following query could in theory use the partial index, but we don't support it right now.
+    runQuery(fromjson("{a: {$elemMatch: {$or: [{b: 1}, {b: 2}]}}}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexElemMatchObjWithBadSubobjectFilter) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{b: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{'a.b': 1}"), filterExpr.get());
+
+    runQuery(fromjson("{a: {$elemMatch: {$or: [{b: 1}, {b: 2}]}}}"));
+    assertNumSolutions(0U);
+
+    runQuery(fromjson("{a: {$elemMatch: {b: {$in: [1, 2]}}}}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexAndSingleAssignment) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{a: 1, f: 1}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[1, 1, true, true]]}}}}}");
+
+    runQuery(fromjson("{a: 1, f: -1}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexAndMultipleAssignments) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{a: {$gte: 0, $lte: 10}, f: 1}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[0, 10, true, true]]}}}}}");
+
+    runQuery(fromjson("{a: {$gte: 0, $lte: 10}, f: -1}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexOr) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{a: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{$or: [{a: 1}, {_id: 0}]}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {or: {nodes: ["
+        "{ixscan: {filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[1, 1, true, true]]}}},"
+        "{ixscan: {filter: null, pattern: {_id: 1}, "
+        "bounds: {_id: [[0, 0, true, true]]}}}]}}}}");
+
+    runQuery(fromjson("{$or: [{a: -1}, {_id: 0}]}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexOrContainingAnd) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{$or: [{a: 1, f: 1}, {_id: 0}]}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {or: {nodes: ["
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1},"
+        "bounds: {a: [[1, 1, true, true]]}}}}},"
+        "{ixscan: {filter: null, pattern: {_id: 1}, "
+        "bounds: {_id: [[0, 0, true, true]]}}}]}}}}");
+
+    runQuery(fromjson("{$or: [{a: 1, f: -1}, {_id: 0}]}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexOrContainingAndMultipleAssignments) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{a: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{$or: [{_id: 0, a: 1}, {a: 2}]}"));
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {or: {nodes: ["
+        "{fetch: {filter: {a: 1}, node: {ixscan: "
+        "{filter: null, pattern: {_id: 1}, "
+        "bounds: {_id: [[0, 0, true, true]]}}}}},"
+        "{ixscan: {filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[2, 2, true, true]]}}}]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {or: {nodes: ["
+        "{fetch: {filter: {_id: 0}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[1, 1, true, true]]}}}}},"
+        "{ixscan: {filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[2, 2, true, true]]}}}]}}}}");
+
+    runQuery(fromjson("{$or: [{_id: 0, a: -1}, {a: 2}]}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {or: {nodes: ["
+        "{fetch: {filter: {a: -1}, node: {ixscan: "
+        "{filter: null, pattern: {_id: 1}, "
+        "bounds: {_id: [[0, 0, true, true]]}}}}},"
+        "{ixscan: {filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[2, 2, true, true]]}}}]}}}}");
+
+    runQuery(fromjson("{$or: [{_id: 0, a: -1}, {a: -2}]}"));
+    assertNumSolutions(0U);
+}
+
+
+TEST_F(QueryPlannerTest, PartialIndexAndContainingOrContainingAnd) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{x: 1, $or: [{a: 1, f: 1}, {_id: 0}]}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: {x: 1}, node: {or: {nodes: ["
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1},"
+        "bounds: {a: [[1, 1, true, true]]}}}}},"
+        "{ixscan: {filter: null, pattern: {_id: 1}, "
+        "bounds: {_id: [[0, 0, true, true]]}}}]}}}}");
+
+    runQuery(fromjson("{x: 1, $or: [{a: 1, f: -1}, {_id: 0}]}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexAndContainingOrContainingAndSatisfyingPredOutside) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}, g: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{f: 1, g: 1, $or: [{a: 1, x: 1}, {_id: 0}]}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: {f: 1, g: 1}, node: {or: {nodes: ["
+        "{fetch: {filter: {x: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1},"
+        "bounds: {a: [[1, 1, true, true]]}}}}},"
+        "{ixscan: {filter: null, pattern: {_id: 1}, "
+        "bounds: {_id: [[0, 0, true, true]]}}}]}}}}");
+
+    // The following query could in theory use the partial index, but we don't support it right now.
+    runQuery(fromjson("{f: 1, x: 1, $or: [{a: 1, g: 1}, {_id: 0}]}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexOrContainingAndContainingOr) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{a: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+    runQuery(fromjson("{$or: [{x: 1, $or: [{a: 1}, {_id: 0}]}, {_id: 1}]}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {or: {nodes: ["
+        "{fetch: {filter: {x: 1}, node: {or: {nodes: ["
+        "{ixscan: {filter: null, pattern: {a: 1},"
+        "bounds: {a: [[1, 1, true, true]]}}},"
+        "{ixscan: {filter: null, pattern: {_id: 1},"
+        "bounds: {_id: [[0, 0, true, true]]}}}]}}}},"
+        "{ixscan: {filter: null, pattern: {_id: 1}, "
+        "bounds: {_id: [[1, 1, true, true]]}}}]}}}}");
+
+    runQuery(fromjson("{$or: [{x: 1, $or: [{a: -1}, {_id: 2}]}, {_id: 1}]}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexProvidingSort) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuerySortProj(fromjson("{f: 1}"), fromjson("{a: 1}"), BSONObj());
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1}, "
+        "bounds: {a: [['MinKey', 'MaxKey', true, true]]}}}}}");
+
+    runQuerySortProj(fromjson("{f: -1}"), fromjson("{a: 1}"), BSONObj());
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexOrContainingNot) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{a: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{$or: [{a: {$ne: 1}}, {_id: 1}]}"));
+    assertNumSolutions(0U);
+
+    runQuery(fromjson("{$or: [{a: {$ne: -1}}, {_id: 1}]}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexMultipleSameAnd) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObjA(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExprA = parseMatchExpression(filterObjA);
+    addIndex(fromjson("{a: 1}"), filterExprA.get());
+    BSONObj filterObjB(fromjson("{g: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExprB = parseMatchExpression(filterObjB);
+    addIndex(fromjson("{b: 1}"), filterExprB.get());
+
+    runQuery(fromjson("{a: 1, b: 1, f: 1, g: 1}"));
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{fetch: {filter: {b: 1, f: 1, g: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[1, 1, true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: 1, f: 1, g: 1}, node: {ixscan: "
+        "{filter: null, pattern: {b: 1}, "
+        "bounds: {b: [[1, 1, true, true]]}}}}}");
+
+    runQuery(fromjson("{a: 1, b: 1, f: 1, g: -1}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: {b: 1, f: 1, g: -1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[1, 1, true, true]]}}}}}");
+
+    runQuery(fromjson("{a: 1, b: 1, f: -1, g: -1}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexMultipleSameAndCompoundSharedPrefix) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1, b: 1}"), filterExpr.get());
+    addIndex(fromjson("{a: 1, c: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{a: 1, f: 1}"));
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[1, 1, true, true]], "
+        "b: [['MinKey', 'MaxKey', true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1, c: 1}, "
+        "bounds: {a: [[1, 1, true, true]], "
+        "c: [['MinKey', 'MaxKey', true, true]]}}}}}");
+
+    runQuery(fromjson("{a: 1, f: -1}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexMultipleSameOr) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObjA(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExprA = parseMatchExpression(filterObjA);
+    addIndex(fromjson("{a: 1}"), filterExprA.get());
+    BSONObj filterObjB(fromjson("{g: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExprB = parseMatchExpression(filterObjB);
+    addIndex(fromjson("{b: 1}"), filterExprB.get());
+
+    runQuery(fromjson("{$or: [{a: 1, f: 1}, {b: 1, g: 1}]}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{or: {nodes: ["
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1}, "
+        "bounds: {a: [[1, 1, true, true]]}}}}},"
+        "{fetch: {filter: {g: 1}, node: {ixscan: "
+        "{filter: null, pattern: {b: 1}, "
+        "bounds: {b: [[1, 1, true, true]]}}}}}]}}");
+
+    runQuery(fromjson("{$or: [{a: 1, f: 1}, {b: 1, g: -1}]}"));
+    assertNumSolutions(0U);
+
+    runQuery(fromjson("{$or: [{a: 1, f: -1}, {b: 1, g: -1}]}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexAndCompoundIndex) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1, b: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{a: 1, b: 1, f: 1}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[1, 1, true, true]], "
+        "b: [[1, 1, true, true]]}}}}}");
+
+    runQuery(fromjson("{a: 1, b: 1, f: -1}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexOrCompoundIndex) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1, b: 1}"), filterExpr.get());
+
+    runQuery(fromjson("{$or: [{a: 1, b: 1, f: 1}, {_id: 1}]}"));
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {or: {nodes: ["
+        "{fetch: {filter: {f: 1}, node: {ixscan: "
+        "{filter: null, pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[1, 1, true, true]], "
+        "b: [[1, 1, true, true]]}}}}},"
+        "{ixscan: {filter: null, pattern: {_id: 1}, "
+        "bounds: {_id: [[1, 1, true, true]]}}}]}}}}");
+
+    runQuery(fromjson("{$or: [{a: 1, b: 1, f: -1}, {_id: 1}]}"));
+    assertNumSolutions(0U);
+}
+
+TEST_F(QueryPlannerTest, PartialIndexNor) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    BSONObj filterObj(fromjson("{f: {$gt: 0}}"));
+    std::unique_ptr<MatchExpression> filterExpr = parseMatchExpression(filterObj);
+    addIndex(fromjson("{a: 1}"), filterExpr.get());
+
+    // The following query could in theory use the partial index, but we don't support it right now.
+    runQuery(fromjson("{$nor: [{a: 1, f: 1}, {_id: 1}]}"));
+    assertNumSolutions(0U);
+
+    runQuery(fromjson("{$nor: [{a: 1, f: -1}, {_id: 1}]}"));
+    assertNumSolutions(0U);
+}
+
+}  // namespace
+}  // namespace mongo
diff --git a/src/mongo/db/query/query_planner_test_fixture.cpp b/src/mongo/db/query/query_planner_test_fixture.cpp
index 496b6e37128..5f70ab0de64 100644
--- a/src/mongo/db/query/query_planner_test_fixture.cpp
+++ b/src/mongo/db/query/query_planner_test_fixture.cpp
@@ -91,6 +91,16 @@ void QueryPlannerTest::addIndex(BSONObj keyPattern, BSONObj infoObj) {
                                         infoObj));
 }
 
+void QueryPlannerTest::addIndex(BSONObj keyPattern, MatchExpression* filterExpr) {
+    params.indices.push_back(IndexEntry(keyPattern,
+                                        false,  // multikey
+                                        false,  // sparse
+                                        false,  // unique
+                                        "foo",
+                                        filterExpr,
+                                        BSONObj()));
+}
+
 void QueryPlannerTest::runQuery(BSONObj query) {
     runQuerySortProjSkipLimit(query, BSONObj(), BSONObj(), 0, 0);
 }
@@ -324,4 +334,13 @@ void QueryPlannerTest::assertHasOneSolutionOf(const std::vector<std::string>& so
     FAIL(ss);
 }
 
+std::unique_ptr<MatchExpression> QueryPlannerTest::parseMatchExpression(const BSONObj& obj) {
+    StatusWithMatchExpression status = MatchExpressionParser::parse(obj);
+    if (!status.isOK()) {
+        FAIL(str::stream() << "failed to parse query: " << obj.toString()
+                           << ". Reason: " << status.getStatus().toString());
+    }
+    return std::unique_ptr<MatchExpression>(status.getValue());
+}
+
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_planner_test_fixture.h b/src/mongo/db/query/query_planner_test_fixture.h
index 843ed949e1a..de229a89e45 100644
--- a/src/mongo/db/query/query_planner_test_fixture.h
+++ b/src/mongo/db/query/query_planner_test_fixture.h
@@ -57,6 +57,8 @@ protected:
 
     void addIndex(BSONObj keyPattern, BSONObj infoObj);
 
+    void addIndex(BSONObj keyPattern, MatchExpression* filterExpr);
+
     //
     // Execute planner.
     //
@@ -178,6 +180,11 @@ protected:
      */
     void assertHasOneSolutionOf(const std::vector<std::string>& solnStrs) const;
 
+    /**
+     * Helper function to parse a MatchExpression.
+     */
+    static std::unique_ptr<MatchExpression> parseMatchExpression(const BSONObj& obj);
+
     //
     // Data members.
     //