mongodb-dev 1:2.4.9-1ubuntu2 / usr / include / mongo / db / queryoptimizer.h

// @file queryoptimizer.h

/**
*    Copyright (C) 2008 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/>.
*/

#pragma once

#include "mongo/base/disallow_copying.h"
#include "mongo/db/clientcursor.h"
#include "mongo/db/cursor.h"
#include "mongo/db/explain.h"
#include "mongo/db/matcher.h"
#include "mongo/db/queryoptimizercursor.h"
#include "mongo/db/querypattern.h"
#include "mongo/db/queryutil.h"
#include "mongo/util/elapsed_tracker.h"

namespace mongo {

    static const int OutOfOrderDocumentsAssertionCode = 14810;

    class IndexDetails;
    class IndexType;
    class QueryPlanSummary;
    
    /**
     * A plan for executing a query using the given index spec and FieldRangeSet.  An object of this
     * class may only be used by one thread at a time.
     */
    class QueryPlan : boost::noncopyable {
    public:

        /**
         * @param originalFrsp - original constraints for this query clause.  If null, frsp will be used instead.
         */
        static QueryPlan *make( NamespaceDetails *d,
                               int idxNo, // -1 = no index
                               const FieldRangeSetPair &frsp,
                               const FieldRangeSetPair *originalFrsp,
                               const BSONObj &originalQuery,
                               const BSONObj &order,
                               const shared_ptr<const ParsedQuery> &parsedQuery =
                                       shared_ptr<const ParsedQuery>(),
                               const BSONObj &startKey = BSONObj(),
                               const BSONObj &endKey = BSONObj(),
                               const std::string& special="" );

        /** Categorical classification of a QueryPlan's utility. */
        enum Utility {
            Impossible, // Cannot produce any matches, so the query must have an empty result set.
                        // No other plans need to be considered.
            Optimal,    // Should run as the only candidate plan in the absence of an Impossible
                        // plan.
            Helpful,    // Should be considered.
            Unhelpful,  // Should not be considered.
            Disallowed  // Must not be considered unless explicitly hinted.  May produce a
                        // semantically incorrect result set.
        };

        Utility utility() const { return _utility; }
        
        /** @return true if ScanAndOrder processing will be required for result set. */
        bool scanAndOrderRequired() const { return _scanAndOrderRequired; }
        /**
         * @return false if document matching can be determined entirely using index keys and the
         * FieldRangeSetPair generated for the query, without using a Matcher.  This function may
         * return false positives but not false negatives.  For example, if the field range set's
         * mustBeExactMatchRepresentation() returns a false negative, this function will return a
         * false positive.
         */
        bool mayBeMatcherNecessary() const { return _matcherNecessary; }
        /** @return true if this QueryPlan would perform an unindexed scan. */
        bool willScanTable() const { return _idxNo < 0 && ( _utility != Impossible ); }
        /** @return 'special' attribute of the plan, which was either set explicitly or generated from the index. */
        const string &special() const { return _special; }
                
        /** @return a new cursor based on this QueryPlan's index and FieldRangeSet. */
        shared_ptr<Cursor> newCursor( const DiskLoc& startLoc = DiskLoc(),
                                      bool requestIntervalCursor = false ) const;
        /** @return a new reverse cursor if this is an unindexed plan. */
        shared_ptr<Cursor> newReverseCursor() const;
        /** Register this plan as a winner for its QueryPattern, with specified 'nscanned'. */
        void registerSelf( long long nScanned, CandidatePlanCharacter candidatePlans ) const;

        int direction() const { return _direction; }
        BSONObj indexKey() const;
        bool indexed() const { return _index != 0; }
        const IndexDetails *index() const { return _index; }
        int idxNo() const { return _idxNo; }
        const char *ns() const { return _frs.ns(); }
        NamespaceDetails *nsd() const { return _d; }
        BSONObj originalQuery() const { return _originalQuery; }
        shared_ptr<FieldRangeVector> originalFrv() const { return _originalFrv; }

        const FieldRangeSet &multikeyFrs() const { return _frsMulti; }
        
        shared_ptr<Projection::KeyOnly> keyFieldsOnly() const { return _keyFieldsOnly; }
        const ParsedQuery* parsedQuery() const { return _parsedQuery.get(); }

