SERVER-13104 enumerate all possibilties for $or below an $and

(cherry picked from commit aac8ba84d8fac7dc531a03c63224fdfc8cd3baa3)

2 files changed, 66 insertions, 0 deletions

diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index c958dc3d3a2..8ffc11c0ce0 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -1226,6 +1226,17 @@ namespace mongo {
         }
         else if (NULL != assign->andAssignment) {
             AndAssignment* aa = assign->andAssignment.get();
+
+            // One of our subnodes might have to move on to its next enumeration state.
+            const AndEnumerableState& aes = aa->choices[aa->counter];
+            for (size_t i = 0; i < aes.subnodesToIndex.size(); ++i) {
+                if (!nextMemo(aes.subnodesToIndex[i])) {
+                    return false;
+                }
+            }
+
+            // None of the subnodes had another enumeration state, so we move on to the
+            // next top-level choice.
             ++aa->counter;
             if (aa->counter < aa->choices.size()) {
                 return false;
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index ac800a101f1..870cf68de58 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -4410,6 +4410,61 @@ namespace {
         assertNumSolutions(internalQueryEnumerationMaxOrSolutions);
     }
 
+    // SERVER-13104: test that we properly enumerate all solutions for nested $or.
+    TEST_F(QueryPlannerTest, EnumerateNestedOr) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+        addIndex(BSON("a" << 1));
+        addIndex(BSON("b" << 1));
+        addIndex(BSON("c" << 1));
+
+        runQuery(fromjson("{d: 1, $or: [{a: 1, b: 1}, {c: 1}]}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{fetch: {filter: {d: 1}, node: {or: {nodes: ["
+                                "{fetch: {filter: {b: 1}, node: {ixscan: {pattern: {a: 1}}}}},"
+                                "{ixscan: {pattern: {c: 1}}}]}}}}");
+        assertSolutionExists("{fetch: {filter: {d: 1}, node: {or: {nodes: ["
+                                "{fetch: {filter: {a: 1}, node: {ixscan: {pattern: {b: 1}}}}},"
+                                "{ixscan: {pattern: {c: 1}}}]}}}}");
+    }
+
+    // SERVER-13104: test that we properly enumerate all solutions for nested $or.
+    TEST_F(QueryPlannerTest, EnumerateNestedOr2) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+        addIndex(BSON("a" << 1));
+        addIndex(BSON("b" << 1));
+        addIndex(BSON("c" << 1));
+        addIndex(BSON("d" << 1));
+        addIndex(BSON("e" << 1));
+        addIndex(BSON("f" << 1));
+
+        runQuery(fromjson("{a: 1, b: 1, $or: [{c: 1, d: 1}, {e: 1, f: 1}]}"));
+
+        assertNumSolutions(6U);
+
+        // Four possibilities from indexing the $or.
+        assertSolutionExists("{fetch: {filter: {a: 1, b: 1}, node: {or: {nodes: ["
+                                "{fetch: {filter: {d: 1}, node: {ixscan: {pattern: {c: 1}}}}},"
+                                "{fetch: {filter: {f: 1}, node: {ixscan: {pattern: {e: 1}}}}}"
+                             "]}}}}");
+        assertSolutionExists("{fetch: {filter: {a: 1, b: 1}, node: {or: {nodes: ["
+                                "{fetch: {filter: {c: 1}, node: {ixscan: {pattern: {d: 1}}}}},"
+                                "{fetch: {filter: {f: 1}, node: {ixscan: {pattern: {e: 1}}}}}"
+                             "]}}}}");
+        assertSolutionExists("{fetch: {filter: {a: 1, b: 1}, node: {or: {nodes: ["
+                                "{fetch: {filter: {d: 1}, node: {ixscan: {pattern: {c: 1}}}}},"
+                                "{fetch: {filter: {e: 1}, node: {ixscan: {pattern: {f: 1}}}}}"
+                             "]}}}}");
+        assertSolutionExists("{fetch: {filter: {a: 1, b: 1}, node: {or: {nodes: ["
+                                "{fetch: {filter: {c: 1}, node: {ixscan: {pattern: {d: 1}}}}},"
+                                "{fetch: {filter: {e: 1}, node: {ixscan: {pattern: {f: 1}}}}}"
+                             "]}}}}");
+
+        // Two possibilties from outside the $or.
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: 1}}}}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {b: 1}}}}}");
+    }
+
     //
     // Test the "split limited sort stages" hack.
     //