SERVER-958 Track non single key field ranges and utilize them in query planning

5 files changed, 469 insertions, 327 deletions

diff --git a/db/queryoptimizer.cpp b/db/queryoptimizer.cpp
index bc44722cacf..e4167d2f1b9 100644
--- a/db/queryoptimizer.cpp
+++ b/db/queryoptimizer.cpp
@@ -53,9 +53,9 @@ namespace mongo {
 
     QueryPlan::QueryPlan(
         NamespaceDetails *d, int idxNo,
-        const FieldRangeSet &frs, const FieldRangeSet &originalFrs, const BSONObj &originalQuery, const BSONObj &order, const BSONObj &startKey, const BSONObj &endKey , string special ) :
+        const FieldRangeSetPair &frsp, const FieldRangeSetPair &originalFrsp, const BSONObj &originalQuery, const BSONObj &order, const BSONObj &startKey, const BSONObj &endKey , string special ) :
         _d(d), _idxNo(idxNo),
-        _frs( frs ),
+        _frs( frsp.frsForIndex( _d, _idxNo ) ),
         _originalQuery( originalQuery ),
         _order( order ),
         _index( 0 ),
@@ -65,22 +65,25 @@ namespace mongo {
         _direction( 0 ),
         _endKeyInclusive( endKey.isEmpty() ),
         _unhelpful( false ),
+        _impossible( false ),
         _special( special ),
         _type(0),
         _startOrEndSpec( !startKey.isEmpty() || !endKey.isEmpty() ) {
 
+        BSONObj idxKey = _idxNo < 0 ? BSONObj() : d->idx( _idxNo ).keyPattern();
+            
+        if ( !_frs.matchPossibleForIndex( idxKey ) ) {
+            _impossible = true;
+            _scanAndOrderRequired = false;
+            return;
+        }
+            
         if ( willScanTable() ) {
             if ( _order.isEmpty() || !strcmp( _order.firstElement().fieldName(), "$natural" ) )
                 _scanAndOrderRequired = false;
             return;                
         }
             
-        // FIXME SERVER-1932 This check is only valid for non multikey indexes.
-        if ( !_frs.matchPossible() ) {
-            _unhelpful = true;
-            _scanAndOrderRequired = false;
-            return;
-        }            
         _index = &d->idx(_idxNo);
 
         if ( _special.size() ) {
@@ -92,7 +95,6 @@ namespace mongo {
             return;
         }
 
-        BSONObj idxKey = _index->keyPattern();
         const IndexSpec &idxSpec = _index->getSpec();
         BSONObjIterator o( order );
         BSONObjIterator k( idxKey );
@@ -113,7 +115,7 @@ namespace mongo {
                     goto doneCheckOrder;
                 if ( strcmp( oe.fieldName(), ke.fieldName() ) == 0 )
                     break;
-                if ( !frs.range( ke.fieldName() ).equality() )
+                if ( !_frs.range( ke.fieldName() ).equality() )
                     goto doneCheckOrder;
             }
             int d = elementDirection( oe ) == elementDirection( ke ) ? 1 : -1;
@@ -135,7 +137,7 @@ doneCheckOrder:
             BSONElement e = i.next();
             if ( e.eoo() )
                 break;
-            const FieldRange &fr = frs.range( e.fieldName() );
+            const FieldRange &fr = _frs.range( e.fieldName() );
             if ( stillOptimalIndexedQueryCount ) {
                 if ( fr.nontrivial() )
                     ++optimalIndexedQueryCount;
@@ -154,16 +156,16 @@ doneCheckOrder:
             orderFieldsUnindexed.erase( e.fieldName() );
         }
         if ( !_scanAndOrderRequired &&
-                ( optimalIndexedQueryCount == frs.nNontrivialRanges() ) )
+                ( optimalIndexedQueryCount == _frs.nNontrivialRanges() ) )
             _optimal = true;
-        if ( exactIndexedQueryCount == frs.nNontrivialRanges() &&
+        if ( exactIndexedQueryCount == _frs.nNontrivialRanges() &&
                 orderFieldsUnindexed.size() == 0 &&
                 exactIndexedQueryCount == _index->keyPattern().nFields() &&
                 exactIndexedQueryCount == _originalQuery.nFields() ) {
             _exactKeyMatch = true;
         }
-        _frv.reset( new FieldRangeVector( frs, idxSpec, _direction ) );
-        _originalFrv.reset( new FieldRangeVector( originalFrs, idxSpec, _direction ) );
+        _frv.reset( new FieldRangeVector( _frs, idxSpec, _direction ) );
+        _originalFrv.reset( new FieldRangeVector( originalFrsp.frsForIndex( _d, _idxNo ), idxSpec, _direction ) );
         if ( _startOrEndSpec ) {
             BSONObj newStart, newEnd;
             if ( !startKey.isEmpty() )
@@ -177,7 +179,7 @@ doneCheckOrder:
         }
 
         if ( ( _scanAndOrderRequired || _order.isEmpty() ) &&
-                !frs.range( idxKey.firstElement().fieldName() ).nontrivial() ) {
+                !_frs.range( idxKey.firstElement().fieldName() ).nontrivial() ) {
             _unhelpful = true;
         }
     }
@@ -189,21 +191,20 @@ doneCheckOrder:
             return _type->newCursor( _originalQuery , _order , numWanted );
         }
 
-        if ( willScanTable() ) {
-            if ( _frs.nNontrivialRanges() )
-                checkTableScanAllowed( _frs.ns() );
-            return findTableScan( _frs.ns(), _order, startLoc );
-        }
-        
-        // FIXME SERVER-1932 This check is only valid for non multikey indexes.
-        if ( !_frs.matchPossible() ) {
+        if ( _impossible ) {
             // TODO We might want to allow this dummy table scan even in no table
             // scan mode, since it won't scan anything.
             if ( _frs.nNontrivialRanges() )
                 checkTableScanAllowed( _frs.ns() );
             return shared_ptr<Cursor>( new BasicCursor( DiskLoc() ) );
         }
-        
+
+        if ( willScanTable() ) {
+            if ( _frs.nNontrivialRanges() )
+                checkTableScanAllowed( _frs.ns() );
+            return findTableScan( _frs.ns(), _order, startLoc );
+        }
+                
         massert( 10363 ,  "newCursor() with start location not implemented for indexed plans", startLoc.isNull() );
 
         if ( _startOrEndSpec ) {
@@ -276,11 +277,11 @@ doneCheckOrder:
         _init();
     }    
 
-    QueryPlanSet::QueryPlanSet( const char *ns, auto_ptr<FieldRangeSet> frs, auto_ptr<FieldRangeSet> originalFrs, const BSONObj &originalQuery, const BSONObj &order, const BSONElement *hint, bool honorRecordedPlan, const BSONObj &min, const BSONObj &max, bool bestGuessOnly, bool mayYield ) :
+    QueryPlanSet::QueryPlanSet( const char *ns, auto_ptr<FieldRangeSetPair> frsp, auto_ptr<FieldRangeSetPair> originalFrsp, const BSONObj &originalQuery, const BSONObj &order, const BSONElement *hint, bool honorRecordedPlan, const BSONObj &min, const BSONObj &max, bool bestGuessOnly, bool mayYield ) :
         _ns(ns),
         _originalQuery( originalQuery ),
-        _frs( frs ),
-        _originalFrs( originalFrs ),
+        _frsp( frsp ),
+        _originalFrsp( originalFrsp ),
         _mayRecordPlan( true ),
         _usingPrerecordedPlan( false ),
         _hint( BSONObj() ),
@@ -318,10 +319,10 @@ doneCheckOrder:
             string errmsg;
             BSONObj keyPattern = id.keyPattern();
             // This reformats _min and _max to be used for index lookup.
-            massert( 10365 ,  errmsg, indexDetailsForRange( _frs->ns(), errmsg, _min, _max, keyPattern ) );
+            massert( 10365 ,  errmsg, indexDetailsForRange( _frsp->ns(), errmsg, _min, _max, keyPattern ) );
         }
         NamespaceDetails *d = nsdetails(_ns);
-        _plans.push_back( QueryPlanPtr( new QueryPlan( d, d->idxNo(id), *_frs, *_originalFrs, _originalQuery, _order, _min, _max ) ) );
+        _plans.push_back( QueryPlanPtr( new QueryPlan( d, d->idxNo(id), *_frsp, *_originalFrsp, _originalQuery, _order, _min, _max ) ) );
     }
 
     // returns an IndexDetails * for a hint, 0 if hint is $natural.
