SERVER-100 checkpoint field range organization improvements

6 files changed, 175 insertions, 163 deletions

diff --git a/db/queryoptimizer.cpp b/db/queryoptimizer.cpp
index 2d6d7033506..f2b03e9cd33 100644
--- a/db/queryoptimizer.cpp
+++ b/db/queryoptimizer.cpp
@@ -33,7 +33,7 @@ namespace mongo {
     
     QueryPlan::QueryPlan( 
         NamespaceDetails *_d, int _idxNo,
-        const FieldBoundSet &fbs, const BSONObj &order, const BSONObj &startKey, const BSONObj &endKey ) :
+        const FieldRangeSet &fbs, const BSONObj &order, const BSONObj &startKey, const BSONObj &endKey ) :
     d(_d), idxNo(_idxNo),
     fbs_( fbs ),
     order_( order ),
@@ -76,7 +76,7 @@ namespace mongo {
                     goto doneCheckOrder;
                 if ( strcmp( oe.fieldName(), ke.fieldName() ) == 0 )
                     break;
-                if ( !fbs.bound( ke.fieldName() ).equality() )
+                if ( !fbs.range( ke.fieldName() ).equality() )
                     goto doneCheckOrder;
             }
             int d = elementDirection( oe ) == elementDirection( ke ) ? 1 : -1;
@@ -100,11 +100,11 @@ namespace mongo {
             BSONElement e = i.next();
             if ( e.eoo() )
                 break;
-            const FieldBound &fb = fbs.bound( e.fieldName() );
+            const FieldRange &fb = fbs.range( e.fieldName() );
             int number = (int) e.number(); // returns 0.0 if not numeric
             bool forward = ( ( number >= 0 ? 1 : -1 ) * ( direction_ >= 0 ? 1 : -1 ) > 0 );
-            startKeyBuilder.appendAs( forward ? fb.lower() : fb.upper(), "" );
-            endKeyBuilder.appendAs( forward ? fb.upper() : fb.lower(), "" );
+            startKeyBuilder.appendAs( forward ? fb.min() : fb.max(), "" );
+            endKeyBuilder.appendAs( forward ? fb.max() : fb.min(), "" );
             if ( stillOptimalIndexedQueryCount ) {
                 if ( fb.nontrivial() )
                     ++optimalIndexedQueryCount;
@@ -115,16 +115,16 @@ namespace mongo {
                     optimalIndexedQueryCount = -1;
             }
             if ( fb.equality() ) {
-                BSONElement e = fb.upper();
+                BSONElement e = fb.max();
                 if ( !e.isNumber() && !e.mayEncapsulate() && e.type() != RegEx )
                     ++exactIndexedQueryCount;
             }
             orderFieldsUnindexed.erase( e.fieldName() );
         }
         if ( !scanAndOrderRequired_ &&
-             ( optimalIndexedQueryCount == fbs.nNontrivialBounds() ) )
+             ( optimalIndexedQueryCount == fbs.nNontrivialRanges() ) )
             optimal_ = true;
