SERVER-13732 rewrite contained $or queries to rooted $or in the SubplanStage

This allows queries with an $or contained within an explicit or implicit $and to be answered with
more efficient plans. It also expands the use of the SubplanStage to include contained $or queries
and therefore may reduce the number of plans considered for these queries.

1 files changed, 22 insertions, 0 deletions

diff --git a/src/mongo/db/query/planner_access.h b/src/mongo/db/query/planner_access.h
index 8ab6bf9d58a..a5844f4fa58 100644
--- a/src/mongo/db/query/planner_access.h
+++ b/src/mongo/db/query/planner_access.h
@@ -265,6 +265,28 @@ public:
                                       std::vector<MatchExpression*>* subnodesOut);
 
     /**
+     * Given a list of OR-related subtrees returned by processIndexScans(), looks for logically
+     * equivalent IndexScanNodes and combines them. This is an optimization to avoid creating
+     * plans that repeat index access work.
+     *
+     * Example:
+     *  Suppose processIndexScans() returns a list of the following three query solutions:
+     *    1) IXSCAN (bounds: {b: [[2,2]]})
+     *    2) FETCH (filter: {d:1}) -> IXSCAN (bounds: {c: [[3,3]]})
+     *    3) FETCH (filter: {e:1}) -> IXSCAN (bounds: {c: [[3,3]]})
+     *  This method would collapse scans #2 and #3, resulting in the following output:
+     *    1) IXSCAN (bounds: {b: [[2,2]]})
+     *    2) FETCH (filter: {$or:[{d:1}, {e:1}]}) -> IXSCAN (bounds: {c: [[3,3]]})
+     *
+     * Used as a helper for buildIndexedOr().
+     *
+     * Takes ownership of 'scans'. The caller assumes ownership of the pointers in the returned
+     * list of QuerySolutionNode*.
+     */
+    static std::vector<QuerySolutionNode*> collapseEquivalentScans(
+        const std::vector<QuerySolutionNode*> scans);
+
+    /**
      * Helper used by buildIndexedAnd and buildIndexedOr.
      *
      * The children of AND and OR nodes are sorted by the index that the subtree rooted at