@@ -362,11 +363,11 @@ doneCheckOrder:
         _mayRecordPlan = true;
         _usingPrerecordedPlan = false;
 
-        const char *ns = _frs->ns();
+        const char *ns = _frsp->ns();
         NamespaceDetails *d = nsdetails( ns );
-        if ( !d || !_frs->matchPossible() ) { // FIXME SERVER-1932 This check is only valid for non multikey indexes.
+        if ( !d || !_frsp->matchPossible() ) {
             // Table scan plan, when no matches are possible
-            _plans.push_back( QueryPlanPtr( new QueryPlan( d, -1, *_frs, *_originalFrs, _originalQuery, _order ) ) );
+            _plans.push_back( QueryPlanPtr( new QueryPlan( d, -1, *_frsp, *_originalFrsp, _originalQuery, _order ) ) );
             return;
         }
 
@@ -380,7 +381,7 @@ doneCheckOrder:
             else {
                 massert( 10366 ,  "natural order cannot be specified with $min/$max", _min.isEmpty() && _max.isEmpty() );
                 // Table scan plan
-                _plans.push_back( QueryPlanPtr( new QueryPlan( d, -1, *_frs, *_originalFrs, _originalQuery, _order ) ) );
+                _plans.push_back( QueryPlanPtr( new QueryPlan( d, -1, *_frsp, *_originalFrsp, _originalQuery, _order ) ) );
             }
             return;
         }
@@ -390,7 +391,7 @@ doneCheckOrder:
             BSONObj keyPattern;
             IndexDetails *idx = indexDetailsForRange( ns, errmsg, _min, _max, keyPattern );
             massert( 10367 ,  errmsg, idx );
-            _plans.push_back( QueryPlanPtr( new QueryPlan( d, d->idxNo(*idx), *_frs, *_originalFrs, _originalQuery, _order, _min, _max ) ) );
+            _plans.push_back( QueryPlanPtr( new QueryPlan( d, d->idxNo(*idx), *_frsp, *_originalFrsp, _originalQuery, _order, _min, _max ) ) );
             return;
         }
 
@@ -399,19 +400,19 @@ doneCheckOrder:
             if ( idx >= 0 ) {
                 _usingPrerecordedPlan = true;
                 _mayRecordPlan = false;
-                _plans.push_back( QueryPlanPtr( new QueryPlan( d , idx , *_frs , *_frs , _originalQuery, _order ) ) );
+                _plans.push_back( QueryPlanPtr( new QueryPlan( d , idx , *_frsp , *_originalFrsp , _originalQuery, _order ) ) );
                 return;
             }
         }
 
         if ( _originalQuery.isEmpty() && _order.isEmpty() ) {
-            _plans.push_back( QueryPlanPtr( new QueryPlan( d, -1, *_frs, *_originalFrs, _originalQuery, _order ) ) );
+            _plans.push_back( QueryPlanPtr( new QueryPlan( d, -1, *_frsp, *_originalFrsp, _originalQuery, _order ) ) );
             return;
         }
 