        /** @return a shared, lazily initialized matcher for the query plan. */
        shared_ptr<CoveredIndexMatcher> matcher() const;
        
        QueryPlanSummary summary() const;

        /** The following member functions are for testing, or public for testing. */
        
        shared_ptr<FieldRangeVector> frv() const { return _frv; }
        bool isMultiKey() const;
        string toString() const;
        bool queryBoundsExactOrderSuffix() const;

    private:
        
        QueryPlan(NamespaceDetails *d,
                  int idxNo,
                  const FieldRangeSetPair &frsp,
                  const BSONObj &originalQuery,
                  const BSONObj &order,
                  const shared_ptr<const ParsedQuery> &parsedQuery,
                  const std::string& special );
        void init( const FieldRangeSetPair *originalFrsp,
                  const BSONObj &startKey,
                  const BSONObj &endKey );

        void checkTableScanAllowed() const;
        int independentRangesSingleIntervalLimit() const;
        /** @return true when the plan's query may contains an $exists:false predicate. */
        bool hasPossibleExistsFalsePredicate() const;

        NamespaceDetails * _d;
        int _idxNo;
        const FieldRangeSet &_frs;
        const FieldRangeSet &_frsMulti;
        const BSONObj _originalQuery;
        const BSONObj _order;
        shared_ptr<const ParsedQuery> _parsedQuery;
        const IndexDetails * _index;
        bool _scanAndOrderRequired;
        bool _matcherNecessary;
        int _direction;
        shared_ptr<FieldRangeVector> _frv;
        shared_ptr<FieldRangeVector> _originalFrv;
        BSONObj _startKey;
        BSONObj _endKey;
        bool _endKeyInclusive;
        Utility _utility;
        string _special;
        IndexType * _type;
        bool _startOrEndSpec;
        shared_ptr<Projection::KeyOnly> _keyFieldsOnly;
        mutable shared_ptr<CoveredIndexMatcher> _matcher; // Lazy initialization.
    };

    std::ostream &operator<< ( std::ostream &out, const QueryPlan::Utility &utility );

    /**
     * A QueryPlanSummary owns its own attributes and may be shared.  Currently a QueryPlan
     * should only be owned by a QueryPlanSet.
     */
    class QueryPlanSummary {
    public:
        QueryPlanSummary() :
        _scanAndOrderRequired() {
        }
        QueryPlanSummary( const QueryPlan &queryPlan ) :
        _fieldRangeSetMulti( new FieldRangeSet( queryPlan.multikeyFrs() ) ),
        _keyFieldsOnly( queryPlan.keyFieldsOnly() ),
        _scanAndOrderRequired( queryPlan.scanAndOrderRequired() ) {
        }
        bool valid() const { return _fieldRangeSetMulti; }
        shared_ptr<FieldRangeSet> _fieldRangeSetMulti;
        shared_ptr<Projection::KeyOnly> _keyFieldsOnly;
        bool _scanAndOrderRequired;
    };

    /**
     * Helper class for a QueryPlanRunner to cache and count matches.  One object of this type is
     * used per candidate QueryPlan (as there is one QueryPlanRunner per QueryPlan).
     *
     * Typical usage:
     * 1) resetMatch() - reset stored match value to Unkonwn.
     * 2) setMatch() - set match value to a definite true/false value.
     * 3) knowMatch() - check if setMatch() has been called.
     * 4) incMatch() - increment count if match is true.
     */
    class CachedMatchCounter {
    public:
        /**
         * @param aggregateNscanned - shared count of nscanned for this and other plans.
         * @param cumulativeCount - starting point for accumulated count over a series of plans.
         */
        CachedMatchCounter( long long& aggregateNscanned, int cumulativeCount );
        
        /** Set whether dup checking is enabled when counting. */
        void setCheckDups( bool checkDups ) { _checkDups = checkDups; }
        
        void resetMatch();

        /** @return true if the match was not previously recorded. */
        bool setMatch( bool match );
        
        bool knowMatch() const { return _match != Unknown; }

        void incMatch( const DiskLoc& loc );

        bool wouldIncMatch( const DiskLoc& loc ) const;
        
        bool enoughCumulativeMatchesToChooseAPlan() const;
        
        bool enoughMatchesToRecordPlan() const;
        
