SERVER-1752 Optimize simple indexed counts by counting the number of btree keys in a range, without checking the bson value of each key.

25 files changed, 2369 insertions, 98 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index c49a7f1b179..f5d9a803f70 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -333,6 +333,8 @@ serverOnlyFiles = [ "db/curop.cpp",
                     "db/prefetch.cpp",
                     "db/repl_block.cpp",
                     "db/btreecursor.cpp",
+                    "db/intervalbtreecursor.cpp",
+                    "db/btreeposition.cpp",
                     "db/cloner.cpp",
                     "db/namespace_details.cpp",
                     "db/cap.cpp",
diff --git a/src/mongo/db/btree.cpp b/src/mongo/db/btree.cpp
index f9dbd023ac5..061813ecd8a 100644
--- a/src/mongo/db/btree.cpp
+++ b/src/mongo/db/btree.cpp
@@ -894,6 +894,11 @@ namespace mongo {
      * This function is only needed in cases where k has a left or right child;
      * in other cases a simpler key removal implementation is possible.
      *
+     * NOTE on noncompliant BtreeBuilder btrees:
+     * It is possible (though likely rare) for btrees created by BtreeBuilder to
+     * have k' that is not a leaf, see SERVER-2732.  These cases are handled in
+     * the same manner as described in the "legacy btree structures" note below.
+     *
      * NOTE on legacy btree structures:
      * In legacy btrees, k' can be a nonleaf.  In such a case we 'delete' k by
      * marking it as an unused node rather than replacing it with k'.  Also, k'
diff --git a/src/mongo/db/btreeposition.cpp b/src/mongo/db/btreeposition.cpp
new file mode 100644
index 00000000000..ba2ffd28945
--- /dev/null
+++ b/src/mongo/db/btreeposition.cpp
@@ -0,0 +1,96 @@
+/**
+ *    Copyright (C) 2012 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "mongo/db/btreeposition.h"
+
+#include "mongo/db/btree.h"
+#include "mongo/db/index.h"
+
+namespace mongo {
+
+    std::ostream& operator<<( std::ostream& stream, const BtreeKeyLocation& loc ) {
+        return stream << BSON( "bucket" << loc.bucket.toString() <<
+                               "index" << loc.pos ).jsonString();
+    }
+
+    LogicalBtreePosition::LogicalBtreePosition( const IndexDetails& indexDetails,
+                                                Ordering ordering,
+                                                const BtreeKeyLocation& initialLocation ) :
+        _indexDetails( &indexDetails ),
+        _ordering( ordering ),
+        _initialLocation( initialLocation ),
+        _initialLocationValid() {
+        fassert( 16494, _indexDetails->version() == 1 );
+    }
+
+    void LogicalBtreePosition::init() {
+        if ( _initialLocation.bucket.isNull() ) {
+            // Abort if the initial location is not a valid bucket.
+            return;
+        }
+
+        // Store the key and record referenced at the supplied initial location.
+        BucketBasics<V1>::KeyNode keyNode =
+                _initialLocation.bucket.btree<V1>()->keyNode( _initialLocation.pos );
+        _key = keyNode.key.toBson().getOwned();
+        _record = keyNode.recordLoc;
+        _initialLocationValid = true;
+    }
+
+    BtreeKeyLocation LogicalBtreePosition::currentLocation() const {
+        if ( _initialLocation.bucket.isNull() ) {
+            // Abort if the initial location is not a valid bucket.
+            return BtreeKeyLocation();
+        }
+
+        // If the initial location has not been invalidated ...
+        if ( _initialLocationValid ) {
+
+            const BtreeBucket<V1>* bucket = _initialLocation.bucket.btree<V1>();
+            if ( // ... and the bucket was not marked as invalid ...
+                 bucket->getN() != bucket->INVALID_N_SENTINEL &&
+                 // ... and the initial location index is valid for the bucket ...
+                 _initialLocation.pos < bucket->getN() ) {
+
+                BucketBasics<V1>::KeyNode keyNode = bucket->keyNode( _initialLocation.pos );
+                if ( // ... and the record location equals the initial record location ...
+                     keyNode.recordLoc == _record &&
+                     // ... and the key equals the initial key ...
+                     keyNode.key.toBson().binaryEqual( _key ) ) {
+                    // ... then the initial location is the current location, so return it.
+                    return _initialLocation;
+                }
+            }
+        }
+
+        // Relocate the key and record location retrieved from _initialLocation.
+        BtreeKeyLocation ret;
+        bool found;
+        ret.bucket = _indexDetails->head.btree<V1>()->locate( *_indexDetails,
+                                                              _indexDetails->head,
+                                                              _key,
+                                                              _ordering,
+                                                              ret.pos,
+                                                              found,
+                                                              _record,
+                                                              1 // Forward direction means the next
+                                                                // ordered key will be returned if
+                                                                // the requested key is missing.
+                                                             );
+        return ret;
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/btreeposition.h b/src/mongo/db/btreeposition.h
new file mode 100644
index 00000000000..5499dc43662
--- /dev/null
+++ b/src/mongo/db/btreeposition.h
@@ -0,0 +1,105 @@
+/**
+ *    Copyright (C) 2012 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#pragma once
+
+#include "mongo/db/diskloc.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/platform/cstdint.h"
+
+namespace mongo {
+
+    class IndexDetails;
+
+    /**
+     * Physical location of a key within a btree.  Comprised of the DiskLoc address of a btree
+     * bucket and the index of a key within that bucket.
+     */
+    struct BtreeKeyLocation {
+
+        BtreeKeyLocation() :
+            pos() {
+        }
+
+        BtreeKeyLocation( DiskLoc initialBucket, int32_t initialPos ) :
+            bucket( initialBucket ),
+            pos( initialPos ) {
+        }
+
+        bool operator==( const BtreeKeyLocation& other ) const {
+            return bucket == other.bucket && pos == other.pos;
+        }
+
+        DiskLoc bucket; // Bucket within btree.
+        int32_t pos;    // Index within bucket.
+    };
+
+    std::ostream& operator<<( std::ostream& stream, const BtreeKeyLocation& loc );
+
+    /**
+     * Logical btree position independent of the physical structure of a btree.  This is used to
+     * track a position within a btree while the structure of the btree is changing.
+     *
+     * For example, a btree containing keys 'a', 'b', and 'c' might have all three keys in one
+     * bucket or alternatively 'b' within a left child of 'c'.  The same LogicalBtreePosition can
+     * represent the position of 'b' in both cases and can retrieve the physical BtreeKeyLocation of
+     * 'b' in each case.  If the btree is changed so that it lacks a 'b' key, the position will
+     * reference the lowest key greater than 'b'.  This is desirable behavior when the logical btree
+     * position is used to implement a forward direction iterator.
+     *
+     * The class is seeded with a BtreeKeyLocation identifying a btree key.  This initial physical
+     * location is cached in order to quickly check if the physical location corresponding to the
+     * logical position is unchanged and can be returned as is.
+     *
+     * NOTE Only supports V1 indexes.
+     */
+    class LogicalBtreePosition {
+    public:
+
+        /**
+         * Create a position with the @param 'indexDetails', @param 'ordering', and initial key
+         * location @param 'initialLocation' specified.
+         * @fasserts if 'indexDetails' is not a V1 index.
+         */
+        LogicalBtreePosition( const IndexDetails& indexDetails,
+                              Ordering ordering,
+                              const BtreeKeyLocation& initialLocation );
+
+        /** Initialize the position by reading the key at the supplied initial location. */
+        void init();
+
+        /**
+         * Invalidate the supplied initial location.  This may be called when bucket containing the
+         * supplied location is deleted.
+         */
+        void invalidateInitialLocation() { _initialLocationValid = false; }
+
+        /**
+         * Retrieve the current physical location in the btree corresponding to this logical
+         * position.
+         */
+        BtreeKeyLocation currentLocation() const;
+
+    private:
+        const IndexDetails* _indexDetails;
+        Ordering _ordering;
+        BtreeKeyLocation _initialLocation;
+        bool _initialLocationValid;
+        BSONObj _key;
+        DiskLoc _record;
+    };
+
+} // namespace mongo
diff --git a/src/mongo/db/diskloc.h b/src/mongo/db/diskloc.h
index 8682d8d97d4..a6adb204a58 100644
--- a/src/mongo/db/diskloc.h
+++ b/src/mongo/db/diskloc.h
@@ -22,7 +22,8 @@
 
 #pragma once
 
-#include "jsobj.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/platform/cstdint.h"
 
 namespace mongo {
 
@@ -51,7 +52,7 @@ namespace mongo {
 
             // Caps the number of files that may be allocated in a database, allowing about 32TB of
             // data per db.  Note that the DiskLoc and DiskLoc56Bit types supports more files than
-            // this value, as does the storage format.
+            // this value, as does the data storage format.
             MaxFiles=16000
         };
 
@@ -130,6 +131,8 @@ namespace mongo {
             return compare(b) < 0;
         }
 
+        uint64_t asUint64() const { return *reinterpret_cast<const uint64_t*>( this ); }
+
         /**
          * Marks this disk loc for writing
          * @returns a non const reference to this disk loc
@@ -158,6 +161,10 @@ namespace mongo {
     };
 #pragma pack()
 
+    inline std::ostream& operator<<( std::ostream &stream, const DiskLoc &loc ) {
+        return stream << loc.toString();
+    }
+
     // Minimum allowed DiskLoc.  No Record may begin at this location because file and extent
     // headers must precede Records in a file.
     const DiskLoc minDiskLoc(0, 0);
diff --git a/src/mongo/db/intervalbtreecursor.cpp b/src/mongo/db/intervalbtreecursor.cpp
new file mode 100644
index 00000000000..1690e43bbb2
--- /dev/null
+++ b/src/mongo/db/intervalbtreecursor.cpp
@@ -0,0 +1,200 @@
+/**
+ *    Copyright (C) 2012 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "mongo/db/intervalbtreecursor.h"
+
+#include "mongo/db/btree.h"
+#include "mongo/db/kill_current_op.h"
+
+namespace mongo {
+
+    /**
+     * Advance 'loc' until it does not reference an unused key, or the end of the btree is reached.
+     */
+    static void skipUnused( BtreeKeyLocation* loc ) {
+
+        // While loc points to an unused key ...
+        while( !loc->bucket.isNull() &&
+               loc->bucket.btree<V1>()->k( loc->pos ).isUnused() ) {
+
+            // ... advance loc to the next key in the btree.
+            loc->bucket = loc->bucket.btree<V1>()->advance( loc->bucket,
+                                                            loc->pos,
+                                                            1,
+                                                            __FUNCTION__ );
+        }
+    }
+
+    IntervalBtreeCursor* IntervalBtreeCursor::make( NamespaceDetails* namespaceDetails,
+                                                    const IndexDetails& indexDetails,
+                                                    const BSONObj& lowerBound,
+                                                    bool lowerBoundInclusive,
+                                                    const BSONObj& upperBound,
+                                                    bool upperBoundInclusive ) {
+        if ( indexDetails.version() != 1 ) {
+            // Only v1 indexes are supported.
+            return NULL;
+        }
+        auto_ptr<IntervalBtreeCursor> ret( new IntervalBtreeCursor( namespaceDetails,
+                                                                    indexDetails,
+                                                                    lowerBound,
+                                                                    lowerBoundInclusive,
+                                                                    upperBound,
+                                                                    upperBoundInclusive ) );
+        ret->init();
+        return ret.release();
+    }
+
+    IntervalBtreeCursor::IntervalBtreeCursor( NamespaceDetails* namespaceDetails,
+                                              const IndexDetails& indexDetails,
+                                              const BSONObj& lowerBound,
+                                              bool lowerBoundInclusive,
+                                              const BSONObj& upperBound,
+                                              bool upperBoundInclusive ) :
+        _namespaceDetails( *namespaceDetails ),
+        _indexNo( namespaceDetails->idxNo( indexDetails ) ),
+        _indexDetails( indexDetails ),
+        _ordering( Ordering::make( _indexDetails.keyPattern() ) ),
+        _lowerBound( lowerBound ),
+        _lowerBoundInclusive( lowerBoundInclusive ),
+        _upperBound( upperBound ),
+        _upperBoundInclusive( upperBoundInclusive ),
+        _currRecoverable( _indexDetails, _ordering, _curr ),
+        _nscanned(),
+        _multikeyFlag() {
+    }
+
+    void IntervalBtreeCursor::init() {
+        _multikeyFlag = _namespaceDetails.isMultikey( _indexNo );
+        _curr = locateKey( _lowerBound, !_lowerBoundInclusive );
+        skipUnused( &_curr );
+        relocateEnd();
+        if ( ok() ) {
+            _nscanned = 1;
+        }
+    }
+
+    bool IntervalBtreeCursor::ok() {
+        return !_curr.bucket.isNull();
+    }
+
+    DiskLoc IntervalBtreeCursor::currLoc() {
+        if ( eof() ) {
+            return DiskLoc();
+        }
+        return _curr.bucket.btree<V1>()->keyNode( _curr.pos ).recordLoc;
+    }
+
+    bool IntervalBtreeCursor::advance() {
+        RARELY killCurrentOp.checkForInterrupt();
+        if ( eof() ) {
+            return false;
+        }
+        // Advance _curr to the next key in the btree.
+        _curr.bucket = _curr.bucket.btree<V1>()->advance( _curr.bucket,
+                                                          _curr.pos,
+                                                          1,
+                                                          __FUNCTION__ );
+        skipUnused( &_curr );
+        if ( _curr == _end ) {
+            // _curr has reached _end, so iteration is complete.
+            _curr.bucket.Null();
+        }
+        else {
+            ++_nscanned;
+        }
+        return ok();
+    }
+
+    BSONObj IntervalBtreeCursor::currKey() const {
+        if ( _curr.bucket.isNull() ) {
+            return BSONObj();
+        }
+        return _curr.bucket.btree<V1>()->keyNode( _curr.pos ).key.toBson();
+    }
+
+    void IntervalBtreeCursor::aboutToDeleteBucket( const DiskLoc& b ) {
+        if ( b == _curr.bucket ) {
+            _currRecoverable.invalidateInitialLocation();
+        }
+    }
+
+    void IntervalBtreeCursor::noteLocation() {
+        _currRecoverable = LogicalBtreePosition( _indexDetails, _ordering, _curr );
+        _currRecoverable.init();
+    }
+
+    void IntervalBtreeCursor::checkLocation() {
+        _multikeyFlag = _namespaceDetails.isMultikey( _indexNo );
+        _curr = _currRecoverable.currentLocation();
+        skipUnused( &_curr );
+        relocateEnd();
+    }
+
+    bool IntervalBtreeCursor::getsetdup( DiskLoc loc ) {
+        // TODO _multikeyFlag may be set part way through an iteration by checkLocation().  In this
+        // case results returned earlier, when _multikeyFlag was false, will not be deduped.  This
+        // is an old issue with all mongo btree cursor implementations.
+        return _multikeyFlag && !_dups.insert( loc.asUint64() ).second;
+    }
+
+    BSONObj IntervalBtreeCursor::prettyIndexBounds() const {
+        return BSON( "lower" << _lowerBound.replaceFieldNames( _indexDetails.keyPattern() ) <<
+                     "upper" << _upperBound.replaceFieldNames( _indexDetails.keyPattern() ) );
+    }
+
+    BtreeKeyLocation IntervalBtreeCursor::locateKey( const BSONObj& key, bool afterKey ) {
+        bool found;
+        BtreeKeyLocation ret;
+
+        // To find the first btree location equal to the specified key, specify a record location of
+        // minDiskLoc, which is below any actual Record location.  To find the first btree location
+        // greater than the specified key, specify a record location of maxDiskLoc, which is above
+        // any actual Record location.
+        DiskLoc targetRecord = afterKey ? maxDiskLoc : minDiskLoc;
+
+        // Find the requested location in the btree.
+        ret.bucket = _indexDetails.head.btree<V1>()->locate( _indexDetails,
+                                                             _indexDetails.head,
+                                                             key,
+                                                             _ordering,
+                                                             ret.pos,
+                                                             found,
+                                                             targetRecord,
+                                                             1 );
+        return ret;
+    }
+
+    void IntervalBtreeCursor::relocateEnd() {
+        if ( eof() ) {
+            return;
+        }
+
+        // If the current key is above the upper bound ...
+        int32_t cmp = currKey().woCompare( _upperBound, _ordering, false );
+        if ( cmp > 0 || ( cmp == 0 && !_upperBoundInclusive ) ) {
+
+            // ... then iteration is complete.
+            _curr.bucket.Null();
+            return;
+        }
+
+        // Otherwise, relocate _end.
+        _end = locateKey( _upperBound, _upperBoundInclusive );
+        skipUnused( &_end );
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/intervalbtreecursor.h b/src/mongo/db/intervalbtreecursor.h
new file mode 100644
index 00000000000..6d9214baa22
--- /dev/null
+++ b/src/mongo/db/intervalbtreecursor.h
@@ -0,0 +1,145 @@
+/**
+ *    Copyright (C) 2012 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#pragma once
+
+#include "mongo/db/btreeposition.h"
+#include "mongo/db/cursor.h"
+#include "mongo/db/namespace_details.h"
+#include "mongo/platform/cstdint.h"
+#include "mongo/platform/unordered_set.h"
+
+namespace mongo {
+
+    /**
+     * An optimized btree cursor that iterates through all btree keys between a lower bound and an
+     * upper bound.  The contents of the individual keys are not examined by the implementation,
+     * which simply advances through the tree until reaching a predetermined end location.  The goal
+     * is to optimize count operations where the keys must only be counted, not tested for matching.
+     *
+     * Limitations compared to a standard BtreeCursor (partial list):
+     * - Only supports index constraints consisting of a single interval within an index.
+     * - Only supports forward direction iteration.
+     * - Does not support covered index projections.
+     * - Does not support get more.
+     * - Only supports V1 indexes (not V0).
+     */
+    class IntervalBtreeCursor : public Cursor {
+    public:
+
+        /**
+         * @return a cursor, or NULL if no cursor can be created.
+         * @param namespaceDetails - Collection metadata that will not be modified.
+         * @param indexDetails - Index metadata, if not a v1 index then make() will return NULL.
+         * @param lowerBound - Lower bound of the key range to iterate, according to the index's
+         *     native ordering.
+         * @param lowerBoundInclusive - If true, the lower bound includes the endpoint.
+         * @param upperBound - Upper bound of the key range to iterate.
+         * @param upperBoundInclusive - If true, the upper bound includes the endpoint.
+         */
+        static IntervalBtreeCursor* make( /* const */ NamespaceDetails* namespaceDetails,
+                                          const IndexDetails& indexDetails,
+                                          const BSONObj& lowerBound,
+                                          bool lowerBoundInclusive,
+                                          const BSONObj& upperBound,
+                                          bool upperBoundInclusive );
+
+        /** Virtuals from Cursor. */
+
+        virtual bool ok();
+
+        virtual Record* _current() { return currLoc().rec(); }
+
+        virtual BSONObj current() { return currLoc().obj(); }
+
+        virtual DiskLoc currLoc();
+
+        virtual bool advance();
+
+        virtual BSONObj currKey() const;
+
+        virtual DiskLoc refLoc() { return currLoc(); }
+
+        virtual void aboutToDeleteBucket( const DiskLoc& b );
+
+        virtual BSONObj indexKeyPattern() { return _indexDetails.keyPattern(); }
+
+        virtual bool supportGetMore() { return false; }
+
+        virtual void noteLocation();
+
+        virtual void checkLocation();
+
+        virtual bool supportYields() { return true; }
+
+        virtual string toString() { return "IntervalBtreeCursor"; }
+
+        virtual bool getsetdup( DiskLoc loc );
+
+        virtual bool isMultiKey() const { return _multikeyFlag; }
+
+        virtual bool modifiedKeys() const { return _multikeyFlag; }
+
+        virtual BSONObj prettyIndexBounds() const;
+
+        virtual long long nscanned() { return _nscanned; }
+
+        virtual CoveredIndexMatcher* matcher() const { return _matcher.get(); }
+
+        virtual void setMatcher( shared_ptr<CoveredIndexMatcher> matcher ) { _matcher = matcher; }
+
+    private:
+        IntervalBtreeCursor( NamespaceDetails* namespaceDetails,
+                             const IndexDetails& indexDetails,
+                             const BSONObj& lowerBound,
+                             bool lowerBoundInclusive,
+                             const BSONObj& upperBound,
+                             bool upperBoundInclusive );
+
+        void init();
+
+        /**
+         * @return a location in the btree, determined by the parameters specified.
+         * @param key - The key to search for.
+         * @param afterKey - If true, return the first btree key greater than the supplied 'key'.
+         *     If false, return the first key equal to the supplied 'key'.
+         */
+        BtreeKeyLocation locateKey( const BSONObj& key, bool afterKey );
+
+        /** Find the iteration end location and set _end to it. */
+        void relocateEnd();
+
+        const NamespaceDetails& _namespaceDetails;
+        const int32_t _indexNo;
+        const IndexDetails& _indexDetails;
+        const Ordering _ordering;
+        const BSONObj _lowerBound;
+        const bool _lowerBoundInclusive;
+        const BSONObj _upperBound;
+        const bool _upperBoundInclusive;
+
+        BtreeKeyLocation _curr; // Current position in the btree.
+        LogicalBtreePosition _currRecoverable; // Helper to track the position of _curr if the
+                                               // btree is modified during a mutex yield.
+        BtreeKeyLocation _end; // Exclusive end location in the btree.
+        int64_t _nscanned;
+
+        shared_ptr<CoveredIndexMatcher> _matcher;
+        bool _multikeyFlag;
+        unordered_set<uint64_t> _dups;
+    };
+
+} // namespace mongo
diff --git a/src/mongo/db/namespace_details.h b/src/mongo/db/namespace_details.h
index 585470f1e58..b35670e34a2 100644
--- a/src/mongo/db/namespace_details.h
+++ b/src/mongo/db/namespace_details.h
@@ -484,14 +484,6 @@ namespace mongo {
          *
          * @param planPolicy - A policy for selecting query plans - see queryoptimizercursor.h
          *
-         * @param requestMatcher - Set to true to request that the returned Cursor provide a
-         * matcher().  If false, the cursor's matcher() may return NULL if the Cursor can perform
-         * accurate query matching internally using a non Matcher mechanism.  One case where a
-         * Matcher might be requested even though not strictly necessary to select matching
-         * documents is if metadata about matches may be requested using MatchDetails.  NOTE This is
-         * a hint that the Cursor use a Matcher, but the hint may be ignored.  In some cases the
-         * returned cursor may not provide a matcher even if 'requestMatcher' is true.
-         *
          * @param parsedQuery - Additional query parameters, as from a client query request.
          *
          * @param requireOrder - If false, the resulting cursor may return results in an order
@@ -511,15 +503,15 @@ namespace mongo {
          * - covered indexes
          * - in memory sorting
          */
-        static shared_ptr<Cursor> getCursor( const char *ns, const BSONObj &query,
-                                            const BSONObj &order = BSONObj(),
-                                            const QueryPlanSelectionPolicy &planPolicy =
-                                            QueryPlanSelectionPolicy::any(),
-                                            bool requestMatcher = true,
-                                            const shared_ptr<const ParsedQuery> &parsedQuery =
-                                            shared_ptr<const ParsedQuery>(),
-                                            bool requireOrder = true,
-                                            QueryPlanSummary *singlePlanSummary = 0 );
+        static shared_ptr<Cursor> getCursor( const char* ns,
+                                             const BSONObj& query,
+                                             const BSONObj& order = BSONObj(),
+                                             const QueryPlanSelectionPolicy& planPolicy =
+                                                 QueryPlanSelectionPolicy::any(),
+                                             const shared_ptr<const ParsedQuery>& parsedQuery =
+                                                 shared_ptr<const ParsedQuery>(),
+                                             bool requireOrder = true,
+                                             QueryPlanSummary* singlePlanSummary = NULL );
 
         /**
          * @return a single cursor that may work well for the given query.  A $or style query will
diff --git a/src/mongo/db/ops/count.cpp b/src/mongo/db/ops/count.cpp
index 713c40edb5a..c63b4e5d8c6 100644
--- a/src/mongo/db/ops/count.cpp
+++ b/src/mongo/db/ops/count.cpp
@@ -26,6 +26,33 @@
 #include "mongo/util/elapsed_tracker.h"
 
 namespace mongo {
+
+    namespace {
+
+        /**
+         * Specialized Cursor creation rules that the count operator provides to the query
+         * processing system.  These rules limit the performance overhead when counting index keys
+         * matching simple predicates.  See SERVER-1752.
+         */
+        class CountPlanPolicies : public QueryPlanSelectionPolicy {
+
+            virtual string name() const { return "CountPlanPolicies"; }
+
+            virtual bool requestMatcher() const {
+                // Avoid using a Matcher when a Cursor will exactly match a query.
+                return false;
+            }
+
+            virtual bool requestIntervalCursor() const {
+                // Request use of an IntervalBtreeCursor when the index bounds represent a single
+                // btree interval.  This Cursor implementation is optimized for performing counts
+                // between two endpoints.
+                return true;
+            }
+
+        } _countPlanPolicies;
+
+    }
     
     long long runCount( const char *ns, const BSONObj &cmd, string &err, int &errCode ) {
         Client::Context cx(ns);
@@ -53,11 +80,7 @@ namespace mongo {
                 NamespaceDetailsTransient::getCursor( ns,
                                                       query,
                                                       BSONObj(),
-                                                      QueryPlanSelectionPolicy::any(),
-                                                      // Avoid using a Matcher when a Cursor can
-                                                      // exactly match the query using a
-                                                      // FieldRangeVector.  See SERVER-1752.
-                                                      false /* requestMatcher */ );
+                                                      _countPlanPolicies );
         ClientCursor::Holder ccPointer;
         ElapsedTracker timeToStartYielding( 256, 20 );
         try {
diff --git a/src/mongo/db/ops/query.cpp b/src/mongo/db/ops/query.cpp
index ff11c9721a9..05df12a0045 100644
--- a/src/mongo/db/ops/query.cpp
+++ b/src/mongo/db/ops/query.cpp
@@ -678,8 +678,13 @@ namespace mongo {
         }
         else {
             cursor =
-                NamespaceDetailsTransient::getCursor( ns.c_str(), query, order, QueryPlanSelectionPolicy::any(),
-                                                      true, pq_shared, false, &queryPlan );
+                NamespaceDetailsTransient::getCursor( ns.c_str(),
+                                                      query,
+                                                      order,
+                                                      QueryPlanSelectionPolicy::any(),
+                                                      pq_shared,
+                                                      false,
+                                                      &queryPlan );
         }
         verify( cursor );
         
diff --git a/src/mongo/db/pipeline/pipeline_d.cpp b/src/mongo/db/pipeline/pipeline_d.cpp
index 4a92045fddf..98c419afc9f 100755
--- a/src/mongo/db/pipeline/pipeline_d.cpp
+++ b/src/mongo/db/pipeline/pipeline_d.cpp
@@ -146,7 +146,7 @@ namespace mongo {
             shared_ptr<Cursor> pSortedCursor(
                 pCursor = NamespaceDetailsTransient::getCursor(
                     fullName.c_str(), *pQueryObj, *pSortObj,
-                    QueryPlanSelectionPolicy::any(), true, pq));
+                    QueryPlanSelectionPolicy::any(), pq));
 
             if (pSortedCursor.get()) {
                 /* success:  remove the sort from the pipeline */
@@ -165,7 +165,7 @@ namespace mongo {
             shared_ptr<Cursor> pUnsortedCursor(
                 pCursor = NamespaceDetailsTransient::getCursor(
                     fullName.c_str(), *pQueryObj, BSONObj(),
-                    QueryPlanSelectionPolicy::any(), true, pq));
+                    QueryPlanSelectionPolicy::any(), pq));
 
             pCursor = pUnsortedCursor;
         }
diff --git a/src/mongo/db/queryoptimizer.cpp b/src/mongo/db/queryoptimizer.cpp
index c7439208b1f..d5f534e00a7 100644
--- a/src/mongo/db/queryoptimizer.cpp
+++ b/src/mongo/db/queryoptimizer.cpp
@@ -16,14 +16,17 @@
 *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
-#include "pch.h"
+#include "mongo/pch.h"
+
 #include "mongo/db/queryoptimizer.h"
-#include "db.h"
-#include "mongo/db/btreecursor.h"
-#include "cmdline.h"
-#include "../server.h"
-#include "pagefault.h"
+
 #include "mongo/client/dbclientinterface.h"
+#include "mongo/db/btreecursor.h"
+#include "mongo/db/cmdline.h"
+#include "mongo/db/db.h"
+#include "mongo/db/intervalbtreecursor.h"
+#include "mongo/db/pagefault.h"
+#include "mongo/server.h"
 
 //#define DEBUGQO(x) cout << x << endl;
 #define DEBUGQO(x)
@@ -258,7 +261,8 @@ doneCheckOrder:
         }
     }
 
-    shared_ptr<Cursor> QueryPlan::newCursor( const DiskLoc &startLoc ) const {
+    shared_ptr<Cursor> QueryPlan::newCursor( const DiskLoc& startLoc,
+                                             bool requestIntervalCursor ) const {
 
         if ( _type ) {
             // hopefully safe to use original query in these contexts - don't think we can mix type with $or clause separation yet
@@ -301,6 +305,27 @@ doneCheckOrder:
                                                           _direction >= 0 ? 1 : -1 ) );
         }
 
+        // An IntervalBtreeCursor is returned if explicitly requested AND _frv is exactly
+        // represented by a single interval within the btree.
+        if ( // If an interval cursor is requested and ...
+             requestIntervalCursor &&
+             // ... equalities come before ranges (a requirement of Optimal) and ...
+             _utility == Optimal &&
+             // ... the field range vector exactly represents a single interval ...
+             _frv->isSingleInterval() ) {
+            // ... and an interval cursor can be created ...
+            shared_ptr<Cursor> ret( IntervalBtreeCursor::make( _d,
+                                                               *_index,
+                                                               _frv->startKey(),
+                                                               _frv->startKeyInclusive(),
+                                                               _frv->endKey(),
+                                                               _frv->endKeyInclusive() ) );
+            if ( ret ) {
+                // ... then return the interval cursor.
+                return ret;
+            }
+        }
+
         return shared_ptr<Cursor>( BtreeCursor::make( _d,
                                                       *_index,
                                                       _frv,
diff --git a/src/mongo/db/queryoptimizer.h b/src/mongo/db/queryoptimizer.h
index 7663de2444d..67286a17134 100644
--- a/src/mongo/db/queryoptimizer.h
+++ b/src/mongo/db/queryoptimizer.h
@@ -88,7 +88,8 @@ namespace mongo {
         const string &special() const { return _special; }
                 
         /** @return a new cursor based on this QueryPlan's index and FieldRangeSet. */
-        shared_ptr<Cursor> newCursor( const DiskLoc &startLoc = DiskLoc() ) const;
+        shared_ptr<Cursor> newCursor( const DiskLoc& startLoc = DiskLoc(),
+                                      bool requestIntervalCursor = false ) const;
         /** @return a new reverse cursor if this is an unindexed plan. */
         shared_ptr<Cursor> newReverseCursor() const;
         /** Register this plan as a winner for its QueryPattern, with specified 'nscanned'. */
diff --git a/src/mongo/db/queryoptimizercursor.h b/src/mongo/db/queryoptimizercursor.h
index 92de60e29c4..2b826b65b42 100644
--- a/src/mongo/db/queryoptimizercursor.h
+++ b/src/mongo/db/queryoptimizercursor.h
@@ -27,8 +27,8 @@ namespace mongo {
     class CandidatePlanCharacter;
     
     /**
-     * An interface for policies overriding the query optimizer's default query plan selection
-     * behavior.
+     * An interface for policies overriding the query optimizer's default behavior for selecting
+     * query plans and creating cursors.
      */
     class QueryPlanSelectionPolicy {
     public:
@@ -38,6 +38,26 @@ namespace mongo {
         virtual bool permitOptimalIdPlan() const { return true; }
         virtual bool permitPlan( const QueryPlan &plan ) const { return true; }
         virtual BSONObj planHint( const char *ns ) const { return BSONObj(); }
+
+        /**
+         * @return true to request that a created Cursor provide a matcher().  If false, the
+         * Cursor's matcher() may be NULL if the Cursor can perform accurate query matching
+         * internally using a non Matcher mechanism.  One case where a Matcher might be requested
+         * even though not strictly necessary to select matching documents is if metadata about
+         * matches may be requested using MatchDetails.  NOTE This is a hint that the Cursor use a
+         * Matcher, but the hint may be ignored.  In some cases the Cursor may not provide
+         * a Matcher even if 'requestMatcher' is true.
+         */
+        virtual bool requestMatcher() const { return true; }
+
+        /**
+         * @return true to request creating an IntervalBtreeCursor rather than a BtreeCursor when
+         * possible.  An IntervalBtreeCursor is optimized for counting the number of documents
+         * between two endpoints in a btree.  NOTE This is a hint to create an interval cursor, but
+         * the hint may be ignored.  In some cases a different cursor type may be created even if
+         * 'requestIntervalCursor' is true.
+         */
+        virtual bool requestIntervalCursor() const { return false; }
         
         /** Allow any query plan selection, permitting the query optimizer's default behavior. */
         static const QueryPlanSelectionPolicy &any();
diff --git a/src/mongo/db/queryoptimizercursorimpl.cpp b/src/mongo/db/queryoptimizercursorimpl.cpp
index 5af241ca772..98c8c859209 100644
--- a/src/mongo/db/queryoptimizercursorimpl.cpp
+++ b/src/mongo/db/queryoptimizercursorimpl.cpp
@@ -386,13 +386,17 @@ namespace mongo {
                                          const BSONObj &query,
                                          const BSONObj &order,
                                          const QueryPlanSelectionPolicy &planPolicy,
-                                         bool requestMatcher,
                                          const shared_ptr<const ParsedQuery> &parsedQuery,
                                          bool requireOrder,
                                          QueryPlanSummary *singlePlanSummary ) {
 
-        CursorGenerator generator( ns, query, order, planPolicy, requestMatcher, parsedQuery,
-                                   requireOrder, singlePlanSummary );
+        CursorGenerator generator( ns,
+                                   query,
+                                   order,
+                                   planPolicy,
+                                   parsedQuery,
+                                   requireOrder,
+                                   singlePlanSummary );
         return generator.generate();
     }
     
@@ -400,7 +404,6 @@ namespace mongo {
                                      const BSONObj &query,
                                      const BSONObj &order,
                                      const QueryPlanSelectionPolicy &planPolicy,
-                                     bool requestMatcher,
                                      const shared_ptr<const ParsedQuery> &parsedQuery,
                                      bool requireOrder,
                                      QueryPlanSummary *singlePlanSummary ) :
@@ -408,7 +411,6 @@ namespace mongo {
     _query( query ),
     _order( order ),
     _planPolicy( planPolicy ),
-    _requestMatcher( requestMatcher ),
     _parsedQuery( parsedQuery ),
     _requireOrder( requireOrder ),
     _singlePlanSummary( singlePlanSummary ) {
@@ -486,7 +488,8 @@ namespace mongo {
         if ( _singlePlanSummary ) {
             *_singlePlanSummary = singlePlan->summary();
         }
-        shared_ptr<Cursor> single = singlePlan->newCursor();
+        shared_ptr<Cursor> single = singlePlan->newCursor( DiskLoc(),
+                                                           _planPolicy.requestIntervalCursor() );
         if ( !_query.isEmpty() && !single->matcher() ) {
 
             // The query plan must have a matcher.  The matcher's constructor performs some aspects
@@ -494,7 +497,7 @@ namespace mongo {
             fassert( 16449, singlePlan->matcher() );
 
             if ( // If a matcher is requested or ...
-                 _requestMatcher ||
+                 _planPolicy.requestMatcher() ||
                  // ... the index ranges do not exactly match the query or ...
                  singlePlan->mayBeMatcherNecessary() ||
                  // ... the matcher must look at the full record ...
diff --git a/src/mongo/db/queryoptimizercursorimpl.h b/src/mongo/db/queryoptimizercursorimpl.h
index dcc0c5cb6e4..3d978afb312 100644
--- a/src/mongo/db/queryoptimizercursorimpl.h
+++ b/src/mongo/db/queryoptimizercursorimpl.h
@@ -257,7 +257,6 @@ namespace mongo {
                         const BSONObj &query,
                         const BSONObj &order,
                         const QueryPlanSelectionPolicy &planPolicy,
-                        bool requestMatcher,
                         const shared_ptr<const ParsedQuery> &parsedQuery,
                         bool requireOrder,
                         QueryPlanSummary *singlePlanSummary );
@@ -288,7 +287,6 @@ namespace mongo {
         BSONObj _query;
         BSONObj _order;
         const QueryPlanSelectionPolicy &_planPolicy;
-        bool _requestMatcher;
         shared_ptr<const ParsedQuery> _parsedQuery;
         bool _requireOrder;
         QueryPlanSummary *_singlePlanSummary;
diff --git a/src/mongo/db/queryutil-inl.h b/src/mongo/db/queryutil-inl.h
index 0a10da23f30..17965daa784 100644
--- a/src/mongo/db/queryutil-inl.h
+++ b/src/mongo/db/queryutil-inl.h
@@ -74,7 +74,7 @@ namespace mongo {
         return true;
     }
 
-    inline unsigned FieldRangeVector::size() {
+    inline unsigned FieldRangeVector::size() const {
         unsigned ret = 1;
         for( vector<FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
             unsigned long long product =
diff --git a/src/mongo/db/queryutil.cpp b/src/mongo/db/queryutil.cpp
index 360949c785c..8a27a1c37b9 100644
--- a/src/mongo/db/queryutil.cpp
+++ b/src/mongo/db/queryutil.cpp
@@ -1153,6 +1153,26 @@ namespace mongo {
         }
     }
 
+    /**
+     * @return true if @param range is universal or can be easily identified as a reverse universal
+     * range (see FieldRange::reverse()).
+     */
+    static bool universalOrReverseUniversalRange( const FieldRange& range ) {
+        if ( range.universal() ) {
+            return true;
+        }
+        if ( range.intervals().size() != 1 ) {
+            return false;
+        }
+        if ( !range.min().valuesEqual( maxKey.firstElement() ) ) {
+            return false;
+        }
+        if ( !range.max().valuesEqual( minKey.firstElement() ) ) {
+            return false;
+        }
+        return true;
+    }
+
     FieldRangeVector::FieldRangeVector( const FieldRangeSet &frs, const IndexSpec &indexSpec,
                                         int direction ) :
         _indexSpec( indexSpec ),
@@ -1218,24 +1238,117 @@ namespace mongo {
                 size() < MAX_IN_COMBINATIONS );
     }    
 
+    bool FieldRangeVector::isSingleInterval() const {
+        size_t i = 0;
+
+        // Skip all equality ranges.
+        while( i < _ranges.size() && _ranges[ i ].equality() ) {
+            ++i;
+        }
+
+        // If there are no ranges left ...
+        if ( i >= _ranges.size() ) {
+            // ... then all ranges are equalities.
+            return true;
+        }
+
+        // If the first non equality range does not consist of a single interval ...
+        if ( _ranges[ i ].intervals().size() != 1 ) {
+            // ... then the full FieldRangeVector does not consist of a single interval.
+            return false;
+        }
+        ++i;
+
+        while( i < _ranges.size() ) {
+            // If a range after the first non equality is not universal ...
+            if ( !universalOrReverseUniversalRange( _ranges[ i ] ) ) {
+                // ... then the full FieldRangeVector does not consist of a single interval.
+                return false;
+            }
+            ++i;
+        }
+
+        // The FieldRangeVector consists of zero or more equalities, then zero or one inequality
+        // with a single interval, then zero or more universal ranges.
+        return true;
+    }
+
     BSONObj FieldRangeVector::startKey() const {
         BSONObjBuilder b;
-        for( vector<FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
+        BSONObjIterator keys( _indexSpec.keyPattern );
+        vector<FieldRange>::const_iterator i = _ranges.begin();
+        for( ; i != _ranges.end(); ++i, ++keys ) {
+            // Append lower bounds until an exclusive bound is found.
             const FieldInterval &fi = i->intervals().front();
             b.appendAs( fi._lower._bound, "" );
+            if ( !fi._lower._inclusive ) {
+                ++i;
+                ++keys;
+                break;
+            }
+        }
+        for( ; i != _ranges.end(); ++i, ++keys ) {
+            // After the first exclusive bound is found, use extreme values for subsequent fields.
+            // For example, on index { a:1, b:1 } with query { a:{ $gt: 5 } } the start key is
+            // { '':5, '':MaxKey }.
+            bool forward = ( ( (*keys).number() >= 0 ? 1 : -1 ) * _direction > 0 );
+            if ( forward ) {
+                b.appendMaxKey( "" );
+            }
+            else {
+                b.appendMinKey( "" );
+            }
         }
         return b.obj();
     }
 
+    bool FieldRangeVector::startKeyInclusive() const {
+        for( vector<FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
+            if( !i->intervals().front()._lower._inclusive ) {
+                return false;
+            }
+        }
+        return true;
+    }
+
     BSONObj FieldRangeVector::endKey() const {
         BSONObjBuilder b;
-        for( vector<FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
+        BSONObjIterator keys( _indexSpec.keyPattern );
+        vector<FieldRange>::const_iterator i = _ranges.begin();
+        for( ; i != _ranges.end(); ++i, ++keys ) {
+            // Append upper bounds until an exclusive bound is found.
             const FieldInterval &fi = i->intervals().back();
             b.appendAs( fi._upper._bound, "" );
+            if ( !fi._upper._inclusive ) {
+                ++i;
+                ++keys;
+                break;
+            }
+        }
+        for( ; i != _ranges.end(); ++i, ++keys ) {
+            // After the first exclusive bound is found, use extreme values for subsequent fields.
+            // For example, on index { a:1, b:1 } with query { a:{ $lt: 5 } } the end key is
+            // { '':5, '':MinKey }.
+            bool forward = ( ( (*keys).number() >= 0 ? 1 : -1 ) * _direction > 0 );
+            if ( forward ) {
+                b.appendMinKey( "" );
+            }
+            else {
+                b.appendMaxKey( "" );
+            }
         }
         return b.obj();
     }
 
+    bool FieldRangeVector::endKeyInclusive() const {
+        for( vector<FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
+            if( !i->intervals().front()._upper._inclusive ) {
+                return false;
+            }
+        }
+        return true;
+    }
+
     BSONObj FieldRangeVector::obj() const {
         BSONObjBuilder b;
         BSONObjIterator k( _indexSpec.keyPattern );
@@ -1391,8 +1504,8 @@ namespace mongo {
             return _multiKey;
         }
         return nsd->isMultikey( idxNo ) ? _multiKey : _singleKey;
-    }    
-        
+    }
+
     bool FieldRangeVector::matchesElement( const BSONElement &e, int i, bool forward ) const {
         bool eq;
         int l = matchingLowElement( e, i, forward, eq );
@@ -1668,26 +1781,6 @@ namespace mongo {
         return advancePast( i );
     }
 
-    /**
-     * @return true if @param range is universal or can be easily identified as a reverse universal
-     * range (see FieldRange::reverse()).
-     */
-    static bool universalOrReverseUniversalRange( const FieldRange& range ) {
-        if ( range.universal() ) {
-            return true;
-        }
-        if ( range.intervals().size() != 1 ) {
-            return false;
-        }
-        if ( !range.min().valuesEqual( maxKey.firstElement() ) ) {
-            return false;
-        }
-        if ( !range.max().valuesEqual( minKey.firstElement() ) ) {
-            return false;
-        }
-        return true;
-    }
-
     int FieldRangeVectorIterator::endNonUniversalRanges() const {
         int i = _v._ranges.size() - 1;
         while( i > -1 && universalOrReverseUniversalRange( _v._ranges[ i ] ) ) {
diff --git a/src/mongo/db/queryutil.h b/src/mongo/db/queryutil.h
index 41e54dcb1ab..8d7d33aacea 100644
--- a/src/mongo/db/queryutil.h
+++ b/src/mongo/db/queryutil.h
@@ -619,12 +619,67 @@ namespace mongo {
          */
         FieldRangeVector( const FieldRangeSet &frs, const IndexSpec &indexSpec, int direction );
 
-        /** @return the number of index ranges represented by 'this' */
-        unsigned size();
-        /** @return starting point for an index traversal. */
+        /**
+         * Methods for identifying compound start and end btree bounds describing this field range
+         * vector.
+         *
+         * A FieldRangeVector contains the FieldRange bounds for every field of an index.  A
+         * FieldRangeVectorIterator may be used to efficiently search for btree keys within these
+         * bounds.  Alternatively, a single compound field interval of the btree may be scanned,
+         * between a compound field start point and end point.  If isSingleInterval() is true then
+         * the interval between the start and end points will be an exact description of this
+         * FieldRangeVector, otherwise the start/end interval will be a superset of this
+         * FieldRangeVector.  For example:
+         *
+         * index { a:1 }, query { a:{ $gt:2, $lte:4 } }
+         *     -> frv ( 2, 4 ]
+         *         -> start/end bounds ( { '':2 }, { '':4 } ]
+         *
+         * index { a:1, b:1 }, query { a:2, b:{ $gte:7, $lt:9 } }
+         *     -> frv [ 2, 2 ], [ 7, 9 )
+         *         -> start/end bounds [ { '':2, '':7 }, { '':2, '':9 } )
+         *
+         * index { a:1, b:-1 }, query { a:2, b:{ $gte:7, $lt:9 } }
+         *     -> frv [ 2, 2 ], ( 9, 7 ]
+         *         -> start/end bounds ( { '':2, '':9 }, { '':2, '':7 } ]
+         *
+         * index { a:1, b:1 }, query { a:{ $gte:7, $lt:9 } }
+         *     -> frv [ 7, 9 )
+         *         -> start/end bounds [ { '':7, '':MinKey }, { '':9, '':MinKey } )
+         *
+         * index { a:1, b:1 }, query { a:{ $gte:2, $lte:5 }, b:{ $gte:7, $lte:9 } }
+         *     -> frv [ 2, 5 ], [ 7, 9 ]
+         *         -> start/end bounds [ { '':2, '':7 }, { '':5, '':9 } ]
+         *            (isSingleInterval() == false)
+         */
+
+        /**
+         * @return true if this FieldRangeVector represents a single interval within a btree,
+         * comprised of all keys between a single start point and a single end point.
+         */
+        bool isSingleInterval() const;
+
+        /**
+         * @return a starting point for an index traversal, a lower bound on the ranges represented
+         * by this FieldRangeVector according to the btree's native ordering.
+         */
         BSONObj startKey() const;
-        /** @return end point for an index traversal. */
+
+        /** @return true if the startKey() bound is inclusive. */
+        bool startKeyInclusive() const;
+
+        /**
+         * @return an end point for an index traversal, an upper bound on the ranges represented
+         * by this FieldRangeVector according to the btree's native ordering.
+         */
         BSONObj endKey() const;
+
+        /** @return true if the endKey() bound is inclusive. */
+        bool endKeyInclusive() const;
+
+        /** @return the number of index ranges represented by 'this' */
+        unsigned size() const;
+
         /** @return a client readable representation of 'this' */
         BSONObj obj() const;
         
diff --git a/src/mongo/dbtests/btreepositiontests.cpp b/src/mongo/dbtests/btreepositiontests.cpp
new file mode 100644
index 00000000000..ed8628aae7b
--- /dev/null
+++ b/src/mongo/dbtests/btreepositiontests.cpp
@@ -0,0 +1,327 @@
+/**
+ *    Copyright (C) 2012 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "mongo/db/btreeposition.h"
+
+#include "mongo/db/btree.h"
+#include "mongo/db/btreecursor.h"
+#include "mongo/db/pdfile.h"
+#include "mongo/dbtests/dbtests.h"
+#include "mongo/platform/cstdint.h"
+
+namespace BtreePositionTests {
+
+    DBDirectClient _client;
+    const char* _ns = "unittests.btreeposition";
+
+    namespace BtreeKeyLocation {
+        using mongo::BtreeKeyLocation;
+
+        /** Check equality comparison performed by BtreeKeyLocation::operator==. */
+        class Equality {
+        public:
+            void run() {
+                // Equal initially.
+                BtreeKeyLocation one, two;
+                ASSERT_EQUALS( one, two );
+
+                // Unequal with equal indexes but unequal buckets.
+                one.bucket = DiskLoc( 1, 2 );
+                ASSERT( !( one == two ) );
+
+                // Unequal with equal buckets but unequal indexes.
+                one.pos = 1;
+                two.bucket = DiskLoc( 1, 2 );
+                ASSERT( !( one == two ) );
+
+                // Equal with both bucket and index equal.
+                two.pos = 1;
+                ASSERT_EQUALS( one, two );
+            }
+        };
+
+    } // namespace BtreeKeyLocation
+
+    namespace LogicalBtreePosition {
+        using mongo::LogicalBtreePosition;
+        using mongo::BtreeKeyLocation;
+
+        /** Helper to construct custom btrees for tests. */
+        class TestableBtree : public BtreeBucket<V1> {
+        public:
+
+            /**
+             * Create a btree structure based on the json structure in @param 'spec', and set
+             * @param 'id' to this btree.
+             * @return the btree.
+             *
+             * For example the spec { b:{ a:null }, d:{ c:null }, _:{ e:null } } would create the
+             * btree
+             *
+             *      [ b, d ]
+             *     /   |    \
+             * [ a ] [ c ] [ e ]
+             *
+             * Dummy record locations are populated based on the string values.  The first character
+             * of each string value must be a hex digit.  See dummyRecordForKey().
+             */
+            static TestableBtree* set( const string& spec, IndexDetails& id ) {
+                DiskLoc btree = make( spec, id );
+                id.head = btree;
+                return cast( btree );
+            }
+
+            /** Cast a disk location to a TestableBtree. */
+            static TestableBtree* cast( const DiskLoc& l ) {
+                return static_cast<TestableBtree*>( l.btreemod<V1>() );
+            }
+
+            /** Push a new key to this bucket. */
+            void push( const BSONObj& key, DiskLoc child ) {
+                KeyOwned k(key);
+                pushBack( dummyRecordForKey( key ),
+                          k,
+                          Ordering::make( BSON( "a" << 1 ) ),
+                          child );
+            }
+
+            /** Delete a key from this bucket. */
+            void delKey( int index ) { _delKeyAtPos( index ); }
+
+            /** Reset the number of keys for this bucket. */
+            void setN( int newN ) { n = newN; }
+
+            /** Set the right child for this bucket. */
+            void setNext( const DiskLoc &child ) { nextChild = child; }
+
+            /** A dummy record DiskLoc generated from a key's string value. */
+            static DiskLoc dummyRecordForKey( const BSONObj& key ) {
+                return DiskLoc( 0, fromHex( key.firstElement().String()[ 0 ] ) );
+            }
+
+        private:
+            static DiskLoc make( const string& specString, IndexDetails& id ) {
+                BSONObj spec = fromjson( specString );
+                DiskLoc bucket = addBucket( id );
+                cast( bucket )->init();
+                TestableBtree* btree = TestableBtree::cast( bucket );
+                BSONObjIterator i( spec );
+                while( i.more() ) {
+                    BSONElement e = i.next();
+                    DiskLoc child;
+                    if ( e.type() == Object ) {
+                        child = make( e.embeddedObject().jsonString(), id );
+                    }
+                    if ( e.fieldName() == string( "_" ) ) {
+                        btree->setNext( child );
+                    }
+                    else {
+                        btree->push( BSON( "" << e.fieldName() ), child );
+                    }
+                }
+                btree->fixParentPtrs( bucket );
+                return bucket;
+            }
+        };
+
+        /**
+         * Helper to check that the expected key and its corresponding dummy record are located at
+         * the supplied key location.
+         */
+        void assertKeyForPosition( const string& expectedKey,
+                                   const BtreeKeyLocation& location ) {
+            BucketBasics<V1>::KeyNode keyNode =
+                    location.bucket.btree<V1>()->keyNode( location.pos );
+            BSONObj expectedKeyObj = BSON( "" << expectedKey );
+            ASSERT_EQUALS( expectedKeyObj, keyNode.key.toBson() );
+            ASSERT_EQUALS( TestableBtree::dummyRecordForKey( expectedKeyObj ),
+                           keyNode.recordLoc );
+        }
+
+        /** A btree position is recovered when the btree bucket is unmodified. */
+        class RecoverPositionBucketUnchanged {
+        public:
+            void run() {
+                Client::WriteContext ctx( _ns );
+                _client.dropCollection( _ns );
+
+                // Add an index and populate it with dummy keys.
+                _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+                IndexDetails& idx = nsdetails( _ns )->idx( 1 );
+                TestableBtree* btree = TestableBtree::set( "{b:{a:null},_:{c:null}}", idx );
+
+                // Locate the 'a' key.
+                BtreeKeyLocation aLocation( btree->keyNode( 0 ).prevChildBucket, 0 );
+
+                // Try to recover the key location.
+                Ordering ordering = Ordering::make( nsdetails( _ns )->idx( 1 ).keyPattern() );
+                LogicalBtreePosition logical( idx, ordering, aLocation );
+                logical.init();
+
+                // Check that the original location is recovered.
+                ASSERT_EQUALS( aLocation, logical.currentLocation() );
+
+                // Invalidate the original location.
+                logical.invalidateInitialLocation();
+
+                // Check that the original location is still recovered.
+                ASSERT_EQUALS( aLocation, logical.currentLocation() );
+                assertKeyForPosition( "a", logical.currentLocation() );
+            }
+        };
+
+        /** A btree position is recovered after its initial bucket is deallocated. */
+        class RecoverPositionBucketDeallocated {
+        public:
+            void run() {
+                Client::WriteContext ctx( _ns );
+                _client.dropCollection( _ns );
+
+                // Add an index and populate it with dummy keys.
+                _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+                IndexDetails& idx = nsdetails( _ns )->idx( 1 );
+                TestableBtree* btree = TestableBtree::set( "{b:{a:null},_:{c:null}}", idx );
+
+                // Locate the 'c' key.
+                BtreeKeyLocation cLocation( btree->getNextChild(), 0 );
+
+                // Identify the key position.
+                Ordering ordering = Ordering::make( nsdetails( _ns )->idx( 1 ).keyPattern() );
+                LogicalBtreePosition logical( idx, ordering, cLocation );
+                logical.init();
+
+                // Invalidate the 'c' key's btree bucket.
+                TestableBtree::cast( cLocation.bucket )->deallocBucket( cLocation.bucket, idx );
+
+                // Add the 'c' key back to the tree, in the root bucket.
+                btree->push( BSON( "" << "c" ),
+                             TestableBtree::dummyRecordForKey( BSON( "" << "c" ) ) );
+
+                // Check that the new location of 'c' is recovered.
+                ASSERT_EQUALS( BtreeKeyLocation( idx.head, 1 ), logical.currentLocation() );
+                assertKeyForPosition( "c", logical.currentLocation() );
+            }
+        };
+
+        /** A btree position is recovered after its initial bucket shrinks. */
+        class RecoverPositionKeyIndexInvalid {
+        public:
+            void run() {
+                Client::WriteContext ctx( _ns );
+                _client.dropCollection( _ns );
+
+                // Add an index and populate it with dummy keys.
+                _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+                IndexDetails& idx = nsdetails( _ns )->idx( 1 );
+                TestableBtree::set( "{b:{a:null},c:null,_:{d:null}}", idx );
+
+                // Locate the 'c' key.
+                BtreeKeyLocation cLocation( idx.head, 1 );
+
+                // Identify the key position.
+                Ordering ordering = Ordering::make( nsdetails( _ns )->idx( 1 ).keyPattern() );
+                LogicalBtreePosition logical( idx, ordering, cLocation );
+                logical.init();
+
+                // Remove the 'c' key by resizing the root bucket.
+                TestableBtree::cast( cLocation.bucket )->setN( 1 );
+
+                // Check that the location of 'd' is recovered.
+                assertKeyForPosition( "d", logical.currentLocation() );
+            }
+        };
+
+        /** A btree position is recovered after the key it refers to is removed. */
+        class RecoverPositionKeyRemoved {
+        public:
+            void run() {
+                Client::WriteContext ctx( _ns );
+                _client.dropCollection( _ns );
+
+                // Add an index and populate it with dummy keys.
+                _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+                IndexDetails& idx = nsdetails( _ns )->idx( 1 );
+                TestableBtree::set( "{b:{a:null},c:null,e:{d:null}}", idx );
+
+                // Locate the 'c' key.
+                BtreeKeyLocation cLocation( idx.head, 1 );
+
+                // Identify the key position.
+                Ordering ordering = Ordering::make( nsdetails( _ns )->idx( 1 ).keyPattern() );
+                LogicalBtreePosition logical( idx, ordering, cLocation );
+                logical.init();
+
+                // Remove the 'c' key.
+                TestableBtree::cast( cLocation.bucket )->delKey( 1 );
+
+                // Check that the location of 'd' is recovered.
+                assertKeyForPosition( "d", logical.currentLocation() );
+            }
+        };
+
+        /**
+         * A btree position is recovered after the key it refers to is removed, and a subsequent key
+         * has the same record location.
+         */
+        class RecoverPositionKeyRemovedWithMatchingRecord {
+        public:
+            void run() {
+                Client::WriteContext ctx( _ns );
+                _client.dropCollection( _ns );
+
+                // Add an index and populate it with dummy keys.
+                _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+                IndexDetails& idx = nsdetails( _ns )->idx( 1 );
+                TestableBtree* btree =
+                        TestableBtree::set( "{b:{a:null},c:null,ccc:{cc:null}}", idx );
+
+                // Verify that the 'c' key has the the same record location as the 'ccc' key, which
+                // is a requirement of this test.
+                ASSERT_EQUALS( btree->keyNode( 1 ).recordLoc, btree->keyNode( 2 ).recordLoc );
+
+                // Locate the 'c' key.
+                BtreeKeyLocation cLocation( idx.head, 1 );
+
+                // Identify the key position.
+                Ordering ordering = Ordering::make( nsdetails( _ns )->idx( 1 ).keyPattern() );
+                LogicalBtreePosition logical( idx, ordering, cLocation );
+                logical.init();
+
+                // Remove the 'c' key.
+                TestableBtree::cast( cLocation.bucket )->delKey( 1 );
+
+                // Check that the location of 'cc' is recovered.
+                assertKeyForPosition( "cc", logical.currentLocation() );
+            }
+        };
+
+    } // namespace LogicalBtreePosition
+
+    class All : public Suite {
+    public:
+        All() : Suite( "btreeposition" ) {
+        }
+        void setupTests() {
+            add<BtreeKeyLocation::Equality>();
+            add<LogicalBtreePosition::RecoverPositionBucketUnchanged>();
+            add<LogicalBtreePosition::RecoverPositionBucketDeallocated>();
+            add<LogicalBtreePosition::RecoverPositionKeyIndexInvalid>();
+            add<LogicalBtreePosition::RecoverPositionKeyRemoved>();
+            add<LogicalBtreePosition::RecoverPositionKeyRemovedWithMatchingRecord>();
+        }
+    } myall;
+
+} // BtreePositionTests
diff --git a/src/mongo/dbtests/cursortests.cpp b/src/mongo/dbtests/cursortests.cpp
index 14297e6f51e..b775c3baac1 100644
--- a/src/mongo/dbtests/cursortests.cpp
+++ b/src/mongo/dbtests/cursortests.cpp
@@ -351,6 +351,11 @@ namespace CursorTests {
             }
         };
 
+        class RequestMatcherFalse : public QueryPlanSelectionPolicy {
+            virtual string name() const { return "RequestMatcherFalse"; }
+            virtual bool requestMatcher() const { return false; }
+        } _requestMatcherFalse;
+
         /**
          * A BtreeCursor typically moves from one index match to another when its advance() method
          * is called.  However, to prevent excessive iteration advance() may bail out early before
@@ -381,8 +386,7 @@ namespace CursorTests {
                         NamespaceDetailsTransient::getCursor( ns(),
                                                               query,
                                                               BSONObj(),
-                                                              QueryPlanSelectionPolicy::any(),
-                                                              /* requestMatcher */ false );
+                                                              _requestMatcherFalse );
                 // The BtreeCursor attempts to find each of the values 0, 1, 2, ... etc in the
                 // btree.  Because the values 0.5, 1.5, etc are present in the btree, the
                 // BtreeCursor will explicitly look for all the values in the $in list during
@@ -425,8 +429,7 @@ namespace CursorTests {
                         NamespaceDetailsTransient::getCursor( ns(),
                                                               BSON( "a" << GT << 0 << LT << 5 ),
                                                               BSONObj(),
-                                                              QueryPlanSelectionPolicy::any(),
-                                                              /* requestMatcher */ false );
+                                                              _requestMatcherFalse );
                 while( c->ok() ) {
                     // A Matcher is provided even though 'requestMatcher' is false.
                     ASSERT( c->matcher() );
@@ -461,8 +464,7 @@ namespace CursorTests {
                         NamespaceDetailsTransient::getCursor( ns(),
                                                               BSON( "a.b" << 2 << "a.c" << 2 ),
                                                               BSONObj(),
-                                                              QueryPlanSelectionPolicy::any(),
-                                                              /* requestMatcher */ false );
+                                                              _requestMatcherFalse );
                 while( c->ok() ) {
                     // A Matcher is provided even though 'requestMatcher' is false.
                     ASSERT( c->matcher() );
@@ -491,8 +493,7 @@ namespace CursorTests {
                         NamespaceDetailsTransient::getCursor( ns(),
                                                               BSON( "a" << GTE << "" ),
                                                               BSONObj(),
-                                                              QueryPlanSelectionPolicy::any(),
-                                                              /* requestMatcher */ false );
+                                                              _requestMatcherFalse );
                 while( c->ok() ) {
                     ASSERT( !c->matcher() );
                     if ( c->currentMatches() ) {
@@ -520,8 +521,7 @@ namespace CursorTests {
                         NamespaceDetailsTransient::getCursor( ns(),
                                                               BSON( "a" << LTE << Date_t( 1 ) ),
                                                               BSONObj(),
-                                                              QueryPlanSelectionPolicy::any(),
-                                                              /* requestMatcher */ false );
+                                                              _requestMatcherFalse );
                 while( c->ok() ) {
                     ASSERT( !c->matcher() );
                     if ( c->currentMatches() ) {
diff --git a/src/mongo/dbtests/intervalbtreecursortests.cpp b/src/mongo/dbtests/intervalbtreecursortests.cpp
new file mode 100644
index 00000000000..4bb5a02ad94
--- /dev/null
+++ b/src/mongo/dbtests/intervalbtreecursortests.cpp
@@ -0,0 +1,660 @@
+/**
+ *    Copyright (C) 2012 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "mongo/db/intervalbtreecursor.h"
+
+#include "mongo/db/btree.h"
+#include "mongo/db/pdfile.h"
+#include "mongo/dbtests/dbtests.h"
+#include "mongo/platform/cstdint.h"
+
+namespace IntervalBtreeCursorTests {
+
+    DBDirectClient _client;
+    const char* _ns = "unittests.intervalbtreecursor";
+
+    /** An IntervalBtreeCursor can only be created for a version 1 index. */
+    class WrongIndexVersion {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+
+            // Create a version 0 index.
+            _client.ensureIndex( _ns, BSON( "a" << 1 ), false, "", true, false, /* version */ 0 );
+
+            // Attempt to create a cursor on the a:1 index.
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 5 ),
+                                                                  true,
+                                                                  BSON( "" << 6 ),
+                                                                  true ) );
+
+            // No cursor was created because the index was not of version 1.
+            ASSERT( !cursor );
+        }
+    };
+
+    class BasicAccessors {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            _client.insert( _ns, BSON( "a" << 5 ) );
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 5 ),
+                                                                  true,
+                                                                  BSON( "" << 6 ),
+                                                                  true ) );
+
+            // Create a reference BasicCursor, which will return identical values from certain
+            // accessors.
+            boost::shared_ptr<Cursor> reference = theDataFileMgr.findAll( _ns );
+
+            ASSERT( cursor->ok() );
+            ASSERT( reference->_current() == cursor->_current() );
+            ASSERT_EQUALS( reference->current(), cursor->current() );
+            ASSERT_EQUALS( reference->currLoc(), cursor->currLoc() );
+            ASSERT_EQUALS( BSON( "" << 5 ), cursor->currKey() );
+            ASSERT_EQUALS( cursor->currLoc(), cursor->refLoc() );
+            ASSERT_EQUALS( BSON( "a" << 1 ), cursor->indexKeyPattern() );
+            ASSERT( !cursor->supportGetMore() );
+            ASSERT( cursor->supportYields() );
+            ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+            ASSERT( !cursor->isMultiKey() );
+            ASSERT( !cursor->modifiedKeys() );
+            ASSERT_EQUALS( BSON( "lower" << BSON( "a" << 5 ) << "upper" << BSON( "a" << 6 ) ),
+                           cursor->prettyIndexBounds() );
+
+            // Advance the cursor to the end.
+            ASSERT( !cursor->advance() );
+            ASSERT( !cursor->ok() );
+            ASSERT( cursor->currLoc().isNull() );
+            ASSERT( cursor->currKey().isEmpty() );
+            ASSERT( cursor->refLoc().isNull() );
+        }
+    };
+
+    /**
+     * Check nscanned counting semantics.  The expectation is to match the behavior of BtreeCursor,
+     * as described in the test comments.
+     */
+    class Nscanned {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << 5 ) );
+            }
+            _client.insert( _ns, BSON( "a" << 7 ) );
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 5 ),
+                                                                  true,
+                                                                  BSON( "" << 6 ),
+                                                                  true ) );
+            // nscanned is 1 for the first match.
+            ASSERT_EQUALS( 1, cursor->nscanned() );
+            for( int32_t i = 1; i < 10; ++i ) {
+                ASSERT( cursor->ok() );
+
+                // nscanned is incremented by 1 for intermediate matches.
+                ASSERT_EQUALS( i, cursor->nscanned() );
+                ASSERT( cursor->advance() );
+            }
+            ASSERT( cursor->ok() );
+            ASSERT_EQUALS( 10, cursor->nscanned() );
+            ASSERT( !cursor->advance() );
+            ASSERT( !cursor->ok() );
+
+            // nscanned is not incremented when reaching the end of the cursor.
+            ASSERT_EQUALS( 10, cursor->nscanned() );            
+        }
+    };
+
+    /** Check that a CoveredIndexMatcher can be set and used properly by the cursor. */
+    class Matcher {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+
+            // Insert a document that will match.
+            _client.insert( _ns, BSON( "a" << 5 << "b" << 1 ) );
+
+            // Insert a document that will not match.
+            _client.insert( _ns, BSON( "a" << 5 << "b" << 2 ) );
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 5 ),
+                                                                  true,
+                                                                  BSON( "" << 5 ),
+                                                                  true ) );
+
+            // No matcher is set yet.
+            ASSERT( !cursor->matcher() );
+            ASSERT( cursor->currentMatches() );
+
+            // Create a matcher and set it on the cursor.
+            boost::shared_ptr<CoveredIndexMatcher> matcher
+                    ( new CoveredIndexMatcher( BSON( "a" << 5 << "b" << 1 ), BSON( "a" << 1 ) ) );
+            cursor->setMatcher( matcher );
+
+            // The document with b:1 matches.
+            ASSERT_EQUALS( 1, cursor->current()[ "b" ].Int() );
+            ASSERT( cursor->matcher()->matchesCurrent( cursor.get() ) );
+            ASSERT( cursor->currentMatches() );
+            cursor->advance();
+
+            // The document with b:2 does not match.
+            ASSERT_EQUALS( 2, cursor->current()[ "b" ].Int() );
+            ASSERT( !cursor->matcher()->matchesCurrent( cursor.get() ) );
+            ASSERT( !cursor->currentMatches() );
+        }
+    };
+
+    /** Check that dups are properly identified by the cursor. */
+    class Dups {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            _client.insert( _ns, BSON( "a" << BSON_ARRAY( 5 << 7 ) ) );
+            _client.insert( _ns, BSON( "a" << BSON_ARRAY( 6 << 8 ) ) );
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 5 ),
+                                                                  true,
+                                                                  BSON( "" << 10 ),
+                                                                  true ) );
+            ASSERT( cursor->isMultiKey() );
+            ASSERT( cursor->modifiedKeys() );
+
+            // This is the 5,7 document, first time seen.  Not a dup.
+            DiskLoc firstLoc = cursor->currLoc();
+            ASSERT( !cursor->getsetdup( cursor->currLoc() ) );
+            cursor->advance();
+
+            // This is the 6,8 document, first time seen.  Not a dup.
+            DiskLoc secondLoc = cursor->currLoc();
+            ASSERT( !cursor->getsetdup( cursor->currLoc() ) );
+            cursor->advance();
+
+            // This is the 5,7 document, second time seen.  A dup.
+            ASSERT_EQUALS( firstLoc, cursor->currLoc() );
+            ASSERT( cursor->getsetdup( cursor->currLoc() ) );
+            cursor->advance();
+
+            // This is the 6,8 document, second time seen.  A dup.
+            ASSERT_EQUALS( secondLoc, cursor->currLoc() );
+            ASSERT( cursor->getsetdup( cursor->currLoc() ) );            
+        }
+    };
+
+    /** Check that expected results are returned with inclusive bounds. */
+    class InclusiveBounds {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+
+            // Save 'a' values 1-10.
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << i ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+
+            // Iterate over 'a' values 3-7 inclusive.
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 3 ),
+                                                                  true,
+                                                                  BSON( "" << 7 ),
+                                                                  true ) );
+
+            // Check that the expected 'a' values are returned.
+            for( int32_t i = 3; i < 8; ++i, cursor->advance() ) {
+                ASSERT_EQUALS( i, cursor->current()[ "a" ].Int() );
+            }
+            ASSERT( !cursor->ok() );
+        }
+    };
+
+    /** Check that expected results are returned with exclusive bounds. */
+    class ExclusiveBounds {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+
+            // Save 'a' values 1-10.
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << i ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+
+            // Iterate over 'a' values 3-7 exclusive.
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 3 ),
+                                                                  false,
+                                                                  BSON( "" << 7 ),
+                                                                  false ) );
+
+            // Check that the expected 'a' values are returned.
+            for( int32_t i = 4; i < 7; ++i, cursor->advance() ) {
+                ASSERT_EQUALS( i, cursor->current()[ "a" ].Int() );
+            }
+            ASSERT( !cursor->ok() );
+        }
+    };
+
+    /** Check that killOp will interrupt cursor iteration. */
+    class Interrupt {
+    public:
+        ~Interrupt() {
+            // Reset curop's kill flag.
+            cc().curop()->reset();
+        }
+        void run() {
+            _client.dropCollection( _ns );
+            for( int32_t i = 0; i < 150; ++i ) {
+                _client.insert( _ns, BSON( "a" << 5 ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            Client::ReadContext ctx( _ns );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 5 ),
+                                                                  true,
+                                                                  BSON( "" << 5 ),
+                                                                  true ) );
+
+            // Register a request to kill the current operation.
+            cc().curop()->kill();
+
+            // Check that an exception is thrown when iterating the cursor.
+            ASSERT_THROWS( exhaustCursor( cursor.get() ), UserException );
+        }
+    private:
+        void exhaustCursor( Cursor* cursor ) {
+            while( cursor->advance() );
+        }
+    };
+
+    /** Check that a cursor returns no results if all documents are below the lower bound. */
+    class NothingAboveLowerBound {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            _client.insert( _ns, BSON( "a" << 2 ) );
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 2 ),
+                                                                  false,
+                                                                  BSON( "" << 3 ),
+                                                                  false ) );
+
+            // The cursor returns no results.
+            ASSERT( !cursor->ok() );
+        }
+    };
+
+    /** Check that a cursor returns no results if there are no documents within the interval. */
+    class NothingInInterval {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            _client.insert( _ns, BSON( "a" << 2 ) );
+            _client.insert( _ns, BSON( "a" << 3 ) );
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 2 ),
+                                                                  false,
+                                                                  BSON( "" << 3 ),
+                                                                  false ) );
+
+            // The cursor returns no results.
+            ASSERT( !cursor->ok() );
+        }
+    };
+    
+    /**
+     * Check that a cursor returns no results if there are no documents within the interval and
+     * the first key located during initialization is above the upper bound.
+     */
+    class NothingInIntervalFirstMatchBeyondUpperBound {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            _client.insert( _ns, BSON( "a" << 2 ) );
+            _client.insert( _ns, BSON( "a" << 4 ) );
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+
+            // Iterate over 'a' values ( 2, 3 ].
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                 nsdetails( _ns )->idx( 1 ),
+                                                                 BSON( "" << 2 ),
+                                                                 false,
+                                                                 BSON( "" << 3 ),
+                                                                 true ) );
+            ASSERT( !cursor->ok() );
+        }
+    };
+
+    /** Check that a cursor recovers its position properly if there is no change during a yield. */
+    class NoChangeDuringYield {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << i ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 2 ),
+                                                                  false,
+                                                                  BSON( "" << 6 ),
+                                                                  true ) );
+            while( cursor->current()[ "a" ].Int() != 5 ) {
+                cursor->advance();
+            }
+
+            // Prepare the cursor to yield.
+            cursor->prepareToYield();
+
+            // Recover the cursor.
+            cursor->recoverFromYield();
+
+            // The cursor is still at its original position.
+            ASSERT_EQUALS( 5, cursor->current()[ "a" ].Int() );
+
+            // The cursor can be advanced from this position.
+            ASSERT( cursor->advance() );
+            ASSERT_EQUALS( 6, cursor->current()[ "a" ].Int() );
+        }
+    };
+    
+    /**
+     * Check that a cursor recovers its position properly if its current location is deleted
+     * during a yield.
+     */
+    class DeleteDuringYield {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << i ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 2 ),
+                                                                  false,
+                                                                  BSON( "" << 6 ),
+                                                                  true ) );
+            while( cursor->current()[ "a" ].Int() != 5 ) {
+                cursor->advance();
+            }
+
+            // Prepare the cursor to yield.
+            cursor->prepareToYield();
+
+            // Remove the current iterate and all remaining iterates.
+            _client.remove( _ns, BSON( "a" << GTE << 5 ) );
+
+            // Recover the cursor.
+            cursor->recoverFromYield();
+
+            // The cursor is exhausted.
+            ASSERT( !cursor->ok() );
+        }
+    };
+    
+    /**
+     * Check that a cursor relocates its end location properly if the end location changes during a
+     * yield.
+     */
+    class InsertNewDocsDuringYield {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << i ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 2 ),
+                                                                  false,
+                                                                  BSON( "" << 6 ),
+                                                                  true ) );
+            while( cursor->current()[ "a" ].Int() != 4 ) {
+                cursor->advance();
+            }
+
+            // Prepare the cursor to yield.
+            cursor->prepareToYield();
+
+            // Insert one doc before the end.
+            _client.insert( _ns, BSON( "a" << 5.5 ) );
+
+            // Insert one doc after the end.
+            _client.insert( _ns, BSON( "a" << 6.5 ) );
+
+            // Recover the cursor.
+            cursor->recoverFromYield();
+
+            // Check that the cursor returns the expected remaining documents.
+            ASSERT_EQUALS( 4, cursor->current()[ "a" ].Int() );
+            ASSERT( cursor->advance() );
+            ASSERT_EQUALS( 5, cursor->current()[ "a" ].Int() );
+            ASSERT( cursor->advance() );
+            ASSERT_EQUALS( 5.5, cursor->current()[ "a" ].number() );
+            ASSERT( cursor->advance() );
+            ASSERT_EQUALS( 6, cursor->current()[ "a" ].Int() );
+            ASSERT( !cursor->advance() );
+        }
+    };
+
+    /** Check that isMultiKey() is updated correctly if an index becomes multikey during a yield. */
+    class BecomesMultikeyDuringYield {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << i ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 2 ),
+                                                                  false,
+                                                                  BSON( "" << 50 ),
+                                                                  true ) );
+            while( cursor->current()[ "a" ].Int() != 4 ) {
+                cursor->advance();
+            }
+
+            // Check that the cursor is not multikey.
+            ASSERT( !cursor->isMultiKey() );
+
+            // Prepare the cursor to yield.
+            cursor->prepareToYield();
+
+            // Insert a document with two values of 'a'.
+            _client.insert( _ns, BSON( "a" << BSON_ARRAY( 10 << 11 ) ) );
+
+            // Recover the cursor.
+            cursor->recoverFromYield();
+
+            // Check that the cursor becomes multikey.
+            ASSERT( cursor->isMultiKey() );
+
+            // Check that keys 10 and 11 are detected as duplicates.
+            while( cursor->currKey().firstElement().Int() != 10 ) {
+                ASSERT( cursor->advance() );
+            }
+            ASSERT( !cursor->getsetdup( cursor->currLoc() ) );
+            ASSERT( cursor->advance() );
+            ASSERT_EQUALS( 11, cursor->currKey().firstElement().Int() );
+            ASSERT( cursor->getsetdup( cursor->currLoc() ) );
+        }
+    };
+
+    /** Unused keys are not returned during iteration. */
+    class UnusedKeys {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << i ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+
+            // Mark keys at position 0, 3, and 4 as unused.
+            nsdetails( _ns )->idx( 1 ).head.btreemod<V1>()->_k( 0 ).setUnused();
+            nsdetails( _ns )->idx( 1 ).head.btreemod<V1>()->_k( 3 ).setUnused();
+            nsdetails( _ns )->idx( 1 ).head.btreemod<V1>()->_k( 4 ).setUnused();
+
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 0 ),
+                                                                  true,
+                                                                  BSON( "" << 6 ),
+                                                                  true ) );
+            
+            // Check that the unused keys are not returned but the other keys are returned.
+            ASSERT_EQUALS( 1, cursor->current()[ "a" ].Int() );
+            ASSERT( cursor->advance() );
+            ASSERT_EQUALS( 2, cursor->current()[ "a" ].Int() );
+            ASSERT( cursor->advance() );
+            ASSERT_EQUALS( 5, cursor->current()[ "a" ].Int() );
+            ASSERT( cursor->advance() );
+            ASSERT_EQUALS( 6, cursor->current()[ "a" ].Int() );
+            ASSERT( !cursor->advance() );
+        }
+    };
+
+    /** Iteration is properly terminated when the end location is an unused key. */
+    class UnusedEndKey {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << i ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+
+            // Mark the key at position 5 as unused.
+            nsdetails( _ns )->idx( 1 ).head.btreemod<V1>()->_k( 5 ).setUnused();
+
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                  nsdetails( _ns )->idx( 1 ),
+                                                                  BSON( "" << 4 ),
+                                                                  true,
+                                                                  BSON( "" << 5 ),
+                                                                  false ) );
+            
+            // Check the documents produced by the cursor.
+            ASSERT_EQUALS( 4, cursor->current()[ "a" ].Int() );
+            ASSERT( !cursor->advance() );
+        }
+    };
+
+    /** Advances past a key that becomes unused during a yield. */
+    class KeyBecomesUnusedDuringYield {
+    public:
+        void run() {
+            Client::WriteContext ctx( _ns );
+            _client.dropCollection( _ns );
+            for( int32_t i = 0; i < 10; ++i ) {
+                _client.insert( _ns, BSON( "a" << i ) );
+            }
+            _client.ensureIndex( _ns, BSON( "a" << 1 ) );
+            
+            scoped_ptr<Cursor> cursor( IntervalBtreeCursor::make( nsdetails( _ns ),
+                                                                 nsdetails( _ns )->idx( 1 ),
+                                                                 BSON( "" << 3 ),
+                                                                 true,
+                                                                 BSON( "" << 9 ),
+                                                                 true ) );
+            
+            // Advance the cursor to key a:5.
+            while( cursor->current()[ "a" ].Int() != 5 ) {
+                cursor->advance();
+            }
+
+            // Backup the cursor position.
+            cursor->prepareToYield();
+
+            // Mark the key at position 5 as unused.
+            nsdetails( _ns )->idx( 1 ).head.btreemod<V1>()->_k( 5 ).setUnused();
+
+            // Restore the cursor position.
+            cursor->recoverFromYield();
+
+            // The cursor advanced from 5, now unused, to 6.
+            ASSERT_EQUALS( 6, cursor->current()[ "a" ].Int() );
+        }
+    };
+
+    class All : public Suite {
+    public:
+        All() : Suite( "intervalbtreecursor" ) {
+        }
+        void setupTests() {
+            add<WrongIndexVersion>();
+            add<BasicAccessors>();
+            add<Nscanned>();
+            add<Matcher>();
+            add<Dups>();
+            add<InclusiveBounds>();
+            add<ExclusiveBounds>();
+            add<Interrupt>();
+            add<NothingAboveLowerBound>();
+            add<NothingInInterval>();
+            add<NothingInIntervalFirstMatchBeyondUpperBound>();
+            add<NoChangeDuringYield>();
+            add<DeleteDuringYield>();
+            add<InsertNewDocsDuringYield>();
+            add<BecomesMultikeyDuringYield>();
+            add<UnusedKeys>();
+            add<UnusedEndKey>();
+            add<KeyBecomesUnusedDuringYield>();
+        }
+    } myall;
+
+} // namespace IntervalBtreeCursorTests
diff --git a/src/mongo/dbtests/queryoptimizercursortests.cpp b/src/mongo/dbtests/queryoptimizercursortests.cpp
index 16709ba62ff..13be3cc2bc0 100644
--- a/src/mongo/dbtests/queryoptimizercursortests.cpp
+++ b/src/mongo/dbtests/queryoptimizercursortests.cpp
@@ -996,7 +996,7 @@ namespace QueryOptimizerCursorTests {
                                       BSON( "$query" << query << "$orderby" << order ),
                                       BSONObj() ) );
             return NamespaceDetailsTransient::getCursor( ns(), query, order,
-                                                        QueryPlanSelectionPolicy::any(), 0,
+                                                        QueryPlanSelectionPolicy::any(),
                                                         parsedQuery, false );
         }
     };
