SERVER-1026 handle stacked constraints from in clauses

4 files changed, 92 insertions, 26 deletions

diff --git a/db/queryutil.cpp b/db/queryutil.cpp
index c9107b361ba..09eefb1db28 100644
--- a/db/queryutil.cpp
+++ b/db/queryutil.cpp
@@ -746,38 +746,50 @@ namespace mongo {
     }
     
     BoundList FieldRangeSet::indexBounds( const BSONObj &keyPattern, int direction ) const {
-        BSONObjBuilder equalityBuilder;
         typedef vector< pair< shared_ptr< BSONObjBuilder >, shared_ptr< BSONObjBuilder > > > BoundBuilders;
         BoundBuilders builders;
+        builders.push_back( make_pair( shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ), shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ) ) );        
         BSONObjIterator i( keyPattern );
+        bool ineq = false; // until ineq is true, we are just dealing with equality and $in bounds
         while( i.more() ) {
             BSONElement e = i.next();
             const FieldRange &fr = 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 );
-            if ( builders.empty() ) {
+            if ( !ineq ) {
                 if ( fr.equality() ) {
-                    equalityBuilder.appendAs( fr.min(), "" );
+                    for( BoundBuilders::const_iterator j = builders.begin(); j != builders.end(); ++j ) {
+                        j->first->appendAs( fr.min(), "" );
+                        j->second->appendAs( fr.min(), "" );
+                    }
                 } else {
-                    BSONObj equalityObj = equalityBuilder.done();
+                    if ( !fr.inQuery() ) {
+                        ineq = true;
+                    }
+                    BoundBuilders newBuilders;
                     const vector< FieldInterval > &intervals = fr.intervals();
-                    if ( forward ) {
-                        for( vector< FieldInterval >::const_iterator j = intervals.begin(); j != intervals.end(); ++j ) {
-                            builders.push_back( make_pair( shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ), shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ) ) );
-                            builders.back().first->appendElements( equalityObj );
-                            builders.back().second->appendElements( equalityObj );
-                            builders.back().first->appendAs( j->_lower._bound, "" );
-                            builders.back().second->appendAs( j->_upper._bound, "" );
+                    for( BoundBuilders::const_iterator i = builders.begin(); i != builders.end(); ++i ) {
+                        BSONObj first = i->first->obj();
+                        BSONObj second = i->second->obj();
+                        if ( forward ) {
+                            for( vector< FieldInterval >::const_iterator j = intervals.begin(); j != intervals.end(); ++j ) {
+                                newBuilders.push_back( make_pair( shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ), shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ) ) );
+                                newBuilders.back().first->appendElements( first );
+                                newBuilders.back().second->appendElements( second );
+                                newBuilders.back().first->appendAs( j->_lower._bound, "" );
+                                newBuilders.back().second->appendAs( j->_upper._bound, "" );
+                            }
+                        } else {
+                            for( vector< FieldInterval >::const_reverse_iterator j = intervals.rbegin(); j != intervals.rend(); ++j ) {
+                                newBuilders.push_back( make_pair( shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ), shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ) ) );
+                                newBuilders.back().first->appendElements( first );
+                                newBuilders.back().second->appendElements( second );
+                                newBuilders.back().first->appendAs( j->_upper._bound, "" );
+                                newBuilders.back().second->appendAs( j->_lower._bound, "" );
+                            }
                         }
-                    } else {
-                        for( vector< FieldInterval >::const_reverse_iterator j = intervals.rbegin(); j != intervals.rend(); ++j ) {
-                            builders.push_back( make_pair( shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ), shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ) ) );
-                            builders.back().first->appendElements( equalityObj );
-                            builders.back().second->appendElements( equalityObj );
-                            builders.back().first->appendAs( j->_upper._bound, "" );
-                            builders.back().second->appendAs( j->_lower._bound, "" );
-                        }                       
                     }
+                    builders = newBuilders;
                 }
             } else {
                 for( BoundBuilders::const_iterator j = builders.begin(); j != builders.end(); ++j ) {
@@ -786,13 +798,6 @@ namespace mongo {
                 }
             }
         }
-        if ( builders.empty() ) {
-            BSONObj equalityObj = equalityBuilder.done();
-            assert( !equalityObj.isEmpty() );
-            builders.push_back( make_pair( shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ), shared_ptr< BSONObjBuilder >( new BSONObjBuilder() ) ) );
-            builders.back().first->appendElements( equalityObj );
-            builders.back().second->appendElements( equalityObj );            
-        }
         BoundList ret;
         for( BoundBuilders::const_iterator i = builders.begin(); i != builders.end(); ++i )
             ret.push_back( make_pair( i->first->obj(), i->second->obj() ) );
diff --git a/db/queryutil.h b/db/queryutil.h
index ee616b69211..593823d05a4 100644
--- a/db/queryutil.h
+++ b/db/queryutil.h
@@ -67,6 +67,17 @@ namespace mongo {
                 maxInclusive() &&
                 minInclusive();
         }