-        if ( exactIndexedQueryCount == fbs.nNontrivialBounds() &&
+        if ( exactIndexedQueryCount == fbs.nNontrivialRanges() &&
             orderFieldsUnindexed.size() == 0 &&
             exactIndexedQueryCount == index_->keyPattern().nFields() &&
             exactIndexedQueryCount == fbs.query().nFields() ) {
@@ -135,7 +135,7 @@ namespace mongo {
         if ( endKey_.isEmpty() )
             endKey_ = endKeyBuilder.obj();
         if ( ( scanAndOrderRequired_ || order_.isEmpty() ) &&
-            !fbs.bound( idxKey.firstElement().fieldName() ).nontrivial() )
+            !fbs.range( idxKey.firstElement().fieldName() ).nontrivial() )
             unhelpful_ = true;
     }
     
@@ -289,7 +289,7 @@ namespace mongo {
             return;
 
         // If table scan is optimal or natural order requested
-        if ( ( fbs_.nNontrivialBounds() == 0 && order_.isEmpty() ) ||
+        if ( ( fbs_.nNontrivialRanges() == 0 && order_.isEmpty() ) ||
             ( !order_.isEmpty() && !strcmp( order_.firstElement().fieldName(), "$natural" ) ) ) {
             // Table scan plan
             addPlan( PlanPtr( new QueryPlan( d, -1, fbs_, order_ ) ), checkFirst );
diff --git a/db/queryoptimizer.h b/db/queryoptimizer.h
index ceb50ff2404..651cd0e0b7a 100644
--- a/db/queryoptimizer.h
+++ b/db/queryoptimizer.h
@@ -29,12 +29,11 @@ namespace mongo {
     public:
         QueryPlan(NamespaceDetails *_d, 
                   int _idxNo, // -1 = no index
-                  const FieldBoundSet &fbs,
+                  const FieldRangeSet &fbs,
                   const BSONObj &order,
                   const BSONObj &startKey = BSONObj(),
                   const BSONObj &endKey = BSONObj() );
 
-//        QueryPlan( const QueryPlan &other );
         /* If true, no other index can do better. */
         bool optimal() const { return optimal_; }
         /* ScanAndOrder processing will be required if true */
@@ -55,12 +54,12 @@ namespace mongo {
         const char *ns() const { return fbs_.ns(); }
         BSONObj query() const { return fbs_.query(); }
         BSONObj simplifiedQuery( const BSONObj& fields = BSONObj() ) const { return fbs_.simplifiedQuery( fields ); }
-        const FieldBound &bound( const char *fieldName ) const { return fbs_.bound( fieldName ); }
+        const FieldRange &range( const char *fieldName ) const { return fbs_.range( fieldName ); }
         void registerSelf( long long nScanned ) const;
     private:
         NamespaceDetails *d;
         int idxNo;
-        const FieldBoundSet &fbs_;
+        const FieldRangeSet &fbs_;
         const BSONObj &order_;
         const IndexDetails *index_;
         bool optimal_;
@@ -120,7 +119,7 @@ namespace mongo {
         shared_ptr< T > runOp( T &op ) {
             return dynamic_pointer_cast< T >( runOp( static_cast< QueryOp& >( op ) ) );
         }
-        const FieldBoundSet &fbs() const { return fbs_; }
+        const FieldRangeSet &fbs() const { return fbs_; }
         BSONObj explain() const;
         bool usingPrerecordedPlan() const { return usingPrerecordedPlan_; }
     private:
@@ -143,7 +142,7 @@ namespace mongo {
             static void nextOp( QueryOp &op );
         };
         const char *ns;
-        FieldBoundSet fbs_;
+        FieldRangeSet fbs_;
         PlanSet plans_;
         bool mayRecordPlan_;
         bool usingPrerecordedPlan_;
diff --git a/db/queryutil.cpp b/db/queryutil.cpp
index bb9b544b110..ed05a083e0d 100644
--- a/db/queryutil.cpp
+++ b/db/queryutil.cpp
@@ -24,36 +24,36 @@
 
 namespace mongo {
 
-    FieldBound::FieldBound( const BSONElement &e , bool optimize ) :
-    lower_( minKey.firstElement() ),
-    lowerInclusive_( true ),
-    upper_( maxKey.firstElement() ),
-    upperInclusive_( true ) {
+    FieldRange::FieldRange( const BSONElement &e, bool optimize ) {
+        lower() = minKey.firstElement();
+        lowerInclusive() = true;
+        upper() = maxKey.firstElement();
+        upperInclusive() = true;
         if ( e.eoo() )
             return;
         if ( e.type() == RegEx ) {
             const char *r = e.simpleRegex();
             if ( r ) {
-                lower_ = addObj( BSON( "" << r ) ).firstElement();
-                upper_ = addObj( BSON( "" << simpleRegexEnd( r ) ) ).firstElement();
-                upperInclusive_ = false;
+                lower() = addObj( BSON( "" << r ) ).firstElement();
+                upper() = addObj( BSON( "" << simpleRegexEnd( r ) ) ).firstElement();
+                upperInclusive() = false;
             }            
             return;
         }
         switch( e.getGtLtOp() ) {
             case BSONObj::Equality:
-                lower_ = e;
-                upper_ = e;
+                lower() = e;
+                upper() = e;
                 break;
             case BSONObj::LT:
-                upperInclusive_ = false;
+                upperInclusive() = false;
             case BSONObj::LTE:
-                upper_ = e;
+                upper() = e;
                 break;
             case BSONObj::GT:
-                lowerInclusive_ = false;
+                lowerInclusive() = false;
             case BSONObj::GTE:
-                lower_ = e;
+                lower() = e;
                 break;
 	    case BSONObj::opALL: {
 	        massert( "$all requires array", e.type() == Array );
@@ -61,7 +61,7 @@ namespace mongo {
 		if ( i.moreWithEOO() ) {
  		    BSONElement f = i.next();
 		    if ( !f.eoo() )
-		      lower_ = upper_ = f;
+                        lower() = upper() = f;
 		}
 		break;
 	    }
@@ -79,62 +79,62 @@ namespace mongo {
                     if ( min.woCompare( f, false ) > 0 )
                         min = f;
                 }
-                lower_ = min;
-                upper_ = max;
+                lower() = min;
+                upper() = max;
             }
             default:
                 break;
         }
         
         if ( optimize ){
-            if ( lower_.type() != MinKey && upper_.type() == MaxKey && lower_.isSimpleType() ){ // TODO: get rid of isSimpleType
+            if ( lower().type() != MinKey && upper().type() == MaxKey && lower().isSimpleType() ){ // TODO: get rid of isSimpleType
                 BSONObjBuilder b;
-                b.appendMaxForType( lower_.fieldName() , lower_.type() );
-                upper_ = addObj( b.obj() ).firstElement();
+                b.appendMaxForType( lower().fieldName() , lower().type() );
+                upper() = addObj( b.obj() ).firstElement();
             }
-            else if ( lower_.type() == MinKey && upper_.type() != MaxKey && upper_.isSimpleType() ){ // TODO: get rid of isSimpleType
+            else if ( lower().type() == MinKey && upper().type() != MaxKey && upper().isSimpleType() ){ // TODO: get rid of isSimpleType
                 BSONObjBuilder b;
-                b.appendMinForType( upper_.fieldName() , upper_.type() );
-                lower_ = addObj( b.obj() ).firstElement();
+                b.appendMinForType( upper().fieldName() , upper().type() );
+                lower() = addObj( b.obj() ).firstElement();
             }
         }
 
     }
     
-    const FieldBound &FieldBound::operator&=( const FieldBound &other ) {
+    const FieldRange &FieldRange::operator&=( const FieldRange &other ) {
         int cmp;
-        cmp = other.upper_.woCompare( upper_, false );
+        cmp = other.max().woCompare( upper(), false );
         if ( cmp == 0 )
-            if ( !other.upperInclusive_ )
-                upperInclusive_ = false;
+            if ( !other.maxInclusive() )
+                upperInclusive() = false;
         if ( cmp < 0 ) {
-            upper_ = other.upper_;
-            upperInclusive_ = other.upperInclusive_;
+            upper() = other.max();
+            upperInclusive() = other.maxInclusive();
         }
-        cmp = other.lower_.woCompare( lower_, false );
+        cmp = other.min().woCompare( lower(), false );
         if ( cmp == 0 )
-            if ( !other.lowerInclusive_ )
-                lowerInclusive_ = false;
+            if ( !other.minInclusive() )
+                lowerInclusive() = false;
         if ( cmp > 0 ) {
-            lower_ = other.lower_;
-            lowerInclusive_ = other.lowerInclusive_;
+            lower() = other.min();
+            lowerInclusive() = other.minInclusive();
         }
         for( vector< BSONObj >::const_iterator i = other.objData_.begin(); i != other.objData_.end(); ++i )
             objData_.push_back( *i );
         return *this;
     }
     
-    string FieldBound::simpleRegexEnd( string regex ) {
+    string FieldRange::simpleRegexEnd( string regex ) {
         ++regex[ regex.length() - 1 ];
         return regex;
     }    
     
-    BSONObj FieldBound::addObj( const BSONObj &o ) {
+    BSONObj FieldRange::addObj( const BSONObj &o ) {
         objData_.push_back( o );
         return o;
     }
     
-    FieldBoundSet::FieldBoundSet( const char *ns, const BSONObj &query , bool optimize ) :
+    FieldRangeSet::FieldRangeSet( const char *ns, const BSONObj &query , bool optimize ) :
     ns_( ns ),
     query_( query.getOwned() ) {
         BSONObjIterator i( query_ );
@@ -145,7 +145,7 @@ namespace mongo {
             if ( strcmp( e.fieldName(), "$where" ) == 0 )
                 continue;
             if ( getGtLtOp( e ) == BSONObj::Equality ) {
-                bounds_[ e.fieldName() ] &= FieldBound( e , optimize );
+                ranges_[ e.fieldName() ] &= FieldRange( e , optimize );
             }
             else {
                 BSONObjIterator i( e.embeddedObject() );
@@ -153,24 +153,24 @@ namespace mongo {
                     BSONElement f = i.next();
                     if ( f.eoo() )
                         break;
-                    bounds_[ e.fieldName() ] &= FieldBound( f , optimize );
+                    ranges_[ e.fieldName() ] &= FieldRange( f , optimize );
                 }                
             }
         }
     }
     
-    FieldBound *FieldBoundSet::trivialBound_ = 0;
-    FieldBound &FieldBoundSet::trivialBound() {
-        if ( trivialBound_ == 0 )
-            trivialBound_ = new FieldBound();
-        return *trivialBound_;
+    FieldRange *FieldRangeSet::trivialRange_ = 0;
+    FieldRange &FieldRangeSet::trivialRange() {
+        if ( trivialRange_ == 0 )
+            trivialRange_ = new FieldRange();
+        return *trivialRange_;
     }
     
-    BSONObj FieldBoundSet::simplifiedQuery( const BSONObj &_fields ) const {
+    BSONObj FieldRangeSet::simplifiedQuery( const BSONObj &_fields ) const {
         BSONObj fields = _fields;
         if ( fields.isEmpty() ) {
             BSONObjBuilder b;
-            for( map< string, FieldBound >::const_iterator i = bounds_.begin(); i != bounds_.end(); ++i ) {
+            for( map< string, FieldRange >::const_iterator i = ranges_.begin(); i != ranges_.end(); ++i ) {
                 b.append( i->first.c_str(), 1 );
             }
             fields = b.obj();
@@ -182,29 +182,29 @@ namespace mongo {
             if ( e.eoo() )
                 break;
             const char *name = e.fieldName();
-            const FieldBound &bound = bounds_[ name ];
-            if ( bound.equality() )
-                b.appendAs( bound.lower(), name );
-            else if ( bound.nontrivial() ) {
+            const FieldRange &range = ranges_[ name ];
+            if ( range.equality() )
+                b.appendAs( range.min(), name );
+            else if ( range.nontrivial() ) {
                 BSONObjBuilder c;
-                if ( bound.lower().type() != MinKey )
-                    c.appendAs( bound.lower(), bound.lowerInclusive() ? "$gte" : "$gt" );
-                if ( bound.upper().type() != MaxKey )
-                    c.appendAs( bound.upper(), bound.upperInclusive() ? "$lte" : "$lt" );
+                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" );
                 b.append( name, c.done() );                
             }
         }
         return b.obj();
     }
     
-    QueryPattern FieldBoundSet::pattern( const BSONObj &sort ) const {
+    QueryPattern FieldRangeSet::pattern( const BSONObj &sort ) const {
         QueryPattern qp;
-        for( map< string, FieldBound >::const_iterator i = bounds_.begin(); i != bounds_.end(); ++i ) {
+        for( map< string, FieldRange >::const_iterator i = ranges_.begin(); i != ranges_.end(); ++i ) {
             if ( i->second.equality() ) {
                 qp.fieldTypes_[ i->first ] = QueryPattern::Equality;
             } else if ( i->second.nontrivial() ) {
-                bool upper = i->second.upper().type() != MaxKey;
-                bool lower = i->second.lower().type() != MinKey;
+                bool upper = i->second.max().type() != MaxKey;
+                bool lower = i->second.min().type() != MinKey;
                 if ( upper && lower )
                     qp.fieldTypes_[ i->first ] = QueryPattern::UpperAndLowerBound;
                 else if ( upper )
diff --git a/db/queryutil.h b/db/queryutil.h
index 5b925622081..35a2267a2bc 100644
--- a/db/queryutil.h
+++ b/db/queryutil.h
@@ -22,34 +22,47 @@
 
 namespace mongo {
 
-    // bounds on a field's value that may be determined from query -- used to
+    struct FieldBound {
+        BSONElement bound_;
+        bool inclusive_;
+    };
+
+    struct FieldInterval {
+        FieldBound lower_;
+        FieldBound upper_;
+    };
+
+    // range of a field's value that may be determined from query -- used to
     // determine index limits
-    class FieldBound {
+    class FieldRange {
     public:
-        FieldBound( const BSONElement &e = BSONObj().firstElement() , bool optimize=true );
-        const FieldBound &operator&=( const FieldBound &other );
-        BSONElement lower() const { return lower_; }
-        BSONElement upper() const { return upper_; }
-        bool lowerInclusive() const { return lowerInclusive_; }
-        bool upperInclusive() const { return upperInclusive_; }
+        FieldRange( const BSONElement &e = BSONObj().firstElement() , bool optimize=true );
+        const FieldRange &operator&=( const FieldRange &other );
+        BSONElement min() const { return interval_.lower_.bound_; }
+        BSONElement max() const { return interval_.upper_.bound_; }
+        bool minInclusive() const { return interval_.lower_.inclusive_; }
+        bool maxInclusive() const { return interval_.upper_.inclusive_; }
         bool equality() const {
             return
-            lower_.woCompare( upper_, false ) == 0 &&
-            upperInclusive_ &&
-            lowerInclusive_;
+                min().woCompare( max(), false ) == 0 &&
+                maxInclusive() &&
+                minInclusive();
         }
         bool nontrivial() const {
             return
-            minKey.firstElement().woCompare( lower_, false ) != 0 ||
-            maxKey.firstElement().woCompare( upper_, false ) != 0;
+                minKey.firstElement().woCompare( min(), false ) != 0 ||
+                maxKey.firstElement().woCompare( max(), false ) != 0;
         }
     private:
+        // towards replacing interval_ with a set of intervals
+        BSONElement &lower() { return interval_.lower_.bound_; }
+        BSONElement &upper() { return interval_.upper_.bound_; }
+        bool &lowerInclusive() { return interval_.lower_.inclusive_; }
+        bool &upperInclusive() { return interval_.upper_.inclusive_; }
+
         BSONObj addObj( const BSONObj &o );
         string simpleRegexEnd( string regex );
-        BSONElement lower_;
-        bool lowerInclusive_;
-        BSONElement upper_;
-        bool upperInclusive_;
+        FieldInterval interval_;
         vector< BSONObj > objData_;
     };
     
@@ -57,7 +70,7 @@ namespace mongo {
     // similar to an earlier query and should use the same plan
     class QueryPattern {
     public:
-        friend class FieldBoundSet;
+        friend class FieldRangeSet;
         enum Type {
             Equality,
             LowerBound,
@@ -118,20 +131,20 @@ namespace mongo {
         BSONObj sort_;
     };
     
-    // bounds on fields' value that may be determined from query -- used to
+    // ranges of fields' value that may be determined from query -- used to
     // determine index limits
-    class FieldBoundSet {
+    class FieldRangeSet {
     public:
-        FieldBoundSet( const char *ns, const BSONObj &query , bool optimize=true );
-        const FieldBound &bound( const char *fieldName ) const {
-            map< string, FieldBound >::const_iterator f = bounds_.find( fieldName );
-            if ( f == bounds_.end() )
-                return trivialBound();
+        FieldRangeSet( const char *ns, const BSONObj &query , bool optimize=true );
+        const FieldRange &range( const char *fieldName ) const {
+            map< string, FieldRange >::const_iterator f = ranges_.find( fieldName );
+            if ( f == ranges_.end() )
+                return trivialRange();
             return f->second;
         }
-        int nNontrivialBounds() const {
+        int nNontrivialRanges() const {
             int count = 0;
-            for( map< string, FieldBound >::const_iterator i = bounds_.begin(); i != bounds_.end(); ++i )
+            for( map< string, FieldRange >::const_iterator i = ranges_.begin(); i != ranges_.end(); ++i )
                 if ( i->second.nontrivial() )
                     ++count;
             return count;
@@ -141,16 +154,16 @@ namespace mongo {
         // if fields is specified, order fields of returned object to match those of 'fields'
         BSONObj simplifiedQuery( const BSONObj &fields = BSONObj() ) const;
         bool matchPossible() const {
-            for( map< string, FieldBound >::const_iterator i = bounds_.begin(); i != bounds_.end(); ++i )
-                if ( i->second.lower().woCompare( i->second.upper(), false ) > 0 )
+            for( map< string, FieldRange >::const_iterator i = ranges_.begin(); i != ranges_.end(); ++i )
+                if ( i->second.min().woCompare( i->second.max(), false ) > 0 )
                     return false;
             return true;
         }
         QueryPattern pattern( const BSONObj &sort = BSONObj() ) const;
     private:
-        static FieldBound *trivialBound_;
-        static FieldBound &trivialBound();
-        mutable map< string, FieldBound > bounds_;
+        static FieldRange *trivialRange_;
+        static FieldRange &trivialRange();
+        mutable map< string, FieldRange > ranges_;
         const char *ns_;
         BSONObj query_;
     };
diff --git a/dbtests/queryoptimizertests.cpp b/dbtests/queryoptimizertests.cpp
index 61ad92a5f6e..85ffade8f5a 100644
--- a/dbtests/queryoptimizertests.cpp
+++ b/dbtests/queryoptimizertests.cpp
@@ -32,16 +32,16 @@ namespace mongo {
 
 namespace QueryOptimizerTests {
 
-    namespace FieldBoundTests {
+    namespace FieldRangeTests {
         class Base {
         public:
             virtual ~Base() {}
             void run() {
-                FieldBoundSet s( "ns", query() );
-                checkElt( lower(), s.bound( "a" ).lower() );
-                checkElt( upper(), s.bound( "a" ).upper() );
-                ASSERT_EQUALS( lowerInclusive(), s.bound( "a" ).lowerInclusive() );
-                ASSERT_EQUALS( upperInclusive(), s.bound( "a" ).upperInclusive() );
+                FieldRangeSet s( "ns", query() );
+                checkElt( lower(), s.range( "a" ).min() );
+                checkElt( upper(), s.range( "a" ).max() );
+                ASSERT_EQUALS( lowerInclusive(), s.range( "a" ).minInclusive() );
+                ASSERT_EQUALS( upperInclusive(), s.range( "a" ).maxInclusive() );
             }
         protected:
             virtual BSONObj query() = 0;
@@ -133,7 +133,7 @@ namespace QueryOptimizerTests {
         class EqGteInvalid {
         public:
             void run() {
-                FieldBoundSet fbs( "ns", BSON( "a" << 1 << "a" << GTE << 2 ) );
+                FieldRangeSet fbs( "ns", BSON( "a" << 1 << "a" << GTE << 2 ) );
                 ASSERT( !fbs.matchPossible() );
             }
         };        
@@ -185,25 +185,25 @@ namespace QueryOptimizerTests {
         class Equality {
         public:
             void run() {
-                FieldBoundSet s( "ns", BSON( "a" << 1 ) );
-                ASSERT( s.bound( "a" ).equality() );
-                FieldBoundSet s2( "ns", BSON( "a" << GTE << 1 << LTE << 1 ) );
-                ASSERT( s2.bound( "a" ).equality() );
-                FieldBoundSet s3( "ns", BSON( "a" << GT << 1 << LTE << 1 ) );
-                ASSERT( !s3.bound( "a" ).equality() );
-                FieldBoundSet s4( "ns", BSON( "a" << GTE << 1 << LT << 1 ) );
-                ASSERT( !s4.bound( "a" ).equality() );
-                FieldBoundSet s5( "ns", BSON( "a" << GTE << 1 << LTE << 1 << GT << 1 ) );
-                ASSERT( !s5.bound( "a" ).equality() );
-                FieldBoundSet s6( "ns", BSON( "a" << GTE << 1 << LTE << 1 << LT << 1 ) );
-                ASSERT( !s6.bound( "a" ).equality() );
+                FieldRangeSet s( "ns", BSON( "a" << 1 ) );
+                ASSERT( s.range( "a" ).equality() );
+                FieldRangeSet s2( "ns", BSON( "a" << GTE << 1 << LTE << 1 ) );
+                ASSERT( s2.range( "a" ).equality() );
+                FieldRangeSet s3( "ns", BSON( "a" << GT << 1 << LTE << 1 ) );
+                ASSERT( !s3.range( "a" ).equality() );
+                FieldRangeSet s4( "ns", BSON( "a" << GTE << 1 << LT << 1 ) );
+                ASSERT( !s4.range( "a" ).equality() );
+                FieldRangeSet s5( "ns", BSON( "a" << GTE << 1 << LTE << 1 << GT << 1 ) );
+                ASSERT( !s5.range( "a" ).equality() );
+                FieldRangeSet s6( "ns", BSON( "a" << GTE << 1 << LTE << 1 << LT << 1 ) );
+                ASSERT( !s6.range( "a" ).equality() );
             }
         };
         
         class SimplifiedQuery {
         public:
             void run() {
-                FieldBoundSet fbs( "ns", BSON( "a" << GT << 1 << GT << 5 << LT << 10 << "b" << 4 << "c" << LT << 4 << LT << 6 << "d" << GTE << 0 << GT << 0 << "e" << GTE << 0 << LTE << 10 ) );
+                FieldRangeSet fbs( "ns", BSON( "a" << GT << 1 << GT << 5 << LT << 10 << "b" << 4 << "c" << LT << 4 << LT << 6 << "d" << GTE << 0 << GT << 0 << "e" << GTE << 0 << LTE << 10 ) );
                 BSONObj simple = fbs.simplifiedQuery();
                 cout << "simple: " << simple << endl;
                 ASSERT( !simple.getObjectField( "a" ).woCompare( fromjson( "{$gt:5,$lt:10}" ) ) );
@@ -236,27 +236,27 @@ namespace QueryOptimizerTests {
             }
         private:
             static QueryPattern p( const BSONObj &query, const BSONObj &sort = BSONObj() ) {
-                return FieldBoundSet( "", query ).pattern( sort );
+                return FieldRangeSet( "", query ).pattern( sort );
             }
         };
         
         class NoWhere {
         public:
             void run() {
-                ASSERT_EQUALS( 0, FieldBoundSet( "ns", BSON( "$where" << 1 ) ).nNontrivialBounds() );
+                ASSERT_EQUALS( 0, FieldRangeSet( "ns", BSON( "$where" << 1 ) ).nNontrivialRanges() );
             }
         };
         
         class Numeric {
         public:
             void run() {
-                FieldBoundSet f( "", BSON( "a" << 1 ) );
-                ASSERT( f.bound( "a" ).lower().woCompare( BSON( "a" << 2.0 ).firstElement() ) < 0 );
-                ASSERT( f.bound( "a" ).lower().woCompare( BSON( "a" << 0.0 ).firstElement() ) > 0 );
+                FieldRangeSet f( "", BSON( "a" << 1 ) );
+                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 2.0 ).firstElement() ) < 0 );
+                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 0.0 ).firstElement() ) > 0 );
             }
         };
         
-    } // namespace FieldBoundTests
+    } // namespace FieldRangeTests
     
     namespace QueryPlanTests {
         class Base {
@@ -302,8 +302,8 @@ namespace QueryOptimizerTests {
         // There's a limit of 10 indexes total, make sure not to exceed this in a given test.
 #define INDEXNO(x) nsd()->idxNo( *this->index( BSON(x) ) )
 #define INDEX(x) this->index( BSON(x) )
-        auto_ptr< FieldBoundSet > FieldBoundSet_GLOBAL;
-#define FBS(x) ( FieldBoundSet_GLOBAL.reset( new FieldBoundSet( ns(), x ) ), *FieldBoundSet_GLOBAL )
+        auto_ptr< FieldRangeSet > FieldRangeSet_GLOBAL;
+#define FBS(x) ( FieldRangeSet_GLOBAL.reset( new FieldRangeSet( ns(), x ) ), *FieldRangeSet_GLOBAL )
         
         class NoIndex : public Base {
         public:
@@ -512,17 +512,17 @@ namespace QueryOptimizerTests {
         public:
             void run() {
                 QueryPlan p( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "b" << 1 ) ), BSONObj() );
-                ASSERT( !p.bound( "a" ).nontrivial() );
+                ASSERT( !p.range( "a" ).nontrivial() );
                 ASSERT( p.unhelpful() );
                 QueryPlan p2( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "b" << 1 << "c" << 1 ) ), BSON( "a" << 1 ) );
                 ASSERT( !p2.scanAndOrderRequired() );
-                ASSERT( !p2.bound( "a" ).nontrivial() );
+                ASSERT( !p2.range( "a" ).nontrivial() );
                 ASSERT( !p2.unhelpful() );
                 QueryPlan p3( nsd(), INDEXNO( "b" << 1 ), FBS( BSON( "b" << 1 << "c" << 1 ) ), BSONObj() );
-                ASSERT( p3.bound( "b" ).nontrivial() );
+                ASSERT( p3.range( "b" ).nontrivial() );
                 ASSERT( !p3.unhelpful() );
                 QueryPlan p4( nsd(), INDEXNO( "b" << 1 << "c" << 1 ), FBS( BSON( "c" << 1 << "d" << 1 ) ), BSONObj() );
-                ASSERT( !p4.bound( "b" ).nontrivial() );
+                ASSERT( !p4.range( "b" ).nontrivial() );
                 ASSERT( p4.unhelpful() );
             }
         };
@@ -909,8 +909,8 @@ namespace QueryOptimizerTests {
                 BSONObj one = BSON( "a" << 1 );
                 theDataFileMgr.insert( ns(), one );
                 deleteObjects( ns(), BSON( "a" << 1 ), false );
-                ASSERT( BSON( "a" << 1 ).woCompare( NamespaceDetailsTransient::get( ns() ).indexForPattern( FieldBoundSet( ns(), BSON( "a" << 1 ) ).pattern() ) ) == 0 );
-                ASSERT_EQUALS( 2, NamespaceDetailsTransient::get( ns() ).nScannedForPattern( FieldBoundSet( ns(), BSON( "a" << 1 ) ).pattern() ) );
+                ASSERT( BSON( "a" << 1 ).woCompare( NamespaceDetailsTransient::get( ns() ).indexForPattern( FieldRangeSet( ns(), BSON( "a" << 1 ) ).pattern() ) ) == 0 );
+                ASSERT_EQUALS( 2, NamespaceDetailsTransient::get( ns() ).nScannedForPattern( FieldRangeSet( ns(), BSON( "a" << 1 ) ).pattern() ) );
             }
         };
         
@@ -961,13 +961,13 @@ namespace QueryOptimizerTests {
                 assembleRequest( ns(), QUERY( "b" << 0 << "a" << GTE << 0 ).obj, 2, 0, 0, 0, m );
                 stringstream ss;
                 runQuery( m, ss );
-                ASSERT( BSON( "$natural" << 1 ).woCompare( NamespaceDetailsTransient::get( ns() ).indexForPattern( FieldBoundSet( ns(), BSON( "b" << 0 << "a" << GTE << 0 ) ).pattern() ) ) == 0 );
+                ASSERT( BSON( "$natural" << 1 ).woCompare( NamespaceDetailsTransient::get( ns() ).indexForPattern( FieldRangeSet( ns(), BSON( "b" << 0 << "a" << GTE << 0 ) ).pattern() ) ) == 0 );
                 
                 Message m2;
                 assembleRequest( ns(), QUERY( "b" << 99 << "a" << GTE << 0 ).obj, 2, 0, 0, 0, m2 );
                 runQuery( m2, ss );
-                ASSERT( BSON( "a" << 1 ).woCompare( NamespaceDetailsTransient::get( ns() ).indexForPattern( FieldBoundSet( ns(), BSON( "b" << 0 << "a" << GTE << 0 ) ).pattern() ) ) == 0 );                
-                ASSERT_EQUALS( 2, NamespaceDetailsTransient::get( ns() ).nScannedForPattern( FieldBoundSet( ns(), BSON( "b" << 0 << "a" << GTE << 0 ) ).pattern() ) );
+                ASSERT( BSON( "a" << 1 ).woCompare( NamespaceDetailsTransient::get( ns() ).indexForPattern( FieldRangeSet( ns(), BSON( "b" << 0 << "a" << GTE << 0 ) ).pattern() ) ) == 0 );                
+                ASSERT_EQUALS( 2, NamespaceDetailsTransient::get( ns() ).nScannedForPattern( FieldRangeSet( ns(), BSON( "b" << 0 << "a" << GTE << 0 ) ).pattern() ) );
             }
         };
         
@@ -976,25 +976,25 @@ namespace QueryOptimizerTests {
     class All : public Suite {
     public:
         All() {
-            add< FieldBoundTests::Empty >();
-            add< FieldBoundTests::Eq >();
-            add< FieldBoundTests::DupEq >();
-            add< FieldBoundTests::Lt >();
-            add< FieldBoundTests::Lte >();
-            add< FieldBoundTests::Gt >();
-            add< FieldBoundTests::Gte >();
-            add< FieldBoundTests::TwoLt >();
-            add< FieldBoundTests::TwoGt >();
-            add< FieldBoundTests::EqGte >();
-            add< FieldBoundTests::EqGteInvalid >();
-            add< FieldBoundTests::Regex >();
-            add< FieldBoundTests::UnhelpfulRegex >();
-            add< FieldBoundTests::In >();
-            add< FieldBoundTests::Equality >();
-            add< FieldBoundTests::SimplifiedQuery >();
-            add< FieldBoundTests::QueryPatternTest >();
-            add< FieldBoundTests::NoWhere >();
-            add< FieldBoundTests::Numeric >();
+            add< FieldRangeTests::Empty >();
+            add< FieldRangeTests::Eq >();
+            add< FieldRangeTests::DupEq >();
+            add< FieldRangeTests::Lt >();
+            add< FieldRangeTests::Lte >();
+            add< FieldRangeTests::Gt >();
+            add< FieldRangeTests::Gte >();
+            add< FieldRangeTests::TwoLt >();
+            add< FieldRangeTests::TwoGt >();
+            add< FieldRangeTests::EqGte >();
+            add< FieldRangeTests::EqGteInvalid >();
+            add< FieldRangeTests::Regex >();
+            add< FieldRangeTests::UnhelpfulRegex >();
+            add< FieldRangeTests::In >();
+            add< FieldRangeTests::Equality >();
+            add< FieldRangeTests::SimplifiedQuery >();
+            add< FieldRangeTests::QueryPatternTest >();
+            add< FieldRangeTests::NoWhere >();
+            add< FieldRangeTests::Numeric >();
             add< QueryPlanTests::NoIndex >();
             add< QueryPlanTests::SimpleOrder >();
             add< QueryPlanTests::MoreIndexThanNeeded >();
diff --git a/s/cursors.cpp b/s/cursors.cpp
index 22400113f38..6da8744431e 100644
--- a/s/cursors.cpp
+++ b/s/cursors.cpp
@@ -80,7 +80,7 @@ namespace mongo {
         b.appendElements( filter );
         b.appendElements( extra );
         
-        FieldBoundSet s( "wrong" , b.obj() , false );
+        FieldRangeSet s( "wrong" , b.obj() , false );
         return s.simplifiedQuery();
     }