SERVER-15802 if an equality over a single-field unique index can be used to index an AND, ignore all other indices

11 files changed, 246 insertions, 7 deletions

diff --git a/src/mongo/db/exec/sort.cpp b/src/mongo/db/exec/sort.cpp
index 3ccafbdb318..eee9a44eb45 100644
--- a/src/mongo/db/exec/sort.cpp
+++ b/src/mongo/db/exec/sort.cpp
@@ -229,7 +229,8 @@ namespace mongo {
         params.options = QueryPlannerParams::NO_TABLE_SCAN;
 
         // We're creating a "virtual index" with key pattern equal to the sort order.
-        IndexEntry sortOrder(sortObj, IndexNames::BTREE, true, false, "doesnt_matter", BSONObj());
+        IndexEntry sortOrder(sortObj, IndexNames::BTREE, true, false, false, "doesnt_matter",
+                             BSONObj());
         params.indices.push_back(sortOrder);
 
         CanonicalQuery* rawQueryForSort;
diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp
index 0f4847f8a4e..5248d78cfd9 100644
--- a/src/mongo/db/query/get_executor.cpp
+++ b/src/mongo/db/query/get_executor.cpp
@@ -125,6 +125,7 @@ namespace mongo {
                                                         desc->getAccessMethodName(),
                                                         desc->isMultikey(txn),
                                                         desc->isSparse(),
+                                                        desc->unique(),
                                                         desc->indexName(),
                                                         desc->infoObj()));
         }
@@ -1107,6 +1108,7 @@ namespace mongo {
                                                            desc->getAccessMethodName(),
                                                            desc->isMultikey(txn),
                                                            desc->isSparse(),
+                                                           desc->unique(),
                                                            desc->indexName(),
                                                            desc->infoObj()));
             }