@@ -2844,7 +2844,7 @@ namespace QueryOptimizerCursorTests {
                                       BSONObj() ) );
             shared_ptr<Cursor> cursor =
             NamespaceDetailsTransient::getCursor( ns(), query, order,
-                                                  QueryPlanSelectionPolicy::any(), 0, parsedQuery,
+                                                  QueryPlanSelectionPolicy::any(), parsedQuery,
                                                   false );
             shared_ptr<QueryOptimizerCursor> ret =
             dynamic_pointer_cast<QueryOptimizerCursor>( cursor );
@@ -2897,7 +2897,7 @@ namespace QueryOptimizerCursorTests {
                                       BSON( "b" << 1 ) ) );
             shared_ptr<Cursor> cursor =
             NamespaceDetailsTransient::getCursor( ns(), BSON( "a" << 4 ), BSONObj(),
-                                                  QueryPlanSelectionPolicy::any(), 0, parsedQuery,
+                                                  QueryPlanSelectionPolicy::any(), parsedQuery,
                                                   false );
             while( cursor->advance() );
             // No plan recorded when a hint is used.
@@ -2911,7 +2911,7 @@ namespace QueryOptimizerCursorTests {
             shared_ptr<Cursor> cursor2 =
             NamespaceDetailsTransient::getCursor( ns(), BSON( "a" << 4 ),
                                                  BSON( "b" << 1 << "c" << 1 ),
-                                                 QueryPlanSelectionPolicy::any(), 0,
+                                                 QueryPlanSelectionPolicy::any(),
                                                  parsedQuery2, false );
             while( cursor2->advance() );
             // Plan recorded was for a different query pattern (different sort spec).
@@ -3513,7 +3513,7 @@ namespace QueryOptimizerCursorTests {
                 }
                 shared_ptr<Cursor> c =
                 NamespaceDetailsTransient::getCursor( ns(), extractedQuery, order(), planPolicy(),
-                                                      true, _parsedQuery, false );
+                                                      _parsedQuery, false );
                 string type = c->toString().substr( 0, expectedType().length() );
                 ASSERT_EQUALS( expectedType(), type );
                 check( c );
