text: /**
   *    Copyright (C) 2013 10gen 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.
   */
  
  #pragma once
  
  #include <vector>
  
  #include "mongo/base/disallow_copying.h"
  #include "mongo/base/status.h"
  #include "mongo/db/query/canonical_query.h"
  #include "mongo/db/query/index_entry.h"
  #include "mongo/db/query/index_tag.h"
  #include "mongo/db/query/query_knobs.h"
  #include "mongo/platform/unordered_map.h"
  
  namespace mongo {
  
  struct PlanEnumeratorParams {
      PlanEnumeratorParams()
          : intersect(false),
            maxSolutionsPerOr(internalQueryEnumerationMaxOrSolutions.load()),
            maxIntersectPerAnd(internalQueryEnumerationMaxIntersectPerAnd.load()) {}
  
      // Do we provide solutions that use more indices than the minimum required to provide
      // an indexed solution?
      bool intersect;
  
      // Not owned here.
      MatchExpression* root;
  
      // Not owned here.
      const std::vector<IndexEntry>* indices;
  
      // How many plans are we willing to ouput from an OR? We currently consider
      // all possibly OR plans, which means the product of the number of possibilities
      // for each clause of the OR. This could grow disastrously large.
      size_t maxSolutionsPerOr;
  
      // How many intersect plans are we willing to output from an AND?  Given that we pursue an
      // all-pairs approach, we could wind up creating a lot of enumeration possibilities for
      // certain inputs.
      size_t maxIntersectPerAnd;
  };
  
  /**
   * Provides elements from the power set of possible indices to use.  Uses the available
   * predicate information to make better decisions about what indices are best.
   */
  class PlanEnumerator {
      MONGO_DISALLOW_COPYING(PlanEnumerator);
  
  public:
      /**
       * Constructs an enumerator for the query specified in 'root' which is tagged with
       * RelevantTag(s).  The index patterns mentioned in the tags are described by 'indices'.
       *
       * Does not take ownership of any arguments.  They must outlive any calls to getNext(...).
       */
      PlanEnumerator(const PlanEnumeratorParams& params);
  
      ~PlanEnumerator();
  
      /**
       * Returns OK and performs a sanity check on the input parameters and prepares the
       * internal state so that getNext() can be called. Returns an error status with a
       * description if the sanity check failed.
       */
      Status init();
  
      /**
       * Outputs a possible plan. Leaves in the plan are tagged with an index to use.
       * Returns a MatchExpression representing a point in the query tree (which can be
       * used to build a QueryAssignment) or nullptr if no more plans will be outputted.
       * While owned by the caller, the MatchExpression returned points into data that is
       * owned elsewhere.
       *
       * Nodes in 'tree' are tagged with indices that should be used to answer the tagged nodes.
       * Only nodes that have a field name (getCategory() != kLogical) will be tagged.
       *
       * The output tree is a clone identical to that used to initialize the enumerator, with tags
       * added in order to indicate index usage.
       */
      std::unique_ptr<MatchExpression> getNext();
  
  private:
      //
      // Memoization strategy
      //
  
  
      // Everything is really a size_t but it's far more readable to impose a type via typedef.
  
      // An ID we use to index into _memo.  An entry in _memo is a NodeAssignment.
      typedef size_t MemoID;
  
      // An index in _indices.
      typedef size_t IndexID;
  
      // The position of a field in a possibly compound index.
      typedef size_t IndexPosition;
  
      /**
       * Represents the route that an outside predicate has taken during the PlanEnumerator's
       * recursive descent of the match expression tree.
       */
      struct OutsidePredRoute {
          /**
           * Whether or not the route has traversed through an $elemMatch object node. This is needed
           * because it is not correct to push down a predicate through an $elemMatch object.
           */
          bool traversedThroughElemMatchObj = false;
  
          /**
           * The route of the outside predicate. This starts at the indexed OR sibling of the
           * predicate.  Each value in 'route' is the index of a child in an indexed OR.
           *
           * For example, if the MatchExpression tree is:
           *         AND
           *        /    \
           *   {a: 5}    OR
           *           /    \
           *         AND    {e: 9}
           *       /     \
           *    {b: 6}   OR
           *           /    \
           *       {c: 7}  {d: 8}
           *
           * and the predicate is {a: 5}, then the route will be {0, 1} when the recursive descent
           * reaches {d: 8}.
           */
          std::deque<size_t> route;
      };
  
      struct PrepMemoContext {
          PrepMemoContext() : elemMatchExpr(NULL) {}
          MatchExpression* elemMatchExpr;
  
          // Maps from indexable predicates that can be pushed into the current node to the route
          // through ORs that they have taken to get to this node.
          unordered_map<MatchExpression*, OutsidePredRoute> outsidePreds;
      };
  
      /**
       * Traverses the match expression and generates the memo structure from it.
       * Returns true if the provided node uses an index, false otherwise.
       */
      bool prepMemo(MatchExpression* node, PrepMemoContext context);
  
      /**
       * Traverses the memo structure and annotates the tree with IndexTags for the chosen
       * indices.
       */
      void tagMemo(MemoID id);
  
      /**
       * Move to the next enumeration state.  Each assignment stores its own enumeration state.
       * See the various ____Assignment classes below for details on enumeration state.
       *
       * Returns true if the memo subtree with root 'node' has no further enumeration states.  In
       * this case, that subtree restarts its enumeration at the beginning state.  This implies
       * that the parent of node should move to the next state.  If 'node' is the root of the
       * tree, we are done with enumeration.
       *
       * The return of this function can be thought of like a 'carry' in addition.
       *
       * Returns false if the memo subtree has moved to the next state.
       */
      bool nextMemo(MemoID id);
  
      /**
       * A short word on the memo structure.
       *
       * The PlanEnumerator is interested in matching predicates and indices.  Predicates
       * are leaf nodes in the parse tree.  {x:5}, {x: {$geoWithin:...}} are both predicates.
       *
       * Since the output of an OR is the union of its results, each of its children must be
       * indexed for the entire OR to be indexed.  If each subtree of an OR is indexable, the
       * OR is as well.
       *
       * For an AND to be indexed, only one of its children must be indexed.  AND is an
       * intersection of its children, so each of its children describes a superset of the
       * produced results.
       *
       * Leaf predicates are also given AND assignments, since they may index outside predicates that
       * have been pushed down through OR nodes.
       */
  
      struct OrAssignment {
          OrAssignment() : counter(0) {}
  
          // Each child of an OR must be indexed for the OR to be indexed. When an OR moves to a
          // subsequent state it just asks all its children to move their states forward.
  
          // Must use all of subnodes.
          std::vector<MemoID> subnodes;
  
          // The number of OR states that we've enumerated so far.
          size_t counter;
      };
  
      // This is used by AndAssignment and is not an actual assignment.
      struct OneIndexAssignment {
          // 'preds[i]' is uses index 'index' at position 'positions[i]'
          std::vector<MatchExpression*> preds;
          std::vector<IndexPosition> positions;
          IndexID index;
  
          // True if the bounds on 'index' for the leaf expressions in 'preds' can be intersected
          // and/or compounded, and false otherwise. If 'canCombineBounds' is set to false and
          // multiple predicates are assigned to the same position of a multikey index, then the
          // access planner should generate a self-intersection plan.
          bool canCombineBounds = true;
  
          // The expressions that should receive an OrPushdownTag when this assignment is made.
          std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> orPushdowns;
      };
  
      struct AndEnumerableState {
          std::vector<OneIndexAssignment> assignments;
          std::vector<MemoID> subnodesToIndex;
      };
  
      struct AndAssignment {
          AndAssignment() : counter(0) {}
  
          std::vector<AndEnumerableState> choices;
  
          // We're on the counter-th member of state.
          size_t counter;
      };
  
      struct ArrayAssignment {
          ArrayAssignment() : counter(0) {}
          std::vector<MemoID> subnodes;
          size_t counter;
      };
  
      /**
       * Associates indices with predicates.
       */
      struct NodeAssignment {
          std::unique_ptr<OrAssignment> orAssignment;
          std::unique_ptr<AndAssignment> andAssignment;
          std::unique_ptr<ArrayAssignment> arrayAssignment;
          std::string toString() const;
      };
  
      /**
       * Allocates a NodeAssignment and associates it with the provided 'expr'.
       *
       * The unique MemoID of the new assignment is outputted in '*id'.
       * The out parameter '*slot' points to the newly allocated NodeAssignment.
       */
      void allocateAssignment(MatchExpression* expr, NodeAssignment** slot, MemoID* id);
  
      /**
       * Predicates inside $elemMatch's that are semantically "$and of $and"
       * predicates are not rewritten to the top-level during normalization.
       * However, we would like to make predicates inside $elemMatch available
       * for combining index bounds with the top-level $and predicates.
       *
       * This function deeply traverses $and and $elemMatch expressions of
       * the tree rooted at 'node', adding all preds that can use an index
       * to the output vector 'indexOut'. At the same time, $elemMatch
       * context information is stashed in the tags so that we don't lose
       * information due to flattening.
       *
       * Does not take ownership of arguments.
       *
       * Returns false if the AND cannot be indexed. Otherwise returns true.
       */
      void getIndexedPreds(MatchExpression* node,
                           PrepMemoContext context,
                           std::vector<MatchExpression*>* indexOut);
  
      /**
       * Recursively traverse 'node', with OR nodes as the base case. The OR nodes are not
       * explored--instead we call prepMemo() on the OR subnode, and add its assignment to the output.
       * Subnodes are "mandatory" if they *must* use an index (TEXT and GEO).
       * Returns a boolean indicating whether all mandatory subnodes can be indexed.
       */
      bool prepSubNodes(MatchExpression* node,
                        PrepMemoContext context,
                        std::vector<MemoID>* subnodesOut,
                        std::vector<MemoID>* mandatorySubnodes);
  
      /**
       * Finds a set of predicates that can be safely compounded with the set
       * of predicates in 'assigned', under the assumption that we are assigning
       * predicates to a compound, multikey index.
       *
       * The list of candidate predicates that we could compound is passed
       * in 'couldCompound'. A subset of these predicates that is safe to
       * combine by compounding is returned in the out-parameter 'out'.
       *
       * Does not take ownership of its arguments.
       *
       * The rules for when to compound for multikey indices are reasonably
       * complex, and are dependent on the structure of $elemMatch's used
       * in the query. Ignoring $elemMatch for the time being, the rule is this:
       *
       *   "Any set of predicates for which no two predicates share a path
       *    prefix can be compounded."
       *
       * Suppose we have predicates over paths 'a.b' and 'a.c'. These cannot
       * be compounded because they share the prefix 'a'. Similarly, the bounds
       * for 'a' and 'a.b' cannot be compounded (in the case of multikey index
       * {a: 1, 'a.b': 1}). You *can* compound predicates over the paths 'a.b.c',
       * 'd', and 'e.b.c', because there is no shared prefix.
       *
       * The rules are different in the presence of $elemMatch. For $elemMatch
       * {a: {$elemMatch: {<pred1>, ..., <predN>}}}, we are allowed to compound
       * bounds for pred1 through predN, even though these predicates share the
       * path prefix 'a'. However, we still cannot compound in the case of
       * {a: {$elemMatch: {'b.c': {$gt: 1}, 'b.d': 5}}} because 'b.c' and 'b.d'
       * share a prefix. In other words, what matters inside an $elemMatch is not
       * the absolute prefix, but rather the "relative prefix" after the shared
       * $elemMatch part of the path.
       *
       * A few more examples:
       *    1) {'a.b': {$elemMatch: {c: {$gt: 1}, d: 5}}}. In this case, we can
       *    compound, because the $elemMatch is applied to the shared part of
       *    the path 'a.b'.
       *
       *    2) {'a.b': 1, a: {$elemMatch: {b: {$gt: 0}}}}. We cannot combine the
       *    bounds here because the prefix 'a' is shared by two predicates which
       *    are not joined together by an $elemMatch.
       *
       * NOTE:
       *   Usually 'assigned' has just one predicate. However, in order to support
       *   mandatory predicate assignment (TEXT and GEO_NEAR), we allow multiple
       *   already-assigned predicates to be passed. If a mandatory predicate is over
       *   a trailing field in a multikey compound index, then we assign both a predicate
       *   over the leading field as well as the mandatory predicate prior to calling
       *   this function.
       *
       *   Ex:
       *      Say we have index {a: 1, b: 1, c: "2dsphere", d: 1} as well as a $near
       *      predicate and a $within predicate over "c". The $near predicate is mandatory
       *      and must be assigned. The $within predicate is not mandatory. Furthermore,
       *      it cannot be assigned in addition to the $near predicate because the index
       *      is multikey.
       *
       *      In this case the enumerator must assign the $near predicate, and pass it in
       *      in 'assigned'. Otherwise it would be possible to assign the $within predicate,
       *      and then not assign the $near because the $within is already assigned (and
       *      has the same path).
       */
      void getMultikeyCompoundablePreds(const std::vector<MatchExpression*>& assigned,
                                        const std::vector<MatchExpression*>& couldCompound,
                                        std::vector<MatchExpression*>* out);
  
      /**
       * Assigns predicates from 'couldAssign' to 'indexAssignment' that can safely be assigned
       * according to the intersecting and compounding rules for multikey indexes. The rules can
       * loosely be stated as follows:
       *
       *   - It is always safe to assign a predicate on path Y to the index when no prefix of the path
       *     Y causes the index to be multikey.
       *
       *   - For any non-$elemMatch predicate on path X already assigned to the index, it isn't safe
       *     to assign a predicate on path Y (possibly equal to X) to the index when a shared prefix
       *     of the paths X and Y causes the index to be multikey.
       *
       *   - For any $elemMatch predicate on path X already assigned to the index, it isn't safe to
       *     assign a predicate on path Y (possibly equal to X) to the index when
       *       (a) a shared prefix of the paths X and Y causes the index to be multikey and the
       *           predicates aren't joined by the same $elemMatch context, or
       *       (b) a shared prefix of the paths X and Y inside the innermost $elemMatch causes the
       *           index to be multikey.
       *
       * If a predicate in 'couldAssign' is also in 'outsidePreds', then it is assumed to be an
       * outside predicate that was pushed down through an OR. Instead of adding it to
       * indexAssignment->preds, we add it to indexAssignment->orPushdowns. We create its
       * OrPushdownTag using the route specified in 'outsidePreds'.
       *
       * This function should only be called if the index has path-level multikey information.
       * Otherwise, getMultikeyCompoundablePreds() and compound() should be used instead.
       */
      void assignMultikeySafePredicates(
          const std::vector<MatchExpression*>& couldAssign,
          const unordered_map<MatchExpression*, OutsidePredRoute>& outsidePreds,
          OneIndexAssignment* indexAssignment);
  
      /**
       * 'andAssignment' contains assignments that we've already committed to outputting,
       * including both single index assignments and ixisect assignments.
       *
       * 'ixisectAssigned' is a set of predicates that we are about to add to 'andAssignment'
       * as an index intersection assignment.
       *
       * Returns true if an single index assignment which is already in 'andAssignment'
       * contains a superset of the predicates in 'ixisectAssigned'. This means that we
       * can assign the same preds to a compound index rather than using index intersection.
       *
       * Ex.
       *   Suppose we have indices {a: 1}, {b: 1}, and {a: 1, b: 1} with query
       *   {a: 2, b: 2}. When we try to intersect {a: 1} and {b: 1} the predicates
       *   a==2 and b==2 will get assigned to respective indices. But then we will
       *   call this function with ixisectAssigned equal to the set {'a==2', 'b==2'},
       *   and notice that we have already assigned this same set of predicates to
       *   the single index {a: 1, b: 1} via compounding.
       */
      bool alreadyCompounded(const std::set<MatchExpression*>& ixisectAssigned,
                             const AndAssignment* andAssignment);
      /**
       * Output index intersection assignments inside of an AND node.
       */
      typedef unordered_map<IndexID, std::vector<MatchExpression*>> IndexToPredMap;
  
      /**
       * Generate index intersection assignments given the predicate/index structure in idxToFirst
       * and idxToNotFirst (and the sub-trees in 'subnodes').  Outputs the assignments in
       * 'andAssignment'.
       */
      void enumerateAndIntersect(const IndexToPredMap& idxToFirst,
                                 const IndexToPredMap& idxToNotFirst,
                                 const std::vector<MemoID>& subnodes,
                                 AndAssignment* andAssignment);
  
      /**
       * Generate one-index-at-once assignments given the predicate/index structure in idxToFirst
       * and idxToNotFirst (and the sub-trees in 'subnodes').  Outputs the assignments into
       * 'andAssignment'. The predicates in 'outsidePreds' are considered for OrPushdownTags.
       */
      void enumerateOneIndex(IndexToPredMap idxToFirst,
                             IndexToPredMap idxToNotFirst,
                             const std::vector<MemoID>& subnodes,
                             const unordered_map<MatchExpression*, OutsidePredRoute>& outsidePreds,
                             AndAssignment* andAssignment);
  
      /**
       * Generate single-index assignments for queries which contain mandatory
       * predicates (TEXT and GEO_NEAR, which are required to use a compatible index).
       * Outputs these assignments into 'andAssignment'.
       *
       * Returns true if it generated at least one assignment, and false if no assignment
       * of 'mandatoryPred' is possible.
       */
      bool enumerateMandatoryIndex(const IndexToPredMap& idxToFirst,
                                   const IndexToPredMap& idxToNotFirst,
                                   MatchExpression* mandatoryPred,
                                   const std::set<IndexID>& mandatoryIndices,
                                   AndAssignment* andAssignment);
  
      /**
       * Assigns predicates in 'predsOverLeadingField' and 'idxToNotFirst' to 'indexAssign'. Assumes
       * that the index is not multikey. Also assumes that that the index is of a type used to answer
       * "mandatory predicates" such as text or geoNear.
       */
      void assignToNonMultikeyMandatoryIndex(
          const IndexEntry& index,
          const std::vector<MatchExpression*>& predsOverLeadingField,
          const IndexToPredMap& idxToNotFirst,
          OneIndexAssignment* indexAssign);
  
      /**
       * Try to assign predicates in 'tryCompound' to 'thisIndex' as compound assignments.
       * Output the assignments in 'assign'.
       */
      void compound(const std::vector<MatchExpression*>& tryCompound,
                    const IndexEntry& thisIndex,
                    OneIndexAssignment* assign);
  
      /**
       * Returns the position that 'predicate' can use in the key pattern for 'indexEntry'. It is
       * illegal to call this if 'predicate' does not have a RelevantTag, or it cannot use the index.
       */
      size_t getPosition(const IndexEntry& indexEntry, MatchExpression* predicate);
  
      /**
       * Adds 'pred' to 'indexAssignment', using 'position' as its position in the index. If 'pred' is
       * in 'outsidePreds', then it is assumed to be an outside predicate that was pushed down through
       * an OR. Instead of adding it to indexAssignment->preds, we add it to
       * indexAssignment->orPushdowns. We create its OrPushdownTag using the route specified in
       * 'outsidePreds'. 'pred' must be able to use the index and be multikey-safe to add to
       * 'indexAssignment'.
       */
      void assignPredicate(const unordered_map<MatchExpression*, OutsidePredRoute>& outsidePreds,
                           MatchExpression* pred,
                           size_t position,
                           OneIndexAssignment* indexAssignment);
  
      /**
       * Sets a flag on all outside pred routes that descend through an $elemMatch object node.
       */
      void markTraversedThroughElemMatchObj(PrepMemoContext* context);
  
      /**
       * Return the memo entry for 'node'.  Does some sanity checking to ensure that a memo entry
       * actually exists.
       */
      MemoID memoIDForNode(MatchExpression* node);
  
      std::string dumpMemo();
  
      // Map from expression to its MemoID.
      unordered_map<MatchExpression*, MemoID> _nodeToId;
  
      // Map from MemoID to its precomputed solution info.
      unordered_map<MemoID, NodeAssignment*> _memo;
  
      // If true, there are no further enumeration states, and getNext should return false.
      // We could be _done immediately after init if we're unable to output an indexed plan.
      bool _done;
  
      //
      // Data used by all enumeration strategies
      //
  
      // Match expression we're planning for.  Not owned by us.
      MatchExpression* _root;
  
      // Indices we're allowed to enumerate with.  Not owned here.
      const std::vector<IndexEntry>* _indices;
  
      // Do we output >1 index per AND (index intersection)?
      bool _ixisect;
  
      // How many enumerations are we willing to produce from each OR?
      size_t _orLimit;
  
      // How many things do we want from each AND?
      size_t _intersectLimit;
  };
  
  }  // namespace mongo
  