SERVER-5848 determine index suitability using a FieldRangeSet

Previously each special index type would determine the suitability
of the index by analyzing the original query.  To avoid re-parsing
the query for each index, we now pass in a FieldRangeSet, which is
a better representation of all the constraints implied by the query.

9 files changed, 45 insertions, 31 deletions

diff --git a/src/mongo/db/geo/2d.cpp b/src/mongo/db/geo/2d.cpp
index fa15e1aae7e..64e28b185c8 100644
--- a/src/mongo/db/geo/2d.cpp
+++ b/src/mongo/db/geo/2d.cpp
@@ -240,7 +240,10 @@ namespace mongo {
         virtual shared_ptr<Cursor> newCursor(const BSONObj& query, const BSONObj& order,
                                              int numWanted) const;
 
-        virtual IndexSuitability suitability(const BSONObj& query, const BSONObj& order) const {
+        virtual IndexSuitability suitability( const FieldRangeSet& queryConstraints ,
+                                              const BSONObj& order ) const {
+            BSONObj query = queryConstraints.originalQuery();
+
             BSONElement e = query.getFieldDotted(_geo.c_str());
             switch (e.type()) {
             case Object: {
diff --git a/src/mongo/db/geo/s2index.cpp b/src/mongo/db/geo/s2index.cpp
index 670f3801540..8ef1f221fe3 100644
--- a/src/mongo/db/geo/s2index.cpp
+++ b/src/mongo/db/geo/s2index.cpp
@@ -265,7 +265,10 @@ namespace mongo {
             }
         }
 
-        virtual IndexSuitability suitability(const BSONObj& query, const BSONObj& order) const {
+        virtual IndexSuitability suitability( const FieldRangeSet& queryConstraints ,
+                                              const BSONObj& order ) const {
+            BSONObj query = queryConstraints.originalQuery();
+
             for (size_t i = 0; i < _fields.size(); ++i) {
                 const IndexedField &field = _fields[i];
                 if (IndexedField::GEO != field.type) { continue; }
diff --git a/src/mongo/db/hashindex.cpp b/src/mongo/db/hashindex.cpp
index 8b981b91341..a1bb718063d 100644
--- a/src/mongo/db/hashindex.cpp
+++ b/src/mongo/db/hashindex.cpp
@@ -59,9 +59,9 @@ namespace mongo {
 
     HashedIndexType::~HashedIndexType() { }
 
-    IndexSuitability HashedIndexType::suitability( const BSONObj& query , const BSONObj& order ) const {
-        FieldRangeSet frs( "" , query , true, true );
-        if ( frs.isPointIntervalSet( _hashedField ) )
+    IndexSuitability HashedIndexType::suitability( const FieldRangeSet& queryConstraints ,
+                                                   const BSONObj& order ) const {
+        if ( queryConstraints.isPointIntervalSet( _hashedField ) )
             return HELPFUL;
         return USELESS;
     }
diff --git a/src/mongo/db/hashindex.h b/src/mongo/db/hashindex.h
index 5605654eed1..51bf82e1c0f 100644
--- a/src/mongo/db/hashindex.h
+++ b/src/mongo/db/hashindex.h
@@ -74,7 +74,8 @@ namespace mongo {
          *   {b : 3} USELESS
          *   {a : {$gt : 3}} USELESS
          */
-        IndexSuitability suitability( const BSONObj& query , const BSONObj& order ) const;
+        IndexSuitability suitability( const FieldRangeSet& queryConstraints ,
+                                      const BSONObj& order ) const;
 
         /* The input is "obj" which should have a field corresponding to the hashedfield.
          * The output is a BSONObj with a single BSONElement whose value is the hash
diff --git a/src/mongo/db/indexkey.cpp b/src/mongo/db/indexkey.cpp
index 56ce794919c..b6c48d83c34 100644
--- a/src/mongo/db/indexkey.cpp
+++ b/src/mongo/db/indexkey.cpp
@@ -23,6 +23,7 @@
 #include "../util/stringutils.h"
 #include "mongo/util/mongoutils/str.h"
 #include "../util/text.h"
+#include "mongo/db/queryutil.h"
 
 namespace mongo {
 
@@ -448,21 +449,25 @@ namespace mongo {
         return false;
     }
 
-    IndexSuitability IndexSpec::suitability( const BSONObj& query , const BSONObj& order ) const {
+    IndexSuitability IndexSpec::suitability( const FieldRangeSet& queryConstraints ,
+                                             const BSONObj& order ) const {
         if ( _indexType.get() )
-            return _indexType->suitability( query , order );
-        return _suitability( query , order );
+            return _indexType->suitability( queryConstraints , order );
+        return _suitability( queryConstraints , order );
     }
 
-    IndexSuitability IndexSpec::_suitability( const BSONObj& query , const BSONObj& order ) const {
+    IndexSuitability IndexSpec::_suitability( const FieldRangeSet& queryConstraints ,
+                                              const BSONObj& order ) const {
         // TODO: optimize
-        if ( anyElementNamesMatch( keyPattern , query ) == 0 && anyElementNamesMatch( keyPattern , order ) == 0 )
+        if ( ! anyElementNamesMatch( keyPattern , queryConstraints.simplifiedQuery(keyPattern) )  &&
+             ! anyElementNamesMatch( keyPattern , order ) )
             return USELESS;
         return HELPFUL;
     }
 
-    IndexSuitability IndexType::suitability( const BSONObj& query , const BSONObj& order ) const {
-        return _spec->_suitability( query , order );
+    IndexSuitability IndexType::suitability( const FieldRangeSet& queryConstraints ,
+                                             const BSONObj& order ) const {
+        return _spec->_suitability( queryConstraints , order );
     }
     
     int IndexSpec::indexVersion() const {
diff --git a/src/mongo/db/indexkey.h b/src/mongo/db/indexkey.h
index 1fea111980e..0dfac9d0679 100644
--- a/src/mongo/db/indexkey.h
+++ b/src/mongo/db/indexkey.h
@@ -34,6 +34,7 @@ namespace mongo {
     class IndexType; // TODO: this name sucks
     class IndexPlugin;
     class IndexDetails;
+    class FieldRangeSet;
 
     enum IndexSuitability { USELESS = 0 , HELPFUL = 1 , OPTIMAL = 2 };
 
@@ -62,7 +63,15 @@ namespace mongo {
 
         const BSONObj& keyPattern() const;
 
-        virtual IndexSuitability suitability( const BSONObj& query , const BSONObj& order ) const ;
+        /* Determines the suitability level of this index for answering a given query. The query is
+         * represented as a set of constraints given by a FieldRangeSet, and a desired ordering of
+         * the output.
+         *
+         * Note: it is the responsibility of the caller to pass in the correct FieldRangeSet, which
+         * may depend upon whether this is a single or multi-key index at the time of calling.
+         */
+        virtual IndexSuitability suitability( const FieldRangeSet& queryConstraints ,
+                                              const BSONObj& order ) const;
 
         virtual bool scanAndOrderRequired( const BSONObj& query , const BSONObj& order ) const ;
 
@@ -161,7 +170,8 @@ namespace mongo {
             return _details;
         }
 
-        IndexSuitability suitability( const BSONObj& query , const BSONObj& order ) const ;
+        IndexSuitability suitability( const FieldRangeSet& queryConstraints ,
+                                      const BSONObj& order ) const ;
 
         bool isSparse() const { return _sparse; }
 
@@ -171,7 +181,8 @@ namespace mongo {
 
         int indexVersion() const;
         
-        IndexSuitability _suitability( const BSONObj& query , const BSONObj& order ) const ;
+        IndexSuitability _suitability( const FieldRangeSet& queryConstraints ,
+                                       const BSONObj& order ) const ;
 
         BSONSizeTracker _sizeTracker;
         vector<const char*> _fieldNames;
diff --git a/src/mongo/db/queryoptimizer.cpp b/src/mongo/db/queryoptimizer.cpp
index ad563b9e218..f69a3907f53 100644
--- a/src/mongo/db/queryoptimizer.cpp
+++ b/src/mongo/db/queryoptimizer.cpp
@@ -139,7 +139,7 @@ namespace mongo {
         // 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( _originalQuery, _order ) != USELESS ) ) {
+             _index->getSpec().getType()->suitability( _frs, _order ) != USELESS ) ) {
 
             _type  = _index->getSpec().getType();
             if (_special.empty()) _special = _index->getSpec().getType()->getPlugin()->getName();
@@ -1009,8 +1009,8 @@ doneCheckOrder:
                 const IndexSpec& spec = ii.getSpec();
                 // TODO(hk): Make sure we can do a $near and $within query, one using
                 // the index one using the matcher.
-                if (special.has(spec.getTypeName())
-                    && spec.suitability( _qps.originalQuery(), _qps.order())) {
+                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;
@@ -1976,13 +1976,9 @@ doneCheckOrder:
             // No matches are possible in the index so the index may be useful.
             return true;   
         }
-        // Hashed index types can't use simplified query bounds, since they could turn equalities
-        // into ranges, e.g.{$in : [1,2] } into {$gte : 1 , $lte : 2}
-        // TODO: refactor suitability to take a FieldRangeSetPair, and get rid of this special case
-        // See SERVER-5858.
-        BSONObj query = ( d->idx( idxNo ).getSpec().getTypeName() == "hashed" ) ?
-                        frsp.originalQuery() : frsp.simplifiedQueryForIndex( d, idxNo, keyPattern );
-        return d->idx( idxNo ).getSpec().suitability( query, order ) != USELESS;
+
+        return d->idx( idxNo ).getSpec().suitability( frsp.frsForIndex( d , idxNo ) , order )
+               != USELESS;
     }
     
     void QueryUtilIndexed::clearIndexesForPatterns( const FieldRangeSetPair &frsp, const BSONObj &order ) {
diff --git a/src/mongo/db/queryutil.cpp b/src/mongo/db/queryutil.cpp
index 10450ee8e35..d801bb61f9c 100644
--- a/src/mongo/db/queryutil.cpp
+++ b/src/mongo/db/queryutil.cpp
@@ -1482,10 +1482,6 @@ namespace mongo {
                     ).jsonString();
     }
     
-    BSONObj FieldRangeSetPair::simplifiedQueryForIndex( NamespaceDetails *d, int idxNo, const BSONObj &keyPattern ) const {
-        return frsForIndex( d, idxNo ).simplifiedQuery( keyPattern );
-    }    
-    
     void FieldRangeSetPair::assertValidIndex( const NamespaceDetails *d, int idxNo ) const {
         massert( 14048, "FieldRangeSetPair invalid index specified", idxNo >= 0 && idxNo < d->nIndexes );   
     }
diff --git a/src/mongo/db/queryutil.h b/src/mongo/db/queryutil.h
index 67ad3ec34c1..8462819014c 100644
--- a/src/mongo/db/queryutil.h
+++ b/src/mongo/db/queryutil.h
@@ -645,7 +645,6 @@ 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 &keyPattern ) const;        
         FieldRangeSet _singleKey;
         FieldRangeSet _multiKey;
         friend class OrRangeGenerator;