@@ -3651,7 +3651,7 @@ namespace QueryOptimizerCursorTests {
                                           BSONObj() ) );
                 shared_ptr<Cursor> c =
                 NamespaceDetailsTransient::getCursor( ns(), BSONObj(), BSON( "a" << 1 ),
-                                                     QueryPlanSelectionPolicy::any(), 0,
+                                                     QueryPlanSelectionPolicy::any(),
                                                      parsedQuery, false );
                 ASSERT( c );
             }
@@ -3990,6 +3990,11 @@ namespace QueryOptimizerCursorTests {
             }
         };
 
+        class RequestMatcherFalse : public QueryPlanSelectionPolicy {
+            virtual string name() const { return "RequestMatcherFalse"; }
+            virtual bool requestMatcher() const { return false; }
+        } _requestMatcherFalse;
+
         /**
          * A Cursor returned by NamespaceDetailsTransient::getCursor() may or may not have a
          * matcher().  A Matcher will generally exist if required to match the provided query or
@@ -4020,8 +4025,9 @@ namespace QueryOptimizerCursorTests {
                         NamespaceDetailsTransient::getCursor( ns(),
                                                               query,
                                                               BSONObj(),
-                                                              QueryPlanSelectionPolicy::any(),
-                                                              requestMatcher );
+                                                              requestMatcher ?
+                                                                  QueryPlanSelectionPolicy::any() :
+                                                                  _requestMatcherFalse );
                 return cursor->matcher();
             }
         };
@@ -4040,11 +4046,33 @@ namespace QueryOptimizerCursorTests {
                         ( NamespaceDetailsTransient::getCursor( ns(),
                                                                 fromjson( "{a:undefined}" ),
                                                                 BSONObj(),
-                                                                QueryPlanSelectionPolicy::any(),
-                                                                /* requestMatcher */ false ),
+                                                                _requestMatcherFalse ),
                           UserException );
             }
         };