        int cumulativeCount() const { return _cumulativeCount; }
        int count() const { return _count; }
        
        /** Update local and aggregate nscanned counts. */
        void updateNscanned( long long nscanned );

        long long nscanned() const { return _nscanned; }
        long long& aggregateNscanned() const { return _aggregateNscanned; }

    private:
        bool getsetdup( const DiskLoc& loc );
        bool getdup( const DiskLoc& loc ) const;

        long long& _aggregateNscanned;
        long long _nscanned;
        int _cumulativeCount;
        int _count;
        bool _checkDups;
        enum MatchState { Unknown, False, True };
        MatchState _match;
        bool _counted;
        set<DiskLoc> _dups;
    };

    /**
     * Iterates through a QueryPlan's candidate matches, keeping track of accumulated nscanned.
     * Generally used along with runners for other QueryPlans in a QueryPlanRunnerQueue priority
     * queue.  Eg if there are three candidate QueryPlans evaluated in parallel, there are three
     * QueryPlanRunners, one checking for matches on each query.
     *
     * Typical usage:
     * 1) A new QueryPlanRunner is generated using createChild().
     * 2) A QueryPlan is assigned using setQueryPlan().
     * 3) init() is called to initialize the runner.
     * 4) next() is called repeatedly, with nscanned() checked after each call.
     * 5) In one of these calls to next(), setComplete() is called internally.
     * 6) The QueryPattern for the QueryPlan may be recorded as a winning plan.
     */
    class QueryPlanRunner {
        MONGO_DISALLOW_COPYING( QueryPlanRunner );
    public:
        /**
         * @param aggregateNscanned Shared long long counting total nscanned for runners for all
         *     cursors.
         * @param selectionPolicy Characterizes the set of QueryPlans allowed for this operation.
         *     See queryoptimizercursor.h for more information.
         * @param requireOrder Whether only ordered plans are allowed.
         * @param alwaysCountMatches Whether matches are to be counted regardless of ordering.
         * @param cumulativeCount Total count.
         */
        QueryPlanRunner( long long& aggregateNscanned,
                         const QueryPlanSelectionPolicy& selectionPolicy,
                         const bool& requireOrder,
                         bool alwaysCountMatches,
                         int cumulativeCount = 0 );

        /** @return QueryPlan assigned to this runner by the query optimizer. */
        const QueryPlan& queryPlan() const { return *_queryPlan; }
                
        /** Advance to the next potential matching document (eg using a cursor). */
        void next();

        /**
         * @return current 'nscanned' metric for this runner.  Used to compare cost to other
         * runners.
         */
        long long nscanned() const;

        /** Take any steps necessary before the db mutex is yielded. */
        void prepareToYield();

        /** Recover once the db mutex is regained. */
        void recoverFromYield();

        /** Take any steps necessary before an earlier iterate of the cursor is modified. */
        void prepareToTouchEarlierIterate();

        /** Recover after the earlier iterate is modified. */
        void recoverFromTouchingEarlierIterate();

        DiskLoc currLoc() const { return _c ? _c->currLoc() : DiskLoc(); }
        BSONObj currKey() const { return _c ? _c->currKey() : BSONObj(); }
        bool currentMatches( MatchDetails* details );
        
        /**
         * @return true iff the QueryPlan for this runner may be registered
         * as a winning plan.
         */
        bool mayRecordPlan() const;

        shared_ptr<Cursor> cursor() const { return _c; }

        /** @return true iff the implementation called setComplete() or setStop(). */
        bool complete() const { return _complete; }
        /** @return true iff the implementation called setStop(). */
        bool stopRequested() const { return _stopRequested; }
        bool completeWithoutStop() const { return complete() && !stopRequested(); }
        /** @return true iff the implementation errored out. */
        bool error() const { return _error; }
        /** @return the error information. */
        ExceptionInfo exception() const { return _exception; }
        
        /** To be called by QueryPlanSet::Runner only. */
        
        /**
         * @return a copy of the inheriting class, which will be run with its own query plan.  The
         * child runner will assume its parent runner has completed execution.
         */
        QueryPlanRunner* createChild() const;

        void setQueryPlan( const QueryPlan* queryPlan );

        /** Handle initialization after a QueryPlan has been set. */
        void init();

        void setException( const DBException& e );