-        DEBUGQO( "\t special : " << _frs->getSpecial() );
-        if ( _frs->getSpecial().size() ) {
-            _special = _frs->getSpecial();
+        DEBUGQO( "\t special : " << _frsp->getSpecial() );
+        if ( _frsp->getSpecial().size() ) {
+            _special = _frsp->getSpecial();
             NamespaceDetails::IndexIterator i = d->ii();
             while( i.more() ) {
                 int j = i.pos();
@@ -420,7 +421,7 @@ doneCheckOrder:
                 if ( spec.getTypeName() == _special && spec.suitability( _originalQuery , _order ) ) {
                     _usingPrerecordedPlan = true;
                     _mayRecordPlan = false;
-                    _plans.push_back( QueryPlanPtr( new QueryPlan( d , j , *_frs , *_frs , _originalQuery, _order ,
+                    _plans.push_back( QueryPlanPtr( new QueryPlan( d , j , *_frsp , *_originalFrsp , _originalQuery, _order ,
                                                     BSONObj() , BSONObj() , _special ) ) );
                     return;
                 }
@@ -429,20 +430,15 @@ doneCheckOrder:
         }
 
         if ( _honorRecordedPlan ) {
-            BSONObj bestIndex;
-            long long oldNScanned;
-            {
-                scoped_lock lk(NamespaceDetailsTransient::_qcMutex);
-                NamespaceDetailsTransient& nsd = NamespaceDetailsTransient::get_inlock( ns );
-                bestIndex = nsd.indexForPattern( _frs->pattern( _order ) );
-                oldNScanned = nsd.nScannedForPattern( _frs->pattern( _order ) );
-            }
+            pair< BSONObj, long long > best = _frsp->bestIndexForPatterns( _order );
+            BSONObj bestIndex = best.first;
+            long long oldNScanned = best.second;
             if ( !bestIndex.isEmpty() ) {
                 QueryPlanPtr p;
                 _oldNScanned = oldNScanned;
                 if ( !strcmp( bestIndex.firstElement().fieldName(), "$natural" ) ) {
                     // Table scan plan
-                    p.reset( new QueryPlan( d, -1, *_frs, *_originalFrs, _originalQuery, _order ) );
+                    p.reset( new QueryPlan( d, -1, *_frsp, *_originalFrsp, _originalQuery, _order ) );
                 }
 
                 NamespaceDetails::IndexIterator i = d->ii();
@@ -450,7 +446,7 @@ doneCheckOrder:
                     int j = i.pos();
                     IndexDetails& ii = i.next();
                     if( ii.keyPattern().woCompare(bestIndex) == 0 ) {
-                        p.reset( new QueryPlan( d, j, *_frs, *_originalFrs, _originalQuery, _order ) );
+                        p.reset( new QueryPlan( d, j, *_frsp, *_originalFrsp, _originalQuery, _order ) );
                     }
                 }
 
@@ -468,47 +464,56 @@ doneCheckOrder:
     }
 
     void QueryPlanSet::addOtherPlans( bool checkFirst ) {
-        const char *ns = _frs->ns();
+        const char *ns = _frsp->ns();
         NamespaceDetails *d = nsdetails( ns );
         if ( !d )
             return;
 
         // If table scan is optimal or natural order requested or tailable cursor requested
-        // FIXME SERVER-1932 This check is only valid for non multikey indexes.
-        if ( !_frs->matchPossible() || ( _frs->nNontrivialRanges() == 0 && _order.isEmpty() ) ||
+        if ( !_frsp->matchPossible() || ( _frsp->noNontrivialRanges() && _order.isEmpty() ) ||
                 ( !_order.isEmpty() && !strcmp( _order.firstElement().fieldName(), "$natural" ) ) ) {
             // Table scan plan
-            addPlan( QueryPlanPtr( new QueryPlan( d, -1, *_frs, *_originalFrs, _originalQuery, _order ) ), checkFirst );
+            addPlan( QueryPlanPtr( new QueryPlan( d, -1, *_frsp, *_originalFrsp, _originalQuery, _order ) ), checkFirst );
             return;
         }
 
         bool normalQuery = _hint.isEmpty() && _min.isEmpty() && _max.isEmpty();
 
         PlanSet plans;
+        QueryPlanPtr optimalPlan;
         for( int i = 0; i < d->nIndexes; ++i ) {
-            IndexDetails& id = d->idx(i);
-            const IndexSpec& spec = id.getSpec();
-            IndexSuitability suitability = HELPFUL;
             if ( normalQuery ) {
-                suitability = spec.suitability( _frs->simplifiedQuery() , _order );
-                if ( suitability == USELESS )
+                if ( !_frsp->matchPossibleForIndex( d, i ) ) {
+                    // If no match is possible, only generate a trival plan that won't
+                    // scan any documents.
+                    QueryPlanPtr p( new QueryPlan( d, i, *_frsp, *_originalFrsp, _originalQuery, _order ) );
+                    addPlan( p, checkFirst );
+                    return;
+                }
+                if ( !_frsp->indexUseful( d, i, _order ) ) {
                     continue;
+                }
             }
 
-            QueryPlanPtr p( new QueryPlan( d, i, *_frs, *_originalFrs, _originalQuery, _order ) );
+            QueryPlanPtr p( new QueryPlan( d, i, *_frsp, *_originalFrsp, _originalQuery, _order ) );
             if ( p->optimal() ) {
-                addPlan( p, checkFirst );
-                return;
+                if ( !optimalPlan.get() ) {
+                    optimalPlan = p;
+                }
             }
             else if ( !p->unhelpful() ) {
                 plans.push_back( p );
             }
         }
+        if ( optimalPlan.get() ) {
+            addPlan( optimalPlan, checkFirst );
+            return;
+        }
         for( PlanSet::iterator i = plans.begin(); i != plans.end(); ++i )
             addPlan( *i, checkFirst );
 
         // Table scan plan
-        addPlan( QueryPlanPtr( new QueryPlan( d, -1, *_frs, *_originalFrs, _originalQuery, _order ) ), checkFirst );
+        addPlan( QueryPlanPtr( new QueryPlan( d, -1, *_frsp, *_originalFrsp, _originalQuery, _order ) ), checkFirst );
     }
 
     shared_ptr<QueryOp> QueryPlanSet::runOp( QueryOp &op ) {
@@ -518,10 +523,7 @@ doneCheckOrder:
             // _plans.size() > 1 if addOtherPlans was called in Runner::run().
             if ( _bestGuessOnly || res->complete() || _plans.size() > 1 )
                 return res;
-            {
-                scoped_lock lk(NamespaceDetailsTransient::_qcMutex);
-                NamespaceDetailsTransient::get_inlock( _frs->ns() ).registerIndexForPattern( _frs->pattern( _order ), BSONObj(), 0 );
-            }
+            _frsp->clearIndexesForPatterns( _order );
             init();
         }
         Runner r( *this, op );
@@ -551,7 +553,7 @@ doneCheckOrder:
             }
 
             warning() << "best guess query plan requested, but scan and order are required for all plans "
-            		  << " query: " << _frs->simplifiedQuery()
+            		  << " query: " << _originalQuery
             		  << " order: " << _order
             		  << " choices: ";
 
@@ -647,7 +649,7 @@ doneCheckOrder:
             queue.push( holder );
             if ( !_plans._bestGuessOnly && _plans._usingPrerecordedPlan && op.nscanned() > _plans._oldNScanned * 10 && _plans._special.empty() ) {
                 holder._offset = -op.nscanned();
-                _plans.addOtherPlans( true );
+                _plans.addOtherPlans( /* avoid duplicating the initial plan */ true );
                 PlanSet::iterator i = _plans._plans.begin();
                 ++i;
                 for( ; i != _plans._plans.end(); ++i ) {
@@ -756,9 +758,9 @@ doneCheckOrder:
         }
         // if _or == false, don't use or clauses for index selection
         if ( !_or ) {
-            auto_ptr<FieldRangeSet> frs( new FieldRangeSet( ns, _query ) );
-            auto_ptr<FieldRangeSet> oldFrs( new FieldRangeSet( *frs ) );
-            _currentQps.reset( new QueryPlanSet( ns, frs, oldFrs, _query, order, hint, honorRecordedPlan, min, max, _bestGuessOnly, _mayYield ) );
+            auto_ptr<FieldRangeSetPair> frsp( new FieldRangeSetPair( ns, _query, true ) );
+            auto_ptr<FieldRangeSetPair> oldFrsp( new FieldRangeSetPair( *frsp ) );
+            _currentQps.reset( new QueryPlanSet( ns, frsp, oldFrsp, _query, order, hint, honorRecordedPlan, min, max, _bestGuessOnly, _mayYield ) );
         }
         else {
             BSONElement e = _query.getField( "$or" );
@@ -773,15 +775,15 @@ doneCheckOrder:
             return _currentQps->runOp( op );
         }
         ++_i;
-        auto_ptr<FieldRangeSet> frs( _fros.topFrs() );
-        auto_ptr<FieldRangeSet> originalFrs( _fros.topFrsOriginal() );
+        auto_ptr<FieldRangeSetPair> frsp( _fros.topFrsp() );
+        auto_ptr<FieldRangeSetPair> originalFrsp( _fros.topFrspOriginal() );
         BSONElement hintElt = _hint.firstElement();
-        _currentQps.reset( new QueryPlanSet( _ns, frs, originalFrs, _query, BSONObj(), &hintElt, _honorRecordedPlan, BSONObj(), BSONObj(), _bestGuessOnly, _mayYield ) );
+        _currentQps.reset( new QueryPlanSet( _ns, frsp, originalFrsp, _query, BSONObj(), &hintElt, _honorRecordedPlan, BSONObj(), BSONObj(), _bestGuessOnly, _mayYield ) );
         shared_ptr<QueryOp> ret( _currentQps->runOp( op ) );
         if ( ret->qp().willScanTable() ) {
             _tableScanned = true;
         }
-        _fros.popOrClause( ret->qp().indexed() ? ret->qp().indexKey() : BSONObj() );
+        _fros.popOrClause( ret->qp().nsd(), ret->qp().idxNo() );
         return ret;
     }
 
@@ -798,37 +800,14 @@ doneCheckOrder:
         if ( !nsd ) {
             return true;
         }
-        IndexDetails *id = 0;
         if ( !hint.eoo() ) {
             IndexDetails *id = parseHint( hint, nsd );
             if ( !id ) {
                 return true;
             }
+            return _fros.uselessOr( nsd, nsd->idxNo( *id ) );
         }
-        vector<BSONObj> ret;
-        _fros.allClausesSimplified( ret );
-        for( vector<BSONObj>::const_iterator i = ret.begin(); i != ret.end(); ++i ) {
-            if ( id ) {
-                if ( id->getSpec().suitability( *i, BSONObj() ) == USELESS ) {
-                    return true;
-                }
-            }
-            else {
-                bool useful = false;
-                NamespaceDetails::IndexIterator j = nsd->ii();
-                while( j.more() ) {
-                    IndexDetails &id = j.next();
-                    if ( id.getSpec().suitability( *i, BSONObj() ) != USELESS ) {
-                        useful = true;
-                        break;
-                    }
-                }
-                if ( !useful ) {
-                    return true;
-                }
-            }
-        }
-        return false;
+        return _fros.uselessOr( nsd, -1 );        
     }
     
     MultiCursor::MultiCursor( const char *ns, const BSONObj &pattern, const BSONObj &order, shared_ptr<CursorOp> op, bool mayYield )
@@ -1037,10 +1016,10 @@ doneCheckOrder:
             return shared_ptr<Cursor>( new MultiCursor( ns, query, sort ) );
         }
         else {
-            auto_ptr<FieldRangeSet> frs( new FieldRangeSet( ns, query ) );
-            auto_ptr<FieldRangeSet> origFrs( new FieldRangeSet( *frs ) );
+            auto_ptr<FieldRangeSetPair> frsp( new FieldRangeSetPair( ns, query, true ) );
+            auto_ptr<FieldRangeSetPair> origFrsp( new FieldRangeSetPair( *frsp ) );
 
-            QueryPlanSet qps( ns, frs, origFrs, query, sort );
+            QueryPlanSet qps( ns, frsp, origFrsp, query, sort );
             QueryPlanSet::QueryPlanPtr qpp = qps.getBestGuess();
             if( ! qpp.get() ) return shared_ptr<Cursor>();
 
diff --git a/db/queryoptimizer.h b/db/queryoptimizer.h
index 5c6f1a06364..c88ab34c450 100644
--- a/db/queryoptimizer.h
+++ b/db/queryoptimizer.h
@@ -35,8 +35,8 @@ namespace mongo {
 
         QueryPlan(NamespaceDetails *d,
                   int idxNo, // -1 = no index
-                  const FieldRangeSet &frs,
-                  const FieldRangeSet &originalFrs,
+                  const FieldRangeSetPair &frsp,
+                  const FieldRangeSetPair &originalFrsp,
                   const BSONObj &originalQuery,
                   const BSONObj &order,
                   const BSONObj &startKey = BSONObj(),
@@ -55,7 +55,7 @@ namespace mongo {
          */
         bool exactKeyMatch() const { return _exactKeyMatch; }
         /** @return true iff this QueryPlan would perform an unindexed scan. */
-        bool willScanTable() const { return _idxNo < 0; }
+        bool willScanTable() const { return _idxNo < 0 && !_impossible; }
 
         /** @return a new cursor based on this QueryPlan's index and FieldRangeSet. */
         shared_ptr<Cursor> newCursor( const DiskLoc &startLoc = DiskLoc() , int numWanted=0 ) const;
@@ -67,6 +67,7 @@ namespace mongo {
         int direction() const { return _direction; }
         BSONObj indexKey() const;
         bool indexed() 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; }
@@ -96,6 +97,7 @@ namespace mongo {
         BSONObj _endKey;
         bool _endKeyInclusive;
         bool _unhelpful;
+        bool _impossible;
         string _special;
         IndexType * _type;
         bool _startOrEndSpec;
@@ -205,8 +207,8 @@ namespace mongo {
         typedef vector<QueryPlanPtr> PlanSet;
 
         QueryPlanSet( const char *ns,
-                      auto_ptr<FieldRangeSet> frs,
-                      auto_ptr<FieldRangeSet> originalFrs,
+                      auto_ptr<FieldRangeSetPair> frsp,
+                      auto_ptr<FieldRangeSetPair> originalFrsp,
                       const BSONObj &originalQuery,
                       const BSONObj &order,
                       const BSONElement *hint = 0,
@@ -238,8 +240,8 @@ namespace mongo {
         QueryPlanPtr getBestGuess() const;
 
         //for testing
-        const FieldRangeSet &frs() const { return *_frs; }
-        const FieldRangeSet &originalFrs() const { return *_originalFrs; }
+        const FieldRangeSetPair &frsp() const { return *_frsp; }
+        const FieldRangeSetPair &originalFrsp() const { return *_originalFrsp; }
         bool modifiedKeys() const;
         bool hasMultiKey() const;
 
@@ -266,8 +268,8 @@ namespace mongo {
 
         const char *_ns;
         BSONObj _originalQuery;
-        auto_ptr<FieldRangeSet> _frs;
-        auto_ptr<FieldRangeSet> _originalFrs;
+        auto_ptr<FieldRangeSetPair> _frsp;
+        auto_ptr<FieldRangeSetPair> _originalFrsp;
         PlanSet _plans;
         bool _mayRecordPlan;
         bool _usingPrerecordedPlan;
diff --git a/db/queryutil-inl.h b/db/queryutil-inl.h
index 68df0885846..d36f949438f 100644
--- a/db/queryutil-inl.h
+++ b/db/queryutil-inl.h
@@ -56,28 +56,6 @@ namespace mongo {
               maxKey.firstElement().woCompare( max(), false ) != 0 );
     }
 
-    inline bool QueryPattern::operator<( const QueryPattern &other ) const {
-        map<string,Type>::const_iterator i = _fieldTypes.begin();
-        map<string,Type>::const_iterator j = other._fieldTypes.begin();
-        while( i != _fieldTypes.end() ) {
-            if ( j == other._fieldTypes.end() )
-                return false;
-            if ( i->first < j->first )
-                return true;
-            else if ( i->first > j->first )
-                return false;
-            if ( i->second < j->second )
-                return true;
-            else if ( i->second > j->second )
-                return false;
-            ++i;
-            ++j;
-        }
-        if ( j != other._fieldTypes.end() )
-            return true;
-        return _sort.woCompare( other._sort ) < 0;
-    }
-
     inline const FieldRange &FieldRangeSet::range( const char *fieldName ) const {
         map<string,FieldRange>::const_iterator f = _ranges.find( fieldName );
         if ( f == _ranges.end() )
@@ -87,8 +65,10 @@ namespace mongo {
 
     inline FieldRange &FieldRangeSet::range( const char *fieldName ) {
         map<string,FieldRange>::iterator f = _ranges.find( fieldName );
-        if ( f == _ranges.end() )
-            return trivialRange();
+        if ( f == _ranges.end() ) {
+            _ranges.insert( make_pair( string( fieldName ), trivialRange() ) );
+            return _ranges.find( fieldName )->second;
+        }
         return f->second;
     }
 
@@ -102,9 +82,28 @@ namespace mongo {
     }
 
     inline bool FieldRangeSet::matchPossible() const {
-        for( map<string,FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i )
-            if ( i->second.empty() )
+        for( map<string,FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
+            if ( i->second.empty() ) {
+                return false;
+            }
+        }
+        return true;
+    }
+    
+    inline bool FieldRangeSet::matchPossibleForIndex( const BSONObj &keyPattern ) const {
+        if ( !_singleKey ) {
+            return matchPossible();   
+        }
+        BSONObjIterator i( keyPattern );
+        while( i.more() ) {
+            BSONElement e = i.next();
+            if ( e.fieldName() == string( "$natural" ) ) {
+                return true;
+            }
+            if ( range( e.fieldName() ).empty() ) {
                 return false;
+            }
+        }
         return true;
     }
 
@@ -116,16 +115,16 @@ namespace mongo {
         return ret;
     }
 
-    inline FieldRangeSet *FieldRangeOrSet::topFrs() const {
-        FieldRangeSet *ret = new FieldRangeSet( _baseSet );
+    inline FieldRangeSetPair *FieldRangeOrSet::topFrsp() const {
+        FieldRangeSetPair *ret = new FieldRangeSetPair( _baseSet );
         if (_orSets.size()) {
             *ret &= _orSets.front();
         }
         return ret;
     }
 
-    inline FieldRangeSet *FieldRangeOrSet::topFrsOriginal() const {
-        FieldRangeSet *ret = new FieldRangeSet( _baseSet );
+    inline FieldRangeSetPair *FieldRangeOrSet::topFrspOriginal() const {
+        FieldRangeSetPair *ret = new FieldRangeSetPair( _baseSet );
         if (_originalOrSets.size()) {
             *ret &= _originalOrSets.front();
         }
diff --git a/db/queryutil.cpp b/db/queryutil.cpp
index 32f3d4555ce..45502db8573 100644
--- a/db/queryutil.cpp
+++ b/db/queryutil.cpp
@@ -150,7 +150,8 @@ namespace mongo {
     }
 
 
-    FieldRange::FieldRange( const BSONElement &e, bool isNot, bool optimize ) {
+    FieldRange::FieldRange( const BSONElement &e, bool singleKey, bool isNot, bool optimize )
+    : _singleKey( singleKey ) {
         // NOTE with $not, we could potentially form a complementary set of intervals.
         if ( !isNot && !e.eoo() && e.type() != RegEx && e.getGtLtOp() == BSONObj::opIN ) {
             set<BSONElement,element_lt> vals;
@@ -160,7 +161,7 @@ namespace mongo {
             while( i.more() ) {
                 BSONElement ie = i.next();
                 if ( ie.type() == RegEx ) {
-                    regexes.push_back( FieldRange( ie, false, optimize ) );
+                    regexes.push_back( FieldRange( ie, singleKey, false, optimize ) );
                 }
                 else {
                     // A document array may be indexed by its first element, or
@@ -446,6 +447,9 @@ namespace mongo {
     }
 
     const FieldRange &FieldRange::operator&=( const FieldRange &other ) {
+        if ( !_singleKey && nontrivial() ) {
+            return *this;
+        }
         vector<FieldInterval> newIntervals;
         vector<FieldInterval>::const_iterator i = _intervals.begin();
         vector<FieldInterval>::const_iterator j = other._intervals.begin();
@@ -612,42 +616,9 @@ namespace mongo {
         return o;
     }
 
-    /** for testing only - speed unimportant */
-    bool QueryPattern::operator==( const QueryPattern &other ) const {
-        bool less = operator<( other );
-        bool more = other.operator<( *this );
-        assert( !( less && more ) );
-        return !( less || more );
-    }
-    
-    /** for testing only - speed unimportant */
-    bool QueryPattern::operator!=( const QueryPattern &other ) const {
-        return !operator==( other );
-    }
-    
-    void QueryPattern::setSort( const BSONObj sort ) {
-        _sort = normalizeSort( sort );
-    }
-    
-    BSONObj QueryPattern::normalizeSort( const BSONObj &spec ) {
-        if ( spec.isEmpty() )
-            return spec;
-        int direction = ( spec.firstElement().number() >= 0 ) ? 1 : -1;
-        BSONObjIterator i( spec );
-        BSONObjBuilder b;
-        while( i.moreWithEOO() ) {
-            BSONElement e = i.next();
-            if ( e.eoo() )
-                break;
-            b.append( e.fieldName(), direction * ( ( e.number() >= 0 ) ? -1 : 1 ) );
-        }
-        return b.obj();
-    }
-    
-    
     string FieldRangeSet::getSpecial() const {
         string s = "";
-        for ( map<string,FieldRange>::iterator i=_ranges.begin(); i!=_ranges.end(); i++ ) {
+        for ( map<string,FieldRange>::const_iterator i=_ranges.begin(); i!=_ranges.end(); i++ ) {
             if ( i->second.getSpecial().size() == 0 )
                 continue;
             uassert( 13033 , "can't have 2 special fields" , s.size() == 0 );
@@ -708,7 +679,7 @@ namespace mongo {
             return *this;
         }
         // nUnincluded == 1
-        _ranges[ unincludedKey ] -= other._ranges[ unincludedKey ];
+        range( unincludedKey.c_str() ) -= other.range( unincludedKey.c_str() );
         appendQueries( other );
         return *this;
     }
@@ -727,12 +698,12 @@ namespace mongo {
                 ++i;
             }
             else {
-                _ranges[ j->first ] = j->second;
+                range( j->first.c_str() ) = j->second;
                 ++j;
             }
         }
         while( j != other._ranges.end() ) {
-            _ranges[ j->first ] = j->second;
+            range( j->first.c_str() ) = j->second;
             ++j;
         }
         appendQueries( other );
@@ -776,18 +747,18 @@ namespace mongo {
 
                 int op3 = getGtLtOp( h );
                 if ( op3 == BSONObj::Equality ) {
-                    _ranges[ fullname ] &= FieldRange( h , isNot , optimize );
+                    range( fullname.c_str() ) &= FieldRange( h , _singleKey , isNot , optimize );
                 }
                 else {
                     BSONObjIterator l( h.embeddedObject() );
                     while ( l.more() ) {
-                        _ranges[ fullname ] &= FieldRange( l.next() , isNot , optimize );
+                        range( fullname.c_str() ) &= FieldRange( l.next() , _singleKey , isNot , optimize );
                     }
                 }
             }
         }
         else {
-            _ranges[ fieldName ] &= FieldRange( f , isNot , optimize );
+            range( fieldName ) &= FieldRange( f , _singleKey , isNot , optimize );
         }
     }
 
@@ -798,7 +769,7 @@ namespace mongo {
         }
 
         if ( equality || ( e.type() == Object && !e.embeddedObject()[ "$regex" ].eoo() ) ) {
-            _ranges[ e.fieldName() ] &= FieldRange( e , false , optimize );
+            range( e.fieldName() ) &= FieldRange( e , _singleKey , false , optimize );
         }
         if ( !equality ) {
             BSONObjIterator j( e.embeddedObject() );
@@ -829,8 +800,8 @@ namespace mongo {
         }
     }
 
-    FieldRangeSet::FieldRangeSet( const char *ns, const BSONObj &query , bool optimize )
-        : _ns( ns ), _queries( 1, query.getOwned() ) {
+    FieldRangeSet::FieldRangeSet( const char *ns, const BSONObj &query, bool singleKey, bool optimize )
+        : _ns( ns ), _queries( 1, query.getOwned() ), _singleKey( singleKey ) {
         BSONObjIterator i( _queries[ 0 ] );
 
         while( i.more() ) {
@@ -865,7 +836,7 @@ namespace mongo {
                 _ranges.push_back( frs.range( e.fieldName() ) );
             }
             else {
-                _ranges.push_back( FieldRange() );
+                _ranges.push_back( FieldRange( BSONObj().firstElement(), frs.singleKey(), false, true ) );
                 frs.range( e.fieldName() ).reverse( _ranges.back() );
             }
             assert( !_ranges.back().empty() );
@@ -905,11 +876,14 @@ namespace mongo {
         return b.obj();
     }
     
-    FieldRange *FieldRangeSet::__trivialRange = 0;
-    FieldRange &FieldRangeSet::trivialRange() {
-        if ( __trivialRange == 0 )
-            __trivialRange = new FieldRange();
-        return *__trivialRange;
+    FieldRange *FieldRangeSet::__singleKeyTrivialRange = 0;
+    FieldRange *FieldRangeSet::__multiKeyTrivialRange = 0;
+    FieldRange &FieldRangeSet::trivialRange() const {
+        FieldRange *&ret = _singleKey ? __singleKeyTrivialRange : __multiKeyTrivialRange;
+        if ( ret == 0 ) {
+            ret = new FieldRange( BSONObj().firstElement(), _singleKey, false, true );
+        }
+        return *ret;
     }
 
     BSONObj FieldRangeSet::simplifiedQuery( const BSONObj &_fields ) const {
@@ -926,17 +900,17 @@ namespace mongo {
         while( i.more() ) {
             BSONElement e = i.next();
             const char *name = e.fieldName();
-            const FieldRange &range = _ranges[ name ];
-            assert( !range.empty() );
-            if ( range.equality() )
-                b.appendAs( range.min(), name );
-            else if ( range.nontrivial() ) {
+            const FieldRange &eRange = range( name );
+            assert( !eRange.empty() );
+            if ( eRange.equality() )
+                b.appendAs( eRange.min(), name );
+            else if ( eRange.nontrivial() ) {
                 BSONObj o;
                 BSONObjBuilder c;
-                if ( range.min().type() != MinKey )
-                    c.appendAs( range.min(), range.minInclusive() ? "$gte" : "$gt" );
-                if ( range.max().type() != MaxKey )
-                    c.appendAs( range.max(), range.maxInclusive() ? "$lte" : "$lt" );
+                if ( eRange.min().type() != MinKey )
+                    c.appendAs( eRange.min(), eRange.minInclusive() ? "$gte" : "$gt" );
+                if ( eRange.max().type() != MaxKey )
+                    c.appendAs( eRange.max(), eRange.maxInclusive() ? "$lte" : "$lt" );
                 o = c.obj();
                 b.append( name, o );
             }
@@ -1034,18 +1008,111 @@ namespace mongo {
     }
 
     FieldRangeSet *FieldRangeSet::subset( const BSONObj &fields ) const {
-        FieldRangeSet *ret = new FieldRangeSet( _ns, BSONObj() );
+        FieldRangeSet *ret = new FieldRangeSet( _ns, BSONObj(), _singleKey, true );
         BSONObjIterator i( fields );
         while( i.more() ) {
             BSONElement e = i.next();
-            if ( _ranges[ e.fieldName() ].nontrivial() ) {
-                ret->_ranges[ e.fieldName() ] = _ranges[ e.fieldName() ];
+            if ( range( e.fieldName() ).nontrivial() ) {
+                ret->range( e.fieldName() ) = range( e.fieldName() );
             }
         }
         ret->_queries = _queries;
         return ret;
     }
+    
+    const FieldRangeSet &FieldRangeSetPair::frsForIndex( const NamespaceDetails* nsd, int idxNo ) const {
+        assertValidIndexOrNoIndex( nsd, idxNo );
+        if ( idxNo < 0 ) {
+            // An unindexed cursor cannot have a "single key" constraint.
+            return _multiKey;
+        }
+        return nsd->isMultikey( idxNo ) ? _multiKey : _singleKey;
+    }    
+
+    bool FieldRangeSetPair::noNontrivialRanges() const {
+        return _singleKey.matchPossible() && _singleKey.nNontrivialRanges() == 0 &&
+                 _multiKey.matchPossible() && _multiKey.nNontrivialRanges() == 0;
+    }
+    
+    bool FieldRangeSetPair::matchPossibleForIndex( NamespaceDetails *d, int idxNo ) const {
+        assertValidIndexOrNoIndex( d, idxNo );
+        if ( !matchPossible() ) {
+            return false;
+        }
+        if ( idxNo < 0 ) {
+            // multi key matchPossible() is true, so return true.
+            return true;   
+        }
+        return frsForIndex( d, idxNo ).matchPossibleForIndex( d->idx( idxNo ).keyPattern() );
+    }
+    
+    bool FieldRangeSetPair::indexUseful( NamespaceDetails *d, int idxNo, const BSONObj &order ) const {
+        assertValidIndex( d, idxNo );
+        if ( !matchPossibleForIndex( d, idxNo ) ) {
+            // No matches are possible in the index so the index may be useful.
+            return true;   
+        }
+        return d->idx( idxNo ).getSpec().suitability( simplifiedQueryForIndex( d, idxNo ), order ) != USELESS;
+    }
+    
+    void FieldRangeSetPair::clearIndexesForPatterns( const BSONObj &order ) const {
+        scoped_lock lk(NamespaceDetailsTransient::_qcMutex);
+        NamespaceDetailsTransient& nsd = NamespaceDetailsTransient::get_inlock( ns() );
+        nsd.registerIndexForPattern( _singleKey.pattern( order ), BSONObj(), 0 );
+        nsd.registerIndexForPattern( _multiKey.pattern( order ), BSONObj(), 0 );
+    }
+    
+    pair< BSONObj, long long > FieldRangeSetPair::bestIndexForPatterns( const BSONObj &order ) const {
+        scoped_lock lk(NamespaceDetailsTransient::_qcMutex);
+        NamespaceDetailsTransient& nsd = NamespaceDetailsTransient::get_inlock( ns() );
+        // TODO Maybe it would make sense to return the index with the lowest
+        // nscanned if there are two possibilities.
+        if ( _singleKey.matchPossible() ) {
+            QueryPattern pattern = _singleKey.pattern( order );
+            BSONObj oldIdx = nsd.indexForPattern( pattern );
+            if ( !oldIdx.isEmpty() ) {
+                long long oldNScanned = nsd.nScannedForPattern( pattern );
+                return make_pair( oldIdx, oldNScanned );
+            }
+        }
+        if ( _multiKey.matchPossible() ) {
+            QueryPattern pattern = _multiKey.pattern( order );
+            BSONObj oldIdx = nsd.indexForPattern( pattern );
+            if ( !oldIdx.isEmpty() ) {
+                long long oldNScanned = nsd.nScannedForPattern( pattern );
+                return make_pair( oldIdx, oldNScanned );
+            }
+        }
+        return make_pair( BSONObj(), 0 );
+    }
+    
+    FieldRangeSetPair &FieldRangeSetPair::operator&=( const FieldRangeSetPair &other ) {
+        _singleKey &= other._singleKey;
+        _multiKey &= other._multiKey;
+        return *this;
+    }
 
+    FieldRangeSetPair &FieldRangeSetPair::operator-=( const FieldRangeSet &scanned ) {
+        _singleKey -= scanned;
+        _multiKey -= scanned;
+        return *this;            
+    }    
+    
+    void FieldRangeSetPair::assertValidIndex( const NamespaceDetails *d, int idxNo ) const {
+        massert( 14029, "FieldRangeSetPair invalid index specified", idxNo >= 0 && idxNo < d->nIndexes );   
+    }
+    
+    void FieldRangeSetPair::assertValidIndexOrNoIndex( const NamespaceDetails *d, int idxNo ) const {
+        massert( 14030, "FieldRangeSetPair invalid index specified", idxNo >= -1 );
+        if ( idxNo >= 0 ) {
+            assertValidIndex( d, idxNo );   
+        }
+    }    
+    
+    BSONObj FieldRangeSetPair::simplifiedQueryForIndex( NamespaceDetails *d, int idxNo ) const {
+        return frsForIndex( d, idxNo ).simplifiedQuery( d->idx( idxNo ).keyPattern() );
+    }    
+    
     bool FieldRangeVector::matchesElement( const BSONElement &e, int i, bool forward ) const {
         bool eq;
         int l = matchingLowElement( e, i, forward, eq );
@@ -1129,7 +1196,7 @@ namespace mongo {
     }
 
     // TODO optimize more
-    int FieldRangeVector::Iterator::advance( const BSONObj &curr ) {
+    int FieldRangeVectorIterator::advance( const BSONObj &curr ) {
         BSONObjIterator j( curr );
         BSONObjIterator o( _v._indexSpec.keyPattern );
         // track first field for which we are not at the end of the valid values,
@@ -1269,14 +1336,14 @@ namespace mongo {
         return -1;
     }
 
-    void FieldRangeVector::Iterator::prepDive() {
+    void FieldRangeVectorIterator::prepDive() {
         for( int j = 0; j < (int)_i.size(); ++j ) {
             _cmp[ j ] = &_v._ranges[ j ].intervals().front()._lower._bound;
             _inc[ j ] = _v._ranges[ j ].intervals().front()._lower._inclusive;
         }
     }
 
-    BSONObj FieldRangeVector::Iterator::startKey() {
+    BSONObj FieldRangeVectorIterator::startKey() {
         BSONObjBuilder b;
         for( int unsigned i = 0; i < _i.size(); ++i ) {
             const FieldInterval &fi = _v._ranges[ i ].intervals()[ _i[ i ] ];
@@ -1286,7 +1353,7 @@ namespace mongo {
     }
 
     // temp
-    BSONObj FieldRangeVector::Iterator::endKey() {
+    BSONObj FieldRangeVectorIterator::endKey() {
         BSONObjBuilder b;
         for( int unsigned i = 0; i < _i.size(); ++i ) {
             const FieldInterval &fi = _v._ranges[ i ].intervals()[ _i[ i ] ];
@@ -1298,7 +1365,7 @@ namespace mongo {
     FieldRangeOrSet::FieldRangeOrSet( const char *ns, const BSONObj &query , bool optimize )
     : _baseSet( ns, query, optimize ), _orFound() {
         
-        BSONObjIterator i( _baseSet._queries[ 0 ] );
+        BSONObjIterator i( _baseSet.originalQuery() );
         
         while( i.more() ) {
             BSONElement e = i.next();
@@ -1308,7 +1375,7 @@ namespace mongo {
                 while( j.more() ) {
                     BSONElement f = j.next();
                     massert( 13263, "$or array must contain objects", f.type() == Object );
-                    _orSets.push_back( FieldRangeSet( ns, f.embeddedObject(), optimize ) );
+                    _orSets.push_back( FieldRangeSetPair( ns, f.embeddedObject(), optimize ) );
                     massert( 13291, "$or may not contain 'special' query", _orSets.back().getSpecial().empty() );
                     _originalOrSets.push_back( _orSets.back() );
                 }
@@ -1317,6 +1384,28 @@ namespace mongo {
             }
         }
     }
+
+    void FieldRangeOrSet::assertMayPopOrClause() {
+        massert( 13274, "no or clause to pop", !orFinished() );        
+    }
+    
+    void FieldRangeOrSet::popOrClause( NamespaceDetails *nsd, int idxNo ) {
+        assertMayPopOrClause();
+        auto_ptr<FieldRangeSet> holder;
+        const FieldRangeSet *toDiff = &_originalOrSets.front().frsForIndex( nsd, idxNo );
+        BSONObj indexSpec = ( idxNo >= 0 ) ? nsd->idx( idxNo ).keyPattern() : BSONObj();
+        if ( !indexSpec.isEmpty() && toDiff->matchPossibleForIndex( indexSpec ) ) {
+            holder.reset( toDiff->subset( indexSpec ) );
+            toDiff = holder.get();
+        }
+        popOrClause( toDiff, nsd, idxNo );
+    }
+    
+    void FieldRangeOrSet::popOrClauseSingleKey() {
+        assertMayPopOrClause();
+        FieldRangeSet *toDiff = &_originalOrSets.front()._singleKey;
+        popOrClause( toDiff );
+    }
     
     /**
      * Removes the top or clause, which would have been recently scanned, and
@@ -1327,22 +1416,16 @@ namespace mongo {
      * clause.  Used to determine the range of keys that were scanned.  If
      * empty we do not constrain the previous clause's ranges using index keys,
      * which may reduce opportunities for range elimination.
-     */    
-    void FieldRangeOrSet::popOrClause( const BSONObj &indexSpec ) {
-        massert( 13274, "no or clause to pop", !orFinished() );
-        auto_ptr<FieldRangeSet> holder;
-        FieldRangeSet *toDiff = &_originalOrSets.front();
-        if ( toDiff->matchPossible() && !indexSpec.isEmpty() ) {
-            holder.reset( toDiff->subset( indexSpec ) );
-            toDiff = holder.get();
-        }
-        list<FieldRangeSet>::iterator i = _orSets.begin();
-        list<FieldRangeSet>::iterator j = _originalOrSets.begin();
+     */
+    void FieldRangeOrSet::popOrClause( const FieldRangeSet *toDiff, NamespaceDetails *d, int idxNo ) {
+        list<FieldRangeSetPair>::iterator i = _orSets.begin();
+        list<FieldRangeSetPair>::iterator j = _originalOrSets.begin();
         ++i;
         ++j;
         while( i != _orSets.end() ) {
             *i -= *toDiff;
-            if( !i->matchPossible() ) {
+            // Check if match is possible at all, and if it is possible for the recently scanned index.
+            if( !i->matchPossible() || ( d && !i->matchPossibleForIndex( d, idxNo ) ) ) {
                 i = _orSets.erase( i );
                 j = _originalOrSets.erase( j );
             }
@@ -1356,13 +1439,28 @@ namespace mongo {
         _originalOrSets.pop_front();
     }
     
-    void FieldRangeOrSet::allClausesSimplified( vector<BSONObj> &ret ) const {
-        for( list<FieldRangeSet>::const_iterator i = _orSets.begin(); i != _orSets.end(); ++i ) {
-            if ( i->matchPossible() ) {
-                ret.push_back( i->simplifiedQuery() );
+    bool FieldRangeOrSet::uselessOr( NamespaceDetails *d, int hintIdx ) const {
+        for( list<FieldRangeSetPair>::const_iterator i = _originalOrSets.begin(); i != _originalOrSets.end(); ++i ) {
+            if ( hintIdx != -1 ) {
+                if ( !i->indexUseful( d, hintIdx, BSONObj() ) ) {
+                    return true;   
+                }
+            }
+            else {
+                bool useful = false;
+                for( int j = 0; j < d->nIndexes; ++j ) {
+                    if ( i->indexUseful( d, j, BSONObj() ) ) {
+                        useful = true;
+                        break;
+                    }
+                }
+                if ( !useful ) {
+                    return true;
+                }
             }
         }
-    }    
+        return false;
+    }
     
     struct SimpleRegexUnitTest : UnitTest {
         void run() {
diff --git a/db/queryutil.h b/db/queryutil.h
index 01a2cdffa80..8a1d07cfa7e 100644
--- a/db/queryutil.h
+++ b/db/queryutil.h
@@ -61,7 +61,7 @@ namespace mongo {
      */
     class FieldRange {
     public:
-        FieldRange( const BSONElement &e = BSONObj().firstElement() , bool isNot=false , bool optimize=true );
+        FieldRange( const BSONElement &e , bool singleKey , bool isNot=false , bool optimize=true );
 
         /** @return Range intersection with 'other'. */
         const FieldRange &operator&=( const FieldRange &other );
@@ -107,39 +107,10 @@ namespace mongo {
         BSONObj addObj( const BSONObj &o );
         void finishOperation( const vector<FieldInterval> &newIntervals, const FieldRange &other );
         vector<FieldInterval> _intervals;
-        // BSONObj references to keep our BSONElement memory valid.
+        // Owns memory for our BSONElements.
         vector<BSONObj> _objData;
         string _special;
-    };
-
-    /**
-     * Implements query pattern matching, used to determine if a query is
-     * similar to an earlier query and should use the same plan.
-     *
-     * Two queries will generate the same QueryPattern, and therefore match each
-     * other, if their fields have the same Types and they have the same sort
-     * spec.
-     */
-    class QueryPattern {
-    public:
-        friend class FieldRangeSet;
-        enum Type {
-            Equality,
-            LowerBound,
-            UpperBound,
-            UpperAndLowerBound
-        };
-        bool operator<( const QueryPattern &other ) const;
-        /** for testing only */
-        bool operator==( const QueryPattern &other ) const;
-        /** for testing only */
-        bool operator!=( const QueryPattern &other ) const;
-    private:
-        QueryPattern() {}
-        void setSort( const BSONObj sort );
-        static BSONObj normalizeSort( const BSONObj &spec );
-        map<string,Type> _fieldTypes;
-        BSONObj _sort;
+        bool _singleKey;
     };
 
     /**
@@ -151,6 +122,8 @@ namespace mongo {
      */
     typedef vector<pair<BSONObj,BSONObj> > BoundList;
 
+    class QueryPattern;
+    
     /**
      * A set of FieldRanges determined from constraints on the fields of a query,
      * that may be used to determine index bounds.
@@ -159,7 +132,7 @@ namespace mongo {
     public:
         friend class FieldRangeOrSet;
         friend class FieldRangeVector;
-        FieldRangeSet( const char *ns, const BSONObj &query , bool optimize=true );
+        FieldRangeSet( const char *ns, const BSONObj &query , bool singleKey , bool optimize=true );
         
         /** @return true if there is a nontrivial range for the given field. */
         bool hasRange( const char *fieldName ) const {
@@ -172,10 +145,18 @@ namespace mongo {
         FieldRange &range( const char *fieldName );
         /** @return the number of nontrivial ranges. */
         int nNontrivialRanges() const;
-        /**
-         * @return true iff no FieldRanges are empty.
+        /** 
+         * @return true if a match could be possible on every field. Generally this
+         * is not useful information for a single key FieldRangeSet and
+         * matchPossibleForIndex() should be used instead.
          */
         bool matchPossible() const;
+        /**
+         * @return true if a match could be possible given the value of _singleKey
+         * and index key 'keyPattern'.
+         * @param keyPattern May be {} or {$natural:1} for a non index scan.
+         */
+        bool matchPossibleForIndex( const BSONObj &keyPattern ) const;
         
         const char *ns() const { return _ns; }
         
@@ -215,19 +196,97 @@ namespace mongo {
          * will be included in the returned FieldRangeSet.
          */
         FieldRangeSet *subset( const BSONObj &fields ) const;
+        
+        bool singleKey() const { return _singleKey; }
+        
+        BSONObj originalQuery() const { return _queries[ 0 ]; }
     private:
         void appendQueries( const FieldRangeSet &other );
         void makeEmpty();
         void processQueryField( const BSONElement &e, bool optimize );
         void processOpElement( const char *fieldName, const BSONElement &f, bool isNot, bool optimize );
-        static FieldRange *__trivialRange;
-        static FieldRange &trivialRange();
-        mutable map<string,FieldRange> _ranges;
+        static FieldRange *__singleKeyTrivialRange;
+        static FieldRange *__multiKeyTrivialRange;
+        FieldRange &trivialRange() const;
+        map<string,FieldRange> _ranges;
         const char *_ns;
-        // make sure memory for FieldRange BSONElements is owned
+        // Owns memory for FieldRange BSONElements.
         vector<BSONObj> _queries;
+        bool _singleKey;
     };
 
+    class NamespaceDetails;
+    
+    /**
+     * A pair of FieldRangeSets, one representing constraints for single key
+     * indexes and the other representing constraints for multi key indexes and
+     * unindexed scans.  In several member functions the caller is asked to
+     * supply an index so that the implementation may utilize the proper
+     * FieldRangeSet and return results that are appropriate with respect to the
+     * supplied index.
+     */
+    class FieldRangeSetPair {
+    public:
+        FieldRangeSetPair( const char *ns, const BSONObj &query, bool optimize=true )
+        :_singleKey( ns, query, true, optimize ), _multiKey( ns, query, false, optimize ) {}
+
+        /**
+         * @return the appropriate single or multi key FieldRangeSet for the specified index.
+         * @param idxNo -1 for non index scan.
+         */
+        const FieldRangeSet &frsForIndex( const NamespaceDetails* nsd, int idxNo ) const;
+
+        /** @return a field range in the single key FieldRangeSet. */
+        const FieldRange &singleKeyRange( const char *fieldName ) const {
+            return _singleKey.range( fieldName );
+        }
+        /** @return true if the range limits are equivalent to an empty query. */
+        bool noNontrivialRanges() const;
+        /** @return false if a match is impossible regardless of index. */
+        bool matchPossible() const { return _multiKey.matchPossible(); }
+        /**
+         * @return false if a match is impossible on the specified index.
+         * @param idxNo -1 for non index scan.
+         */
+        bool matchPossibleForIndex( NamespaceDetails *d, int idxNo ) const;
+        /** @return true if the index may be useful according to its KeySpec. */
+        bool indexUseful( NamespaceDetails *d, int idxNo, const BSONObj &order ) const;
+        
+        const char *ns() const { return _singleKey.ns(); }
+
+        /** Clear any indexes recorded as the best for either the single or multi key pattern. */
+        void clearIndexesForPatterns( const BSONObj &order ) const;
+        /** Return a recorded best index for the single or multi key pattern. */
+        pair< BSONObj, long long > bestIndexForPatterns( const BSONObj &order ) const;
+
+        string getSpecial() const { return _singleKey.getSpecial(); }
+
+        /** Intersect with another FieldRangeSetPair. */
+        FieldRangeSetPair &operator&=( const FieldRangeSetPair &other );
+        /**
+         * Subtract a FieldRangeSet, generally one expressing a range that has
+         * already been scanned.
+         */
+        FieldRangeSetPair &operator-=( const FieldRangeSet &scanned );
+
+        BoundList singleKeyIndexBounds( const BSONObj &keyPattern, int direction ) const {
+            return _singleKey.indexBounds( keyPattern, direction );
+        }
+        
+        BSONObj originalQuery() const { return _singleKey.originalQuery(); }
+
+    private:
+        FieldRangeSetPair( const FieldRangeSet &singleKey, const FieldRangeSet &multiKey )
+        :_singleKey( singleKey ), _multiKey( multiKey ) {}
+        void assertValidIndex( const NamespaceDetails *d, int idxNo ) const;
+        void assertValidIndexOrNoIndex( const NamespaceDetails *d, int idxNo ) const;
+        /** matchPossibleForIndex() must be true. */
+        BSONObj simplifiedQueryForIndex( NamespaceDetails *d, int idxNo ) const;        
+        FieldRangeSet _singleKey;
+        FieldRangeSet _multiKey;
+        friend class FieldRangeOrSet;
+    };
+    
     class IndexSpec;
 
     /**
@@ -260,50 +319,6 @@ namespace mongo {
          */
         bool matches( const BSONObj &obj ) const;
         
-        /**
-         * Helper class for iterating through an ordered representation of keys
-         * to find those keys that match a specified FieldRangeVector.
-         */
-        class Iterator {
-        public:
-            Iterator( const FieldRangeVector &v ) : _v( v ), _i( _v._ranges.size(), -1 ), _cmp( _v._ranges.size(), 0 ), _inc( _v._ranges.size(), false ), _after() {
-            }
-            static BSONObj minObject() {
-                BSONObjBuilder b; b.appendMinKey( "" );
-                return b.obj();
-            }
-            static BSONObj maxObject() {
-                BSONObjBuilder b; b.appendMaxKey( "" );
-                return b.obj();
-            }
-            /**
-             * @return Suggested advance method, based on current key.
-             *   -2 Iteration is complete, no need to advance.
-             *   -1 Advance to the next key, without skipping.
-             *  >=0 Skip parameter.  If @return is r, skip to the key comprised
-             *      of the first r elements of curr followed by the (r+1)th and
-             *      remaining elements of cmp() (with inclusivity specified by
-             *      the (r+1)th and remaining elements of inc()).  If after() is
-             *      true, skip past this key not to it.
-             */
-            int advance( const BSONObj &curr );
-            const vector<const BSONElement *> &cmp() const { return _cmp; }
-            const vector<bool> &inc() const { return _inc; }
-            bool after() const { return _after; }
-            void prepDive();
-            void setZero( int i ) { for( int j = i; j < (int)_i.size(); ++j ) _i[ j ] = 0; }
-            void setMinus( int i ) { for( int j = i; j < (int)_i.size(); ++j ) _i[ j ] = -1; }
-            bool ok() { return _i[ 0 ] < (int)_v._ranges[ 0 ].intervals().size(); }
-            BSONObj startKey();
-            // temp
-            BSONObj endKey();
-        private:
-            const FieldRangeVector &_v;
-            vector<int> _i;
-            vector<const BSONElement*> _cmp;
-            vector<bool> _inc;
-            bool _after;
-        };
     private:
         int matchingLowElement( const BSONElement &e, int i, bool direction, bool &lowEquality ) const;
         bool matchesElement( const BSONElement &e, int i, bool direction ) const;
@@ -311,10 +326,56 @@ namespace mongo {
         const IndexSpec &_indexSpec;
         int _direction;
         vector<BSONObj> _queries; // make sure mem owned
+        friend class FieldRangeVectorIterator;
     };
-
+    
+    /**
+     * Helper class for iterating through an ordered representation of keys
+     * to find those keys that match a specified FieldRangeVector.
+     */
+    class FieldRangeVectorIterator {
+    public:
+        FieldRangeVectorIterator( const FieldRangeVector &v ) : _v( v ), _i( _v._ranges.size(), -1 ), _cmp( _v._ranges.size(), 0 ), _inc( _v._ranges.size(), false ), _after() {
+        }
+        static BSONObj minObject() {
+            BSONObjBuilder b; b.appendMinKey( "" );
+            return b.obj();
+        }
+        static BSONObj maxObject() {
+            BSONObjBuilder b; b.appendMaxKey( "" );
+            return b.obj();
+        }
+        /**
+         * @return Suggested advance method, based on current key.
+         *   -2 Iteration is complete, no need to advance.
+         *   -1 Advance to the next key, without skipping.
+         *  >=0 Skip parameter.  If @return is r, skip to the key comprised
+         *      of the first r elements of curr followed by the (r+1)th and
+         *      remaining elements of cmp() (with inclusivity specified by
+         *      the (r+1)th and remaining elements of inc()).  If after() is
+         *      true, skip past this key not to it.
+         */
+        int advance( const BSONObj &curr );
+        const vector<const BSONElement *> &cmp() const { return _cmp; }
+        const vector<bool> &inc() const { return _inc; }
+        bool after() const { return _after; }
+        void prepDive();
+        void setZero( int i ) { for( int j = i; j < (int)_i.size(); ++j ) _i[ j ] = 0; }
+        void setMinus( int i ) { for( int j = i; j < (int)_i.size(); ++j ) _i[ j ] = -1; }
+        bool ok() { return _i[ 0 ] < (int)_v._ranges[ 0 ].intervals().size(); }
+        BSONObj startKey();
+        // temp
+        BSONObj endKey();
+    private:
+        const FieldRangeVector &_v;
+        vector<int> _i;
+        vector<const BSONElement*> _cmp;
+        vector<bool> _inc;
+        bool _after;
+    };
+    
     /**
-     * As we iterate through $or clauses this class generates a FieldRangeSet
+     * As we iterate through $or clauses this class generates a FieldRangeSetPair
      * for the current $or clause, in some cases by excluding ranges that were
      * included in a previous clause.
      */
@@ -328,28 +389,31 @@ namespace mongo {
          */
         bool orFinished() const { return _orFound && _orSets.empty(); }
         /** Iterates to the next $or clause by removing the current $or clause. */
-        void popOrClause( const BSONObj &indexSpec = BSONObj() );
-        /** @return FieldRangeSet for the current $or clause. */
-        FieldRangeSet *topFrs() const;
+        void popOrClause( NamespaceDetails *nsd, int idxNo );
+        void popOrClauseSingleKey();
+        /** @return FieldRangeSetPair for the current $or clause. */
+        FieldRangeSetPair *topFrsp() const;
         /**
-         * @return original FieldRangeSet for the current $or clause. While the
+         * @return original FieldRangeSetPair for the current $or clause. While the
          * original bounds are looser, they are composed of fewer ranges and it
          * is faster to do operations with them; when they can be used instead of
          * more precise bounds, they should.
          */
-        FieldRangeSet *topFrsOriginal() const;
+        FieldRangeSetPair *topFrspOriginal() const;
         
-        /** @ret a returned vector of simplified queries for all clauses. */
-        void allClausesSimplified( vector<BSONObj> &ret ) const;
         string getSpecial() const { return _baseSet.getSpecial(); }
 
         bool moreOrClauses() const { return !_orSets.empty(); }
+        
+        bool uselessOr( NamespaceDetails *d, int hintIdx ) const;
     private:
-        FieldRangeSet _baseSet;
-        list<FieldRangeSet> _orSets;
-        list<FieldRangeSet> _originalOrSets;
-        // make sure memory is owned
-        list<FieldRangeSet> _oldOrSets;
+        void assertMayPopOrClause();
+        void popOrClause( const FieldRangeSet *toDiff, NamespaceDetails *d = 0, int idxNo = -1 );
+        FieldRangeSetPair _baseSet;
+        list<FieldRangeSetPair> _orSets;
+        list<FieldRangeSetPair> _originalOrSets;
+        // ensure memory is owned
+        list<FieldRangeSetPair> _oldOrSets;
         bool _orFound;
     };