+
+        class RequestIntervalCursorTrue : public QueryPlanSelectionPolicy {
+            virtual string name() const { return "RequestIntervalCursorTrue"; }
+            virtual bool requestIntervalCursor() const { return true; }
+        } _requestIntervalCursorTrue;
+
+        /** An IntervalBtreeCursor is selected when requested by a QueryPlanSelectionPolicy. */
+        class IntervalCursor : public Base {
+        public:
+            IntervalCursor() {
+                _cli.insert( ns(), BSON( "a" << 2 << "b" << 3 ) );
+                _cli.ensureIndex( ns(), BSON( "a" << 1 ) );
+            }
+            void run() {
+                Client::ReadContext ctx( ns() );
+                shared_ptr<Cursor> cursor =
+                        NamespaceDetailsTransient::getCursor( ns(),
+                                                              BSON( "a" << 1 ),
+                                                              BSONObj(),
+                                                              _requestIntervalCursorTrue );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+            }
+        };
         
     } // namespace GetCursor
     
@@ -4068,7 +4096,8 @@ namespace QueryOptimizerCursorTests {
                         ( new ParsedQuery( ns(), 0, 0, 0,
                                           BSON( "$query" << query << "$explain" << true ),
                                           BSONObj() ) );
-                c = NamespaceDetailsTransient::getCursor( ns(), query, BSONObj(), QueryPlanSelectionPolicy::any(), 0,
+                c = NamespaceDetailsTransient::getCursor( ns(), query, BSONObj(),
+                                                          QueryPlanSelectionPolicy::any(),
                                                           parsedQuery, false );
                 set<BSONObj> indexKeys;
                 while( c->ok() ) {
@@ -4093,7 +4122,8 @@ namespace QueryOptimizerCursorTests {
                                           fields() ) );
                 _cursor =
                 dynamic_pointer_cast<QueryOptimizerCursor>
-                ( NamespaceDetailsTransient::getCursor( ns(), query(), BSONObj(), QueryPlanSelectionPolicy::any(), 0,
+                ( NamespaceDetailsTransient::getCursor( ns(), query(), BSONObj(),
+                                                        QueryPlanSelectionPolicy::any(),
                                                         parsedQuery, false ) );
                 ASSERT( _cursor );
                 
@@ -4907,6 +4937,7 @@ namespace QueryOptimizerCursorTests {
             add<GetCursor::MatcherValidation>();
             add<GetCursor::MatcherSet>();
             add<GetCursor::MatcherValidate>();
+            add<GetCursor::IntervalCursor>();
             add<Explain::ClearRecordedIndex>();
             add<Explain::Initial>();
             add<Explain::Empty>();
diff --git a/src/mongo/dbtests/queryoptimizertests.cpp b/src/mongo/dbtests/queryoptimizertests.cpp
index 6360b3f0f5a..52269e15b4d 100644
--- a/src/mongo/dbtests/queryoptimizertests.cpp
+++ b/src/mongo/dbtests/queryoptimizertests.cpp
@@ -641,6 +641,219 @@ namespace {
                 ASSERT_EQUALS( QueryPlan::Disallowed, newPlan( query )->utility() );
             }
         };
+
+        /** Test conditions in which QueryPlan::newCursor() returns an IntervalBtreeCursor. */
+        class IntervalCursorCreate : public Base {
+        public:
+            void run() {
+                // An interval cursor will not be created if the query plan is not Optimal.  (See
+                // comments on Optimal value of QueryPlan::Utility enum.)
+                BSONObj query = fromjson( "{a:{$gt:4},b:{$gt:5}}" );
+                scoped_ptr<QueryPlan> plan( QueryPlan::make( nsd(),
+                                                             INDEXNO( "a" << 1 << "b" << 1 ),
+                                                             FRSP( query ),
+                                                             FRSP2( query ),
+                                                             query,
+                                                             BSONObj() ) );
+                shared_ptr<Cursor> cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_NOT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+
+                // An interval cursor will not be created if the query plan is Optimal but does not
+                // consist of a single interval.
+                query = fromjson( "{a:4,b:{$in:[5,6]}}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             INDEXNO( "a" << 1 << "b" << 1 ),
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_NOT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+
+                // An interval cursor will be created if the field ranges consist of a single
+                // interval.
+                query = fromjson( "{a:4,b:{$gt:6,$lte:9}}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             INDEXNO( "a" << 1 << "b" << 1 ),
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+                ASSERT_EQUALS( BSON( "lower" << BSON( "a" << 4 << "b" << 6 ) <<
+                                     "upper" << BSON( "a" << 4 << "b" << 9 ) ),
+                               cursor->prettyIndexBounds() );
+
+                // But an interval cursor will not be created if it is not requested.
+                query = fromjson( "{a:4,b:{$gt:6,$lte:9}}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             INDEXNO( "a" << 1 << "b" << 1 ),
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), /* requestIntervalCursor */ false );
+                ASSERT_NOT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+
+                // An interval cursor will not be created for a v0 index (unsupported).
+                client().ensureIndex( ns(),
+                                      BSON( "x" << 1 << "y" << 1 ),
+                                      false,
+                                      "",
+                                      false,
+                                      false,
+                                      0 );
+                query = fromjson( "{x:2,y:3}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             indexno( BSON( "x" << 1 << "y" << 1 ) ),
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_NOT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+            }
+        };
+
+        /**
+         * Test that interval cursors returned by newCursor iterate over matching documents only.
+         */
+        class IntervalCursorBounds : public Base {
+        public:
+            void run() {
+                client().insert( ns(), BSON( "_id" << 0 << "a" << 1 << "b" << 1 ) );
+                client().insert( ns(), BSON( "_id" << 1 << "a" << 1 << "b" << 2 ) );
+                client().insert( ns(), BSON( "_id" << 2 << "a" << 2 << "b" << 1 ) );
+                client().insert( ns(), BSON( "_id" << 3 << "a" << 2 << "b" << 2 ) );
+
+                BSONObj query = fromjson( "{a:2,b:{$lte:2}}" );
+                scoped_ptr<QueryPlan> plan( QueryPlan::make( nsd(),
+                                                             INDEXNO( "a" << 1 << "b" << 1 ),
+                                                             FRSP( query ),
+                                                             FRSP2( query ),
+                                                             query,
+                                                             BSONObj() ) );
+                shared_ptr<Cursor> cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+                ASSERT_EQUALS( BSON( "_id" << 2 << "a" << 2 << "b" << 1 ), cursor->current() );
+                ASSERT( cursor->advance() );
+                ASSERT_EQUALS( BSON( "_id" << 3 << "a" << 2 << "b" << 2 ), cursor->current() );
+                ASSERT( !cursor->advance() );
+
+                query = fromjson( "{a:{$lt:2}}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             INDEXNO( "a" << 1 << "b" << 1 ),
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+                ASSERT_EQUALS( BSON( "_id" << 0 << "a" << 1 << "b" << 1 ), cursor->current() );
+                ASSERT( cursor->advance() );
+                ASSERT_EQUALS( BSON( "_id" << 1 << "a" << 1 << "b" << 2 ), cursor->current() );
+                ASSERT( !cursor->advance() );
+
+                query = fromjson( "{a:{$lt:2}}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             INDEXNO( "a" << 1 << "b" << -1 ), // note -1
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+                ASSERT_EQUALS( BSON( "_id" << 1 << "a" << 1 << "b" << 2 ), cursor->current() );
+                ASSERT( cursor->advance() );
+                ASSERT_EQUALS( BSON( "_id" << 0 << "a" << 1 << "b" << 1 ), cursor->current() );
+                ASSERT( !cursor->advance() );
+
+                query = fromjson( "{a:{$gt:1}}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             INDEXNO( "a" << 1 << "b" << 1 ),
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+                ASSERT_EQUALS( BSON( "_id" << 2 << "a" << 2 << "b" << 1 ), cursor->current() );
+                ASSERT( cursor->advance() );
+                ASSERT_EQUALS( BSON( "_id" << 3 << "a" << 2 << "b" << 2 ), cursor->current() );
+                ASSERT( !cursor->advance() );
+
+                query = fromjson( "{a:{$gt:1}}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             INDEXNO( "a" << 1 << "b" << -1 ), // note -1
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+                ASSERT_EQUALS( BSON( "_id" << 3 << "a" << 2 << "b" << 2 ), cursor->current() );
+                ASSERT( cursor->advance() );
+                ASSERT_EQUALS( BSON( "_id" << 2 << "a" << 2 << "b" << 1 ), cursor->current() );
+                ASSERT( !cursor->advance() );
+
+                query = fromjson( "{a:2,b:{$lte:2}}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             INDEXNO( "a" << 1 << "b" << -1 ), // note -1
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+                ASSERT_EQUALS( BSON( "_id" << 3 << "a" << 2 << "b" << 2 ), cursor->current() );
+                ASSERT( cursor->advance() );
+                ASSERT_EQUALS( BSON( "_id" << 2 << "a" << 2 << "b" << 1 ), cursor->current() );
+                ASSERT( !cursor->advance() );
+
+                query = fromjson( "{a:1,b:{$gte:1}}" );
+                plan.reset( QueryPlan::make( nsd(),
+                                             INDEXNO( "a" << -1 << "b" << -1 ), // note -1
+                                             FRSP( query ),
+                                             FRSP2( query ),
+                                             query,
+                                             BSONObj() ) );
+                cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+                ASSERT_EQUALS( BSON( "_id" << 1 << "a" << 1 << "b" << 2 ), cursor->current() );
+                ASSERT( cursor->advance() );
+                ASSERT_EQUALS( BSON( "_id" << 0 << "a" << 1 << "b" << 1 ), cursor->current() );
+                ASSERT( !cursor->advance() );
+            }
+        };
+
+        /** IntervalBtreeCursor is used and a Matcher is necessary. */
+        class IntervalCursorWithMatcher : public Base {
+        public:
+            void run() {
+                client().insert( ns(), BSON( "_id" << 0 << "a" << 1 ) );
+                client().insert( ns(), BSON( "_id" << 1 << "a" << 1 << "b" << "exists" ) );
+                BSONObj query = BSON( "a" << 1 << "b" << BSON( "$exists" << true ) );
+                scoped_ptr<QueryPlan> plan( QueryPlan::make( nsd(),
+                                            INDEXNO( "a" << 1 ),
+                                            FRSP( query ),
+                                            FRSP2( query ),
+                                            query,
+                                            BSONObj() ) );
+                shared_ptr<Cursor> cursor = plan->newCursor( DiskLoc(), true );
+                ASSERT_EQUALS( "IntervalBtreeCursor", cursor->toString() );
+                ASSERT( plan->mayBeMatcherNecessary() );
+                cursor->setMatcher( plan->matcher() );
+
+                // Check the cursor's results, and whether they match.
+                ASSERT_EQUALS( 0, cursor->current()[ "_id" ].Int() );
+                ASSERT( !cursor->currentMatches() );
+                ASSERT( cursor->advance() );
+                ASSERT_EQUALS( 1, cursor->current()[ "_id" ].Int() );
+                ASSERT( cursor->currentMatches() );
+                ASSERT( !cursor->advance() );
+            }
+        };
         
         namespace QueryBoundsExactOrderSuffix {
             
@@ -861,6 +1074,9 @@ namespace {
             add<QueryPlanTests::Unhelpful>();
             add<QueryPlanTests::KeyFieldsOnly>();
             add<QueryPlanTests::SparseExistsFalse>();
+            add<QueryPlanTests::IntervalCursorCreate>();
+            add<QueryPlanTests::IntervalCursorBounds>();
+            add<QueryPlanTests::IntervalCursorWithMatcher>();
             add<QueryPlanTests::QueryBoundsExactOrderSuffix::Unindexed>();
             add<QueryPlanTests::QueryBoundsExactOrderSuffix::RangeSort>();
             add<QueryPlanTests::QueryBoundsExactOrderSuffix::RangeBeforeSort>();
diff --git a/src/mongo/dbtests/queryutiltests.cpp b/src/mongo/dbtests/queryutiltests.cpp
index 171798493ef..9c4fc3c8d3a 100644
--- a/src/mongo/dbtests/queryutiltests.cpp
+++ b/src/mongo/dbtests/queryutiltests.cpp
@@ -1820,6 +1820,266 @@ namespace QueryUtilTests {
             }
         };
 
+        /** Detecting cases where a FieldRangeVector describes a single btree interval. */
+        class SingleInterval {
+        public:
+            void run() {
+                // Equality on a single field is a single interval.
+                FieldRangeVector frv1( FieldRangeSet( "dummy", BSON( "a" << 5 ), true, true ),
+                                       IndexSpec( BSON( "a" << 1 ) ),
+                                       1 );
+                ASSERT( frv1.isSingleInterval() );
+                // Single interval on a single field is a single interval.
+                FieldRangeVector frv2( FieldRangeSet( "dummy", BSON( "a" << GT << 5 ), true, true ),
+                                       IndexSpec( BSON( "a" << 1 ) ),
+                                       1 );
+                ASSERT( frv2.isSingleInterval() );
+                // Multiple intervals on a single field is not a single interval.
+                FieldRangeVector frv3( FieldRangeSet( "dummy",
+                                                      fromjson( "{a:{$in:[4,5]}}" ),
+                                                      true,
+                                                      true ),
+                                      IndexSpec( BSON( "a" << 1 ) ),
+                                      1 );
+                ASSERT( !frv3.isSingleInterval() );
+
+                // Equality on two fields is a compound single interval.
+                FieldRangeVector frv4( FieldRangeSet( "dummy",
+                                                      BSON( "a" << 5 << "b" << 6 ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 ) ),
+                                       1 );
+                ASSERT( frv4.isSingleInterval() );
+                // Equality on first field and single interval on second field is a compound
+                // single interval.
+                FieldRangeVector frv5( FieldRangeSet( "dummy",
+                                                      BSON( "a" << 5 << "b" << GT << 6 ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 ) ),
+                                       1 );
+                ASSERT( frv5.isSingleInterval() );
+                // Single interval on first field and single interval on second field is not a
+                // compound single interval.
+                FieldRangeVector frv6( FieldRangeSet( "dummy",
+                                                      BSON( "a" << LT << 5 << "b" << GT << 6 ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 ) ),
+                                       1 );
+                ASSERT( !frv6.isSingleInterval() );
+                // Multiple intervals on two fields is not a compound single interval.
+                FieldRangeVector frv7( FieldRangeSet( "dummy",
+                                                      fromjson( "{a:{$in:[4,5]},b:{$in:[7,8]}}" ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 ) ),
+                                       1 );
+                ASSERT( !frv7.isSingleInterval() );
+
+                // With missing second field is still a single compound interval.
+                FieldRangeVector frv8( FieldRangeSet( "dummy",
+                                                      BSON( "a" << 5 ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 ) ),
+                                       1 );
+                ASSERT( frv8.isSingleInterval() );
+                // With missing second field is still a single compound interval.
+                FieldRangeVector frv9( FieldRangeSet( "dummy",
+                                                      BSON( "b" << 5 ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 ) ),
+                                       1 );
+                ASSERT( !frv9.isSingleInterval() );
+
+                // Equality on first two fields and single interval on third field is a compound
+                // single interval.
+                FieldRangeVector frv10( FieldRangeSet( "dummy",
+                                                       fromjson( "{a:5,b:6,c:{$gt:7}}" ),
+                                                       true,
+                                                       true ),
+                                        IndexSpec( BSON( "a" << 1 << "b" << 1 << "c" << 1 ) ),
+                                        1 );
+                ASSERT( frv10.isSingleInterval() );
+
+                // Equality, then single interval, then missing is a compound single interval.
+                FieldRangeVector frv11( FieldRangeSet( "dummy",
+                                                       fromjson( "{a:5,b:{$gt:7}}" ),
+                                                       true,
+                                                       true ),
+                                        IndexSpec( BSON( "a" << 1 << "b" << 1 << "c" << 1 ) ),
+                                        1 );
+                ASSERT( frv11.isSingleInterval() );
+                // Equality, then single interval, then missing, then missing is a compound single
+                // interval.
+                FieldRangeVector frv12( FieldRangeSet( "dummy",
+                                                       fromjson( "{a:5,b:{$gt:7}}" ),
+                                                       true,
+                                                       true ),
+                                        IndexSpec( BSON( "a" << 1 <<
+                                                         "b" << 1 <<
+                                                         "c" << 1 <<
+                                                         "d" << 1 ) ),
+                                        1 );
+                ASSERT( frv12.isSingleInterval() );
+                // Equality, then single interval, then missing, then missing, with mixed order
+                // fields is a compound single interval.
+                FieldRangeVector frv13( FieldRangeSet( "dummy",
+                                                       fromjson( "{a:5,b:{$gt:7}}" ),
+                                                       true,
+                                                       true ),
+                                        IndexSpec( BSON( "a" << 1 <<
+                                                         "b" << 1 <<
+                                                         "c" << 1 <<
+                                                         "d" << -1 ) ),
+                                        1 );
+                ASSERT( frv13.isSingleInterval() );
+                // Equality, then single interval, then missing, then single interval is not a
+                // compound single interval.
+                FieldRangeVector frv14( FieldRangeSet( "dummy",
+                                                       fromjson( "{a:5,b:{$gt:7},d:{$gt:1}}" ),
+                                                       true,
+                                                       true ),
+                                        IndexSpec( BSON( "a" << 1 <<
+                                                         "b" << 1 <<
+                                                         "c" << 1 <<
+                                                         "d" << 1 ) ),
+                                        1 );
+                ASSERT( !frv14.isSingleInterval() );
+            }
+        };
+
+        /** Check start and end key values. */
+        class StartEndKey {
+        public:
+            void run() {
+                // Equality on a single field.
+                FieldRangeVector frv1( FieldRangeSet( "dummy", BSON( "a" << 5 ), true, true ),
+                                       IndexSpec( BSON( "a" << 1 ) ),
+                                       1 );
+                ASSERT_EQUALS( BSON( "" << 5 ), frv1.startKey() );
+                ASSERT( frv1.startKeyInclusive() );
+                ASSERT_EQUALS( BSON( "" << 5 ), frv1.endKey() );
+                ASSERT( frv1.endKeyInclusive() );
+                // Single interval on a single field.
+                FieldRangeVector frv2( FieldRangeSet( "dummy", BSON( "a" << GT << 5 ), true, true ),
+                                       IndexSpec( BSON( "a" << 1 ) ),
+                                       1 );
+                ASSERT_EQUALS( BSON( "" << 5 ), frv2.startKey() );
+                ASSERT( !frv2.startKeyInclusive() );
+                ASSERT_EQUALS( BSON( "" << numeric_limits<double>::max() ), frv2.endKey() );
+                ASSERT( frv2.endKeyInclusive() );
+
+                // Equality on two fields.
+                FieldRangeVector frv3( FieldRangeSet( "dummy",
+                                                      BSON( "a" << 5 << "b" << 6 ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 ) ),
+                                       1 );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << 6 ), frv3.startKey() );
+                ASSERT( frv3.startKeyInclusive() );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << 6 ), frv3.endKey() );
+                ASSERT( frv3.endKeyInclusive() );
+                // Equality on first field and single interval on second field.
+                FieldRangeVector frv4( FieldRangeSet( "dummy",
+                                                      BSON( "a" << 5 << "b" << LT << 6 ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 ) ),
+                                       1 );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << -numeric_limits<double>::max() ),
+                               frv4.startKey() );
+                ASSERT( frv4.startKeyInclusive() );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << 6 ),
+                               frv4.endKey() );
+                ASSERT( !frv4.endKeyInclusive() );
+
+                // With missing second field.
+                FieldRangeVector frv5( FieldRangeSet( "dummy",
+                                                      BSON( "a" << 5 ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 ) ),
+                                       1 );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << MINKEY ), frv5.startKey() );
+                ASSERT( frv5.startKeyInclusive() );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << MAXKEY ), frv5.endKey() );
+                ASSERT( frv5.endKeyInclusive() );
+                // Equality, then single interval, then missing.
+                FieldRangeVector frv6( FieldRangeSet( "dummy",
+                                                      fromjson( "{a:5,b:{$gt:7}}" ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 << "b" << 1 << "c" << 1 ) ),
+                                       1 );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << 7 << "" << MAXKEY ), frv6.startKey() );
+                ASSERT( !frv6.startKeyInclusive() );
+                ASSERT_EQUALS( BSON( "" << 5 <<
+                                     "" << numeric_limits<double>::max() <<
+                                     "" << MAXKEY ),
+                               frv6.endKey() );
+                ASSERT( frv6.endKeyInclusive() );
+                // Equality, then single interval, then missing, then missing.
+                FieldRangeVector frv7( FieldRangeSet( "dummy",
+                                                      fromjson( "{a:5,b:{$gt:7}}" ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 <<
+                                                        "b" << 1 <<
+                                                        "c" << 1 <<
+                                                        "d" << 1 ) ),
+                                       1 );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << 7 << "" << MAXKEY << "" << MAXKEY ),
+                               frv7.startKey() );
+                ASSERT( !frv7.startKeyInclusive() );
+                ASSERT_EQUALS( BSON( "" << 5 <<
+                                     "" << numeric_limits<double>::max() <<
+                                     "" << MAXKEY <<
+                                     "" << MAXKEY ),
+                               frv7.endKey() );
+                ASSERT( frv7.endKeyInclusive() );
+
+                // Equality, then single exclusive interval on both ends, then missing, then
+                // missing with mixed direction index ordering.
+                FieldRangeVector frv8( FieldRangeSet( "dummy",
+                                                      fromjson( "{a:5,b:{$gt:7,$lt:10}}" ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 <<
+                                                        "b" << 1 <<
+                                                        "c" << 1 <<
+                                                        "d" << -1 ) ),
+                                       1 );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << 7 << "" << MAXKEY << "" << MINKEY ),
+                               frv8.startKey() );
+                ASSERT( !frv8.startKeyInclusive() );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << 10 << "" << MINKEY << "" << MAXKEY ),
+                               frv8.endKey() );
+                ASSERT( !frv8.endKeyInclusive() );
+                // Equality, then single exclusive interval on both ends, then missing, then
+                // missing with mixed direction index ordering and reverse direction traversal.
+                FieldRangeVector frv9( FieldRangeSet( "dummy",
+                                                      fromjson( "{a:5,b:{$gt:7,$lt:10}}" ),
+                                                      true,
+                                                      true ),
+                                       IndexSpec( BSON( "a" << 1 <<
+                                                        "b" << 1 <<
+                                                        "c" << 1 <<
+                                                        "d" << -1 ) ),
+                                       -1 );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << 10 << "" << MINKEY << "" << MAXKEY ),
+                               frv9.startKey() );
+                ASSERT( !frv9.startKeyInclusive() );
+                ASSERT_EQUALS( BSON( "" << 5 << "" << 7 << "" << MAXKEY << "" << MINKEY ),
+                               frv9.endKey() );
+                ASSERT( !frv9.endKeyInclusive() );
+            }
+        };
+
     } // namespace FieldRangeVectorTests
     
     // These are currently descriptive, not normative tests.  SERVER-5450
@@ -2795,6 +3055,8 @@ namespace QueryUtilTests {
             add<FieldRangeSetPairTests::BestIndexForPatterns>();
             add<FieldRangeVectorTests::ToString>();
             add<FieldRangeVectorTests::HasAllIndexedRanges>();
+            add<FieldRangeVectorTests::SingleInterval>();
+            add<FieldRangeVectorTests::StartEndKey>();
             add<FieldRangeVectorIteratorTests::AdvanceToNextIntervalEquality>();
             add<FieldRangeVectorIteratorTests::AdvanceToNextIntervalExclusiveInequality>();
             add<FieldRangeVectorIteratorTests::AdvanceToNextIntervalEqualityReverse>();