SERVER-5063 $in limit efficiency.

1 files changed, 55 insertions, 2 deletions

diff --git a/src/mongo/db/queryoptimizer.cpp b/src/mongo/db/queryoptimizer.cpp
index 00e88637699..bab670342de 100644
--- a/src/mongo/db/queryoptimizer.cpp
+++ b/src/mongo/db/queryoptimizer.cpp
@@ -241,7 +241,9 @@ doneCheckOrder:
             return shared_ptr<Cursor>( BtreeCursor::make( _d, _idxNo, *_index, _frv->startKey(), _frv->endKey(), true, _direction >= 0 ? 1 : -1 ) );
         }
         else {
-            return shared_ptr<Cursor>( BtreeCursor::make( _d, _idxNo, *_index, _frv, _direction >= 0 ? 1 : -1 ) );
+            return shared_ptr<Cursor>( BtreeCursor::make( _d, _idxNo, *_index, _frv,
+                                                         independentRangesSingleIntervalLimit(),
+                                                         _direction >= 0 ? 1 : -1 ) );
         }
     }
 
@@ -313,6 +315,56 @@ doneCheckOrder:
             }
         }
     }
+    
+    int QueryPlan::independentRangesSingleIntervalLimit() const {
+        if ( _scanAndOrderRequired &&
+            _parsedQuery &&
+            !_parsedQuery->wantMore() &&
+            !isMultiKey() &&
+            queryFiniteSetOrderSuffix() ) {
+            verify( 16111, _direction == 0 );
+            // Limit the results for each compound interval. SERVER-5063
+            return _parsedQuery->getSkip() + _parsedQuery->getNumToReturn();
+        }
+        return 0;
+    }
+    
+    bool QueryPlan::queryFiniteSetOrderSuffix() const {
+        if ( !indexed() ) {
+            return false;
+        }
+        if ( !_frs.simpleFiniteSet() ) {
+            return false;
+        }
+        BSONObj idxKey = indexKey();
+        BSONObjIterator index( idxKey );
+        BSONObjIterator order( _order );
+        int coveredNonUniversalRanges = 0;
+        while( index.more() ) {
+            if ( _frs.range( (*index).fieldName() ).universal() ) {
+                break;
+            }
+            ++coveredNonUniversalRanges;
+            if ( order.more() && str::equals( (*index).fieldName(), (*order).fieldName() ) ) {
+                ++order;
+            }
+            ++index;
+        }
+        if ( coveredNonUniversalRanges != _frs.numNonUniversalRanges() ) {
+            return false;
+        }
+        while( index.more() && order.more() ) {
+            if ( !str::equals( (*index).fieldName(), (*order).fieldName() ) ) {
+                return false;
+            }
+            if ( ( elementDirection( *index ) < 0 ) != ( elementDirection( *order ) < 0 ) ) {
+                return false;
+            }
+            ++order;
+            ++index;
+        }
+        return !order.more();
+    }
 
     /**
      * @return a copy of the inheriting class, which will be run with its own
@@ -334,7 +386,8 @@ doneCheckOrder:
     string QueryPlan::toString() const {
         return BSON(
                     "index" << indexKey() <<
-                    "frv" << ( _frv ? _frv->toString() : "" )
+                    "frv" << ( _frv ? _frv->toString() : "" ) <<
+                    "order" << _order
                     ).jsonString();
     }