        /** @return an ExplainPlanInfo object that will be updated as the query runs. */
        shared_ptr<ExplainPlanInfo> generateExplainInfo();
        shared_ptr<ExplainPlanInfo> explainInfo() const { return _explainPlanInfo; }

        const Projection::KeyOnly* keyFieldsOnly() const {
            return queryPlan().keyFieldsOnly().get();
        }
        
    private:
        /** Call if all results have been found. */
        void setComplete() { _complete = true; }
        /** Call if the scan is complete even if not all results have been found. */
        void setStop() { setComplete(); _stopRequested = true; }

        void mayAdvance();
        bool countingMatches();
        bool countMatches() const;
        /**
         * @return true if the results generated by this query plan will be loaded from the record
         *     store (not built from an index entry).
         */
        bool hasDocumentLoadingQueryPlan() const;

        void recordCursorLocation();
        void checkCursorAdvanced();
        void handleCursorAdvanced();
        void checkCursorOrdering();

        bool _complete;
        bool _stopRequested;
        ExceptionInfo _exception;
        const QueryPlan* _queryPlan;
        bool _error;
        CachedMatchCounter _matchCounter;
        bool _countingMatches;
        bool _mustAdvance;
        bool _capped;
        shared_ptr<Cursor> _c;
        ClientCursor::Holder _cc;
        DiskLoc _posBeforeYield;
        ClientCursor::YieldData _yieldData;
        const QueryPlanSelectionPolicy& _selectionPolicy;
        const bool& _requireOrder; // TODO don't use a ref for this, but signal change explicitly
        shared_ptr<ExplainPlanInfo> _explainPlanInfo;
        bool _alwaysCountMatches;
    };

    /**
     * This class works if T::operator< is variant unlike a regular stl priority queue, but it's
     * very slow.  However if _vec.size() is always very small, it would be fine, maybe even faster
     * than a smart impl that does more memory allocations.
     * TODO Clean up this temporary code.
     */
    template<class T>
    class PriorityQueue {
        MONGO_DISALLOW_COPYING( PriorityQueue );
    public:
        PriorityQueue() {
            _vec.reserve(4);
        }
        int size() const { return _vec.size(); }
        bool empty() const { return _vec.empty(); }
        void push(const T & x) { 
            _vec.push_back(x);
        }
        T pop() { 
            size_t t = 0;
            for( size_t i = 1; i < _vec.size(); i++ ) {
                if( _vec[t] < _vec[i] )
                    t = i;
            }
            T ret = _vec[t];
            _vec.erase(_vec.begin()+t);
            return ret;
        }
    private:
        vector<T> _vec;
    };

    class QueryPlanSet;

    /** Populates a provided QueryPlanSet with candidate query plans, when requested. */
    class QueryPlanGenerator {
    public:

        /** Policies for utilizing recorded plans. */
        typedef enum {
            Ignore, // Ignore the recorded plan and try all candidate plans.
            UseIfInOrder, // Use the recorded plan if it is properly ordered.
            Use // Always use the recorded plan.
        } RecordedPlanPolicy;

        /** @param qps The QueryPlanSet to which plans will be provided. */
        QueryPlanGenerator( QueryPlanSet &qps,
                           auto_ptr<FieldRangeSetPair> originalFrsp,
                           const shared_ptr<const ParsedQuery> &parsedQuery,
                           const BSONObj &hint,
                           RecordedPlanPolicy recordedPlanPolicy,
                           const BSONObj &min,
                           const BSONObj &max,
                           bool allowSpecial );
        /** Populate the provided QueryPlanSet with an initial set of plans. */
        void addInitialPlans();
        /** Supplement a cached plan provided earlier by adding additional query plans. */
        void addFallbackPlans();

    private:

