SERVER-41872 PlanEnumerator AndAssignment::choices ordering not stable and is relevant to set of plans generated

(cherry picked from commit 6ca9be706ce03a2c79d29feac3cfd294cc09445d)
(cherry picked from commit 4af99c4f2845a228fab9c4aaaafe513e21c792a5)
(cherry picked from commit 5959f04d2c6c661a5446be04264e0f5fa79747d8)

2 files changed, 73 insertions, 4 deletions

diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h
index 53643b2a95c..8b563ed145b 100644
--- a/src/mongo/db/query/plan_enumerator.h
+++ b/src/mongo/db/query/plan_enumerator.h
@@ -430,10 +430,16 @@ private:
      */
     bool alreadyCompounded(const std::set<MatchExpression*>& ixisectAssigned,
                            const AndAssignment* andAssignment);
+
+    struct CmpByIndexID {
+        bool operator()(IndexID a, IndexID b) const {
+            return a < b;
+        }
+    };
     /**
-     * Output index intersection assignments inside of an AND node.
+     * Maps from index id to the list of predicates assigned to that index.
      */
-    typedef unordered_map<IndexID, std::vector<MatchExpression*>> IndexToPredMap;
+    typedef std::map<IndexID, std::vector<MatchExpression*>, CmpByIndexID> IndexToPredMap;
 
     /**
      * Generate index intersection assignments given the predicate/index structure in idxToFirst
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index b9a79204a81..e07a5a37b51 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -1521,8 +1521,7 @@ TEST_F(QueryPlannerTest, CantUseHashedIndexToProvideSortWithIndexablePred) {
 TEST_F(QueryPlannerTest, CantUseTextIndexToProvideSort) {
     addIndex(BSON("x" << 1 << "_fts"
                       << "text"
-                      << "_ftsx"
-                      << 1));
+                      << "_ftsx" << 1));
     runQuerySortProj(BSONObj(), BSON("x" << 1), BSONObj());
 
     ASSERT_EQUALS(getNumSolutions(), 1U);
@@ -5623,4 +5622,68 @@ TEST_F(QueryPlannerTest, EmptyQueryWithProjectionUsesCollscanIfIndexCollationDif
         "{proj: {spec: {_id: 0, a: 1}, node: "
         "{cscan: {dir: 1}}}}");
 }
+
+// SERVER-41872 fixed a case where variable "choice" ordering in the PlanEnumerator memo could lead
+// to different sets of solutions generated for the same input. This would occur in the case where
+// we only enumerate a subset of possible plans due to reaching internal limits and enumerate plans
+// in a non-stable order. With the fix for SERVER-41872, PlanEnumerator ordering is stable and
+// expected to always return the same set of solutions for a given input.
+TEST_F(QueryPlannerTest, SolutionSetStableWhenOrEnumerationLimitIsReached) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+    addIndex(BSON("d" << 1));
+    addIndex(BSON("e" << 1));
+    addIndex(BSON("f" << 1));
+    addIndex(BSON("f" << 1 << "y" << 1));
+    addIndex(BSON("a" << 1));
+    addIndex(BSON("b" << 1));
+    addIndex(BSON("c" << 1));
+    addIndex(BSON("c" << 1 << "x" << 1));
+
+    runQueryAsCommand(
+        fromjson("{find: 'testns', filter: {$or: [{a: 1, b: 1, c: 1}, {d: 1, e: 1, f: 1}]}}"));
+
+    assertNumSolutions(10U);
+
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {b: {$eq: 1}, c: {$eq: 1} }, node: {ixscan: {pattern: {a: "
+        "1}}}}}, {fetch: {filter: {e: {$eq: 1}, f: {$eq: 1} }, node: {ixscan: {pattern: {d: "
+        "1}}}}}]}}");
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {a: {$eq: 1}, c: {$eq: 1} }, node: {ixscan: {pattern: {b: "
+        "1}}}}}, {fetch: {filter: {e: {$eq: 1}, f: {$eq: 1} }, node: {ixscan: {pattern: {d: "
+        "1}}}}}]}}");
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {a: {$eq: 1}, b: {$eq: 1} }, node: {ixscan: {pattern: {c: "
+        "1}}}}}, {fetch: {filter: {e: {$eq: 1}, f: {$eq: 1} }, node: {ixscan: {pattern: {d: "
+        "1}}}}}]}}");
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {a: {$eq: 1}, b: {$eq: 1} }, node: {ixscan: {pattern: {c: "
+        "1, x: 1}}}}}, {fetch: {filter: {e: {$eq: 1}, f: {$eq: 1} }, node: {ixscan: {pattern: {d: "
+        "1}}}}}]}}");
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {b: {$eq: 1}, c: {$eq: 1} }, node: {ixscan: {pattern: {a: "
+        "1}}}}}, {fetch: {filter: {d: {$eq: 1}, f: {$eq: 1} }, node: {ixscan: {pattern: {e: "
+        "1}}}}}]}}");
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {a: {$eq: 1}, c: {$eq: 1} }, node: {ixscan: {pattern: {b: "
+        "1}}}}}, {fetch: {filter: {d: {$eq: 1}, f: {$eq: 1} }, node: {ixscan: {pattern: {e: "
+        "1}}}}}]}}");
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {a: {$eq: 1}, b: {$eq: 1} }, node: {ixscan: {pattern: {c: "
+        "1}}}}}, {fetch: {filter: {d: {$eq: 1}, f: {$eq: 1} }, node: {ixscan: {pattern: {e: "
+        "1}}}}}]}}");
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {a: {$eq: 1}, b: {$eq: 1} }, node: {ixscan: {pattern: {c: "
+        "1, x: 1}}}}}, {fetch: {filter: {d: {$eq: 1}, f: {$eq: 1} }, node: {ixscan: {pattern: {e: "
+        "1}}}}}]}}");
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {b: {$eq: 1}, c: {$eq: 1} }, node: {ixscan: {pattern: {a: "
+        "1}}}}}, {fetch: {filter: {d: {$eq: 1}, e: {$eq: 1} }, node: {ixscan: {pattern: {f: "
+        "1}}}}}]}}");
+    assertSolutionExists(
+        "{or: {nodes: [{fetch: {filter: {a: {$eq: 1}, c: {$eq: 1} }, node: {ixscan: {pattern: {b: "
+        "1}}}}}, {fetch: {filter: {d: {$eq: 1}, e: {$eq: 1} }, node: {ixscan: {pattern: {f: "
+        "1}}}}}]}}");
+}
+
 }  // namespace