SERVER-958 merge and address mongos dependency differences

7 files changed, 113 insertions, 102 deletions

diff --git a/db/oplog.cpp b/db/oplog.cpp
index 193fb0481cf..8676a88254b 100644
--- a/db/oplog.cpp
+++ b/db/oplog.cpp
@@ -407,7 +407,7 @@ namespace mongo {
         }
         switch( _findingStartMode ) {
             case Initial: {
-                if ( !_matcher->matches( _findingStartCursor->currKey(), _findingStartCursor->currLoc() ) ) {
+                if ( !_matcher->matchesCurrent( _findingStartCursor->c() ) ) {
                     _findingStart = false; // found first record out of query range, so scan normally
                     _c = _qp.newCursor( _findingStartCursor->currLoc() );
                     destroyClientCursor();
@@ -424,7 +424,7 @@ namespace mongo {
                 return;
             }
             case FindExtent: {
-                if ( !_matcher->matches( _findingStartCursor->currKey(), _findingStartCursor->currLoc() ) ) {
+                if ( !_matcher->matchesCurrent( _findingStartCursor->c() ) ) {
                     _findingStartMode = InExtent;
                     return;
                 }
@@ -440,7 +440,7 @@ namespace mongo {
                 return;
             }
             case InExtent: {
-                if ( _matcher->matches( _findingStartCursor->currKey(), _findingStartCursor->currLoc() ) ) {
+                if ( _matcher->matchesCurrent( _findingStartCursor->c() ) ) {
                     _findingStart = false; // found first record in query range, so scan normally
                     _c = _qp.newCursor( _findingStartCursor->currLoc() );
                     destroyClientCursor();
diff --git a/db/queryoptimizer.cpp b/db/queryoptimizer.cpp
index e4167d2f1b9..88418f802bb 100644
--- a/db/queryoptimizer.cpp
+++ b/db/queryoptimizer.cpp
@@ -430,7 +430,7 @@ doneCheckOrder:
         }
 
         if ( _honorRecordedPlan ) {
-            pair< BSONObj, long long > best = _frsp->bestIndexForPatterns( _order );
+            pair< BSONObj, long long > best = QueryUtilIndexed::bestIndexForPatterns( *_frsp, _order );
             BSONObj bestIndex = best.first;
             long long oldNScanned = best.second;
             if ( !bestIndex.isEmpty() ) {
@@ -483,14 +483,14 @@ doneCheckOrder:
         QueryPlanPtr optimalPlan;
         for( int i = 0; i < d->nIndexes; ++i ) {
             if ( normalQuery ) {
-                if ( !_frsp->matchPossibleForIndex( d, i ) ) {
+                if ( !_frsp->matchPossibleForIndex( d, i, d->idx( i ).keyPattern() ) ) {
                     // 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 ) ) {
+                if ( !QueryUtilIndexed::indexUseful( *_frsp, d, i, _order ) ) {
                     continue;
                 }
             }
@@ -523,7 +523,7 @@ doneCheckOrder:
             // _plans.size() > 1 if addOtherPlans was called in Runner::run().
             if ( _bestGuessOnly || res->complete() || _plans.size() > 1 )
                 return res;
-            _frsp->clearIndexesForPatterns( _order );
+            QueryUtilIndexed::clearIndexesForPatterns( *_frsp, _order );
             init();
         }
         Runner r( *this, op );
@@ -783,7 +783,7 @@ doneCheckOrder:
         if ( ret->qp().willScanTable() ) {
             _tableScanned = true;
         }
-        _fros.popOrClause( ret->qp().nsd(), ret->qp().idxNo() );
+        _fros.popOrClause( ret->qp().nsd(), ret->qp().idxNo(), ret->qp().indexed() ? ret->qp().indexKey() : BSONObj() );
         return ret;
     }
 
@@ -805,9 +805,9 @@ doneCheckOrder:
             if ( !id ) {
                 return true;
             }
-            return _fros.uselessOr( nsd, nsd->idxNo( *id ) );
+            return QueryUtilIndexed::uselessOr( _fros, nsd, nsd->idxNo( *id ) );
         }
-        return _fros.uselessOr( nsd, -1 );        
+        return QueryUtilIndexed::uselessOr( _fros, nsd, -1 );
     }
     
     MultiCursor::MultiCursor( const char *ns, const BSONObj &pattern, const BSONObj &order, shared_ptr<CursorOp> op, bool mayYield )
@@ -1034,4 +1034,67 @@ doneCheckOrder:
         }
     }
 
+    bool QueryUtilIndexed::indexUseful( const FieldRangeSetPair &frsp, NamespaceDetails *d, int idxNo, const BSONObj &order ) {
+        frsp.assertValidIndex( d, idxNo );
+        if ( !frsp.matchPossibleForIndex( d, idxNo, d->idx( idxNo ).keyPattern() ) ) {
+            // No matches are possible in the index so the index may be useful.
+            return true;   
+        }
+        return d->idx( idxNo ).getSpec().suitability( frsp.simplifiedQueryForIndex( d, idxNo, d->idx( idxNo ).keyPattern() ), order ) != USELESS;
+    }
+    
+    void QueryUtilIndexed::clearIndexesForPatterns( const FieldRangeSetPair &frsp, const BSONObj &order ) {
+        scoped_lock lk(NamespaceDetailsTransient::_qcMutex);
+        NamespaceDetailsTransient& nsd = NamespaceDetailsTransient::get_inlock( frsp.ns() );
+        nsd.registerIndexForPattern( frsp._singleKey.pattern( order ), BSONObj(), 0 );
+        nsd.registerIndexForPattern( frsp._multiKey.pattern( order ), BSONObj(), 0 );
+    }
+    
+    pair< BSONObj, long long > QueryUtilIndexed::bestIndexForPatterns( const FieldRangeSetPair &frsp, const BSONObj &order ) {
+        scoped_lock lk(NamespaceDetailsTransient::_qcMutex);
+        NamespaceDetailsTransient& nsd = NamespaceDetailsTransient::get_inlock( frsp.ns() );
+        // TODO Maybe it would make sense to return the index with the lowest
+        // nscanned if there are two possibilities.
+        if ( frsp._singleKey.matchPossible() ) {
+            QueryPattern pattern = frsp._singleKey.pattern( order );
+            BSONObj oldIdx = nsd.indexForPattern( pattern );
+            if ( !oldIdx.isEmpty() ) {
+                long long oldNScanned = nsd.nScannedForPattern( pattern );
+                return make_pair( oldIdx, oldNScanned );
+            }
+        }
+        if ( frsp._multiKey.matchPossible() ) {
+            QueryPattern pattern = frsp._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 );
+    }    
+    
+    bool QueryUtilIndexed::uselessOr( const FieldRangeOrSet &fros, NamespaceDetails *d, int hintIdx ) {
+        for( list<FieldRangeSetPair>::const_iterator i = fros._originalOrSets.begin(); i != fros._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
diff --git a/db/queryoptimizer.h b/db/queryoptimizer.h
index c88ab34c450..ae9cf7e30a1 100644
--- a/db/queryoptimizer.h
+++ b/db/queryoptimizer.h
@@ -433,4 +433,21 @@ namespace mongo {
      */
     shared_ptr<Cursor> bestGuessCursor( const char *ns, const BSONObj &query, const BSONObj &sort );
 
+    /**
+     * Add-on functionality for queryutil classes requiring access to indexing
+     * functionality not currently linked to mongos.
+     * TODO Clean this up a bit, possibly with separate sharded and non sharded
+     * implementations for the appropriate queryutil classes or by pulling index
+     * related functionality into separate wrapper classes.
+     */
+    struct QueryUtilIndexed {
+        /** @return true if the index may be useful according to its KeySpec. */
+        static bool indexUseful( const FieldRangeSetPair &frsp, NamespaceDetails *d, int idxNo, const BSONObj &order );
+        /** Clear any indexes recorded as the best for either the single or multi key pattern. */
+        static void clearIndexesForPatterns( const FieldRangeSetPair &frsp, const BSONObj &order );
+        /** Return a recorded best index for the single or multi key pattern. */
+        static pair< BSONObj, long long > bestIndexForPatterns( const FieldRangeSetPair &frsp, const BSONObj &order );        
+        static bool uselessOr( const FieldRangeOrSet& fros, NamespaceDetails *d, int hintIdx );
+    };
+    
 } // namespace mongo
diff --git a/db/queryutil.cpp b/db/queryutil.cpp
index 45502db8573..c2a941ac875 100644
--- a/db/queryutil.cpp
+++ b/db/queryutil.cpp
@@ -1034,7 +1034,7 @@ namespace mongo {
                  _multiKey.matchPossible() && _multiKey.nNontrivialRanges() == 0;
     }
     
-    bool FieldRangeSetPair::matchPossibleForIndex( NamespaceDetails *d, int idxNo ) const {
+    bool FieldRangeSetPair::matchPossibleForIndex( NamespaceDetails *d, int idxNo, const BSONObj &keyPattern ) const {
         assertValidIndexOrNoIndex( d, idxNo );
         if ( !matchPossible() ) {
             return false;
@@ -1043,47 +1043,7 @@ namespace mongo {
             // 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 );
+        return frsForIndex( d, idxNo ).matchPossibleForIndex( keyPattern );
     }
     
     FieldRangeSetPair &FieldRangeSetPair::operator&=( const FieldRangeSetPair &other ) {
@@ -1099,18 +1059,18 @@ namespace mongo {
     }    
     
     void FieldRangeSetPair::assertValidIndex( const NamespaceDetails *d, int idxNo ) const {
-        massert( 14029, "FieldRangeSetPair invalid index specified", idxNo >= 0 && idxNo < d->nIndexes );   
+        massert( 14048, "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 );
+        massert( 14049, "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() );
+    BSONObj FieldRangeSetPair::simplifiedQueryForIndex( NamespaceDetails *d, int idxNo, const BSONObj &keyPattern ) const {
+        return frsForIndex( d, idxNo ).simplifiedQuery( keyPattern );
     }    
     
     bool FieldRangeVector::matchesElement( const BSONElement &e, int i, bool forward ) const {
@@ -1389,16 +1349,16 @@ namespace mongo {
         massert( 13274, "no or clause to pop", !orFinished() );        
     }
     
-    void FieldRangeOrSet::popOrClause( NamespaceDetails *nsd, int idxNo ) {
+    void FieldRangeOrSet::popOrClause( NamespaceDetails *nsd, int idxNo, const BSONObj &keyPattern ) {
         assertMayPopOrClause();
         auto_ptr<FieldRangeSet> holder;
         const FieldRangeSet *toDiff = &_originalOrSets.front().frsForIndex( nsd, idxNo );
-        BSONObj indexSpec = ( idxNo >= 0 ) ? nsd->idx( idxNo ).keyPattern() : BSONObj();
+        BSONObj indexSpec = keyPattern;
         if ( !indexSpec.isEmpty() && toDiff->matchPossibleForIndex( indexSpec ) ) {
             holder.reset( toDiff->subset( indexSpec ) );
             toDiff = holder.get();
         }
-        popOrClause( toDiff, nsd, idxNo );
+        popOrClause( toDiff, nsd, idxNo, keyPattern );
     }
     
     void FieldRangeOrSet::popOrClauseSingleKey() {
@@ -1417,7 +1377,7 @@ namespace mongo {
      * empty we do not constrain the previous clause's ranges using index keys,
      * which may reduce opportunities for range elimination.
      */
-    void FieldRangeOrSet::popOrClause( const FieldRangeSet *toDiff, NamespaceDetails *d, int idxNo ) {
+    void FieldRangeOrSet::popOrClause( const FieldRangeSet *toDiff, NamespaceDetails *d, int idxNo, const BSONObj &keyPattern ) {
         list<FieldRangeSetPair>::iterator i = _orSets.begin();
         list<FieldRangeSetPair>::iterator j = _originalOrSets.begin();
         ++i;
@@ -1425,7 +1385,7 @@ namespace mongo {
         while( i != _orSets.end() ) {
             *i -= *toDiff;
             // 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 ) ) ) {
+            if( !i->matchPossible() || ( d && !i->matchPossibleForIndex( d, idxNo, keyPattern ) ) ) {
                 i = _orSets.erase( i );
                 j = _originalOrSets.erase( j );
             }
@@ -1439,29 +1399,6 @@ namespace mongo {
         _originalOrSets.pop_front();
     }
     
-    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 8a1d07cfa7e..99a6b874254 100644
--- a/db/queryutil.h
+++ b/db/queryutil.h
@@ -248,17 +248,10 @@ namespace mongo {
          * @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;
+        bool matchPossibleForIndex( NamespaceDetails *d, int idxNo, const BSONObj &keyPattern ) 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. */
@@ -281,10 +274,11 @@ namespace mongo {
         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;        
+        BSONObj simplifiedQueryForIndex( NamespaceDetails *d, int idxNo, const BSONObj &keyPattern ) const;        
         FieldRangeSet _singleKey;
         FieldRangeSet _multiKey;
         friend class FieldRangeOrSet;
+        friend class QueryUtilIndexed;
     };
     
     class IndexSpec;
@@ -389,7 +383,7 @@ namespace mongo {
          */
         bool orFinished() const { return _orFound && _orSets.empty(); }
         /** Iterates to the next $or clause by removing the current $or clause. */
-        void popOrClause( NamespaceDetails *nsd, int idxNo );
+        void popOrClause( NamespaceDetails *nsd, int idxNo, const BSONObj &keyPattern );
         void popOrClauseSingleKey();
         /** @return FieldRangeSetPair for the current $or clause. */
         FieldRangeSetPair *topFrsp() const;
@@ -404,17 +398,16 @@ namespace mongo {
         string getSpecial() const { return _baseSet.getSpecial(); }
 
         bool moreOrClauses() const { return !_orSets.empty(); }
-        
-        bool uselessOr( NamespaceDetails *d, int hintIdx ) const;
     private:
         void assertMayPopOrClause();
-        void popOrClause( const FieldRangeSet *toDiff, NamespaceDetails *d = 0, int idxNo = -1 );
+        void popOrClause( const FieldRangeSet *toDiff, NamespaceDetails *d = 0, int idxNo = -1, const BSONObj &keyPattern = BSONObj() );
         FieldRangeSetPair _baseSet;
         list<FieldRangeSetPair> _orSets;
         list<FieldRangeSetPair> _originalOrSets;
         // ensure memory is owned
         list<FieldRangeSetPair> _oldOrSets;
         bool _orFound;
+        friend class QueryUtilIndexed;
     };
 
     /** returns a string that when used as a matcher, would match a super set of regex()
diff --git a/dbtests/queryoptimizertests.cpp b/dbtests/queryoptimizertests.cpp
index b58d9296905..b5cf2acb982 100644
--- a/dbtests/queryoptimizertests.cpp
+++ b/dbtests/queryoptimizertests.cpp
@@ -879,12 +879,12 @@ namespace QueryOptimizerTests {
                 IndexBase::client_.insert( ns(), BSON( "a" << BSON_ARRAY( 1 << 2 ) << "b" << 1 ) );
                 // Valid ranges match possible for both indexes.
                 FieldRangeSetPair frsp1( ns(), BSON( "a" << GT << 1 << LT << 4 << "b" << GT << 1 << LT << 4 ) );
-                ASSERT( frsp1.matchPossibleForIndex( nsd(), a ) );
-                ASSERT( frsp1.matchPossibleForIndex( nsd(), b ) );
+                ASSERT( frsp1.matchPossibleForIndex( nsd(), a, BSON( "a" << 1 ) ) );
+                ASSERT( frsp1.matchPossibleForIndex( nsd(), b, BSON( "b" << 1 ) ) );
                 // Single key invalid range means match impossible for single key index.
                 FieldRangeSetPair frsp2( ns(), BSON( "a" << GT << 4 << LT << 1 << "b" << GT << 4 << LT << 1 ) );
-                ASSERT( frsp2.matchPossibleForIndex( nsd(), a ) );
-                ASSERT( !frsp2.matchPossibleForIndex( nsd(), b ) );
+                ASSERT( frsp2.matchPossibleForIndex( nsd(), a, BSON( "a" << 1 ) ) );
+                ASSERT( !frsp2.matchPossibleForIndex( nsd(), b, BSON( "b" << 1 ) ) );
             }
         };
         
@@ -1538,7 +1538,7 @@ namespace QueryOptimizerTests {
                 QueryPlanSet s( ns(), frsp, frspOrig, BSON( "a" << 4 ), BSON( "b" << 1 ) );
                 ScanOnlyTestOp op;
                 s.runOp( op );
-                pair< BSONObj, long long > best = s.frsp().bestIndexForPatterns( BSON( "b" << 1 ) );
+                pair< BSONObj, long long > best = QueryUtilIndexed::bestIndexForPatterns( s.frsp(), BSON( "b" << 1 ) );
                 ASSERT( fromjson( "{$natural:1}" ).woCompare( best.first ) == 0 );
                 ASSERT_EQUALS( 1, best.second );
 
diff --git a/s/commands_public.cpp b/s/commands_public.cpp
index 5d2c8ef66ce..e8bab9e155d 100644
--- a/s/commands_public.cpp
+++ b/s/commands_public.cpp
@@ -24,6 +24,7 @@
 #include "../client/parallel.h"
 #include "../db/commands.h"
 #include "../db/query.h"
+#include "../db/queryutil.h"
 
 #include "config.h"
 #include "chunk.h"