        bool addShortCircuitPlan( NamespaceDetails *d );
        bool addHintPlan( NamespaceDetails *d );
        bool addSpecialPlan( NamespaceDetails *d );
        void addStandardPlans( NamespaceDetails *d );
        bool addCachedPlan( NamespaceDetails *d );
        shared_ptr<QueryPlan> newPlan( NamespaceDetails *d,
                                      int idxNo,
                                      const BSONObj &min = BSONObj(),
                                      const BSONObj &max = BSONObj(),
                                      const string &special = "" ) const;
        bool setUnindexedPlanIf( bool set, NamespaceDetails *d );
        void setSingleUnindexedPlan( NamespaceDetails *d );
        void setHintedPlanForIndex( IndexDetails& id );
        void validateAndSetHintedPlan( const shared_ptr<QueryPlan>& plan );
        void warnOnCappedIdTableScan() const;
        QueryPlanSet &_qps;
        auto_ptr<FieldRangeSetPair> _originalFrsp;
        shared_ptr<const ParsedQuery> _parsedQuery;
        BSONObj _hint;
        RecordedPlanPolicy _recordedPlanPolicy;
        BSONObj _min;
        BSONObj _max;
        bool _allowSpecial;
    };

    /** A set of candidate query plans for a query. */
    class QueryPlanSet {
    public:
        typedef boost::shared_ptr<QueryPlan> QueryPlanPtr;
        typedef vector<QueryPlanPtr> PlanVector;

        /**
         * @param originalFrsp - original constraints for this query clause; if null, frsp will be
         * used.
         */
        static QueryPlanSet* make( const char* ns,
                                   auto_ptr<FieldRangeSetPair> frsp,
                                   auto_ptr<FieldRangeSetPair> originalFrsp,
                                   const BSONObj& originalQuery,
                                   const BSONObj& order,
                                   const shared_ptr<const ParsedQuery>& parsedQuery,
                                   const BSONObj& hint,
                                   QueryPlanGenerator::RecordedPlanPolicy recordedPlanPolicy,
                                   const BSONObj& min,
                                   const BSONObj& max,
                                   bool allowSpecial );

        /** @return number of candidate plans. */
        int nPlans() const { return _plans.size(); }

        QueryPlanPtr firstPlan() const { return _plans[ 0 ]; }
        
        /** @return true if a plan is selected based on previous success of this plan. */
        bool usingCachedPlan() const { return _usingCachedPlan; }
        /** @return true if some candidate plans may have been excluded due to plan caching. */
        bool hasPossiblyExcludedPlans() const;
        /** @return a single plan that may work well for the specified query. */
        QueryPlanPtr getBestGuess() const;

        const FieldRangeSetPair &frsp() const { return *_frsp; }
        BSONObj originalQuery() const { return _originalQuery; }
        BSONObj order() const { return _order; }
        
        /** @return true if an active plan is in order. */
        bool haveInOrderPlan() const;
        /** @return true if an active or fallback plan is in order. */
        bool possibleInOrderPlan() const;
        /** @return true if an active or fallback plan is out of order. */
        bool possibleOutOfOrderPlan() const;

        CandidatePlanCharacter characterizeCandidatePlans() const;
        
        bool prepareToRetryQuery();
        
        string toString() const;
        
        /** Configure a single query plan if one has not already been provided. */
        void setSinglePlan( const QueryPlanPtr &plan );
        /** Configure a query plan from the plan cache. */
        void setCachedPlan( const QueryPlanPtr &plan, const CachedQueryPlan &cachedPlan );
        /** Add a candidate query plan, potentially one of many. */
        void addCandidatePlan( const QueryPlanPtr &plan );

        const PlanVector& plans() const { return _plans; }
        bool mayRecordPlan() const { return _mayRecordPlan; }
        int oldNScanned() const { return _oldNScanned; }
        void addFallbackPlans();
        void setUsingCachedPlan( bool usingCachedPlan ) { _usingCachedPlan = usingCachedPlan; }
        
        //for testing
        bool modifiedKeys() const;
        bool hasMultiKey() const;

    private:

        QueryPlanSet( const char *ns,
                     auto_ptr<FieldRangeSetPair> frsp,
                     auto_ptr<FieldRangeSetPair> originalFrsp,
                     const BSONObj &originalQuery,
                     const BSONObj &order,
                     const shared_ptr<const ParsedQuery> &parsedQuery,
                     const BSONObj &hint,
                     QueryPlanGenerator::RecordedPlanPolicy recordedPlanPolicy,
                     const BSONObj &min,
                     const BSONObj &max,
                     bool allowSpecial );
        void init();

        void pushPlan( const QueryPlanPtr& plan );

