diff options
Diffstat (limited to 'db/queryoptimizer.h')
| -rw-r--r-- | db/queryoptimizer.h | 224 |
1 files changed, 131 insertions, 93 deletions
diff --git a/db/queryoptimizer.h b/db/queryoptimizer.h index 8314bfa..cf3180a 100644 --- a/db/queryoptimizer.h +++ b/db/queryoptimizer.h @@ -25,15 +25,17 @@ #include "../util/message.h" namespace mongo { - + class IndexDetails; class IndexType; class QueryPlan : boost::noncopyable { public: - QueryPlan(NamespaceDetails *_d, - int _idxNo, // -1 = no index + + QueryPlan(NamespaceDetails *d, + int idxNo, // -1 = no index const FieldRangeSet &fbs, + const FieldRangeSet &originalFrs, const BSONObj &originalQuery, const BSONObj &order, const BSONObj &startKey = BSONObj(), @@ -41,44 +43,50 @@ namespace mongo { string special="" ); /* If true, no other index can do better. */ - bool optimal() const { return optimal_; } + bool optimal() const { return _optimal; } /* ScanAndOrder processing will be required if true */ - bool scanAndOrderRequired() const { return scanAndOrderRequired_; } + bool scanAndOrderRequired() const { return _scanAndOrderRequired; } /* When true, the index we are using has keys such that it can completely resolve the query expression to match by itself without ever checking the main object. */ - bool exactKeyMatch() const { return exactKeyMatch_; } - /* If true, the startKey and endKey are unhelpful and the index order doesn't match the + bool exactKeyMatch() const { return _exactKeyMatch; } + /* If true, the startKey and endKey are unhelpful and the index order doesn't match the requested sort order */ - bool unhelpful() const { return unhelpful_; } - int direction() const { return direction_; } + bool unhelpful() const { return _unhelpful; } + int direction() const { return _direction; } shared_ptr<Cursor> newCursor( const DiskLoc &startLoc = DiskLoc() , int numWanted=0 ) const; shared_ptr<Cursor> newReverseCursor() const; BSONObj indexKey() const; - bool willScanTable() const { return !index_ && fbs_.matchPossible(); } - const char *ns() const { return fbs_.ns(); } - NamespaceDetails *nsd() const { return d; } + bool indexed() const { return _index; } + bool willScanTable() const { return !_index && _fbs.matchPossible(); } + const char *ns() const { return _fbs.ns(); } + NamespaceDetails *nsd() const { return _d; } BSONObj originalQuery() const { return _originalQuery; } - BSONObj simplifiedQuery( const BSONObj& fields = BSONObj() ) const { return fbs_.simplifiedQuery( fields ); } - const FieldRange &range( const char *fieldName ) const { return fbs_.range( fieldName ); } + BSONObj simplifiedQuery( const BSONObj& fields = BSONObj() ) const { return _fbs.simplifiedQuery( fields ); } + const FieldRange &range( const char *fieldName ) const { return _fbs.range( fieldName ); } void registerSelf( long long nScanned ) const; + shared_ptr< FieldRangeVector > originalFrv() const { return _originalFrv; } + // just for testing shared_ptr< FieldRangeVector > frv() const { return _frv; } + bool isMultiKey() const; + private: - NamespaceDetails *d; - int idxNo; - const FieldRangeSet &fbs_; + NamespaceDetails * _d; + int _idxNo; + const FieldRangeSet &_fbs; const BSONObj &_originalQuery; - const BSONObj &order_; - const IndexDetails *index_; - bool optimal_; - bool scanAndOrderRequired_; - bool exactKeyMatch_; - int direction_; + const BSONObj &_order; + const IndexDetails * _index; + bool _optimal; + bool _scanAndOrderRequired; + bool _exactKeyMatch; + int _direction; shared_ptr< FieldRangeVector > _frv; + shared_ptr< FieldRangeVector > _originalFrv; BSONObj _startKey; BSONObj _endKey; - bool endKeyInclusive_; - bool unhelpful_; + bool _endKeyInclusive; + bool _unhelpful; string _special; IndexType * _type; bool _startOrEndSpec; @@ -93,16 +101,17 @@ namespace mongo { // Used when handing off from one QueryOp type to another QueryOp( const QueryOp &other ) : - _complete(), _stopRequested(), _qp(), _error(), _matcher( other._matcher ), - _orConstraint( other._orConstraint ) {} - + _complete(), _stopRequested(), _qp(), _error(), _matcher( other._matcher ), + _orConstraint( other._orConstraint ) {} + virtual ~QueryOp() {} - + /** these gets called after a query plan is set */ - void init() { + void init() { if ( _oldMatcher.get() ) { _matcher.reset( _oldMatcher->nextClauseMatcher( qp().indexKey() ) ); - } else { + } + else { _matcher.reset( new CoveredIndexMatcher( qp().originalQuery(), qp().indexKey(), alwaysUseRecord() ) ); } _init(); @@ -110,10 +119,12 @@ namespace mongo { virtual void next() = 0; virtual bool mayRecordPlan() const = 0; - + virtual bool prepareToYield() { massert( 13335, "yield not supported", false ); return false; } virtual void recoverFromYield() { massert( 13336, "yield not supported", false ); } - + + virtual long long nscanned() = 0; + /** @return a copy of the inheriting class, which will be run with its own query plan. If multiple plan sets are required for an $or query, the QueryOp of the winning plan from a given set will be cloned @@ -143,17 +154,17 @@ namespace mongo { shared_ptr< CoveredIndexMatcher > matcher() const { return _matcher; } protected: void setComplete() { - _orConstraint = qp().frv(); + _orConstraint = qp().originalFrv(); _complete = true; } void setStop() { setComplete(); _stopRequested = true; } virtual void _init() = 0; - + virtual QueryOp *_createChild() const = 0; - + virtual bool alwaysUseRecord() const { return false; } - + private: bool _complete; bool _stopRequested; @@ -164,42 +175,47 @@ namespace mongo { shared_ptr< CoveredIndexMatcher > _oldMatcher; shared_ptr< FieldRangeVector > _orConstraint; }; - + // Set of candidate query plans for a particular query. Used for running // a QueryOp on these plans. class QueryPlanSet { public: - typedef boost::shared_ptr< QueryPlan > PlanPtr; - typedef vector< PlanPtr > PlanSet; + typedef boost::shared_ptr< QueryPlan > QueryPlanPtr; + typedef vector< QueryPlanPtr > PlanSet; QueryPlanSet( const char *ns, - auto_ptr< FieldRangeSet > frs, - const BSONObj &originalQuery, - const BSONObj &order, - const BSONElement *hint = 0, - bool honorRecordedPlan = true, - const BSONObj &min = BSONObj(), - const BSONObj &max = BSONObj(), - bool bestGuessOnly = false, - bool mayYield = false); - int nPlans() const { return plans_.size(); } + auto_ptr< FieldRangeSet > frs, + auto_ptr< FieldRangeSet > originalFrs, + const BSONObj &originalQuery, + const BSONObj &order, + const BSONElement *hint = 0, + bool honorRecordedPlan = true, + const BSONObj &min = BSONObj(), + const BSONObj &max = BSONObj(), + bool bestGuessOnly = false, + bool mayYield = false); + int nPlans() const { return _plans.size(); } shared_ptr< QueryOp > runOp( QueryOp &op ); template< class T > shared_ptr< T > runOp( T &op ) { return dynamic_pointer_cast< T >( runOp( static_cast< QueryOp& >( op ) ) ); } BSONObj explain() const; - bool usingPrerecordedPlan() const { return usingPrerecordedPlan_; } - PlanPtr getBestGuess() const; + bool usingPrerecordedPlan() const { return _usingPrerecordedPlan; } + QueryPlanPtr getBestGuess() const; //for testing - const FieldRangeSet &fbs() const { return *fbs_; } + const FieldRangeSet &fbs() const { return *_fbs; } + const FieldRangeSet &originalFrs() const { return *_originalFrs; } + bool modifiedKeys() const; + bool hasMultiKey() const; + private: void addOtherPlans( bool checkFirst ); - void addPlan( PlanPtr plan, bool checkFirst ) { - if ( checkFirst && plan->indexKey().woCompare( plans_[ 0 ]->indexKey() ) == 0 ) + void addPlan( QueryPlanPtr plan, bool checkFirst ) { + if ( checkFirst && plan->indexKey().woCompare( _plans[ 0 ]->indexKey() ) == 0 ) return; - plans_.push_back( plan ); + _plans.push_back( plan ); } void init(); void addHint( IndexDetails &id ); @@ -207,25 +223,27 @@ namespace mongo { Runner( QueryPlanSet &plans, QueryOp &op ); shared_ptr< QueryOp > run(); void mayYield( const vector< shared_ptr< QueryOp > > &ops ); - QueryOp &op_; - QueryPlanSet &plans_; + QueryOp &_op; + QueryPlanSet &_plans; static void initOp( QueryOp &op ); static void nextOp( QueryOp &op ); static bool prepareToYield( QueryOp &op ); static void recoverFromYield( QueryOp &op ); }; - const char *ns; + + const char *_ns; BSONObj _originalQuery; - auto_ptr< FieldRangeSet > fbs_; - PlanSet plans_; - bool mayRecordPlan_; - bool usingPrerecordedPlan_; - BSONObj hint_; - BSONObj order_; - long long oldNScanned_; - bool honorRecordedPlan_; - BSONObj min_; - BSONObj max_; + auto_ptr< FieldRangeSet > _fbs; + auto_ptr< FieldRangeSet > _originalFrs; + PlanSet _plans; + bool _mayRecordPlan; + bool _usingPrerecordedPlan; + BSONObj _hint; + BSONObj _order; + long long _oldNScanned; + bool _honorRecordedPlan; + BSONObj _min; + BSONObj _max; string _special; bool _bestGuessOnly; bool _mayYield; @@ -258,24 +276,24 @@ namespace mongo { class MultiPlanScanner { public: MultiPlanScanner( const char *ns, - const BSONObj &query, - const BSONObj &order, - const BSONElement *hint = 0, - bool honorRecordedPlan = true, - const BSONObj &min = BSONObj(), - const BSONObj &max = BSONObj(), - bool bestGuessOnly = false, - bool mayYield = false); + const BSONObj &query, + const BSONObj &order, + const BSONElement *hint = 0, + bool honorRecordedPlan = true, + const BSONObj &min = BSONObj(), + const BSONObj &max = BSONObj(), + bool bestGuessOnly = false, + bool mayYield = false); shared_ptr< QueryOp > runOp( QueryOp &op ); template< class T > shared_ptr< T > runOp( T &op ) { return dynamic_pointer_cast< T >( runOp( static_cast< QueryOp& >( op ) ) ); - } + } shared_ptr< QueryOp > runOpOnce( QueryOp &op ); template< class T > shared_ptr< T > runOpOnce( T &op ) { return dynamic_pointer_cast< T >( runOpOnce( static_cast< QueryOp& >( op ) ) ); - } + } bool mayRunMore() const { return _or ? ( !_tableScanned && !_fros.orFinished() ) : _i == 0; } BSONObj oldExplain() const { assertNotOr(); return _currentQps->explain(); } // just report this when only one query op @@ -284,6 +302,9 @@ namespace mongo { } void setBestGuessOnly() { _bestGuessOnly = true; } void mayYield( bool val ) { _mayYield = val; } + bool modifiedKeys() const { return _currentQps->modifiedKeys(); } + bool hasMultiKey() const { return _currentQps->hasMultiKey(); } + private: void assertNotOr() const { massert( 13266, "not implemented for $or query", !_or ); @@ -301,21 +322,22 @@ namespace mongo { bool _mayYield; bool _tableScanned; }; - + class MultiCursor : public Cursor { public: class CursorOp : public QueryOp { public: CursorOp() {} CursorOp( const QueryOp &other ) : QueryOp( other ) {} - virtual shared_ptr< Cursor > newCursor() const = 0; + virtual shared_ptr< Cursor > newCursor() const = 0; }; // takes ownership of 'op' MultiCursor( const char *ns, const BSONObj &pattern, const BSONObj &order, shared_ptr< CursorOp > op = shared_ptr< CursorOp >(), bool mayYield = false ) - : _mps( new MultiPlanScanner( ns, pattern, order, 0, true, BSONObj(), BSONObj(), !op.get(), mayYield ) ) { + : _mps( new MultiPlanScanner( ns, pattern, order, 0, true, BSONObj(), BSONObj(), !op.get(), mayYield ) ), _nscanned() { if ( op.get() ) { _op = op; - } else { + } + else { _op.reset( new NoOp() ); } if ( _mps->mayRunMore() ) { @@ -323,13 +345,14 @@ namespace mongo { if ( !ok() ) { advance(); } - } else { + } + else { _c.reset( new BasicCursor( DiskLoc() ) ); } } // used to handoff a query to a getMore() MultiCursor( auto_ptr< MultiPlanScanner > mps, const shared_ptr< Cursor > &c, const shared_ptr< CoveredIndexMatcher > &matcher, const QueryOp &op ) - : _op( new NoOp( op ) ), _c( c ), _mps( mps ), _matcher( matcher ) { + : _op( new NoOp( op ) ), _c( c ), _mps( mps ), _matcher( matcher ), _nscanned( -1 ) { _mps->setBestGuessOnly(); _mps->mayYield( false ); // with a NoOp, there's no need to yield in QueryPlanSet if ( !ok() ) { @@ -355,16 +378,24 @@ namespace mongo { } virtual void checkLocation() { _c->checkLocation(); - } + } virtual bool supportGetMore() { return true; } virtual bool supportYields() { return _c->supportYields(); } + // with update we could potentially get the same document on multiple // indexes, but update appears to already handle this with seenObjects // so we don't have to do anything special here. virtual bool getsetdup(DiskLoc loc) { - return _c->getsetdup( loc ); + return _c->getsetdup( loc ); } + + virtual bool modifiedKeys() const { return _mps->modifiedKeys(); } + + virtual bool isMultiKey() const { return _mps->hasMultiKey(); } + virtual CoveredIndexMatcher *matcher() const { return _matcher.get(); } + // return -1 if we're a getmore handoff + virtual long long nscanned() { return _nscanned >= 0 ? _nscanned + _c->nscanned() : _nscanned; } // just for testing shared_ptr< Cursor > sub_c() const { return _c; } private: @@ -377,8 +408,12 @@ namespace mongo { virtual bool mayRecordPlan() const { return false; } virtual QueryOp *_createChild() const { return new NoOp(); } virtual shared_ptr< Cursor > newCursor() const { return qp().newCursor(); } + virtual long long nscanned() { assert( false ); return 0; } }; void nextClause() { + if ( _nscanned >= 0 && _c.get() ) { + _nscanned += _c->nscanned(); + } shared_ptr< CursorOp > best = _mps->runOpOnce( *_op ); if ( ! best->complete() ) throw MsgAssertionException( best->exception() ); @@ -390,12 +425,13 @@ namespace mongo { shared_ptr< Cursor > _c; auto_ptr< MultiPlanScanner > _mps; shared_ptr< CoveredIndexMatcher > _matcher; + long long _nscanned; }; - + // 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 ); - inline bool isSimpleIdQuery( const BSONObj& query ){ + inline bool isSimpleIdQuery( const BSONObj& query ) { BSONObjIterator i(query); if( !i.more() ) return false; BSONElement e = i.next(); @@ -403,14 +439,16 @@ namespace mongo { if( strcmp("_id", e.fieldName()) != 0 ) return false; return e.isSimpleType(); // e.g. not something like { _id : { $gt : ... } - + // matcher() will always work on the returned cursor inline shared_ptr< Cursor > bestGuessCursor( const char *ns, const BSONObj &query, const BSONObj &sort ) { if( !query.getField( "$or" ).eoo() ) { return shared_ptr< Cursor >( new MultiCursor( ns, query, sort ) ); - } else { + } + else { auto_ptr< FieldRangeSet > frs( new FieldRangeSet( ns, query ) ); - shared_ptr< Cursor > ret = QueryPlanSet( ns, frs, query, sort ).getBestGuess()->newCursor(); + auto_ptr< FieldRangeSet > origFrs( new FieldRangeSet( *frs ) ); + shared_ptr< Cursor > ret = QueryPlanSet( ns, frs, origFrs, query, sort ).getBestGuess()->newCursor(); if ( !query.isEmpty() ) { shared_ptr< CoveredIndexMatcher > matcher( new CoveredIndexMatcher( query, ret->indexKeyPattern() ) ); ret->setMatcher( matcher ); @@ -418,5 +456,5 @@ namespace mongo { return ret; } } - + } // namespace mongo |