diff --git a/src/mongo/db/query/index_bounds_builder_test.cpp b/src/mongo/db/query/index_bounds_builder_test.cpp
index accf74f06fa..e82c130b278 100644
--- a/src/mongo/db/query/index_bounds_builder_test.cpp
+++ b/src/mongo/db/query/index_bounds_builder_test.cpp
@@ -495,8 +495,9 @@ namespace {
 
     TEST(IndexBoundsBuilderTest, ExistsTrueSparse) {
         IndexEntry testIndex = IndexEntry(BSONObj(),
-                                          false,
-                                          true,
+                                          false, // multikey
+                                          true, // sparse
+                                          false, // unique
                                           "exists_true_sparse",
                                           BSONObj());
         BSONObj obj = fromjson("{a: {$exists: true}}");
diff --git a/src/mongo/db/query/index_entry.h b/src/mongo/db/query/index_entry.h
index 5cb25c0aac4..78b8996779d 100644
--- a/src/mongo/db/query/index_entry.h
+++ b/src/mongo/db/query/index_entry.h
@@ -47,11 +47,13 @@ namespace mongo {
                    const std::string& accessMethod,
                    bool mk,
                    bool sp,
+                   bool unq,
                    const std::string& n,
                    const BSONObj& io)
             : keyPattern(kp),
               multikey(mk),
               sparse(sp),
+              unique(unq),
               name(n),
               infoObj(io) {
 
@@ -64,16 +66,18 @@ namespace mongo {
         IndexEntry(const BSONObj& kp,
                    bool mk,
                    bool sp,
+                   bool unq,
                    const std::string& n,
                    const BSONObj& io)
             : keyPattern(kp),
               multikey(mk),
               sparse(sp),
+              unique(unq),
               name(n),
               infoObj(io) {
 
             type = IndexNames::nameToType(IndexNames::findPluginName(keyPattern));
-        }     
+        }
 
         /**
          * For testing purposes only.
@@ -82,11 +86,12 @@ namespace mongo {
             : keyPattern(kp),
               multikey(false),
               sparse(false),
+              unique(false),
               name("test_foo"),
               infoObj(BSONObj()) {
 
             type = IndexNames::nameToType(IndexNames::findPluginName(keyPattern));
-        }     
+        }
 
         BSONObj keyPattern;
 
@@ -94,6 +99,8 @@ namespace mongo {
 
         bool sparse;
 
+        bool unique;
+
         std::string name;
 
         // Geo indices have extra parameters.  We need those available to plan correctly.
diff --git a/src/mongo/db/query/plan_cache_test.cpp b/src/mongo/db/query/plan_cache_test.cpp
index e10f112134a..b21cc891d75 100644
--- a/src/mongo/db/query/plan_cache_test.cpp
+++ b/src/mongo/db/query/plan_cache_test.cpp
@@ -470,6 +470,7 @@ namespace {
             params.indices.push_back(IndexEntry(keyPattern,
                                                 multikey,
                                                 false,
+                                                false,
                                                 "hari_king_of_the_stove",
                                                 BSONObj()));
         }
@@ -478,6 +479,7 @@ namespace {
             params.indices.push_back(IndexEntry(keyPattern,
                                                 multikey,
                                                 sparse,
+                                                false,
                                                 "note_to_self_dont_break_build",
                                                 BSONObj()));
         }
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index f00231aee5b..024830399a4 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -379,6 +379,73 @@ namespace mongo {
         }
     }
 
+    namespace {
+
+        /**
+         * For every node in the subtree rooted at 'node' that has a RelevantTag, removes index
+         * assignments from that tag.
+         *
+         * Used as a helper for stripUnneededAssignments().
+         */
+        void clearAssignments(MatchExpression* node) {
+            if (node->getTag()) {
+                RelevantTag* rt = static_cast<RelevantTag*>(node->getTag());
+                rt->first.clear();
+                rt->notFirst.clear();
+            }
+
+            for (size_t i = 0; i < node->numChildren(); i++) {
+                clearAssignments(node->getChild(i));
+            }
+        }
+
+    } // namespace
+
+    // static
+    void QueryPlannerIXSelect::stripUnneededAssignments(MatchExpression* node,
+                                                        const std::vector<IndexEntry>& indices) {
+        if (MatchExpression::AND == node->matchType()) {
+            for (size_t i = 0; i < node->numChildren(); i++) {
+                MatchExpression* child = node->getChild(i);
+
+                if (MatchExpression::EQ != child->matchType()) {
+                    continue;
+                }
+
+                if (!child->getTag()) {
+                    continue;
+                }
+
+                // We found a EQ child of an AND which is tagged.
+                RelevantTag* rt = static_cast<RelevantTag*>(child->getTag());
+
+                // Look through all of the indices for which this predicate can be answered with
+                // the leading field of the index.
+                for (std::vector<size_t>::const_iterator i = rt->first.begin();
+                        i != rt->first.end(); ++i) {
+                    size_t index = *i;
+
+                    if (indices[index].unique && 1 == indices[index].keyPattern.nFields()) {
+                        // Found an EQ predicate which can use a single-field unique index.
+                        // Clear assignments from the entire tree, and add back a single assignment
+                        // for 'child' to the unique index.
+                        clearAssignments(node);
+                        RelevantTag* newRt = static_cast<RelevantTag*>(child->getTag());
+                        newRt->first.push_back(index);
+
+                        // Tag state has been reset in the entire subtree at 'root'; nothing
+                        // else for us to do.
+                        return;
+                    }
+                }
+            }
+        }
+
+        for (size_t i = 0; i < node->numChildren(); i++) {
+            stripUnneededAssignments(node->getChild(i), indices);
+        }
+    }
+
     //
     // Helpers used by stripInvalidAssignments
     //
diff --git a/src/mongo/db/query/planner_ixselect.h b/src/mongo/db/query/planner_ixselect.h
index ca385bd35fa..486ce4a42e5 100644
--- a/src/mongo/db/query/planner_ixselect.h
+++ b/src/mongo/db/query/planner_ixselect.h
@@ -96,6 +96,33 @@ namespace mongo {
         static void stripInvalidAssignments(MatchExpression* node,
                                             const std::vector<IndexEntry>& indices);
 
+        /**
+         * In some special cases, we can strip most of the index assignments from the tree early
+         * on. Specifically, if we find an AND which has a child tagged for equality over a
+         * single-field unique index, then all other predicate-to-index assignments can be
+         * stripped off the subtree rooted at 'node'.
+         *
+         * This is used to ensure that we always favor key-value lookup plans over any
+         * more complex plan.
+         *
+         * Example:
+         *   Suppose you have match expression OR (AND (a==1, b==2), AND (c==3, d==4)).
+         *   There are indices on fields, 'a', 'b', 'c', and 'd'. The index on 'd' is
+         *   the only unique index.
+         *
+         *   This code will find that the subtree AND (c==3, d==4) can be answered by
+         *   looking up the value of 'd' in the unique index. Since no better plan than
+         *   a single key lookup is ever available, all assignments in this subtree
+         *   are stripped, except for the assignment of d==4 to the unique 'd' index.
+         *
+         *   Stripping the assignment for 'c' causes the planner to generate just two
+         *   possible plans:
+         *     1) an OR of an index scan over 'a' and an index scan over 'd'
+         *     2) an OR of an index scan over 'b' and an index scan over 'd'
+         */
+        static void stripUnneededAssignments(MatchExpression* node,
+                                             const std::vector<IndexEntry>& indices);
+
     private:
         /**
          * Amend the RelevantTag lists for all predicates in the subtree rooted at 'node' to remove
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index c17a9965ffb..87b4fb6b2f2 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -689,6 +689,20 @@ namespace mongo {
         QueryPlannerIXSelect::rateIndices(query.root(), "", relevantIndices);
         QueryPlannerIXSelect::stripInvalidAssignments(query.root(), relevantIndices);
 
+        // Unless we have GEO_NEAR, TEXT, or a projection, we may be able to apply an optimization
+        // in which we strip unnecessary index assignments.
+        //
+        // Disallowed with projection because assignment to a non-unique index can allow the plan
+        // to be covered.
+        //
+        // TEXT and GEO_NEAR are special because they require the use of a text/geo index in order
+        // to be evaluated correctly. Stripping these "mandatory assignments" is therefore invalid.
+        if (query.getParsed().getProj().isEmpty()
+            && !QueryPlannerCommon::hasNode(query.root(), MatchExpression::GEO_NEAR)
+            && !QueryPlannerCommon::hasNode(query.root(), MatchExpression::TEXT)) {
+            QueryPlannerIXSelect::stripUnneededAssignments(query.root(), relevantIndices);
+        }
+
         // query.root() is now annotated with RelevantTag(s).
         QLOG() << "Rated tree:" << endl << query.root()->toString();
 
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index fec4c3c5ae9..180d4648d38 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -82,6 +82,7 @@ namespace {
             params.indices.push_back(IndexEntry(keyPattern,
                                                 multikey,
                                                 false,
+                                                false,
                                                 "hari_king_of_the_stove",
                                                 BSONObj()));
         }
@@ -90,12 +91,22 @@ namespace {
             params.indices.push_back(IndexEntry(keyPattern,
                                                 multikey,
                                                 sparse,
+                                                false,
                                                 "note_to_self_dont_break_build",
                                                 BSONObj()));
         }
 
+        void addIndex(BSONObj keyPattern, bool multikey, bool sparse, bool unique) {
+            params.indices.push_back(IndexEntry(keyPattern,
+                                                multikey,
+                                                sparse,
+                                                unique,
+                                                "sql_query_walks_into_bar_and_says_can_i_join_you?",
+                                                BSONObj()));
+        }
+
         void addIndex(BSONObj keyPattern, BSONObj infoObj) {
-            params.indices.push_back(IndexEntry(keyPattern, false, false, "foo", infoObj));
+            params.indices.push_back(IndexEntry(keyPattern, false, false, false, "foo", infoObj));
         }
 
         //
@@ -5123,6 +5134,110 @@ namespace {
                                     "bounds: {a: [[3,3,true,true]]}}}]}}}}");
     }
 
+
+    // If a lookup against a unique index is available as a possible plan, then the planner
+    // should not generate other possibilities.
+    TEST_F(QueryPlannerTest, UniqueIndexLookup) {
+        params.options = QueryPlannerParams::INDEX_INTERSECTION;
+        params.options |= QueryPlannerParams::NO_TABLE_SCAN;
+
+        addIndex(BSON("a" << 1));
+        addIndex(BSON("b" << 1),
+                 false, // multikey
+                 false, // sparse,
+                 true); // unique
+
+        runQuery(fromjson("{a: 1, b: 1}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {filter: {a: 1}, node: "
+                                "{ixscan: {filter: null, pattern: {b: 1}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, HintOnNonUniqueIndex) {
+        params.options = QueryPlannerParams::INDEX_INTERSECTION;
+
+        addIndex(BSON("a" << 1));
+        addIndex(BSON("b" << 1),
+                 false, // multikey
+                 false, // sparse,
+                 true); // unique
+
+        runQueryHint(fromjson("{a: 1, b: 1}"), BSON("a" << 1));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {filter: {b: 1}, node: "
+                                "{ixscan: {filter: null, pattern: {a: 1}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, UniqueIndexLookupBelowOr) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+
+        addIndex(BSON("a" << 1));
+        addIndex(BSON("b" << 1));
+        addIndex(BSON("c" << 1));
+        addIndex(BSON("d" << 1),
+                 false, // multikey
+                 false, // sparse,
+                 true); // unique
+
+        runQuery(fromjson("{$or: [{a: 1, b: 1}, {c: 1, d: 1}]}"));
+
+        // Only two plans because we throw out plans for the right branch of the $or that do not
+        // use equality over the unique index.
+        assertNumSolutions(2U);
+        assertSolutionExists("{or: {nodes: ["
+                                "{fetch: {filter: {a: 1}, node: {ixscan: {pattern: {b: 1}}}}},"
+                                "{fetch: {filter: {c: 1}, node: {ixscan: {pattern: {d: 1}}}}}]}}");
+        assertSolutionExists("{or: {nodes: ["
+                                "{fetch: {filter: {b: 1}, node: {ixscan: {pattern: {a: 1}}}}},"
+                                "{fetch: {filter: {c: 1}, node: {ixscan: {pattern: {d: 1}}}}}]}}");
+    }
+
+    TEST_F(QueryPlannerTest, UniqueIndexLookupBelowOrBelowAnd) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+
+        addIndex(BSON("a" << 1));
+        addIndex(BSON("b" << 1));
+        addIndex(BSON("c" << 1));
+        addIndex(BSON("d" << 1),
+                 false, // multikey
+                 false, // sparse,
+                 true); // unique
+
+        runQuery(fromjson("{e: 1, $or: [{a: 1, b: 1}, {c: 1, d: 1}]}"));
+
+        // Only two plans because we throw out plans for the right branch of the $or that do not
+        // use equality over the unique index.
+        assertNumSolutions(2U);
+        assertSolutionExists("{fetch: {filter: {e: 1}, node: {or: {nodes: ["
+                                "{fetch: {filter: {a: 1}, node: {ixscan: {pattern: {b: 1}}}}},"
+                                "{fetch: {filter: {c: 1}, node: {ixscan: {pattern: {d: 1}}}}}"
+                             "]}}}}");
+        assertSolutionExists("{fetch: {filter: {e: 1}, node: {or: {nodes: ["
+                                "{fetch: {filter: {b: 1}, node: {ixscan: {pattern: {a: 1}}}}},"
+                                "{fetch: {filter: {c: 1}, node: {ixscan: {pattern: {d: 1}}}}}"
+                             "]}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CoveredOrUniqueIndexLookup) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+
+        addIndex(BSON("a" << 1 << "b" << 1));
+        addIndex(BSON("a" << 1),
+                 false, // multikey
+                 false, // sparse,
+                 true); // unique
+
+        runQuerySortProj(fromjson("{a: 1, b: 1}"), BSONObj(), fromjson("{_id: 0, a: 1}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{proj: {spec: {_id: 0, a: 1}, node: "
+                                "{fetch: {filter: {b: 1}, node: {ixscan: {pattern: {a: 1}}}}}}}");
+        assertSolutionExists("{proj: {spec: {_id: 0, a: 1}, node: "
+                                "{ixscan: {filter: null, pattern: {a: 1, b: 1}}}}}");
+    }
+
     //
     // Test bad input to query planner helpers.
     //
diff --git a/src/mongo/db/query/query_planner_text_test.cpp b/src/mongo/db/query/query_planner_text_test.cpp
index f88f9bb16dc..376cf8fd809 100644
--- a/src/mongo/db/query/query_planner_text_test.cpp
+++ b/src/mongo/db/query/query_planner_text_test.cpp
@@ -79,6 +79,7 @@ namespace {
             params.indices.push_back(IndexEntry(keyPattern,
                                                 multikey,
                                                 false,
+                                                false,
                                                 "hari_king_of_the_stove",
                                                 BSONObj()));
         }
@@ -87,6 +88,7 @@ namespace {
             params.indices.push_back(IndexEntry(keyPattern,
                                                 multikey,
                                                 sparse,
+                                                false,
                                                 "note_to_self_dont_break_build",
                                                 BSONObj()));
         }
diff --git a/src/mongo/s/chunk.cpp b/src/mongo/s/chunk.cpp
index 62a19e74213..6722ef3ca8a 100644
--- a/src/mongo/s/chunk.cpp
+++ b/src/mongo/s/chunk.cpp
@@ -1299,7 +1299,8 @@ namespace mongo {
         QueryPlannerParams plannerParams;
         // Must use "shard key" index
         plannerParams.options = QueryPlannerParams::NO_TABLE_SCAN;
-        IndexEntry indexEntry(key, accessMethod, false /* multiKey */, false /* sparse */, "shardkey", BSONObj());
+        IndexEntry indexEntry(key, accessMethod, false /* multiKey */, false /* sparse */,
+                              false /* unique */, "shardkey", BSONObj());
         plannerParams.indices.push_back(indexEntry);
 
         OwnedPointerVector<QuerySolution> solutions;