        QueryPlanGenerator _generator;
        BSONObj _originalQuery;
        auto_ptr<FieldRangeSetPair> _frsp;
        PlanVector _plans;
        bool _mayRecordPlan;
        bool _usingCachedPlan;
        CandidatePlanCharacter _cachedPlanCharacter;
        BSONObj _order;
        long long _oldNScanned;
        ElapsedTracker _yieldSometimesTracker;
        bool _allowSpecial;
    };

    /**
     * A priority queue of QueryPlanRunners ordered by their nscanned values.  The QueryPlanRunners
     * are iterated sequentially and reinserted into the queue until one runner completes or all
     * runners error out.
     */
    class QueryPlanRunnerQueue {
    public:
        QueryPlanRunnerQueue( QueryPlanSet& plans, const QueryPlanRunner& prototypeRunner );
        
        /**
         * Pull a runner from the priority queue, advance it if possible, re-insert it into the
         * queue if it is not done, and return it.  But if this runner errors out, retry with
         * another runner until a non error runner is found or all runners have errored out.
         * @return the next non error runner if there is one, otherwise an error runner.
         * If the returned runner is complete() or error(), this queue becomes done().
         */
        shared_ptr<QueryPlanRunner> next();
        /** @return true if done iterating. */
        bool done() const { return _done; }

        /** Prepare all runners for a database mutex yield. */
        void prepareToYield();
        /** Restore all runners after a database mutex yield. */
        void recoverFromYield();
        
        /** @return an ExplainClauseInfo object that will be updated as the query runs. */
        shared_ptr<ExplainClauseInfo> generateExplainInfo() {
            _explainClauseInfo.reset( new ExplainClauseInfo() );
            return _explainClauseInfo;
        }

    private:
        const QueryPlanRunner& _prototypeRunner;
        QueryPlanSet& _plans;
        static void initRunner( QueryPlanRunner& runner );
        static void nextRunner( QueryPlanRunner& runner );
        static void prepareToYieldRunner( QueryPlanRunner& runner );
        static void recoverFromYieldRunner( QueryPlanRunner& runner );
        
        /** Initialize the Runner. */
        shared_ptr<QueryPlanRunner> init();
        /** Move the Runner forward one iteration, and @return the plan for the iteration. */
        shared_ptr<QueryPlanRunner> _next();

        vector<shared_ptr<QueryPlanRunner> > _runners;
        struct RunnerHolder {
            RunnerHolder( const shared_ptr<QueryPlanRunner>& runner ) :
                _runner( runner ),
                _offset() {
            }
            shared_ptr<QueryPlanRunner> _runner;
            long long _offset;
            bool operator<( const RunnerHolder& other ) const {
                return _runner->nscanned() + _offset > other._runner->nscanned() + other._offset;
            }
        };
        PriorityQueue<RunnerHolder> _queue;
        shared_ptr<ExplainClauseInfo> _explainClauseInfo;
        bool _done;
    };

    /** Handles $or type queries by generating a QueryPlanSet for each $or clause. */
    class MultiPlanScanner {
    public:
        
        static MultiPlanScanner *make( const StringData& ns,
                                      const BSONObj &query,
                                      const BSONObj &order,
                                      const shared_ptr<const ParsedQuery> &parsedQuery =
                                             shared_ptr<const ParsedQuery>(),
                                      const BSONObj &hint = BSONObj(),
                                      QueryPlanGenerator::RecordedPlanPolicy recordedPlanPolicy =
                                             QueryPlanGenerator::Use,
                                      const BSONObj &min = BSONObj(),
                                      const BSONObj &max = BSONObj() );

        /** Set the originalRunner for QueryPlanSet iteration. */
        void initialRunner( const shared_ptr<QueryPlanRunner>& originalRunner ) {
            _baseRunner = originalRunner;
        }
        /**
         * Advance to the next runner, if not doneRunners().
         * @return the next non error runner if there is one, otherwise an error runner.
         * If the returned runner is complete() or error(), the MultiPlanScanner becomes
         * doneRunners() and no further runner iteration is possible.
         */
        shared_ptr<QueryPlanRunner> nextRunner();
        /** @return true if done with runner iteration. */
        bool doneRunners() const { return _doneRunners; }

