summaryrefslogtreecommitdiff
path: root/src/mongo/db/queryoptimizer.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/mongo/db/queryoptimizer.cpp')
-rw-r--r--src/mongo/db/queryoptimizer.cpp2038
1 files changed, 0 insertions, 2038 deletions
diff --git a/src/mongo/db/queryoptimizer.cpp b/src/mongo/db/queryoptimizer.cpp
deleted file mode 100644
index 469d7bf1691..00000000000
--- a/src/mongo/db/queryoptimizer.cpp
+++ /dev/null
@@ -1,2038 +0,0 @@
-// @file queryoptimizer.cpp
-
-/**
-* 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/>.
-*/
-
-#include "mongo/pch.h"
-
-#include "mongo/db/queryoptimizer.h"
-
-#include "mongo/client/dbclientinterface.h"
-#include "mongo/db/btreecursor.h"
-#include "mongo/db/cmdline.h"
-#include "mongo/db/db.h"
-#include "mongo/db/intervalbtreecursor.h"
-#include "mongo/db/pagefault.h"
-#include "mongo/server.h"
-
-//#define DEBUGQO(x) cout << x << endl;
-#define DEBUGQO(x)
-
-namespace mongo {
-
- QueryPlanSummary QueryPlan::summary() const { return QueryPlanSummary( *this ); }
-
- double elementDirection( const BSONElement &e ) {
- if ( e.isNumber() )
- return e.number();
- return 1;
- }
-
- // returns an IndexDetails * for a hint, 0 if hint is $natural.
- // hint must not be eoo()
- IndexDetails *parseHint( const BSONElement &hint, NamespaceDetails *d ) {
- massert( 13292, "hint eoo", !hint.eoo() );
- if( hint.type() == String ) {
- string hintstr = hint.valuestr();
- NamespaceDetails::IndexIterator i = d->ii();
- while( i.more() ) {
- IndexDetails& ii = i.next();
- if ( ii.indexName() == hintstr ) {
- return &ii;
- }
- }
- }
- else if( hint.type() == Object ) {
- BSONObj hintobj = hint.embeddedObject();
- uassert( 10112 , "bad hint", !hintobj.isEmpty() );
- if ( !strcmp( hintobj.firstElementFieldName(), "$natural" ) ) {
- return 0;
- }
- NamespaceDetails::IndexIterator i = d->ii();
- while( i.more() ) {
- IndexDetails& ii = i.next();
- if( ii.keyPattern().woCompare(hintobj) == 0 ) {
- return &ii;
- }
- }
- }
- uassert( 10113 , "bad hint", false );
- return 0;
- }
-
- QueryPlan *QueryPlan::make( NamespaceDetails *d,
- int idxNo,
- const FieldRangeSetPair &frsp,
- const FieldRangeSetPair *originalFrsp,
- const BSONObj &originalQuery,
- const BSONObj &order,
- const shared_ptr<const ParsedQuery> &parsedQuery,
- const BSONObj &startKey,
- const BSONObj &endKey,
- const std::string& special ) {
- auto_ptr<QueryPlan> ret( new QueryPlan( d, idxNo, frsp, originalQuery, order, parsedQuery,
- special ) );
- ret->init( originalFrsp, startKey, endKey );
- return ret.release();
- }
-
- QueryPlan::QueryPlan( NamespaceDetails *d,
- int idxNo,
- const FieldRangeSetPair &frsp,
- const BSONObj &originalQuery,
- const BSONObj &order,
- const shared_ptr<const ParsedQuery> &parsedQuery,
- const std::string& special ) :
- _d(d),
- _idxNo(idxNo),
- _frs( frsp.frsForIndex( _d, _idxNo ) ),
- _frsMulti( frsp.frsForIndex( _d, -1 ) ),
- _originalQuery( originalQuery ),
- _order( order ),
- _parsedQuery( parsedQuery ),
- _index( 0 ),
- _scanAndOrderRequired( true ),
- _matcherNecessary( true ),
- _direction( 0 ),
- _endKeyInclusive(),
- _utility( Helpful ),
- _special( special ),
- _type(0),
- _startOrEndSpec() {
- }
-
- void QueryPlan::init( const FieldRangeSetPair *originalFrsp,
- const BSONObj &startKey,
- const BSONObj &endKey ) {
- _endKeyInclusive = endKey.isEmpty();
- _startOrEndSpec = !startKey.isEmpty() || !endKey.isEmpty();
-
- BSONObj idxKey = _idxNo < 0 ? BSONObj() : _d->idx( _idxNo ).keyPattern();
-
- if ( !_frs.matchPossibleForIndex( idxKey ) ) {
- _utility = Impossible;
- _scanAndOrderRequired = false;
- return;
- }
-
- if ( willScanTable() ) {
- if ( _order.isEmpty() || !strcmp( _order.firstElementFieldName(), "$natural" ) )
- _scanAndOrderRequired = false;
- return;
- }
-
- _index = &_d->idx(_idxNo);
-
- // If the parsing or index indicates this is a special query, don't continue the processing
- if (!_special.empty() ||
- ( _index->getSpec().getType() &&
- _index->getSpec().getType()->suitability( _frs, _order ) != USELESS ) ) {
-
- _type = _index->getSpec().getType();
- if (_special.empty()) _special = _index->getSpec().getType()->getPlugin()->getName();
-
- massert( 13040 , (string)"no type for special: " + _special , _type );
- // hopefully safe to use original query in these contexts;
- // don't think we can mix special with $or clause separation yet
- _scanAndOrderRequired = _type->scanAndOrderRequired( _originalQuery , _order );
- return;
- }
-
- const IndexSpec &idxSpec = _index->getSpec();
- BSONObjIterator o( _order );
- BSONObjIterator k( idxKey );
- if ( !o.moreWithEOO() )
- _scanAndOrderRequired = false;
- while( o.moreWithEOO() ) {
- BSONElement oe = o.next();
- if ( oe.eoo() ) {
- _scanAndOrderRequired = false;
- break;
- }
- if ( !k.moreWithEOO() )
- break;
- BSONElement ke;
- while( 1 ) {
- ke = k.next();
- if ( ke.eoo() )
- goto doneCheckOrder;
- if ( strcmp( oe.fieldName(), ke.fieldName() ) == 0 )
- break;
- if ( !_frs.range( ke.fieldName() ).equality() )
- goto doneCheckOrder;
- }
- int d = elementDirection( oe ) == elementDirection( ke ) ? 1 : -1;
- if ( _direction == 0 )
- _direction = d;
- else if ( _direction != d )
- break;
- }
-doneCheckOrder:
- if ( _scanAndOrderRequired )
- _direction = 0;
- BSONObjIterator i( idxKey );
- int exactIndexedQueryCount = 0;
- int optimalIndexedQueryCount = 0;
- bool awaitingLastOptimalField = true;
- set<string> orderFieldsUnindexed;
- _order.getFieldNames( orderFieldsUnindexed );
- while( i.moreWithEOO() ) {
- BSONElement e = i.next();
- if ( e.eoo() )
- break;
- const FieldRange &fr = _frs.range( e.fieldName() );
- if ( awaitingLastOptimalField ) {
- if ( !fr.universal() )
- ++optimalIndexedQueryCount;
- if ( !fr.equality() )
- awaitingLastOptimalField = false;
- }
- else {
- if ( !fr.universal() )
- optimalIndexedQueryCount = -1;
- }
- if ( fr.equality() ) {
- BSONElement e = fr.max();
- if ( !e.isNumber() && !e.mayEncapsulate() && e.type() != RegEx )
- ++exactIndexedQueryCount;
- }
- orderFieldsUnindexed.erase( e.fieldName() );
- }
- if ( !_scanAndOrderRequired &&
- ( optimalIndexedQueryCount == _frs.numNonUniversalRanges() ) )
- _utility = Optimal;
- _frv.reset( new FieldRangeVector( _frs, idxSpec, _direction ) );
-
- if ( // If all field range constraints are on indexed fields and ...
- _utility == Optimal &&
- // ... the field ranges exactly represent the query and ...
- _frs.mustBeExactMatchRepresentation() &&
- // ... all indexed ranges are represented in the field range vector ...
- _frv->hasAllIndexedRanges() ) {
-
- // ... then the field range vector is sufficient to perform query matching against index
- // keys. No matcher is required.
- _matcherNecessary = false;
- }
-
- if ( originalFrsp ) {
- _originalFrv.reset( new FieldRangeVector( originalFrsp->frsForIndex( _d, _idxNo ),
- idxSpec, _direction ) );
- }
- else {
- _originalFrv = _frv;
- }
- if ( _startOrEndSpec ) {
- BSONObj newStart, newEnd;
- if ( !startKey.isEmpty() )
- _startKey = startKey;
- else
- _startKey = _frv->startKey();
- if ( !endKey.isEmpty() )
- _endKey = endKey;
- else
- _endKey = _frv->endKey();
- }
-
- if ( ( _scanAndOrderRequired || _order.isEmpty() ) &&
- _frs.range( idxKey.firstElementFieldName() ).universal() ) { // NOTE SERVER-2140
- _utility = Unhelpful;
- }
-
- if ( idxSpec.isSparse() && hasPossibleExistsFalsePredicate() ) {
- _utility = Disallowed;
- }
-
- if ( _parsedQuery && _parsedQuery->getFields() && !_d->isMultikey( _idxNo ) ) { // Does not check modifiedKeys()
- _keyFieldsOnly.reset( _parsedQuery->getFields()->checkKey( _index->keyPattern() ) );
- }
- }
-
- shared_ptr<Cursor> QueryPlan::newCursor( const DiskLoc& startLoc,
- bool requestIntervalCursor ) const {
-
- if ( _type ) {
- // hopefully safe to use original query in these contexts - don't think we can mix type with $or clause separation yet
- int numWanted = 0;
- if ( _parsedQuery ) {
- // SERVER-5390
- numWanted = _parsedQuery->getSkip() + _parsedQuery->getNumToReturn();
- }
- return _type->newCursor( _originalQuery , _order , numWanted );
- }
-
- if ( _utility == Impossible ) {
- // Dummy table scan cursor returning no results. Allowed in --notablescan mode.
- return shared_ptr<Cursor>( new BasicCursor( DiskLoc() ) );
- }
-
- if ( willScanTable() ) {
- checkTableScanAllowed();
- return findTableScan( _frs.ns(), _order, startLoc );
- }
-
- massert( 10363 , "newCursor() with start location not implemented for indexed plans", startLoc.isNull() );
-
- if ( _startOrEndSpec ) {
- // we are sure to spec _endKeyInclusive
- return shared_ptr<Cursor>( BtreeCursor::make( _d,
- *_index,
- _startKey,
- _endKey,
- _endKeyInclusive,
- _direction >= 0 ? 1 : -1 ) );
- }
-
- if ( _index->getSpec().getType() ) {
- return shared_ptr<Cursor>( BtreeCursor::make( _d,
- *_index,
- _frv->startKey(),
- _frv->endKey(),
- true,
- _direction >= 0 ? 1 : -1 ) );
- }
-
- // An IntervalBtreeCursor is returned if explicitly requested AND _frv is exactly
- // represented by a single interval within the btree.
- if ( // If an interval cursor is requested and ...
- requestIntervalCursor &&
- // ... equalities come before ranges (a requirement of Optimal) and ...
- _utility == Optimal &&
- // ... the field range vector exactly represents a single interval ...
- _frv->isSingleInterval() ) {
- // ... and an interval cursor can be created ...
- shared_ptr<Cursor> ret( IntervalBtreeCursor::make( _d,
- *_index,
- _frv->startKey(),
- _frv->startKeyInclusive(),
- _frv->endKey(),
- _frv->endKeyInclusive() ) );
- if ( ret ) {
- // ... then return the interval cursor.
- return ret;
- }
- }
-
- return shared_ptr<Cursor>( BtreeCursor::make( _d,
- *_index,
- _frv,
- independentRangesSingleIntervalLimit(),
- _direction >= 0 ? 1 : -1 ) );
- }
-
- shared_ptr<Cursor> QueryPlan::newReverseCursor() const {
- if ( willScanTable() ) {
- int orderSpec = _order.getIntField( "$natural" );
- if ( orderSpec == INT_MIN )
- orderSpec = 1;
- return findTableScan( _frs.ns(), BSON( "$natural" << -orderSpec ) );
- }
- massert( 10364 , "newReverseCursor() not implemented for indexed plans", false );
- return shared_ptr<Cursor>();
- }
-
- BSONObj QueryPlan::indexKey() const {
- if ( !_index )
- return BSON( "$natural" << 1 );
- return _index->keyPattern();
- }
-
- void QueryPlan::registerSelf( long long nScanned,
- CandidatePlanCharacter candidatePlans ) const {
- // Impossible query constraints can be detected before scanning and historically could not
- // generate a QueryPattern.
- if ( _utility == Impossible ) {
- return;
- }
-
- SimpleMutex::scoped_lock lk(NamespaceDetailsTransient::_qcMutex);
- QueryPattern queryPattern = _frs.pattern( _order );
- CachedQueryPlan queryPlanToCache( indexKey(), nScanned, candidatePlans );
- NamespaceDetailsTransient &nsdt = NamespaceDetailsTransient::get_inlock( ns() );
- nsdt.registerCachedQueryPlanForPattern( queryPattern, queryPlanToCache );
- }
-
- void QueryPlan::checkTableScanAllowed() const {
- if ( likely( !cmdLine.noTableScan ) )
- return;
-
- // TODO - is this desirable? See SERVER-2222.
- if ( _frs.numNonUniversalRanges() == 0 )
- return;
-
- if ( strstr( ns() , ".system." ) )
- return;
-
- if( str::startsWith(ns(), "local.") )
- return;
-
- if ( ! nsdetails( ns() ) )
- return;
-
- uassert( 10111 , (string)"table scans not allowed:" + ns() , ! cmdLine.noTableScan );
- }
-
- int QueryPlan::independentRangesSingleIntervalLimit() const {
- if ( _scanAndOrderRequired &&
- _parsedQuery &&
- !_parsedQuery->wantMore() &&
- !isMultiKey() &&
- queryBoundsExactOrderSuffix() ) {
- verify( _direction == 0 );
- // Limit the results for each compound interval. SERVER-5063
- return _parsedQuery->getSkip() + _parsedQuery->getNumToReturn();
- }
- return 0;
- }
-
- /**
- * Detects $exists:false predicates in a matcher. All $exists:false predicates will be
- * detected. Some $exists:true predicates may be incorrectly reported as $exists:false due to
- * the approximate nature of the implementation.
- */
- class ExistsFalseDetector : public MatcherVisitor {
- public:
- ExistsFalseDetector( const Matcher& originalMatcher );
- bool hasFoundExistsFalse() const { return _foundExistsFalse; }
- void visitMatcher( const Matcher& matcher ) { _currentMatcher = &matcher; }
- void visitElementMatcher( const ElementMatcher& elementMatcher );
- private:
- const Matcher* _originalMatcher;
- const Matcher* _currentMatcher;
- bool _foundExistsFalse;
- };
-
- ExistsFalseDetector::ExistsFalseDetector( const Matcher& originalMatcher ) :
- _originalMatcher( &originalMatcher ),
- _currentMatcher( 0 ),
- _foundExistsFalse() {
- }
-
- /** Matches $exists:false and $not:{$exists:true} exactly. */
- static bool isExistsFalsePredicate( const ElementMatcher& elementMatcher ) {
- bool hasTrueValue = elementMatcher._toMatch.trueValue();
- bool hasNotModifier = elementMatcher._isNot;
- return hasNotModifier ? hasTrueValue : !hasTrueValue;
- }
-
- void ExistsFalseDetector::visitElementMatcher( const ElementMatcher& elementMatcher ) {
- if ( elementMatcher._compareOp != BSONObj::opEXISTS ) {
- // Only consider $exists predicates.
- return;
- }
- if ( _currentMatcher != _originalMatcher ) {
- // Treat all $exists predicates nested below the original matcher as $exists:false.
- // This approximation is used because a nesting operator may change the matching
- // semantics of $exists:true.
- _foundExistsFalse = true;
- return;
- }
- if ( isExistsFalsePredicate( elementMatcher ) ) {
- // Top level $exists operators are matched exactly.
- _foundExistsFalse = true;
- }
- }
-
- bool QueryPlan::hasPossibleExistsFalsePredicate() const {
- ExistsFalseDetector detector( matcher()->docMatcher() );
- matcher()->docMatcher().visit( detector );
- return detector.hasFoundExistsFalse();
- }
-
- bool QueryPlan::queryBoundsExactOrderSuffix() const {
- if ( !indexed() ||
- !_frs.matchPossible() ||
- !_frs.mustBeExactMatchRepresentation() ) {
- return false;
- }
- BSONObj idxKey = indexKey();
- BSONObjIterator index( idxKey );
- BSONObjIterator order( _order );
- int coveredNonUniversalRanges = 0;
- while( index.more() ) {
- const FieldRange& indexFieldRange = _frs.range( (*index).fieldName() );
- if ( !indexFieldRange.isPointIntervalSet() ) {
- if ( !indexFieldRange.universal() ) {
- // The last indexed range may be a non point set containing a single interval.
- // SERVER-5777
- if ( indexFieldRange.intervals().size() > 1 ) {
- return false;
- }
- ++coveredNonUniversalRanges;
- }
- break;
- }
- ++coveredNonUniversalRanges;
- if ( order.more() && str::equals( (*index).fieldName(), (*order).fieldName() ) ) {
- ++order;
- }
- ++index;
- }
- if ( coveredNonUniversalRanges != _frs.numNonUniversalRanges() ) {
- return false;
- }
- while( index.more() && order.more() ) {
- if ( !str::equals( (*index).fieldName(), (*order).fieldName() ) ) {
- return false;
- }
- if ( ( elementDirection( *index ) < 0 ) != ( elementDirection( *order ) < 0 ) ) {
- return false;
- }
- ++order;
- ++index;
- }
- return !order.more();
- }
-
- string QueryPlan::toString() const {
- return BSON(
- "index" << indexKey() <<
- "frv" << ( _frv ? _frv->toString() : "" ) <<
- "order" << _order
- ).jsonString();
- }
-
- shared_ptr<CoveredIndexMatcher> QueryPlan::matcher() const {
- if ( !_matcher ) {
- _matcher.reset( new CoveredIndexMatcher( originalQuery(), indexKey() ) );
- }
- return _matcher;
- }
-
- bool QueryPlan::isMultiKey() const {
- if ( _idxNo < 0 )
- return false;
- return _d->isMultikey( _idxNo );
- }
-
- std::ostream &operator<< ( std::ostream &out, const QueryPlan::Utility &utility ) {
- out << "QueryPlan::";
- switch( utility ) {
- case QueryPlan::Impossible: return out << "Impossible";
- case QueryPlan::Optimal: return out << "Optimal";
- case QueryPlan::Helpful: return out << "Helpful";
- case QueryPlan::Unhelpful: return out << "Unhelpful";
- case QueryPlan::Disallowed: return out << "Disallowed";
- default:
- return out << "UNKNOWN(" << utility << ")";
- }
- }
-
- CachedMatchCounter::CachedMatchCounter( long long& aggregateNscanned,
- int cumulativeCount ) :
- _aggregateNscanned( aggregateNscanned ),
- _nscanned(),
- _cumulativeCount( cumulativeCount ),
- _count(),
- _checkDups(),
- _match( Unknown ),
- _counted() {
- }
-
- void CachedMatchCounter::resetMatch() {
- _match = Unknown;
- _counted = false;
- }
-
- bool CachedMatchCounter::setMatch( bool match ) {
- MatchState oldMatch = _match;
- _match = match ? True : False;
- return _match == True && oldMatch != True;
- }
-
- void CachedMatchCounter::incMatch( const DiskLoc& loc ) {
- if ( !_counted && _match == True && !getsetdup( loc ) ) {
- ++_cumulativeCount;
- ++_count;
- _counted = true;
- }
- }
-
- bool CachedMatchCounter::wouldIncMatch( const DiskLoc& loc ) const {
- return !_counted && _match == True && !getdup( loc );
- }
-
- bool CachedMatchCounter::enoughCumulativeMatchesToChooseAPlan() const {
- // This is equivalent to the default condition for switching from
- // a query to a getMore, which was the historical default match count for
- // choosing a plan.
- return _cumulativeCount >= 101;
- }
-
- bool CachedMatchCounter::enoughMatchesToRecordPlan() const {
- // Recording after 50 matches is a historical default (101 default limit / 2).
- return _count > 50;
- }
-
- void CachedMatchCounter::updateNscanned( long long nscanned ) {
- _aggregateNscanned += ( nscanned - _nscanned );
- _nscanned = nscanned;
- }
-
- bool CachedMatchCounter::getsetdup( const DiskLoc& loc ) {
- if ( !_checkDups ) {
- return false;
- }
- pair<set<DiskLoc>::iterator, bool> p = _dups.insert( loc );
- return !p.second;
- }
-
- bool CachedMatchCounter::getdup( const DiskLoc& loc ) const {
- if ( !_checkDups ) {
- return false;
- }
- return _dups.find( loc ) != _dups.end();
- }
-
- QueryPlanRunner::QueryPlanRunner( long long& aggregateNscanned,
- const QueryPlanSelectionPolicy& selectionPolicy,
- const bool& requireOrder,
- bool alwaysCountMatches,
- int cumulativeCount ) :
- _complete(),
- _stopRequested(),
- _queryPlan(),
- _error(),
- _matchCounter( aggregateNscanned, cumulativeCount ),
- _countingMatches(),
- _mustAdvance(),
- _capped(),
- _selectionPolicy( selectionPolicy ),
- _requireOrder( requireOrder ),
- _alwaysCountMatches( alwaysCountMatches ) {
- }
-
- void QueryPlanRunner::next() {
- checkCursorOrdering();
-
- mayAdvance();
-
- if ( countMatches() && _matchCounter.enoughCumulativeMatchesToChooseAPlan() ) {
- setStop();
- if ( _explainPlanInfo ) _explainPlanInfo->notePicked();
- return;
- }
- if ( !_c || !_c->ok() ) {
- if ( _explainPlanInfo && _c ) _explainPlanInfo->noteDone( *_c );
- setComplete();
- return;
- }
-
- _mustAdvance = true;
- }
-
- long long QueryPlanRunner::nscanned() const {
- return _c ? _c->nscanned() : _matchCounter.nscanned();
- }
-
- void QueryPlanRunner::prepareToYield() {
- if ( _c && !_cc ) {
- _cc.reset( new ClientCursor( QueryOption_NoCursorTimeout, _c, queryPlan().ns() ) );
- // Set 'doing deletes' as deletes may occur; if there are no deletes this has no
- // effect.
- _cc->setDoingDeletes( true );
- }
- if ( _cc ) {
- recordCursorLocation();
- _cc->prepareToYield( _yieldData );
- }
- }
-
- void QueryPlanRunner::recoverFromYield() {
- if ( _cc && !ClientCursor::recoverFromYield( _yieldData ) ) {
- // !!! The collection may be gone, and any namespace or index specific memory may
- // have become invalid.
- _c.reset();
- _cc.reset();
-
- if ( _capped ) {
- msgassertedNoTrace( 13338,
- str::stream() << "capped cursor overrun: "
- << queryPlan().ns() );
- }
- msgassertedNoTrace( 15892,
- str::stream() <<
- "QueryPlanRunner::recoverFromYield() failed to recover" );
- }
- else {
- checkCursorAdvanced();
- }
- }
-
- void QueryPlanRunner::prepareToTouchEarlierIterate() {
- recordCursorLocation();
- if ( _c ) {
- _c->prepareToTouchEarlierIterate();
- }
- }
-
- void QueryPlanRunner::recoverFromTouchingEarlierIterate() {
- if ( _c ) {
- _c->recoverFromTouchingEarlierIterate();
- }
- checkCursorAdvanced();
- }
-
- bool QueryPlanRunner::currentMatches( MatchDetails* details ) {
- if ( !_c || !_c->ok() ) {
- _matchCounter.setMatch( false );
- return false;
- }
-
- MatchDetails myDetails;
- if ( !details && _explainPlanInfo ) {
- details = &myDetails;
- }
-
- bool match = queryPlan().matcher()->matchesCurrent( _c.get(), details );
- // Cache the match, so we can count it in mayAdvance().
- bool newMatch = _matchCounter.setMatch( match );
-
- if ( _explainPlanInfo ) {
- // Note iterate results as if this is the only query plan running. But do not account
- // for query parameters that may be appled to the whole result set (results from
- // interleaved plans), for example the 'skip' parameter.
- bool countableMatch = newMatch && _matchCounter.wouldIncMatch( _c->currLoc() );
- bool matchWouldBeLoadedForReturn = countableMatch && hasDocumentLoadingQueryPlan();
- _explainPlanInfo->noteIterate( countableMatch,
- details->hasLoadedRecord() ||
- matchWouldBeLoadedForReturn,
- *_c );
- }
-
- return match;
- }
-
- bool QueryPlanRunner::mayRecordPlan() const {
- return complete() && ( !stopRequested() || _matchCounter.enoughMatchesToRecordPlan() );
- }
-
- QueryPlanRunner* QueryPlanRunner::createChild() const {
- return new QueryPlanRunner( _matchCounter.aggregateNscanned(),
- _selectionPolicy,
- _requireOrder,
- _alwaysCountMatches,
- _matchCounter.cumulativeCount() );
- }
-
- void QueryPlanRunner::setQueryPlan( const QueryPlan* queryPlan ) {
- _queryPlan = queryPlan;
- verify( _queryPlan != NULL );
- }
-
- void QueryPlanRunner::init() {
- checkCursorOrdering();
- if ( !_selectionPolicy.permitPlan( queryPlan() ) ) {
- throw MsgAssertionException( 9011,
- str::stream()
- << "Plan not permitted by query plan selection policy '"
- << _selectionPolicy.name()
- << "'" );
- }
-
- _c = queryPlan().newCursor();
- // The basic and btree cursors used by this implementation do not supply their own
- // matchers, and a matcher from a query plan will be used instead.
- verify( !_c->matcher() );
- // Such cursors all support deduplication.
- verify( _c->autoDedup() );
-
- // The query plan must have a matcher. The matcher's constructor performs some aspects
- // of query validation that should occur as part of this class's init() if not handled
- // already.
- fassert( 16249, queryPlan().matcher() );
-
- // All candidate cursors must support yields for QueryOptimizerCursorImpl's
- // prepareToYield() and prepareToTouchEarlierIterate() to work.
- verify( _c->supportYields() );
- _capped = _c->capped();
-
- // TODO This violates the current Cursor interface abstraction, but for now it's simpler to keep our own set of
- // dups rather than avoid poisoning the cursor's dup set with unreturned documents. Deduping documents
- // matched in this QueryOptimizerCursorOp will run against the takeover cursor.
- _matchCounter.setCheckDups( countMatches() && _c->isMultiKey() );
- // TODO ok if cursor becomes multikey later?
-
- _matchCounter.updateNscanned( _c->nscanned() );
- }
-
- void QueryPlanRunner::setException( const DBException &e ) {
- _error = true;
- _exception = e.getInfo();
- }
-
- shared_ptr<ExplainPlanInfo> QueryPlanRunner::generateExplainInfo() {
- if ( !_c ) {
- return shared_ptr<ExplainPlanInfo>( new ExplainPlanInfo() );
- }
- _explainPlanInfo.reset( new ExplainPlanInfo() );
- _explainPlanInfo->notePlan( *_c, queryPlan().scanAndOrderRequired(),
- queryPlan().keyFieldsOnly() );
- return _explainPlanInfo;
- }
-
- void QueryPlanRunner::mayAdvance() {
- if ( !_c ) {
- return;
- }
- if ( countingMatches() ) {
- // Check match if not yet known.
- if ( !_matchCounter.knowMatch() ) {
- currentMatches( 0 );
- }
- _matchCounter.incMatch( currLoc() );
- }
- if ( _mustAdvance ) {
- _c->advance();
- handleCursorAdvanced();
- }
- _matchCounter.updateNscanned( _c->nscanned() );
- }
-
- bool QueryPlanRunner::countingMatches() {
- if ( _countingMatches ) {
- return true;
- }
- if ( countMatches() ) {
- // Only count matches after the first call to next(), which occurs before the first
- // result is returned.
- _countingMatches = true;
- }
- return false;
- }
-
- bool QueryPlanRunner::countMatches() const {
- return _alwaysCountMatches || !queryPlan().scanAndOrderRequired();
- }
-
- bool QueryPlanRunner::hasDocumentLoadingQueryPlan() const {
- if ( queryPlan().parsedQuery() && queryPlan().parsedQuery()->returnKey() ) {
- // Index keys will be returned using $returnKey.
- return false;
- }
- if ( queryPlan().scanAndOrderRequired() ) {
- // The in memory sort implementation operates on full documents.
- return true;
- }
- if ( keyFieldsOnly() ) {
- // A covered index projection will be used.
- return false;
- }
- // Documents will be loaded for a standard query.
- return true;
- }
-
- void QueryPlanRunner::recordCursorLocation() {
- _posBeforeYield = currLoc();
- }
-
- void QueryPlanRunner::checkCursorAdvanced() {
- // This check will not correctly determine if we are looking at a different document in
- // all cases, but it is adequate for updating the query plan's match count (just used to pick
- // plans, not returned to the client) and adjust iteration via _mustAdvance.
- if ( _posBeforeYield != currLoc() ) {
- // If the yield advanced our position, the next next() will be a no op.
- handleCursorAdvanced();
- }
- }
-
- void QueryPlanRunner::handleCursorAdvanced() {
- _mustAdvance = false;
- _matchCounter.resetMatch();
- }
-
- void QueryPlanRunner::checkCursorOrdering() {
- if ( _requireOrder && queryPlan().scanAndOrderRequired() ) {
- throw MsgAssertionException( OutOfOrderDocumentsAssertionCode, "order spec cannot be satisfied with index" );
- }
- }
-
- QueryPlanGenerator::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 ) :
- _qps( qps ),
- _originalFrsp( originalFrsp ),
- _parsedQuery( parsedQuery ),
- _hint( hint.getOwned() ),
- _recordedPlanPolicy( recordedPlanPolicy ),
- _min( min.getOwned() ),
- _max( max.getOwned() ),
- _allowSpecial( allowSpecial ) {
- }
-
- void QueryPlanGenerator::addInitialPlans() {
- const char *ns = _qps.frsp().ns();
- NamespaceDetails *d = nsdetails( ns );
-
- if ( addShortCircuitPlan( d ) ) {
- return;
- }
-
- addStandardPlans( d );
- warnOnCappedIdTableScan();
- }
-
- void QueryPlanGenerator::addFallbackPlans() {
- const char *ns = _qps.frsp().ns();
- NamespaceDetails *d = nsdetails( ns );
- verify( d );
-
- vector<shared_ptr<QueryPlan> > plans;
- shared_ptr<QueryPlan> optimalPlan;
- shared_ptr<QueryPlan> specialPlan;
- for( int i = 0; i < d->nIndexes; ++i ) {
-
- if ( !QueryUtilIndexed::indexUseful( _qps.frsp(), d, i, _qps.order() ) ) {
- continue;
- }
-
- shared_ptr<QueryPlan> p = newPlan( d, i );
- switch( p->utility() ) {
- case QueryPlan::Impossible:
- _qps.setSinglePlan( p );
- return;
- case QueryPlan::Optimal:
- if ( !optimalPlan ) {
- optimalPlan = p;
- }
- break;
- case QueryPlan::Helpful:
- if ( p->special().empty() ) {
- // Not a 'special' plan.
- plans.push_back( p );
- }
- else if ( _allowSpecial ) {
- specialPlan = p;
- }
- break;
- default:
- break;
- }
- }
-
- if ( optimalPlan ) {
- _qps.setSinglePlan( optimalPlan );
- // Record an optimal plan in the query cache immediately, with a small nscanned value
- // that will be ignored.
- optimalPlan->registerSelf
- ( 0, CandidatePlanCharacter( !optimalPlan->scanAndOrderRequired(),
- optimalPlan->scanAndOrderRequired() ) );
- return;
- }
-
- // Only add a special plan if no standard btree plans have been added. SERVER-4531
- if ( plans.empty() && specialPlan ) {
- _qps.setSinglePlan( specialPlan );
- return;
- }
-
- for( vector<shared_ptr<QueryPlan> >::const_iterator i = plans.begin(); i != plans.end();
- ++i ) {
- _qps.addCandidatePlan( *i );
- }
-
- _qps.addCandidatePlan( newPlan( d, -1 ) );
- }
-
- bool QueryPlanGenerator::addShortCircuitPlan( NamespaceDetails *d ) {
- return
- // The collection is missing.
- setUnindexedPlanIf( !d, d ) ||
- // No match is possible.
- setUnindexedPlanIf( !_qps.frsp().matchPossible(), d ) ||
- // The hint, min, or max parameters are specified.
- addHintPlan( d ) ||
- // A special index operation is requested.
- addSpecialPlan( d ) ||
- // No indexable ranges or ordering are specified.
- setUnindexedPlanIf( _qps.frsp().noNonUniversalRanges() && _qps.order().isEmpty(), d ) ||
- // $natural sort is requested.
- setUnindexedPlanIf( !_qps.order().isEmpty() &&
- str::equals( _qps.order().firstElementFieldName(), "$natural" ), d );
- }
-
- bool QueryPlanGenerator::addHintPlan( NamespaceDetails *d ) {
- BSONElement hint = _hint.firstElement();
- if ( !hint.eoo() ) {
- IndexDetails *id = parseHint( hint, d );
- if ( id ) {
- setHintedPlanForIndex( *id );
- }
- else {
- uassert( 10366, "natural order cannot be specified with $min/$max",
- _min.isEmpty() && _max.isEmpty() );
- setSingleUnindexedPlan( d );
- }
- return true;
- }
-
- if ( !_min.isEmpty() || !_max.isEmpty() ) {
- string errmsg;
- BSONObj keyPattern;
- IndexDetails *idx = indexDetailsForRange( _qps.frsp().ns(), errmsg, _min, _max,
- keyPattern );
- uassert( 10367 , errmsg, idx );
- validateAndSetHintedPlan( newPlan( d, d->idxNo( *idx ), _min, _max ) );
- return true;
- }
-
- return false;
- }
-
- bool QueryPlanGenerator::addSpecialPlan( NamespaceDetails *d ) {
- DEBUGQO( "\t special : " << _qps.frsp().getSpecial().toString() );
- SpecialIndices special = _qps.frsp().getSpecial();
- if (!special.empty()) {
- // Try to handle the special part of the query with an index
- NamespaceDetails::IndexIterator i = d->ii();
- while( i.more() ) {
- int j = i.pos();
- IndexDetails& ii = i.next();
- const IndexSpec& spec = ii.getSpec();
- if (special.has(spec.getTypeName()) &&
- spec.suitability( _qps.frsp().frsForIndex(d, j), _qps.order() ) != USELESS ) {
- uassert( 16330, "'special' query operator not allowed", _allowSpecial );
- _qps.setSinglePlan( newPlan( d, j, BSONObj(), BSONObj(), spec.getTypeName()));
- return true;
- }
- }
- // If all possible special indices require an index and we don't have one,
- // error.
- if (special.allRequireIndex()) {
- uassert(13038, "can't find any special indices: " + special.toString()
- + " for: " + _qps.originalQuery().toString(), false );
- }
- // Otherwise, we can get the same functionality from the matcher.
- }
- return false;
- }
-
- void QueryPlanGenerator::addStandardPlans( NamespaceDetails *d ) {
- if ( !addCachedPlan( d ) ) {
- addFallbackPlans();
- }
- }
-
- bool QueryPlanGenerator::addCachedPlan( NamespaceDetails *d ) {
- if ( _recordedPlanPolicy == Ignore ) {
- return false;
- }
-
- CachedQueryPlan best = QueryUtilIndexed::bestIndexForPatterns( _qps.frsp(), _qps.order() );
- BSONObj bestIndex = best.indexKey();
- if ( bestIndex.isEmpty() ) {
- return false;
- }
-
- shared_ptr<QueryPlan> p;
- if ( str::equals( bestIndex.firstElementFieldName(), "$natural" ) ) {
- p = newPlan( d, -1 );
- }
-
- NamespaceDetails::IndexIterator i = d->ii();
- while( i.more() ) {
- int j = i.pos();
- IndexDetails& ii = i.next();
- if( ii.keyPattern().woCompare(bestIndex) == 0 ) {
- p = newPlan( d, j );
- }
- }
-
- massert( 10368 , "Unable to locate previously recorded index", p );
-
- if ( p->utility() == QueryPlan::Unhelpful ||
- p->utility() == QueryPlan::Disallowed ) {
- return false;
- }
-
- if ( _recordedPlanPolicy == UseIfInOrder && p->scanAndOrderRequired() ) {
- return false;
- }
-
- if ( !_allowSpecial && !p->special().empty() ) {
- return false;
- }
-
- _qps.setCachedPlan( p, best );
- return true;
- }
-
- shared_ptr<QueryPlan> QueryPlanGenerator::newPlan( NamespaceDetails *d,
- int idxNo,
- const BSONObj &min,
- const BSONObj &max,
- const string &special ) const {
- shared_ptr<QueryPlan> ret( QueryPlan::make( d, idxNo, _qps.frsp(), _originalFrsp.get(),
- _qps.originalQuery(), _qps.order(), _parsedQuery,
- min, max, special ) );
- return ret;
- }
-
- bool QueryPlanGenerator::setUnindexedPlanIf( bool set, NamespaceDetails *d ) {
- if ( set ) {
- setSingleUnindexedPlan( d );
- }
- return set;
- }
-
- void QueryPlanGenerator::setSingleUnindexedPlan( NamespaceDetails *d ) {
- _qps.setSinglePlan( newPlan( d, -1 ) );
- }
-
- void QueryPlanGenerator::setHintedPlanForIndex( IndexDetails& id ) {
- if ( !_min.isEmpty() || !_max.isEmpty() ) {
- string errmsg;
- BSONObj keyPattern = id.keyPattern();
- // This reformats _min and _max to be used for index lookup.
- massert( 10365 , errmsg, indexDetailsForRange( _qps.frsp().ns(), errmsg, _min, _max,
- keyPattern ) );
- }
- NamespaceDetails *d = nsdetails( _qps.frsp().ns() );
- validateAndSetHintedPlan( newPlan( d, d->idxNo( id ), _min, _max ) );
- }
-
- void QueryPlanGenerator::validateAndSetHintedPlan( const shared_ptr<QueryPlan>& plan ) {
- uassert( 16331, "'special' plan hint not allowed",
- _allowSpecial || plan->special().empty() );
- _qps.setSinglePlan( plan );
- }
-
- void QueryPlanGenerator::warnOnCappedIdTableScan() const {
- // if we are doing a table scan on _id
- // and it's a capped collection
- // we warn as it's a common user error
- // .system. and local collections are exempt
- const char *ns = _qps.frsp().ns();
- NamespaceDetails *d = nsdetails( ns );
- if ( d &&
- d->isCapped() &&
- _qps.nPlans() == 1 &&
- ( _qps.firstPlan()->utility() != QueryPlan::Impossible ) &&
- !_qps.firstPlan()->indexed() &&
- !_qps.firstPlan()->multikeyFrs().range( "_id" ).universal() ) {
- if (!str::contains( ns , ".system." ) && !str::startsWith( ns , "local." )) {
- warning() << "unindexed _id query on capped collection, "
- << "performance will be poor collection: " << ns << endl;
- }
- }
- }
-
- QueryPlanSet* 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 ) {
- auto_ptr<QueryPlanSet> ret( new QueryPlanSet( ns, frsp, originalFrsp, originalQuery, order,
- parsedQuery, hint, recordedPlanPolicy, min,
- max, allowSpecial ) );
- ret->init();
- return ret.release();
- }
-
-
- QueryPlanSet::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 ) :
- _generator( *this, originalFrsp, parsedQuery, hint, recordedPlanPolicy, min, max,
- allowSpecial ),
- _originalQuery( originalQuery ),
- _frsp( frsp ),
- _mayRecordPlan(),
- _usingCachedPlan(),
- _order( order.getOwned() ),
- _oldNScanned( 0 ),
- _yieldSometimesTracker( 256, 20 ),
- _allowSpecial( allowSpecial ) {
- }
-
- bool QueryPlanSet::hasMultiKey() const {
- for( PlanVector::const_iterator i = _plans.begin(); i != _plans.end(); ++i )
- if ( (*i)->isMultiKey() )
- return true;
- return false;
- }
-
- void QueryPlanSet::init() {
- DEBUGQO( "QueryPlanSet::init " << ns << "\t" << _originalQuery );
- _plans.clear();
- _usingCachedPlan = false;
-
- _generator.addInitialPlans();
- }
-
- void QueryPlanSet::setSinglePlan( const QueryPlanPtr &plan ) {
- if ( nPlans() == 0 ) {
- pushPlan( plan );
- }
- }
-
- void QueryPlanSet::setCachedPlan( const QueryPlanPtr &plan,
- const CachedQueryPlan &cachedPlan ) {
- verify( nPlans() == 0 );
- _usingCachedPlan = true;
- _oldNScanned = cachedPlan.nScanned();
- _cachedPlanCharacter = cachedPlan.planCharacter();
- pushPlan( plan );
- }
-
- void QueryPlanSet::addCandidatePlan( const QueryPlanPtr &plan ) {
- // If _plans is nonempty, the new plan may be supplementing a recorded plan at the first
- // position of _plans. It must not duplicate the first plan.
- if ( nPlans() > 0 && plan->indexKey() == firstPlan()->indexKey() ) {
- return;
- }
- pushPlan( plan );
- _mayRecordPlan = true;
- }
-
- void QueryPlanSet::addFallbackPlans() {
- _generator.addFallbackPlans();
- _mayRecordPlan = true;
- }
-
- void QueryPlanSet::pushPlan( const QueryPlanSet::QueryPlanPtr& plan ) {
- verify( _allowSpecial || plan->special().empty() );
- _plans.push_back( plan );
- }
-
- bool QueryPlanSet::hasPossiblyExcludedPlans() const {
- return
- _usingCachedPlan &&
- ( nPlans() == 1 ) &&
- ( firstPlan()->utility() != QueryPlan::Optimal );
- }
-
- QueryPlanSet::QueryPlanPtr QueryPlanSet::getBestGuess() const {
- verify( _plans.size() );
- if ( _plans[ 0 ]->scanAndOrderRequired() ) {
- for ( unsigned i=1; i<_plans.size(); i++ ) {
- if ( ! _plans[i]->scanAndOrderRequired() )
- return _plans[i];
- }
-
- warning() << "best guess query plan requested, but scan and order are required for all plans "
- << " query: " << _originalQuery
- << " order: " << _order
- << " choices: ";
-
- for ( unsigned i=0; i<_plans.size(); i++ )
- warning() << _plans[i]->indexKey() << " ";
- warning() << endl;
-
- return QueryPlanPtr();
- }
- return _plans[0];
- }
-
- bool QueryPlanSet::haveInOrderPlan() const {
- for( PlanVector::const_iterator i = _plans.begin(); i != _plans.end(); ++i ) {
- if ( !(*i)->scanAndOrderRequired() ) {
- return true;
- }
- }
- return false;
- }
-
- bool QueryPlanSet::possibleInOrderPlan() const {
- if ( haveInOrderPlan() ) {
- return true;
- }
- return _cachedPlanCharacter.mayRunInOrderPlan();
- }
-
- bool QueryPlanSet::possibleOutOfOrderPlan() const {
- for( PlanVector::const_iterator i = _plans.begin(); i != _plans.end(); ++i ) {
- if ( (*i)->scanAndOrderRequired() ) {
- return true;
- }
- }
- return _cachedPlanCharacter.mayRunOutOfOrderPlan();
- }
-
- CandidatePlanCharacter QueryPlanSet::characterizeCandidatePlans() const {
- return CandidatePlanCharacter( possibleInOrderPlan(), possibleOutOfOrderPlan() );
- }
-
- bool QueryPlanSet::prepareToRetryQuery() {
- if ( !hasPossiblyExcludedPlans() || _plans.size() > 1 ) {
- return false;
- }
-
- // A cached plan was used, so clear the plan for this query pattern so the query may be
- // retried without a cached plan.
- QueryUtilIndexed::clearIndexesForPatterns( *_frsp, _order );
- init();
- return true;
- }
-
- string QueryPlanSet::toString() const {
- BSONArrayBuilder bab;
- for( PlanVector::const_iterator i = _plans.begin(); i != _plans.end(); ++i ) {
- bab << (*i)->toString();
- }
- return bab.arr().jsonString();
- }
-
- MultiPlanScanner *MultiPlanScanner::make( const StringData& ns,
- const BSONObj &query,
- const BSONObj &order,
- const shared_ptr<const ParsedQuery> &parsedQuery,
- const BSONObj &hint,
- QueryPlanGenerator::RecordedPlanPolicy
- recordedPlanPolicy,
- const BSONObj &min,
- const BSONObj &max ) {
- auto_ptr<MultiPlanScanner> ret( new MultiPlanScanner( ns, query, parsedQuery, hint,
- recordedPlanPolicy ) );
- ret->init( order, min, max );
- return ret.release();
- }
-
- shared_ptr<QueryPlanRunner> MultiPlanScanner::iterateRunnerQueue
- ( QueryPlanRunner& originalRunner, bool retried ) {
-
- if ( _runnerQueue ) {
- return _runnerQueue->next();
- }
-
- _runnerQueue.reset( new QueryPlanRunnerQueue( *_currentQps, originalRunner ) );
- shared_ptr<ExplainClauseInfo> explainClause;
- if ( _explainQueryInfo ) {
- explainClause = _runnerQueue->generateExplainInfo();
- }
-
- shared_ptr<QueryPlanRunner> runner = _runnerQueue->next();
- if ( runner->error() &&
- _currentQps->prepareToRetryQuery() ) {
-
- // Avoid an infinite loop here - this should never occur.
- verify( !retried );
- _runnerQueue.reset();
- return iterateRunnerQueue( originalRunner, true );
- }
-
- if ( _explainQueryInfo ) {
- _explainQueryInfo->addClauseInfo( explainClause );
- }
- return runner;
- }
-
- void MultiPlanScanner::updateCurrentQps( QueryPlanSet *qps ) {
- _currentQps.reset( qps );
- _runnerQueue.reset();
- }
-
- QueryPlanRunnerQueue::QueryPlanRunnerQueue( QueryPlanSet& plans,
- const QueryPlanRunner& prototypeRunner ) :
- _prototypeRunner( prototypeRunner ),
- _plans( plans ),
- _done() {
- }
-
- void QueryPlanRunnerQueue::prepareToYield() {
- for( vector<shared_ptr<QueryPlanRunner> >::const_iterator i = _runners.begin();
- i != _runners.end(); ++i ) {
- prepareToYieldRunner( **i );
- }
- }
-
- void QueryPlanRunnerQueue::recoverFromYield() {
- for( vector<shared_ptr<QueryPlanRunner> >::const_iterator i = _runners.begin();
- i != _runners.end(); ++i ) {
- recoverFromYieldRunner( **i );
- }
- }
-
- shared_ptr<QueryPlanRunner> QueryPlanRunnerQueue::init() {
- massert( 10369 , "no plans", _plans.plans().size() > 0 );
-
- if ( _plans.plans().size() > 1 )
- LOG(1) << " running multiple plans" << endl;
- for( QueryPlanSet::PlanVector::const_iterator i = _plans.plans().begin();
- i != _plans.plans().end(); ++i ) {
- shared_ptr<QueryPlanRunner> runner( _prototypeRunner.createChild() );
- runner->setQueryPlan( i->get() );
- _runners.push_back( runner );
- }
-
- // Initialize runners.
- for( vector<shared_ptr<QueryPlanRunner> >::iterator i = _runners.begin();
- i != _runners.end(); ++i ) {
- initRunner( **i );
- if ( _explainClauseInfo ) {
- _explainClauseInfo->addPlanInfo( (*i)->generateExplainInfo() );
- }
- }
-
- // See if an op has completed.
- for( vector<shared_ptr<QueryPlanRunner> >::iterator i = _runners.begin();
- i != _runners.end(); ++i ) {
- if ( (*i)->complete() ) {
- return *i;
- }
- }
-
- // Put runnable ops in the priority queue.
- for( vector<shared_ptr<QueryPlanRunner> >::iterator i = _runners.begin();
- i != _runners.end(); ++i ) {
- if ( !(*i)->error() ) {
- _queue.push( *i );
- }
- }
-
- if ( _queue.empty() ) {
- return _runners.front();
- }
-
- return shared_ptr<QueryPlanRunner>();
- }
-
- shared_ptr<QueryPlanRunner> QueryPlanRunnerQueue::next() {
- verify( !done() );
-
- if ( _runners.empty() ) {
- shared_ptr<QueryPlanRunner> initialRet = init();
- if ( initialRet ) {
- _done = true;
- return initialRet;
- }
- }
-
- shared_ptr<QueryPlanRunner> ret;
- do {
- ret = _next();
- } while( ret->error() && !_queue.empty() );
-
- if ( _queue.empty() ) {
- _done = true;
- }
-
- return ret;
- }
-
- shared_ptr<QueryPlanRunner> QueryPlanRunnerQueue::_next() {
- verify( !_queue.empty() );
- RunnerHolder holder = _queue.pop();
- QueryPlanRunner& runner = *holder._runner;
- nextRunner( runner );
- if ( runner.complete() ) {
- if ( _plans.mayRecordPlan() && runner.mayRecordPlan() ) {
- runner.queryPlan().registerSelf( runner.nscanned(),
- _plans.characterizeCandidatePlans() );
- }
- _done = true;
- return holder._runner;
- }
- if ( runner.error() ) {
- return holder._runner;
- }
- if ( _plans.hasPossiblyExcludedPlans() &&
- runner.nscanned() > _plans.oldNScanned() * 10 ) {
- verify( _plans.nPlans() == 1 && _plans.firstPlan()->special().empty() );
- holder._offset = -runner.nscanned();
- _plans.addFallbackPlans();
- QueryPlanSet::PlanVector::const_iterator i = _plans.plans().begin();
- ++i;
- for( ; i != _plans.plans().end(); ++i ) {
- shared_ptr<QueryPlanRunner> runner( _prototypeRunner.createChild() );
- runner->setQueryPlan( i->get() );
- _runners.push_back( runner );
- initRunner( *runner );
- if ( runner->complete() )
- return runner;
- _queue.push( runner );
- }
- _plans.setUsingCachedPlan( false );
- }
- _queue.push( holder );
- return holder._runner;
- }
-
-#define GUARD_RUNNER_EXCEPTION( runner, expression ) \
- try { \
- expression; \
- } \
- catch ( DBException& e ) { \
- runner.setException( e.getInfo() ); \
- } \
- catch ( const std::exception &e ) { \
- runner.setException( ExceptionInfo( e.what(), 0 ) ); \
- } \
- catch ( PageFaultException& pfe ) { \
- throw pfe; \
- } \
- catch ( ... ) { \
- runner.setException( ExceptionInfo( "Caught unknown exception", 0 ) ); \
- }
-
-
- void QueryPlanRunnerQueue::initRunner( QueryPlanRunner &runner ) {
- GUARD_RUNNER_EXCEPTION( runner, runner.init() );
- }
-
- void QueryPlanRunnerQueue::nextRunner( QueryPlanRunner& runner ) {
- GUARD_RUNNER_EXCEPTION( runner, if ( !runner.error() ) { runner.next(); } );
- }
-
- void QueryPlanRunnerQueue::prepareToYieldRunner( QueryPlanRunner& runner ) {
- GUARD_RUNNER_EXCEPTION( runner, if ( !runner.error() ) { runner.prepareToYield(); } );
- }
-
- void QueryPlanRunnerQueue::recoverFromYieldRunner( QueryPlanRunner& runner ) {
- GUARD_RUNNER_EXCEPTION( runner, if ( !runner.error() ) { runner.recoverFromYield(); } );
- }
-
- /**
- * NOTE on our $or implementation: In our current qo implementation we don't
- * keep statistics on our data, but we can conceptualize the problem of
- * selecting an index when statistics exist for all index ranges. The
- * d-hitting set problem on k sets and n elements can be reduced to the
- * problem of index selection on k $or clauses and n index ranges (where
- * d is the max number of indexes, and the number of ranges n is unbounded).
- * In light of the fact that d-hitting set is np complete, and we don't even
- * track statistics (so cost calculations are expensive) our first
- * implementation uses the following greedy approach: We take one $or clause
- * at a time and treat each as a separate query for index selection purposes.
- * But if an index range is scanned for a particular $or clause, we eliminate
- * that range from all subsequent clauses. One could imagine an opposite
- * implementation where we select indexes based on the union of index ranges
- * for all $or clauses, but this can have much poorer worst case behavior.
- * (An index range that suits one $or clause may not suit another, and this
- * is worse than the typical case of index range choice staleness because
- * with $or the clauses may likely be logically distinct.) The greedy
- * implementation won't do any worse than all the $or clauses individually,
- * and it can often do better. In the first cut we are intentionally using
- * QueryPattern tracking to record successful plans on $or clauses for use by
- * subsequent $or clauses, even though there may be a significant aggregate
- * $nor component that would not be represented in QueryPattern.
- */
-
- MultiPlanScanner::MultiPlanScanner( const StringData& ns,
- const BSONObj &query,
- const shared_ptr<const ParsedQuery> &parsedQuery,
- const BSONObj &hint,
- QueryPlanGenerator::RecordedPlanPolicy recordedPlanPolicy ) :
- _ns( ns.toString() ),
- _or( !query.getField( "$or" ).eoo() ),
- _query( query.getOwned() ),
- _parsedQuery( parsedQuery ),
- _i(),
- _recordedPlanPolicy( recordedPlanPolicy ),
- _hint( hint.getOwned() ),
- _tableScanned(),
- _doneRunners() {
- }
-
- void MultiPlanScanner::init( const BSONObj &order, const BSONObj &min, const BSONObj &max ) {
- if ( !order.isEmpty() || !min.isEmpty() || !max.isEmpty() ) {
- _or = false;
- }
- if ( _or ) {
- // Only construct an OrRangeGenerator if we may handle $or clauses.
- _org.reset( new OrRangeGenerator( _ns.c_str(), _query ) );
- if ( !_org->getSpecial().empty() ) {
- _or = false;
- }
- else if ( haveUselessOr() ) {
- _or = false;
- }
- }
-
- // if _or == false, don't use or clauses for index selection
- if ( !_or ) {
- ++_i;
- auto_ptr<FieldRangeSetPair> frsp( new FieldRangeSetPair( _ns.c_str(), _query, true ) );
- updateCurrentQps( QueryPlanSet::make( _ns.c_str(), frsp, auto_ptr<FieldRangeSetPair>(),
- _query, order, _parsedQuery, _hint,
- _recordedPlanPolicy,
- min, max, true ) );
- }
- else {
- BSONElement e = _query.getField( "$or" );
- massert( 13268, "invalid $or spec",
- e.type() == Array && e.embeddedObject().nFields() > 0 );
- handleBeginningOfClause();
- }
- }
-
- void MultiPlanScanner::handleEndOfClause( const QueryPlan &clausePlan ) {
- if ( clausePlan.willScanTable() ) {
- _tableScanned = true;
- } else {
- _org->popOrClause( clausePlan.nsd(), clausePlan.idxNo(),
- clausePlan.indexed() ? clausePlan.indexKey() : BSONObj() );
- }
- }
-
- void MultiPlanScanner::handleBeginningOfClause() {
- assertHasMoreClauses();
- ++_i;
- auto_ptr<FieldRangeSetPair> frsp( _org->topFrsp() );
- auto_ptr<FieldRangeSetPair> originalFrsp( _org->topFrspOriginal() );
- updateCurrentQps( QueryPlanSet::make( _ns.c_str(), frsp, originalFrsp, _query,
- BSONObj(), _parsedQuery, _hint, _recordedPlanPolicy,
- BSONObj(), BSONObj(),
- // 'Special' plans are not supported within $or.
- false ) );
- }
-
- bool MultiPlanScanner::mayHandleBeginningOfClause() {
- if ( hasMoreClauses() ) {
- handleBeginningOfClause();
- return true;
- }
- return false;
- }
-
- shared_ptr<QueryPlanRunner> MultiPlanScanner::nextRunner() {
- verify( !doneRunners() );
- shared_ptr<QueryPlanRunner> ret = _or ? nextRunnerOr() : nextRunnerSimple();
- if ( ret->error() || ret->complete() ) {
- _doneRunners = true;
- }
- return ret;
- }
-
- shared_ptr<QueryPlanRunner> MultiPlanScanner::nextRunnerSimple() {
- return iterateRunnerQueue( *_baseRunner );
- }
-
- shared_ptr<QueryPlanRunner> MultiPlanScanner::nextRunnerOr() {
- shared_ptr<QueryPlanRunner> runner;
- do {
- runner = nextRunnerSimple();
- if ( !runner->completeWithoutStop() ) {
- return runner;
- }
- handleEndOfClause( runner->queryPlan() );
- _baseRunner = runner;
- } while( mayHandleBeginningOfClause() );
- return runner;
- }
-
- const QueryPlan *MultiPlanScanner::nextClauseBestGuessPlan( const QueryPlan &currentPlan ) {
- assertHasMoreClauses();
- handleEndOfClause( currentPlan );
- if ( !hasMoreClauses() ) {
- return 0;
- }
- handleBeginningOfClause();
- shared_ptr<QueryPlan> bestGuess = _currentQps->getBestGuess();
- verify( bestGuess );
- return bestGuess.get();
- }
-
- void MultiPlanScanner::prepareToYield() {
- if ( _runnerQueue ) {
- _runnerQueue->prepareToYield();
- }
- }
-
- void MultiPlanScanner::recoverFromYield() {
- if ( _runnerQueue ) {
- _runnerQueue->recoverFromYield();
- }
- }
-
- void MultiPlanScanner::clearRunnerQueue() {
- if ( _runnerQueue ) {
- _runnerQueue.reset();
- }
- }
-
- int MultiPlanScanner::currentNPlans() const {
- return _currentQps->nPlans();
- }
-
- const QueryPlan *MultiPlanScanner::singlePlan() const {
- if ( _or ||
- _currentQps->nPlans() != 1 ||
- _currentQps->hasPossiblyExcludedPlans() ) {
- return 0;
- }
- return _currentQps->firstPlan().get();
- }
-
- bool MultiPlanScanner::haveUselessOr() const {
- NamespaceDetails *nsd = nsdetails( _ns );
- if ( !nsd ) {
- return true;
- }
- BSONElement hintElt = _hint.firstElement();
- if ( !hintElt.eoo() ) {
- IndexDetails *id = parseHint( hintElt, nsd );
- if ( !id ) {
- return true;
- }
- return QueryUtilIndexed::uselessOr( *_org, nsd, nsd->idxNo( *id ) );
- }
- return QueryUtilIndexed::uselessOr( *_org, nsd, -1 );
- }
-
- BSONObj MultiPlanScanner::cachedPlanExplainSummary() const {
- if ( _or || !_currentQps->usingCachedPlan() ) {
- return BSONObj();
- }
- QueryPlanSet::QueryPlanPtr plan = _currentQps->firstPlan();
- shared_ptr<Cursor> cursor = plan->newCursor();
- return BSON( "cursor" << cursor->toString()
- << "indexBounds" << cursor->prettyIndexBounds() );
- }
-
- void MultiPlanScanner::clearIndexesForPatterns() const {
- QueryUtilIndexed::clearIndexesForPatterns( _currentQps->frsp(), _currentQps->order() );
- }
-
- bool MultiPlanScanner::haveInOrderPlan() const {
- return _or ? true : _currentQps->haveInOrderPlan();
- }
-
- bool MultiPlanScanner::possibleInOrderPlan() const {
- return _or ? true : _currentQps->possibleInOrderPlan();
- }
-
- bool MultiPlanScanner::possibleOutOfOrderPlan() const {
- return _or ? false : _currentQps->possibleOutOfOrderPlan();
- }
-
- string MultiPlanScanner::toString() const {
- return BSON(
- "or" << _or <<
- "currentQps" << _currentQps->toString()
- ).jsonString();
- }
-
- MultiCursor::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 ) :
- _mps( mps ),
- _c( c ),
- _matcher( matcher ),
- _queryPlan( &runner.queryPlan() ),
- _nscanned( nscanned ),
- _explainPlanInfo( explainPlanInfo ) {
- _mps->clearRunnerQueue();
- _mps->setRecordedPlanPolicy( QueryPlanGenerator::UseIfInOrder );
- if ( !ok() ) {
- // If the supplied cursor is exhausted, try to advance it.
- advance();
- }
- }
-
- bool MultiCursor::advance() {
- _c->advance();
- advanceExhaustedClauses();
- return ok();
- }
-
- void MultiCursor::recoverFromYield() {
- Cursor::recoverFromYield();
- advanceExhaustedClauses();
- }
-
- void MultiCursor::advanceClause() {
- _nscanned += _c->nscanned();
- if ( _explainPlanInfo ) _explainPlanInfo->noteDone( *_c );
- shared_ptr<FieldRangeVector> oldClauseFrv = _queryPlan->originalFrv();
- _queryPlan = _mps->nextClauseBestGuessPlan( *_queryPlan );
- if ( _queryPlan ) {
- _matcher.reset( _matcher->nextClauseMatcher( oldClauseFrv, _queryPlan->indexKey() ) );
- _c = _queryPlan->newCursor();
- // The basic and btree cursors used by this implementation support deduplication.
- verify( _c->autoDedup() );
- // All sub cursors must support yields.
- verify( _c->supportYields() );
- if ( _explainPlanInfo ) {
- _explainPlanInfo.reset( new ExplainPlanInfo() );
- _explainPlanInfo->notePlan( *_c, _queryPlan->scanAndOrderRequired(),
- _queryPlan->keyFieldsOnly() );
- shared_ptr<ExplainClauseInfo> clauseInfo( new ExplainClauseInfo() );
- clauseInfo->addPlanInfo( _explainPlanInfo );
- _mps->addClauseInfo( clauseInfo );
- }
- }
- }
-
- void MultiCursor::advanceExhaustedClauses() {
- while( !ok() && _mps->hasMoreClauses() ) {
- advanceClause();
- }
- }
-
- void MultiCursor::noteIterate( bool match, bool loadedRecord ) {
- if ( _explainPlanInfo ) _explainPlanInfo->noteIterate( match, loadedRecord, *_c );
- }
-
- bool indexWorks( const BSONObj &idxPattern, const BSONObj &sampleKey, int direction, int firstSignificantField ) {
- BSONObjIterator p( idxPattern );
- BSONObjIterator k( sampleKey );
- int i = 0;
- while( 1 ) {
- BSONElement pe = p.next();
- BSONElement ke = k.next();
- if ( pe.eoo() && ke.eoo() )
- return true;
- if ( pe.eoo() || ke.eoo() )
- return false;
- if ( strcmp( pe.fieldName(), ke.fieldName() ) != 0 )
- return false;
- if ( ( i == firstSignificantField ) && !( ( direction > 0 ) == ( pe.number() > 0 ) ) )
- return false;
- ++i;
- }
- return false;
- }
-
- BSONObj extremeKeyForIndex( const BSONObj &idxPattern, int baseDirection ) {
- BSONObjIterator i( idxPattern );
- BSONObjBuilder b;
- while( i.moreWithEOO() ) {
- BSONElement e = i.next();
- if ( e.eoo() )
- break;
- int idxDirection = e.number() >= 0 ? 1 : -1;
- int direction = idxDirection * baseDirection;
- switch( direction ) {
- case 1:
- b.appendMaxKey( e.fieldName() );
- break;
- case -1:
- b.appendMinKey( e.fieldName() );
- break;
- default:
- verify( false );
- }
- }
- return b.obj();
- }
-
- pair<int,int> keyAudit( const BSONObj &min, const BSONObj &max ) {
- int direction = 0;
- int firstSignificantField = 0;
- BSONObjIterator i( min );
- BSONObjIterator a( max );
- while( 1 ) {
- BSONElement ie = i.next();
- BSONElement ae = a.next();
- if ( ie.eoo() && ae.eoo() )
- break;
- if ( ie.eoo() || ae.eoo() || strcmp( ie.fieldName(), ae.fieldName() ) != 0 ) {
- return make_pair( -1, -1 );
- }
- int cmp = ie.woCompare( ae );
- if ( cmp < 0 )
- direction = 1;
- if ( cmp > 0 )
- direction = -1;
- if ( direction != 0 )
- break;
- ++firstSignificantField;
- }
- return make_pair( direction, firstSignificantField );
- }
-
- pair<int,int> flexibleKeyAudit( const BSONObj &min, const BSONObj &max ) {
- if ( min.isEmpty() || max.isEmpty() ) {
- return make_pair( 1, -1 );
- }
- else {
- return keyAudit( min, max );
- }
- }
-
- // 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 ) {
- if ( min.isEmpty() && max.isEmpty() ) {
- errmsg = "one of min or max must be specified";
- return 0;
- }
-
- Client::Context ctx( ns );
- IndexDetails *id = 0;
- NamespaceDetails *d = nsdetails( ns );
- if ( !d ) {
- errmsg = "ns not found";
- return 0;
- }
-
- pair<int,int> ret = flexibleKeyAudit( min, max );
- if ( ret == make_pair( -1, -1 ) ) {
- errmsg = "min and max keys do not share pattern";
- return 0;
- }
- if ( keyPattern.isEmpty() ) {
- NamespaceDetails::IndexIterator i = d->ii();
- while( i.more() ) {
- IndexDetails& ii = i.next();
- if ( indexWorks( ii.keyPattern(), min.isEmpty() ? max : min, ret.first, ret.second ) ) {
- if ( ii.getSpec().getType() == 0 ) {
- id = &ii;
- keyPattern = ii.keyPattern();
- break;
- }
- }
- }
-
- }
- else {
- if ( !indexWorks( keyPattern, min.isEmpty() ? max : min, ret.first, ret.second ) ) {
- errmsg = "requested keyPattern does not match specified keys";
- return 0;
- }
- NamespaceDetails::IndexIterator i = d->ii();
- while( i.more() ) {
- IndexDetails& ii = i.next();
- if( ii.keyPattern().woCompare(keyPattern) == 0 ) {
- id = &ii;
- break;
- }
- if ( keyPattern.nFields() == 1 && ii.keyPattern().nFields() == 1 &&
- IndexDetails::isIdIndexPattern( keyPattern ) &&
- ii.isIdIndex() ) {
- id = &ii;
- break;
- }
-
- }
- }
-
- if ( min.isEmpty() ) {
- min = extremeKeyForIndex( keyPattern, -1 );
- }
- else if ( max.isEmpty() ) {
- max = extremeKeyForIndex( keyPattern, 1 );
- }
-
- if ( !id ) {
- errmsg = str::stream() << "no index found for specified keyPattern: " << keyPattern.toString()
- << " min: " << min << " max: " << max;
- return 0;
- }
-
- min = min.extractFieldsUnDotted( keyPattern );
- max = max.extractFieldsUnDotted( keyPattern );
-
- return id;
- }
-
- shared_ptr<Cursor> NamespaceDetailsTransient::bestGuessCursor( const char *ns,
- const BSONObj &query,
- const BSONObj &sort ) {
- auto_ptr<FieldRangeSetPair> frsp( new FieldRangeSetPair( ns, query, true ) );
- auto_ptr<FieldRangeSetPair> origFrsp( new FieldRangeSetPair( *frsp ) );
-
- scoped_ptr<QueryPlanSet> qps( QueryPlanSet::make( ns, frsp, origFrsp, query, sort,
- shared_ptr<const ParsedQuery>(), BSONObj(),
- QueryPlanGenerator::UseIfInOrder,
- BSONObj(), BSONObj(), true ) );
- QueryPlanSet::QueryPlanPtr qpp = qps->getBestGuess();
- if( ! qpp.get() ) return shared_ptr<Cursor>();
-
- shared_ptr<Cursor> ret = qpp->newCursor();
-
- // If we don't already have a matcher, supply one.
- if ( !query.isEmpty() && ! ret->matcher() ) {
- ret->setMatcher( qpp->matcher() );
- }
- return ret;
- }
-
- bool QueryUtilIndexed::indexUseful( const FieldRangeSetPair &frsp, NamespaceDetails *d, int idxNo, const BSONObj &order ) {
- DEV frsp.assertValidIndex( d, idxNo );
- BSONObj keyPattern = d->idx( idxNo ).keyPattern();
- if ( !frsp.matchPossibleForIndex( d, idxNo, keyPattern ) ) {
- // No matches are possible in the index so the index may be useful.
- return true;
- }
-
- return d->idx( idxNo ).getSpec().suitability( frsp.frsForIndex( d , idxNo ) , order )
- != USELESS;
- }
-
- void QueryUtilIndexed::clearIndexesForPatterns( const FieldRangeSetPair &frsp, const BSONObj &order ) {
- SimpleMutex::scoped_lock lk(NamespaceDetailsTransient::_qcMutex);
- NamespaceDetailsTransient &nsdt = NamespaceDetailsTransient::get_inlock( frsp.ns() );
- CachedQueryPlan noCachedPlan;
- nsdt.registerCachedQueryPlanForPattern( frsp._singleKey.pattern( order ), noCachedPlan );
- nsdt.registerCachedQueryPlanForPattern( frsp._multiKey.pattern( order ), noCachedPlan );
- }
-
- CachedQueryPlan QueryUtilIndexed::bestIndexForPatterns( const FieldRangeSetPair &frsp, const BSONObj &order ) {
- SimpleMutex::scoped_lock lk(NamespaceDetailsTransient::_qcMutex);
- NamespaceDetailsTransient &nsdt = NamespaceDetailsTransient::get_inlock( frsp.ns() );
- // TODO Maybe it would make sense to return the index with the lowest
- // nscanned if there are two possibilities.
- {
- QueryPattern pattern = frsp._singleKey.pattern( order );
- CachedQueryPlan cachedQueryPlan = nsdt.cachedQueryPlanForPattern( pattern );
- if ( !cachedQueryPlan.indexKey().isEmpty() ) {
- return cachedQueryPlan;
- }
- }
- {
- QueryPattern pattern = frsp._multiKey.pattern( order );
- CachedQueryPlan cachedQueryPlan = nsdt.cachedQueryPlanForPattern( pattern );
- if ( !cachedQueryPlan.indexKey().isEmpty() ) {
- return cachedQueryPlan;
- }
- }
- return CachedQueryPlan();
- }
-
- bool QueryUtilIndexed::uselessOr( const OrRangeGenerator &org, NamespaceDetails *d, int hintIdx ) {
- for( list<FieldRangeSetPair>::const_iterator i = org._originalOrSets.begin(); i != org._originalOrSets.end(); ++i ) {
- if ( hintIdx != -1 ) {
- if ( !indexUseful( *i, d, hintIdx, BSONObj() ) ) {
- return true;
- }
- }
- else {
- bool useful = false;
- for( int j = 0; j < d->nIndexes; ++j ) {
- if ( indexUseful( *i, d, j, BSONObj() ) ) {
- useful = true;
- break;
- }
- }
- if ( !useful ) {
- return true;
- }
- }
- }
- return false;
- }
-
-} // namespace mongo
generated by cgit v1.2.3 (git 2.39.1) at 2026-09-11 13:38:40 +0000