diff options
Diffstat (limited to 'src')
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>(); |