        /**
         * Advance to the next $or clause; hasMoreClauses() must be true.
         * @param currentPlan QueryPlan of the current $or clause
         * @return best guess query plan of the next $or clause, 0 if there is no such plan.
         */
        const QueryPlan *nextClauseBestGuessPlan( const QueryPlan &currentPlan );

        /** Add explain information for a new clause. */
        void addClauseInfo( const shared_ptr<ExplainClauseInfo> &clauseInfo ) {
            verify( _explainQueryInfo );
            _explainQueryInfo->addClauseInfo( clauseInfo );
        }
        
        /** @return an ExplainQueryInfo object that will be updated as the query runs. */
        shared_ptr<ExplainQueryInfo> generateExplainInfo() {
            _explainQueryInfo.reset( new ExplainQueryInfo() );
            return _explainQueryInfo;
        }
        
        /** Yield the runner member. */
        
        void prepareToYield();
        void recoverFromYield();
        
        /** Clear the runner member. */
        void clearRunnerQueue();
        
        void setRecordedPlanPolicy( QueryPlanGenerator::RecordedPlanPolicy recordedPlanPolicy ) {
            _recordedPlanPolicy = recordedPlanPolicy;
        }
        
        int currentNPlans() const;

        /**
         * @return the query plan that would be used if the scanner would run a single
         * cursor for this query, otherwise 0.  The returned plan is invalid if this
         * MultiPlanScanner is destroyed, hence we return a raw pointer.
         */
        const QueryPlan *singlePlan() const;
        
        /** @return true if more $or clauses need to be scanned. */
        bool hasMoreClauses() const {
            return _or ? ( !_tableScanned && !_org->orRangesExhausted() ) : _i == 0;
        }
        /**
         * @return plan information if there is a cached plan for a non $or query, otherwise an
         * empty object.
         */
        BSONObj cachedPlanExplainSummary() const;
        /**
         * @return true if this is not a $or query and some candidate plans may have been excluded
         * due to plan caching.
         */
        bool hasPossiblyExcludedPlans() const {
            return !_or && _currentQps->hasPossiblyExcludedPlans();
        }
        bool hasMultiKey() const { return _currentQps->hasMultiKey(); }
        
        /** Clear recorded indexes for the current QueryPlanSet's patterns. */
        void clearIndexesForPatterns() const;

        /** @return true if an active plan of _currentQps is in order. */
        bool haveInOrderPlan() const;
        /** @return true if an active or fallback plan of _currentQps is in order. */
        bool possibleInOrderPlan() const;
        /** @return true if an active or fallback plan of _currentQps is out of order. */
        bool possibleOutOfOrderPlan() const;
        
        int i() const { return _i; }
        
        string toString() const;

    private:

        MultiPlanScanner( const StringData& ns,
                         const BSONObj &query,
                         const shared_ptr<const ParsedQuery> &parsedQuery,
                         const BSONObj &hint,
                         QueryPlanGenerator::RecordedPlanPolicy recordedPlanPolicy );
        void init( const BSONObj &order,
                  const BSONObj &min,
                  const BSONObj &max );

        /** Initialize or iterate a runner generated from @param originalOp. */
        shared_ptr<QueryPlanRunner> iterateRunnerQueue( QueryPlanRunner& originalRunner,
                                                        bool retried = false );

        shared_ptr<QueryPlanRunner> nextRunnerSimple();
        shared_ptr<QueryPlanRunner> nextRunnerOr();
        
        void updateCurrentQps( QueryPlanSet *qps );
        
        void assertNotOr() const {
            massert( 13266, "not implemented for $or query", !_or );
        }
        void assertHasMoreClauses() const {
            massert( 13271, "no more clauses", hasMoreClauses() );
        }
        
        void handleEndOfClause( const QueryPlan &clausePlan );
        void handleBeginningOfClause();
        bool mayHandleBeginningOfClause();

        bool haveUselessOr() const;

        const string _ns;
        bool _or;
        BSONObj _query;
        shared_ptr<const ParsedQuery> _parsedQuery;
        scoped_ptr<OrRangeGenerator> _org; // May be null in certain non $or query cases.
        scoped_ptr<QueryPlanSet> _currentQps;
        int _i;
        QueryPlanGenerator::RecordedPlanPolicy _recordedPlanPolicy;
        BSONObj _hint;
        bool _tableScanned;
        shared_ptr<QueryPlanRunner> _baseRunner;
        scoped_ptr<QueryPlanRunnerQueue> _runnerQueue;
        shared_ptr<ExplainQueryInfo> _explainQueryInfo;
        bool _doneRunners;
    };