+        bool inQuery() const {
+            if ( equality() ) {
+                return true;
+            }
+            for( vector< FieldInterval >::const_iterator i = _intervals.begin(); i != _intervals.end(); ++i ) {            
+                if ( !i->equality() ) {
+                    return false;
+                }
+            }
+            return true;
+        }
         bool nontrivial() const {
             return
                 ! empty() && 
diff --git a/jstests/in4.js b/jstests/in4.js
new file mode 100644
index 00000000000..b763d7f8e51
--- /dev/null
+++ b/jstests/in4.js
@@ -0,0 +1,48 @@
+t = db.jstests_in4;
+
+function checkRanges( a, b ) {
+    expectedCount = a;
+    r = b;
+//    printjson( r );
+    assert.eq.automsg( "expectedCount", "r.length" );
+    for( i in r ) {
+        assert.eq.automsg( "r[ i ][ 0 ]", "r[ i ][ 1 ]" );
+    }
+}
+
+t.drop();
+t.ensureIndex( {a:1,b:1} );
+checkRanges( 1, t.find( {a:2,b:3} ).explain().indexBounds );
+checkRanges( 2, t.find( {a:{$in:[2,3]},b:4} ).explain().indexBounds );
+checkRanges( 2, t.find( {a:2,b:{$in:[3,4]}} ).explain().indexBounds );
+checkRanges( 4, t.find( {a:{$in:[2,3]},b:{$in:[4,5]}} ).explain().indexBounds );
+
+assert.eq.automsg( "2", "t.find( {a:{$in:[2,3]},b:{$gt:4,$lt:10}} ).explain().indexBounds.length" );
+
+t.save( {a:1,b:1} );
+t.save( {a:2,b:4.5} );
+t.save( {a:2,b:4} );
+assert.eq.automsg( "1", "t.find( {a:{$in:[2,3]},b:{$in:[4,5]}} ).explain().nscanned" );
+assert.eq.automsg( "2", "t.findOne( {a:{$in:[2,3]},b:{$in:[4,5]}} ).a" );
+assert.eq.automsg( "4", "t.findOne( {a:{$in:[2,3]},b:{$in:[4,5]}} ).b" );
+
+t.drop();
+t.ensureIndex( {a:1,b:1,c:1} );
+checkRanges( 2, t.find( {a:2,b:{$in:[3,4]},c:5} ).explain().indexBounds );
+
+t.save( {a:2,b:3,c:5} );
+t.save( {a:2,b:3,c:4} );
+assert.eq.automsg( "1", "t.find( {a:2,b:{$in:[3,4]},c:5} ).explain().nscanned" );
+t.remove();
+t.save( {a:2,b:4,c:5} );
+t.save( {a:2,b:4,c:4} );
+assert.eq.automsg( "1", "t.find( {a:2,b:{$in:[3,4]},c:5} ).explain().nscanned" );
+
+t.drop();
+t.ensureIndex( {a:1,b:-1} );
+ib = t.find( {a:2,b:{$in:[3,4]}} ).explain().indexBounds;
+checkRanges( 2, ib );
+assert.automsg( "ib[ 0 ][ 0 ].b > ib[ 1 ][ 0 ].b" );
+ib = t.find( {a:2,b:{$in:[3,4]}} ).sort( {a:-1,b:1} ).explain().indexBounds;
+checkRanges( 2, ib );
+assert.automsg( "ib[ 0 ][ 0 ].b < ib[ 1 ][ 0 ].b" );
\ No newline at end of file
diff --git a/mongo.xcodeproj/project.pbxproj b/mongo.xcodeproj/project.pbxproj
index 9c52ff07568..8da938bd3f9 100644
--- a/mongo.xcodeproj/project.pbxproj
+++ b/mongo.xcodeproj/project.pbxproj
@@ -451,6 +451,7 @@
 		937D0E340F28CB070071FFA9 /* repltests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = repltests.cpp; sourceTree = "<group>"; };
 		937D14AB0F2A225F0071FFA9 /* nonce.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = nonce.h; sourceTree = "<group>"; };
 		937D14AC0F2A226E0071FFA9 /* nonce.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = nonce.cpp; sourceTree = "<group>"; };
+		938A748A11D140EC005265E1 /* in4.js */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.javascript; path = in4.js; sourceTree = "<group>"; };
 		938A7A420F54871000FB7A07 /* storage.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = storage.cpp; sourceTree = "<group>"; };
 		938A7A430F54873600FB7A07 /* concurrency.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = concurrency.h; sourceTree = "<group>"; };
 		938A7A440F54873600FB7A07 /* queryutil.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = queryutil.cpp; sourceTree = "<group>"; };
@@ -821,6 +822,7 @@
 		934BEB9A10DFFA9600178102 /* jstests */ = {
 			isa = PBXGroup;
 			children = (
+				938A748A11D140EC005265E1 /* in4.js */,
 				93C529C511D047CF00CF42F7 /* repair2.js */,
 				937884E811C80B22007E85F5 /* or8.js */,
 				937884C311C80276007E85F5 /* indexi.js */,