diff options
Diffstat (limited to 'db/btree.h')
| -rw-r--r-- | db/btree.h | 110 |
1 files changed, 67 insertions, 43 deletions
@@ -18,7 +18,7 @@ #pragma once -#include "../stdafx.h" +#include "../pch.h" #include "jsobj.h" #include "diskloc.h" #include "pdfile.h" @@ -26,7 +26,6 @@ namespace mongo { #pragma pack(1) - struct _KeyNode { DiskLoc prevChildBucket; // the lchild DiskLoc recordLoc; // location of the record associated with the key @@ -60,7 +59,6 @@ namespace mongo { return !isUnused(); } }; - #pragma pack() class BucketBasics; @@ -75,7 +73,6 @@ namespace mongo { }; #pragma pack(1) - /* this class is all about the storage management */ class BucketBasics { friend class BtreeBuilder; @@ -83,8 +80,11 @@ namespace mongo { public: void dumpTree(DiskLoc thisLoc, const BSONObj &order); bool isHead() { return parent.isNull(); } - void assertValid(const BSONObj &order, bool force = false); - int fullValidate(const DiskLoc& thisLoc, const BSONObj &order); /* traverses everything */ + void assertValid(const Ordering &order, bool force = false); + void assertValid(const BSONObj &orderObj, bool force = false) { + return assertValid(Ordering::make(orderObj),force); + } + int fullValidate(const DiskLoc& thisLoc, const BSONObj &order, int *unusedCount = 0); /* traverses everything */ KeyNode keyNode(int i) const { if ( i >= n ){ @@ -106,13 +106,13 @@ namespace mongo { /* returns false if node is full and must be split keypos is where to insert -- inserted after that key #. so keypos=0 is the leftmost one. */ - bool basicInsert(const DiskLoc& thisLoc, int keypos, const DiskLoc& recordLoc, const BSONObj& key, const BSONObj &order); + bool basicInsert(const DiskLoc& thisLoc, int &keypos, const DiskLoc& recordLoc, const BSONObj& key, const Ordering &order); /** * @return true if works, false if not enough space */ - bool _pushBack(const DiskLoc& recordLoc, BSONObj& key, const BSONObj &order, DiskLoc prevChild); - void pushBack(const DiskLoc& recordLoc, BSONObj& key, const BSONObj &order, DiskLoc prevChild){ + bool _pushBack(const DiskLoc& recordLoc, BSONObj& key, const Ordering &order, DiskLoc prevChild); + void pushBack(const DiskLoc& recordLoc, BSONObj& key, const Ordering &order, DiskLoc prevChild){ bool ok = _pushBack( recordLoc , key , order , prevChild ); assert(ok); } @@ -130,12 +130,12 @@ namespace mongo { } int totalDataSize() const; - void pack( const BSONObj &order ); + void pack( const Ordering &order, int &refPos); void setNotPacked(); void setPacked(); int _alloc(int bytes); void _unalloc(int bytes); - void truncateTo(int N, const BSONObj &order); + void truncateTo(int N, const Ordering &order, int &refPos); void markUnused(int keypos); /* BtreeBuilder uses the parent var as a temp place to maintain a linked list chain. @@ -152,7 +152,7 @@ namespace mongo { ss << " n: " << n << endl; ss << " parent: " << parent.toString() << endl; ss << " nextChild: " << parent.toString() << endl; - ss << " Size: " << _Size << " flags:" << flags << endl; + ss << " flags:" << flags << endl; ss << " emptySize: " << emptySize << " topSize: " << topSize << endl; return ss.str(); } @@ -164,7 +164,12 @@ namespace mongo { protected: void _shape(int level, stringstream&); DiskLoc nextChild; // child bucket off and to the right of the highest key. - int _Size; // total size of this btree node in bytes. constant. + + private: + unsigned short _wasSize; // can be reused, value is 8192 in current pdfile version Apr2010 + unsigned short _reserved1; // zero + + protected: int Size() const; int flags; int emptySize; // size of the empty region @@ -179,7 +184,9 @@ namespace mongo { } char data[4]; }; +#pragma pack() +#pragma pack(1) class BtreeBucket : public BucketBasics { friend class BtreeCursor; public: @@ -191,20 +198,20 @@ namespace mongo { BSONObj order = ((IndexDetails&)idx).keyPattern(); likewise below in bt_insert() etc. */ - bool exists(const IndexDetails& idx, DiskLoc thisLoc, const BSONObj& key, BSONObj order); + bool exists(const IndexDetails& idx, DiskLoc thisLoc, const BSONObj& key, const Ordering& order); bool wouldCreateDup( const IndexDetails& idx, DiskLoc thisLoc, - const BSONObj& key, BSONObj order, + const BSONObj& key, const Ordering& order, DiskLoc self); static DiskLoc addBucket(IndexDetails&); /* start a new index off, empty */ - void deallocBucket(const DiskLoc &thisLoc); // clear bucket memory, placeholder for deallocation + void deallocBucket(const DiskLoc &thisLoc, IndexDetails &id); static void renameIndexNamespace(const char *oldNs, const char *newNs); int bt_insert(DiskLoc thisLoc, DiskLoc recordLoc, - const BSONObj& key, const BSONObj &order, bool dupsAllowed, + const BSONObj& key, const Ordering &order, bool dupsAllowed, IndexDetails& idx, bool toplevel = true); bool unindex(const DiskLoc& thisLoc, IndexDetails& id, BSONObj& key, const DiskLoc& recordLoc); @@ -215,7 +222,7 @@ namespace mongo { found - returns true if exact match found. note you can get back a position result even if found is false. */ - DiskLoc locate(const IndexDetails& , const DiskLoc& thisLoc, const BSONObj& key, const BSONObj &order, + DiskLoc locate(const IndexDetails& , const DiskLoc& thisLoc, const BSONObj& key, const Ordering &order, int& pos, bool& found, DiskLoc recordLoc, int direction=1); /** @@ -227,6 +234,9 @@ namespace mongo { /* advance one key position in the index: */ DiskLoc advance(const DiskLoc& thisLoc, int& keyOfs, int direction, const char *caller); + + void advanceTo(const IndexDetails &id, DiskLoc &thisLoc, int &keyOfs, const BSONObj &keyBegin, int keyBeginLen, const vector< const BSONElement * > &keyEnd, const Ordering &order, int direction ); + DiskLoc getHead(const DiskLoc& thisLoc); /* get tree shape */ @@ -243,24 +253,28 @@ namespace mongo { } static BtreeBucket* allocTemp(); /* caller must release with free() */ void insertHere(DiskLoc thisLoc, int keypos, - DiskLoc recordLoc, const BSONObj& key, const BSONObj &order, + DiskLoc recordLoc, const BSONObj& key, const Ordering &order, DiskLoc lchild, DiskLoc rchild, IndexDetails&); int _insert(DiskLoc thisLoc, DiskLoc recordLoc, - const BSONObj& key, const BSONObj &order, bool dupsAllowed, + const BSONObj& key, const Ordering &order, bool dupsAllowed, DiskLoc lChild, DiskLoc rChild, IndexDetails&); - bool find(const IndexDetails& idx, const BSONObj& key, DiskLoc recordLoc, const BSONObj &order, int& pos, bool assertIfDup); + bool find(const IndexDetails& idx, const BSONObj& key, DiskLoc recordLoc, const Ordering &order, int& pos, bool assertIfDup); + bool customFind( int l, int h, const BSONObj &keyBegin, int keyBeginLen, const vector< const BSONElement * > &keyEnd, const Ordering &order, int direction, DiskLoc &thisLoc, int &keyOfs, pair< DiskLoc, int > &bestParent ); static void findLargestKey(const DiskLoc& thisLoc, DiskLoc& largestLoc, int& largestKey); + static int customBSONCmp( const BSONObj &l, const BSONObj &rBegin, int rBeginLen, const vector< const BSONElement * > &rEnd, const Ordering &o ); public: // simply builds and returns a dup key error message string static string dupKeyError( const IndexDetails& idx , const BSONObj& key ); }; +#pragma pack() class BtreeCursor : public Cursor { public: BtreeCursor( NamespaceDetails *_d, int _idxNo, const IndexDetails&, const BSONObj &startKey, const BSONObj &endKey, bool endKeyInclusive, int direction ); - BtreeCursor( NamespaceDetails *_d, int _idxNo, const IndexDetails& _id, const BoundList &_bounds, int _direction ); - + BtreeCursor( NamespaceDetails *_d, int _idxNo, const IndexDetails& _id, const shared_ptr< FieldRangeVector > &_bounds, int _direction ); + ~BtreeCursor(){ + } virtual bool ok() { return !bucket.isNull(); } @@ -272,6 +286,7 @@ namespace mongo { virtual void noteLocation(); // updates keyAtKeyOfs... virtual void checkLocation(); virtual bool supportGetMore() { return true; } + virtual bool supportYields() { return true; } /* used for multikey index traversal to avoid sending back dups. see Matcher::matches(). if a multikey index traversal: @@ -279,7 +294,6 @@ namespace mongo { otherwise, marks loc as sent. @return true if the loc has not been seen */ - set<DiskLoc> dups; virtual bool getsetdup(DiskLoc loc) { if( multikey ) { pair<set<DiskLoc>::iterator, bool> p = dups.insert(loc); @@ -326,7 +340,7 @@ namespace mongo { virtual string toString() { string s = string("BtreeCursor ") + indexDetails.indexName(); if ( direction < 0 ) s += " reverse"; - if ( bounds_.size() > 1 ) s += " multi"; + if ( bounds_.get() && bounds_->size() > 1 ) s += " multi"; return s; } @@ -335,26 +349,31 @@ namespace mongo { } virtual BSONObj prettyIndexBounds() const { - BSONArrayBuilder ba; - if ( bounds_.size() == 0 ) { - ba << BSON_ARRAY( prettyKey( startKey ) << prettyKey( endKey ) ); + if ( !_independentFieldRanges ) { + return BSON( "start" << prettyKey( startKey ) << "end" << prettyKey( endKey ) ); } else { - for( BoundList::const_iterator i = bounds_.begin(); i != bounds_.end(); ++i ) { - ba << BSON_ARRAY( prettyKey( i->first ) << prettyKey( i->second ) ); - } + return bounds_->obj(); } - return ba.arr(); } void forgetEndKey() { endKey = BSONObj(); } + virtual CoveredIndexMatcher *matcher() const { return _matcher.get(); } + + virtual void setMatcher( shared_ptr< CoveredIndexMatcher > matcher ) { + _matcher = matcher; + } + + // for debugging only + DiskLoc getBucket() const { return bucket; } + private: /* Our btrees may (rarely) have "unused" keys when items are deleted. Skip past them. */ - void skipUnusedKeys(); - - /* Check if the current key is beyond endKey. */ + bool skipUnusedKeys( bool mayJump ); + bool skipOutOfRangeKeysAndCheckEnd(); + void skipAndCheck(); void checkEnd(); // selective audits on construction @@ -363,36 +382,40 @@ namespace mongo { // set initial bucket void init(); - // init start / end keys with a new range - void initInterval(); - + void advanceTo( const BSONObj &keyBegin, int keyBeginLen, const vector< const BSONElement * > &keyEnd); + friend class BtreeBucket; + set<DiskLoc> dups; NamespaceDetails *d; int idxNo; + BSONObj startKey; BSONObj endKey; bool endKeyInclusive_; + bool multikey; // note this must be updated every getmore batch in case someone added a multikey... const IndexDetails& indexDetails; BSONObj order; + Ordering _ordering; DiskLoc bucket; int keyOfs; int direction; // 1=fwd,-1=reverse BSONObj keyAtKeyOfs; // so we can tell if things moved around on us between the query and the getMore call DiskLoc locAtKeyOfs; - BoundList bounds_; - unsigned boundIndex_; + shared_ptr< FieldRangeVector > bounds_; + auto_ptr< FieldRangeVector::Iterator > _boundsIterator; const IndexSpec& _spec; + shared_ptr< CoveredIndexMatcher > _matcher; + bool _independentFieldRanges; }; -#pragma pack() inline bool IndexDetails::hasKey(const BSONObj& key) { - return head.btree()->exists(*this, head, key, keyPattern()); + return head.btree()->exists(*this, head, key, Ordering::make(keyPattern())); } inline bool IndexDetails::wouldCreateDup(const BSONObj& key, DiskLoc self) { - return head.btree()->wouldCreateDup(*this, head, key, keyPattern(), self); + return head.btree()->wouldCreateDup(*this, head, key, Ordering::make(keyPattern()), self); } /* build btree from the bottom up */ @@ -403,6 +426,7 @@ namespace mongo { unsigned long long n; BSONObj keyLast; BSONObj order; + Ordering ordering; bool committed; DiskLoc cur, first; |