    /**
     * Provides a cursor interface for serial single Cursor iteration using a MultiPlanScanner.
     * Currently used internally by a QueryOptimizerCursor.
     *
     * A MultiCursor is backed by one BasicCursor or BtreeCursor at a time and forwards calls for
     * ensuring a consistent state after a write to its backing Cursor.
     */
    class MultiCursor : public Cursor {
    public:
        /** @param nscanned is the initial nscanned value. */
        MultiCursor( auto_ptr<MultiPlanScanner> mps, const shared_ptr<Cursor> &c,
                    const shared_ptr<CoveredIndexMatcher> &matcher,
                    const shared_ptr<ExplainPlanInfo> &explainPlanInfo,
                    const QueryPlanRunner& runner, long long nscanned );

        virtual bool ok() { return _c->ok(); }
        virtual Record* _current() { return _c->_current(); }
        virtual BSONObj current() { return _c->current(); }
        virtual DiskLoc currLoc() { return _c->currLoc(); }
        virtual bool advance();
        virtual BSONObj currKey() const { return _c->currKey(); }
        virtual DiskLoc refLoc() { return _c->refLoc(); }
        virtual void noteLocation() { _c->noteLocation(); }
        virtual void checkLocation() { _c->checkLocation(); }
        virtual void recoverFromYield();
        virtual bool supportGetMore() { return true; }
        virtual bool supportYields() { return true; }
        virtual BSONObj indexKeyPattern() { return _c->indexKeyPattern(); }

        /** Deduping documents from a prior cursor is handled by the matcher. */
        virtual bool getsetdup(DiskLoc loc) { return _c->getsetdup( loc ); }

        virtual bool modifiedKeys() const { return true; }

        virtual bool isMultiKey() const { return _mps->hasMultiKey(); }

        virtual CoveredIndexMatcher* matcher() const { return _matcher.get(); }

        virtual bool capped() const { return _c->capped(); }
        
        virtual long long nscanned() { return _nscanned + _c->nscanned(); }
        
        void noteIterate( bool match, bool loadedRecord );
        
        const QueryPlan &queryPlan() const {
            verify( _c->ok() && _queryPlan );
            return *_queryPlan;
        }
        
        const Projection::KeyOnly *keyFieldsOnly() const {
            verify( _c->ok() && _queryPlan );
            return _queryPlan->keyFieldsOnly().get();
        }
    private:
        void advanceClause();
        void advanceExhaustedClauses();
        auto_ptr<MultiPlanScanner> _mps;
        shared_ptr<Cursor> _c;
        shared_ptr<CoveredIndexMatcher> _matcher;
        const QueryPlan *_queryPlan;
        long long _nscanned;
        shared_ptr<ExplainPlanInfo> _explainPlanInfo;
    };

    /** NOTE min, max, and keyPattern will be updated to be consistent with the selected index. */
    IndexDetails *indexDetailsForRange( const char *ns, string &errmsg, BSONObj &min, BSONObj &max, BSONObj &keyPattern );

    class CachedQueryPlan;
    
    /**
     * Add-on functionality for queryutil classes requiring access to indexing
     * functionality not currently linked to mongos.
     * TODO Clean this up a bit, possibly with separate sharded and non sharded
     * implementations for the appropriate queryutil classes or by pulling index
     * related functionality into separate wrapper classes.
     */
    struct QueryUtilIndexed {
        /** @return true if the index may be useful according to its KeySpec. */
        static bool indexUseful( const FieldRangeSetPair &frsp, NamespaceDetails *d, int idxNo, const BSONObj &order );
        /** Clear any indexes recorded as the best for either the single or multi key pattern. */
        static void clearIndexesForPatterns( const FieldRangeSetPair &frsp, const BSONObj &order );
        /** Return a recorded best index for the single or multi key pattern. */
        static CachedQueryPlan bestIndexForPatterns( const FieldRangeSetPair &frsp, const BSONObj &order );        
        static bool uselessOr( const OrRangeGenerator& org, NamespaceDetails *d, int hintIdx );
    };
    
} // namespace mongo