diff options
Diffstat (limited to 'src/mongo')
21 files changed, 696 insertions, 647 deletions
diff --git a/src/mongo/SConscript b/src/mongo/SConscript index 11e26346b10..6d0485feced 100644 --- a/src/mongo/SConscript +++ b/src/mongo/SConscript @@ -539,7 +539,6 @@ serverOnlyFiles = [ "db/curop.cpp", "db/lockstat.cpp", "db/lockstate.cpp", "db/structure/btree/key.cpp", - "db/structure/btree/btreebuilder.cpp", "util/logfile.cpp", "util/alignedbuilder.cpp", "util/elapsed_tracker.cpp", @@ -594,6 +593,7 @@ serverOnlyFiles = [ "db/curop.cpp", "db/index/2d_access_method.cpp", "db/index/btree_access_method.cpp", "db/index/btree_based_access_method.cpp", + "db/index/btree_based_bulk_access_method.cpp", "db/index/btree_index_cursor.cpp", "db/index/index_descriptor.cpp", "db/index/fts_access_method.cpp", diff --git a/src/mongo/db/catalog/index_create.cpp b/src/mongo/db/catalog/index_create.cpp index 44e1fa157c8..f71b107e984 100644 --- a/src/mongo/db/catalog/index_create.cpp +++ b/src/mongo/db/catalog/index_create.cpp @@ -34,20 +34,19 @@ #include "mongo/client/dbclientinterface.h" #include "mongo/db/audit.h" #include "mongo/db/background.h" -#include "mongo/db/structure/btree/btreebuilder.h" +#include "mongo/db/catalog/collection.h" #include "mongo/db/clientcursor.h" #include "mongo/db/curop.h" #include "mongo/db/extsort.h" -#include "mongo/db/structure/catalog/index_details.h" #include "mongo/db/kill_current_op.h" -#include "mongo/db/structure/catalog/namespace_details.h" #include "mongo/db/pdfile_private.h" #include "mongo/db/query/internal_plans.h" #include "mongo/db/query/runner_yield_policy.h" #include "mongo/db/repl/is_master.h" #include "mongo/db/repl/oplog.h" #include "mongo/db/repl/rs.h" -#include "mongo/db/catalog/collection.h" +#include "mongo/db/structure/catalog/index_details.h" +#include "mongo/db/structure/catalog/namespace_details.h" #include "mongo/util/processinfo.h" #include "mongo/util/progress_meter.h" @@ -79,14 +78,13 @@ namespace mongo { unsigned long long addExistingToIndex( Collection* collection, const IndexDescriptor* descriptor, IndexAccessMethod* accessMethod, - bool shouldYield ) { + bool shouldYield) { string ns = collection->ns().ns(); // our copy for sanity bool dupsAllowed = !descriptor->unique(); bool dropDups = descriptor->dropDups(); - string curopMessage; { stringstream ss; @@ -264,6 +262,13 @@ namespace mongo { Status status = btreeState->accessMethod()->commitBulk( bulk, mayInterrupt, &dupsToDrop ); + + // Code above us expects a uassert in case of dupkey errors. + if (ErrorCodes::DuplicateKey == status.code()) { + uassertStatusOK(status); + } + + // Any other errors are probably bad and deserve a massert. massert( 17398, str::stream() << "commitBulk failed: " << status.toString(), status.isOK() ); diff --git a/src/mongo/db/index/btree_access_method.h b/src/mongo/db/index/btree_access_method.h index dbe1a7980af..d40bc013767 100644 --- a/src/mongo/db/index/btree_access_method.h +++ b/src/mongo/db/index/btree_access_method.h @@ -31,10 +31,9 @@ #include <boost/scoped_ptr.hpp> #include "mongo/base/status.h" -#include "mongo/db/structure/btree/btree.h" -#include "mongo/db/index/index_access_method.h" -#include "mongo/db/index/btree_key_generator.h" #include "mongo/db/index/btree_based_access_method.h" +#include "mongo/db/index/btree_key_generator.h" +#include "mongo/db/index/index_access_method.h" #include "mongo/db/jsobj.h" namespace mongo { diff --git a/src/mongo/db/index/btree_based_access_method.cpp b/src/mongo/db/index/btree_based_access_method.cpp index 11b4b92f9c2..ebd933cb0ac 100644 --- a/src/mongo/db/index/btree_based_access_method.cpp +++ b/src/mongo/db/index/btree_based_access_method.cpp @@ -34,6 +34,7 @@ #include "mongo/base/status.h" #include "mongo/db/curop.h" #include "mongo/db/extsort.h" +#include "mongo/db/index/btree_based_bulk_access_method.h" #include "mongo/db/index/btree_index_cursor.h" #include "mongo/db/jsobj.h" #include "mongo/db/keypattern.h" @@ -42,8 +43,6 @@ #include "mongo/db/pdfile_private.h" #include "mongo/db/repl/is_master.h" #include "mongo/db/repl/rs.h" -#include "mongo/db/sort_phase_one.h" -#include "mongo/db/structure/btree/btreebuilder.h" #include "mongo/db/structure/btree/btree_interface.h" #include "mongo/util/progress_meter.h" @@ -189,22 +188,7 @@ namespace mongo { } Status BtreeBasedAccessMethod::initializeAsEmpty() { - if ( !_btreeState->head().isNull() ) - return Status( ErrorCodes::InternalError, "index already initialized" ); - - DiskLoc newHead; - if ( 0 == _descriptor->version() ) { - newHead = BtreeBucket<V0>::addBucket( _btreeState ); - } - else if ( 1 == _descriptor->version() ) { - newHead = BtreeBucket<V1>::addBucket( _btreeState ); - } - else { - return Status( ErrorCodes::InternalError, "invalid index number" ); - } - _btreeState->setHead( newHead ); - - return Status::OK(); + return _newInterface->initAsEmpty(); } Status BtreeBasedAccessMethod::touch(const BSONObj& obj) { @@ -220,23 +204,26 @@ namespace mongo { return Status::OK(); } - DiskLoc BtreeBasedAccessMethod::findSingle( const BSONObj& key ) const { - DiskLoc head = _btreeState->head(); - Record* record = _btreeState->recordStore()->recordFor( head ); + DiskLoc BtreeBasedAccessMethod::findSingle(const BSONObj& key) const { + DiskLoc bucket; + int pos; + + _newInterface->locate(key, minDiskLoc, 1, &bucket, &pos); - if ( 0 == _descriptor->version() ) { - return BtreeBucket<V0>::asVersion( record )->findSingle( _btreeState, - _btreeState->head(), - key ); + // A null bucket means the key wasn't found (nor was anything found after it). + if (bucket.isNull()) { + return DiskLoc(); } - if ( 1 == _descriptor->version() ) { - return BtreeBucket<V1>::asVersion( record )->findSingle( _btreeState, - _btreeState->head(), - key ); + + // We found something but it could be a key after 'key'. Examine what we're pointing at. + if (0 != key.woCompare(_newInterface->getKey(bucket, pos), BSONObj(), false)) { + // If the keys don't match, return "not found." + return DiskLoc(); } - verify( 0 ); - } + // Return the DiskLoc found. + return _newInterface->getDiskLoc(bucket, pos); + } Status BtreeBasedAccessMethod::validate(int64_t* numKeys) { // XXX: long long vs int64_t @@ -284,7 +271,7 @@ namespace mongo { Status BtreeBasedAccessMethod::update(const UpdateTicket& ticket, int64_t* numUpdated) { if (!ticket._isValid) { - return Status(ErrorCodes::InternalError, "Invalid updateticket in update"); + return Status(ErrorCodes::InternalError, "Invalid UpdateTicket in update"); } BtreeBasedPrivateUpdateData* data = @@ -307,255 +294,25 @@ namespace mongo { return Status::OK(); } - // ------- - - class BtreeBulk : public IndexAccessMethod { - public: - BtreeBulk( BtreeBasedAccessMethod* real ) { - _real = real; - } - - ~BtreeBulk() {} - - virtual Status insert(const BSONObj& obj, - const DiskLoc& loc, - const InsertDeleteOptions& options, - int64_t* numInserted) { - BSONObjSet keys; - _real->getKeys(obj, &keys); - _phase1.addKeys(keys, loc, false); - if ( numInserted ) - *numInserted += keys.size(); - return Status::OK(); - } - - virtual Status remove(const BSONObj& obj, - const DiskLoc& loc, - const InsertDeleteOptions& options, - int64_t* numDeleted) { - return _notAllowed(); - } - - virtual Status validateUpdate(const BSONObj& from, - const BSONObj& to, - const DiskLoc& loc, - const InsertDeleteOptions& options, - UpdateTicket* ticket) { - return _notAllowed(); - } - - virtual Status update(const UpdateTicket& ticket, int64_t* numUpdated) { - return _notAllowed(); - } - - virtual Status newCursor(IndexCursor **out) const { - return _notAllowed(); - } - - virtual Status initializeAsEmpty() { - return _notAllowed(); - } - - virtual IndexAccessMethod* initiateBulk() { - return NULL; - } - - virtual Status commitBulk( IndexAccessMethod* bulk, - bool mayInterrupt, - std::set<DiskLoc>* dups ) { - verify( this == bulk ); - return Status::OK(); - } - - virtual Status touch(const BSONObj& obj) { - return _notAllowed(); - } - - virtual Status validate(int64_t* numKeys) { - return _notAllowed(); - } - - // ------- - - template< class V > - void commit( set<DiskLoc>* dupsToDrop, - CurOp* op, - bool mayInterrupt ) { - - Timer timer; - - IndexCatalogEntry* entry = _real->_btreeState; - - bool dupsAllowed = !entry->descriptor()->unique() || - ignoreUniqueIndex(entry->descriptor()); - bool dropDups = entry->descriptor()->dropDups() || inDBRepair; - - BtreeBuilder<V> btBuilder(dupsAllowed, entry); - - BSONObj keyLast; - scoped_ptr<BSONObjExternalSorter::Iterator> i( _phase1.sorter->iterator() ); - - // verifies that pm and op refer to the same ProgressMeter - ProgressMeter& pm = op->setMessage("Index Bulk Build: (2/3) btree bottom up", - "Index: (2/3) BTree Bottom Up Progress", - _phase1.nkeys, - 10); - - while( i->more() ) { - RARELY if ( mayInterrupt ) killCurrentOp.checkForInterrupt(); - ExternalSortDatum d = i->next(); - - try { - if ( !dupsAllowed && dropDups ) { - LastError::Disabled led( lastError.get() ); - btBuilder.addKey(d.first, d.second); - } - else { - btBuilder.addKey(d.first, d.second); - } - } - catch( AssertionException& e ) { - if ( dupsAllowed ) { - // unknown exception?? - throw; - } - - if (ErrorCodes::isInterruption( - DBException::convertExceptionCode(e.getCode()))) { - killCurrentOp.checkForInterrupt(); - } - - if ( ! dropDups ) - throw; - - /* we could queue these on disk, but normally there are very few dups, - * so instead we keep in ram and have a limit. - */ - if ( dupsToDrop ) { - dupsToDrop->insert(d.second); - uassert( 10092, - "too may dups on index build with dropDups=true", - dupsToDrop->size() < 1000000 ); - } - } - pm.hit(); - } - pm.finished(); - op->setMessage("Index Bulk Build: (3/3) btree-middle", - "Index: (3/3) BTree Middle Progress"); - LOG(timer.seconds() > 10 ? 0 : 1 ) << "\t done building bottom layer, going to commit"; - btBuilder.commit( mayInterrupt ); - if ( btBuilder.getn() != _phase1.nkeys && ! dropDups ) { - warning() << "not all entries were added to the index, probably some " - << "keys were too large" << endl; - } - } - - // ------- - - Status _notAllowed() const { - return Status( ErrorCodes::InternalError, "cannot use bulk for this yet" ); - } - - BtreeBasedAccessMethod* _real; // now owned here - SortPhaseOne _phase1; - }; - - int oldCompare(const BSONObj& l,const BSONObj& r, const Ordering &o); // key.cpp - - class BtreeExternalSortComparisonV0 : public ExternalSortComparison { - public: - BtreeExternalSortComparisonV0(const BSONObj& ordering) - : _ordering(Ordering::make(ordering)){ - } - - virtual ~BtreeExternalSortComparisonV0() { } - - virtual int compare(const ExternalSortDatum& l, const ExternalSortDatum& r) const { - int x = oldCompare(l.first, r.first, _ordering); - if (x) { return x; } - return l.second.compare(r.second); - } - private: - const Ordering _ordering; - }; - - class BtreeExternalSortComparisonV1 : public ExternalSortComparison { - public: - BtreeExternalSortComparisonV1(const BSONObj& ordering) - : _ordering(Ordering::make(ordering)) { - } - - virtual ~BtreeExternalSortComparisonV1() { } - - virtual int compare(const ExternalSortDatum& l, const ExternalSortDatum& r) const { - int x = l.first.woCompare(r.first, _ordering, /*considerfieldname*/false); - if (x) { return x; } - return l.second.compare(r.second); - } - private: - const Ordering _ordering; - }; - - ExternalSortComparison* BtreeBasedAccessMethod::getComparison(int version, - const BSONObj& keyPattern) { - - if ( 0 == version ) { - return new BtreeExternalSortComparisonV0( keyPattern ); - } - else if ( 1 == version ) { - return new BtreeExternalSortComparisonV1( keyPattern ); - } - verify( 0 ); - return NULL; - } - IndexAccessMethod* BtreeBasedAccessMethod::initiateBulk() { + // If there's already data in the index, don't do anything. if (!_newInterface->isEmpty()) { return NULL; } - auto_ptr<BtreeBulk> bulk( new BtreeBulk( this ) ); - bulk->_phase1.sortCmp.reset( getComparison( _descriptor->version(), - _descriptor->keyPattern() ) ); - - bulk->_phase1.sorter.reset( new BSONObjExternalSorter(bulk->_phase1.sortCmp.get()) ); - bulk->_phase1.sorter->hintNumObjects( _btreeState->collection()->numRecords() ); - - return bulk.release(); + return new BtreeBasedBulkAccessMethod( + this, _newInterface.get(), _descriptor, _btreeState->collection()->numRecords()); } - Status BtreeBasedAccessMethod::commitBulk( IndexAccessMethod* bulkRaw, - bool mayInterrupt, - set<DiskLoc>* dupsToDrop ) { - + Status BtreeBasedAccessMethod::commitBulk(IndexAccessMethod* bulkRaw, + bool mayInterrupt, + set<DiskLoc>* dupsToDrop) { if (!_newInterface->isEmpty()) { - return Status( ErrorCodes::InternalError, "trying to commit, but has data already" ); - } - - { - DiskLoc oldHead = _btreeState->head(); - _btreeState->setHead( DiskLoc() ); - _btreeState->recordStore()->deleteRecord( oldHead ); + return Status(ErrorCodes::InternalError, "trying to commit but has data already"); } - string ns = _btreeState->collection()->ns().ns(); - - BtreeBulk* bulk = static_cast<BtreeBulk*>( bulkRaw ); - if ( bulk->_phase1.multi ) - _btreeState->setMultikey(); - - bulk->_phase1.sorter->sort( false ); - - if ( _descriptor->version() == 0 ) - bulk->commit<V0>( dupsToDrop, cc().curop(), mayInterrupt ); - else if ( _descriptor->version() == 1 ) - bulk->commit<V1>( dupsToDrop, cc().curop(), mayInterrupt ); - else - return Status( ErrorCodes::InternalError, "bad btree version" ); - - return Status::OK(); + BtreeBasedBulkAccessMethod* bulk = static_cast<BtreeBasedBulkAccessMethod*>(bulkRaw); + return bulk->commit(dupsToDrop, cc().curop(), mayInterrupt); } - } // namespace mongo diff --git a/src/mongo/db/index/btree_based_access_method.h b/src/mongo/db/index/btree_based_access_method.h index f75d63ed042..5d5dab921dc 100644 --- a/src/mongo/db/index/btree_based_access_method.h +++ b/src/mongo/db/index/btree_based_access_method.h @@ -40,7 +40,6 @@ namespace mongo { - class BtreeBulk; class ExternalSortComparison; /** @@ -96,13 +95,9 @@ namespace mongo { // XXX: consider migrating callers to use IndexCursor instead virtual DiskLoc findSingle( const BSONObj& key ) const; - // exposed for testing, used for bulk commit - static ExternalSortComparison* getComparison(int version, - const BSONObj& keyPattern); - protected: // Friends who need getKeys. - friend class BtreeBulk; + friend class BtreeBasedBulkAccessMethod; // See below for body. class BtreeBasedPrivateUpdateData; diff --git a/src/mongo/db/index/btree_based_bulk_access_method.cpp b/src/mongo/db/index/btree_based_bulk_access_method.cpp new file mode 100644 index 00000000000..b812c4d5999 --- /dev/null +++ b/src/mongo/db/index/btree_based_bulk_access_method.cpp @@ -0,0 +1,210 @@ +/** +* Copyright (C) 2013 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/>. +* +* As a special exception, the copyright holders give permission to link the +* code of portions of this program with the OpenSSL library under certain +* conditions as described in each individual source file and distribute +* linked combinations including the program with the OpenSSL library. You +* must comply with the GNU Affero General Public License in all respects for +* all of the code used other than as permitted herein. If you modify file(s) +* with this exception, you may extend this exception to your version of the +* file(s), but you are not obligated to do so. If you do not wish to do so, +* delete this exception statement from your version. If you delete this +* exception statement from all source files in the program, then also delete +* it in the license file. +*/ + +#include "mongo/db/index/btree_based_bulk_access_method.h" + +#include "mongo/db/kill_current_op.h" +#include "mongo/db/pdfile_private.h" // This is for inDBRepair. +#include "mongo/db/repl/rs.h" // This is for ignoreUniqueIndex. +#include "mongo/util/progress_meter.h" + +namespace mongo { + + // + // Comparison for external sorter interface + // + + // Defined in db/structure/btree/key.cpp + // XXX TODO: rename to something more descriptive, etc. etc. + int oldCompare(const BSONObj& l,const BSONObj& r, const Ordering &o); + + class BtreeExternalSortComparisonV0 : public ExternalSortComparison { + public: + BtreeExternalSortComparisonV0(const BSONObj& ordering) + : _ordering(Ordering::make(ordering)){ + } + + virtual ~BtreeExternalSortComparisonV0() { } + + virtual int compare(const ExternalSortDatum& l, const ExternalSortDatum& r) const { + int x = oldCompare(l.first, r.first, _ordering); + if (x) { return x; } + return l.second.compare(r.second); + } + private: + const Ordering _ordering; + }; + + class BtreeExternalSortComparisonV1 : public ExternalSortComparison { + public: + BtreeExternalSortComparisonV1(const BSONObj& ordering) + : _ordering(Ordering::make(ordering)) { + } + + virtual ~BtreeExternalSortComparisonV1() { } + + virtual int compare(const ExternalSortDatum& l, const ExternalSortDatum& r) const { + int x = l.first.woCompare(r.first, _ordering, /*considerfieldname*/false); + if (x) { return x; } + return l.second.compare(r.second); + } + private: + const Ordering _ordering; + }; + + // static + ExternalSortComparison* BtreeBasedBulkAccessMethod::getComparison(int version, const BSONObj& keyPattern) { + if (0 == version) { + return new BtreeExternalSortComparisonV0(keyPattern); + } + else if (1 == version) { + return new BtreeExternalSortComparisonV1(keyPattern); + } + verify( 0 ); + return NULL; + } + + BtreeBasedBulkAccessMethod::BtreeBasedBulkAccessMethod(BtreeBasedAccessMethod* real, + transition::BtreeInterface* interface, + const IndexDescriptor* descriptor, + int numRecords) { + + _real = real; + _interface = interface; + + _docsInserted = 0; + _keysInserted = 0; + _isMultiKey = false; + + _sortCmp.reset(getComparison(descriptor->version(), descriptor->keyPattern())); + _sorter.reset(new BSONObjExternalSorter(_sortCmp.get())); + _sorter->hintNumObjects(numRecords); + } + + Status BtreeBasedBulkAccessMethod::insert(const BSONObj& obj, + const DiskLoc& loc, + const InsertDeleteOptions& options, + int64_t* numInserted) { + BSONObjSet keys; + _real->getKeys(obj, &keys); + + _isMultiKey = _isMultiKey || (keys.size() > 1); + + for (BSONObjSet::iterator it = keys.begin(); it != keys.end(); ++it) { + // False is for mayInterrupt. + _sorter->add(*it, loc, false); + _keysInserted++; + } + + _docsInserted++; + + if (NULL != numInserted) { + *numInserted += keys.size(); + } + + return Status::OK(); + } + + Status BtreeBasedBulkAccessMethod::commit(set<DiskLoc>* dupsToDrop, CurOp* op, bool mayInterrupt) { + DiskLoc oldHead = _real->_btreeState->head(); + // XXX: do we expect the tree to be empty but have a head set? Looks like so from old code. + invariant(!oldHead.isNull()); + _real->_btreeState->setHead(DiskLoc()); + _real->_btreeState->recordStore()->deleteRecord(oldHead); + + if (_isMultiKey) { + _real->_btreeState->setMultikey(); + } + + _sorter->sort(false); + + Timer timer; + IndexCatalogEntry* entry = _real->_btreeState; + + bool dupsAllowed = !entry->descriptor()->unique() + || ignoreUniqueIndex(entry->descriptor()); + + bool dropDups = entry->descriptor()->dropDups() || inDBRepair; + + scoped_ptr<BSONObjExternalSorter::Iterator> i(_sorter->iterator()); + + // verifies that pm and op refer to the same ProgressMeter + ProgressMeter& pm = op->setMessage("Index Bulk Build: (2/3) btree bottom up", + "Index: (2/3) BTree Bottom Up Progress", + _keysInserted, + 10); + + scoped_ptr<transition::BtreeBuilderInterface> builder; + builder.reset(_interface->getBulkBuilder(dupsAllowed)); + + while (i->more()) { + // Get the next datum and add it to the builder. + ExternalSortDatum d = i->next(); + Status status = builder->addKey(d.first, d.second); + + if (!status.isOK()) { + if (ErrorCodes::DuplicateKey != status.code()) { + return status; + } + + // If we're here it's a duplicate key. + if (dropDups) { + static const size_t kMaxDupsToStore = 1000000; + dupsToDrop->insert(d.second); + if (dupsToDrop->size() > kMaxDupsToStore) { + return Status(ErrorCodes::InternalError, + "Too many dups on index build with dropDups = true"); + } + } + else if (!dupsAllowed) { + return status; + } + } + + // If we're here either it's a dup and we're cool with it or the addKey went just + // fine. + pm.hit(); + } + + pm.finished(); + + op->setMessage("Index Bulk Build: (3/3) btree-middle", + "Index: (3/3) BTree Middle Progress"); + + LOG(timer.seconds() > 10 ? 0 : 1 ) << "\t done building bottom layer, going to commit"; + + unsigned long long keysCommit = builder->commit(mayInterrupt); + + if (!dropDups && (keysCommit != _keysInserted)) { + warning() << "not all entries were added to the index, probably some " + << "keys were too large" << endl; + } + return Status::OK(); + } + +} // namespace mongo diff --git a/src/mongo/db/index/btree_based_bulk_access_method.h b/src/mongo/db/index/btree_based_bulk_access_method.h new file mode 100644 index 00000000000..16e72cfc60f --- /dev/null +++ b/src/mongo/db/index/btree_based_bulk_access_method.h @@ -0,0 +1,140 @@ +/** +* Copyright (C) 2013 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/>. +* +* As a special exception, the copyright holders give permission to link the +* code of portions of this program with the OpenSSL library under certain +* conditions as described in each individual source file and distribute +* linked combinations including the program with the OpenSSL library. You +* must comply with the GNU Affero General Public License in all respects for +* all of the code used other than as permitted herein. If you modify file(s) +* with this exception, you may extend this exception to your version of the +* file(s), but you are not obligated to do so. If you do not wish to do so, +* delete this exception statement from your version. If you delete this +* exception statement from all source files in the program, then also delete +* it in the license file. +*/ + +#include <set> +#include <vector> + +#include "mongo/base/error_codes.h" +#include "mongo/base/status.h" +#include "mongo/db/curop.h" +#include "mongo/db/extsort.h" +#include "mongo/db/index/btree_based_access_method.h" +#include "mongo/db/index/index_access_method.h" +#include "mongo/db/index/index_descriptor.h" +#include "mongo/db/jsobj.h" +#include "mongo/db/structure/btree/btree_interface.h" + +namespace mongo { + + class BtreeBasedBulkAccessMethod : public IndexAccessMethod { + public: + BtreeBasedBulkAccessMethod(BtreeBasedAccessMethod* real, + transition::BtreeInterface* interface, + const IndexDescriptor* descriptor, + int numRecords); + + ~BtreeBasedBulkAccessMethod() {} + + virtual Status insert(const BSONObj& obj, + const DiskLoc& loc, + const InsertDeleteOptions& options, + int64_t* numInserted); + + Status commit(std::set<DiskLoc>* dupsToDrop, CurOp* op, bool mayInterrupt); + + // Exposed for testing. + static ExternalSortComparison* getComparison(int version, const BSONObj& keyPattern); + + // + // Stuff below here is a no-op of one form or another. + // + + virtual Status commitBulk(IndexAccessMethod* bulk, + bool mayInterrupt, + std::set<DiskLoc>* dups) { + verify(this == bulk); + return Status::OK(); + } + + virtual Status touch(const BSONObj& obj) { + return _notAllowed(); + } + + virtual Status validate(int64_t* numKeys) { + return _notAllowed(); + } + + virtual Status remove(const BSONObj& obj, + const DiskLoc& loc, + const InsertDeleteOptions& options, + int64_t* numDeleted) { + return _notAllowed(); + } + + virtual Status validateUpdate(const BSONObj& from, + const BSONObj& to, + const DiskLoc& loc, + const InsertDeleteOptions& options, + UpdateTicket* ticket) { + return _notAllowed(); + } + + virtual Status update(const UpdateTicket& ticket, int64_t* numUpdated) { + return _notAllowed(); + } + + virtual Status newCursor(IndexCursor **out) const { + return _notAllowed(); + } + + virtual Status initializeAsEmpty() { + return _notAllowed(); + } + + virtual IndexAccessMethod* initiateBulk() { + return NULL; + } + + private: + Status _notAllowed() const { + return Status(ErrorCodes::InternalError, "cannot use bulk for this yet"); + } + + // Not owned here. + BtreeBasedAccessMethod* _real; + + // Not owned here. + transition::BtreeInterface* _interface; + + // The external sorter. + boost::scoped_ptr<BSONObjExternalSorter> _sorter; + + // A comparison object required by the sorter. + boost::scoped_ptr<ExternalSortComparison> _sortCmp; + + // How many docs are we indexing? + unsigned long long _docsInserted; + + // And how many keys? + unsigned long long _keysInserted; + + // Does any document have >1 key? + bool _isMultiKey; + }; + +} // namespace mongo diff --git a/src/mongo/db/index/hash_access_method.cpp b/src/mongo/db/index/hash_access_method.cpp index 34729a1cf77..7457c68c085 100644 --- a/src/mongo/db/index/hash_access_method.cpp +++ b/src/mongo/db/index/hash_access_method.cpp @@ -26,7 +26,6 @@ * it in the license file. */ -#include "mongo/db/structure/btree/btree.h" #include "mongo/db/hasher.h" #include "mongo/db/index/expression_keys_private.h" #include "mongo/db/index/expression_params.h" diff --git a/src/mongo/db/pdfile.cpp b/src/mongo/db/pdfile.cpp index 4cc0552ebc0..e02008ae18c 100644 --- a/src/mongo/db/pdfile.cpp +++ b/src/mongo/db/pdfile.cpp @@ -69,7 +69,6 @@ _ disallow system* manipulations from the database. #include "mongo/db/ops/delete.h" #include "mongo/db/repair_database.h" #include "mongo/db/repl/is_master.h" -#include "mongo/db/sort_phase_one.h" #include "mongo/db/repl/oplog.h" #include "mongo/db/storage_options.h" #include "mongo/db/catalog/collection.h" diff --git a/src/mongo/db/query/idhack_runner.cpp b/src/mongo/db/query/idhack_runner.cpp index e4cc486d35d..c57aee98ec2 100644 --- a/src/mongo/db/query/idhack_runner.cpp +++ b/src/mongo/db/query/idhack_runner.cpp @@ -29,7 +29,7 @@ #include "mongo/db/query/idhack_runner.h" #include "mongo/client/dbclientinterface.h" -#include "mongo/db/structure/btree/btree.h" +#include "mongo/db/catalog/collection.h" #include "mongo/db/catalog/index_catalog.h" #include "mongo/db/diskloc.h" #include "mongo/db/index/btree_access_method.h" @@ -39,7 +39,7 @@ #include "mongo/db/query/canonical_query.h" #include "mongo/db/query/type_explain.h" #include "mongo/db/query/plan_executor.h" -#include "mongo/db/catalog/collection.h" +#include "mongo/db/storage/record.h" #include "mongo/s/d_logic.h" namespace { diff --git a/src/mongo/db/sort_phase_one.h b/src/mongo/db/sort_phase_one.h deleted file mode 100644 index a0aade9a731..00000000000 --- a/src/mongo/db/sort_phase_one.h +++ /dev/null @@ -1,59 +0,0 @@ -/** -* Copyright (C) 2008 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/>. -* -* As a special exception, the copyright holders give permission to link the -* code of portions of this program with the OpenSSL library under certain -* conditions as described in each individual source file and distribute -* linked combinations including the program with the OpenSSL library. You -* must comply with the GNU Affero General Public License in all respects for -* all of the code used other than as permitted herein. If you modify file(s) -* with this exception, you may extend this exception to your version of the -* file(s), but you are not obligated to do so. If you do not wish to do so, -* delete this exception statement from your version. If you delete this -* exception statement from all source files in the program, then also delete -* it in the license file. -*/ - -#pragma once - -#include "mongo/db/extsort.h" - -namespace mongo { - - /** for bottom up fastbuildindex (where we presort keys) */ - struct SortPhaseOne { - SortPhaseOne() { - n = 0; - nkeys = 0; - multi = false; - } - shared_ptr<BSONObjExternalSorter> sorter; - shared_ptr<ExternalSortComparison> sortCmp; - - unsigned long long n; // # of records - unsigned long long nkeys; - bool multi; // multikey index - - void addKeys(const BSONObjSet& keys, const DiskLoc& loc, bool mayInterrupt) { - multi = multi || (keys.size() > 1); - for (BSONObjSet::iterator it = keys.begin(); it != keys.end(); ++it) { - sorter->add(*it, loc, mayInterrupt); - ++nkeys; - } - ++n; - } - }; - -} // namespace mongo diff --git a/src/mongo/db/structure/btree/btree.cpp b/src/mongo/db/structure/btree/btree.cpp index 0f7f8089155..4537f73d8d9 100644 --- a/src/mongo/db/structure/btree/btree.cpp +++ b/src/mongo/db/structure/btree/btree.cpp @@ -33,7 +33,6 @@ #include "mongo/db/structure/btree/btree.h" #include "mongo/db/structure/btree/btree_stats.h" -#include "mongo/db/structure/btree/btreebuilder.h" #include "mongo/db/client.h" #include "mongo/db/clientcursor.h" #include "mongo/db/curop-inl.h" diff --git a/src/mongo/db/structure/btree/btree_interface.cpp b/src/mongo/db/structure/btree/btree_interface.cpp index a7fc44f6e77..397ef12c453 100644 --- a/src/mongo/db/structure/btree/btree_interface.cpp +++ b/src/mongo/db/structure/btree/btree_interface.cpp @@ -34,6 +34,26 @@ namespace mongo { namespace transition { template <class OnDiskFormat> + class BtreeBuilderInterfaceImpl : public BtreeBuilderInterface { + public: + BtreeBuilderInterfaceImpl(typename BtreeLogic<OnDiskFormat>::Builder* builder) + : _builder(builder) { } + + virtual ~BtreeBuilderInterfaceImpl() { } + + Status addKey(const BSONObj& key, const DiskLoc& loc) { + return _builder->addKey(key, loc); + } + + unsigned long long commit(bool mayInterrupt) { + return _builder->commit(mayInterrupt); + } + + private: + typename BtreeLogic<OnDiskFormat>::Builder* _builder; + }; + + template <class OnDiskFormat> class BtreeInterfaceImpl : public BtreeInterface { public: BtreeInterfaceImpl(HeadManager* headManager, @@ -45,6 +65,10 @@ namespace transition { virtual ~BtreeInterfaceImpl() { } + virtual BtreeBuilderInterface* getBulkBuilder(bool dupsAllowed) { + return new BtreeBuilderInterfaceImpl<OnDiskFormat>(_btree->newBuilder(dupsAllowed)); + } + virtual Status insert(const BSONObj& key, const DiskLoc& loc, bool dupsAllowed) { return _btree->insert(key, loc, dupsAllowed); } @@ -140,6 +164,10 @@ namespace transition { _btree->restorePosition(saved.key, saved.loc, direction, bucketInOut, keyOffsetInOut); } + virtual Status initAsEmpty() { + return _btree->initAsEmpty(); + } + private: scoped_ptr<BtreeLogic<OnDiskFormat> > _btree; }; diff --git a/src/mongo/db/structure/btree/btree_interface.h b/src/mongo/db/structure/btree/btree_interface.h index 9b5d32fcca2..3073867b494 100644 --- a/src/mongo/db/structure/btree/btree_interface.h +++ b/src/mongo/db/structure/btree/btree_interface.h @@ -38,6 +38,30 @@ namespace mongo { namespace transition { /** + * A version-hiding wrapper around the bulk builder for the Btree. + */ + class BtreeBuilderInterface { + public: + virtual ~BtreeBuilderInterface() { } + + /** + * Adds 'key' to intermediate storage. + * + * 'key' must be > or >= the last key passed to this function (depends on _dupsAllowed). If + * this is violated an error Status (ErrorCodes::InternalError) will be returned. + */ + virtual Status addKey(const BSONObj& key, const DiskLoc& loc) = 0; + + /** + * commit work. if not called, destructor will clean up partially completed work + * (in case exception has happened). + * + * Returns number of keys added. + */ + virtual unsigned long long commit(bool mayInterrupt) = 0; + }; + + /** * This is the interface for interacting with the Btree. The index access and catalog layers * should use this. * @@ -68,6 +92,12 @@ namespace transition { // Data changes // + /** + * Caller owns returned pointer. + * 'this' must outlive the returned pointer. + */ + virtual BtreeBuilderInterface* getBulkBuilder(bool dupsAllowed) = 0; + virtual Status insert(const BSONObj& key, const DiskLoc& loc, bool dupsAllowed) = 0; virtual bool unindex(const BSONObj& key, const DiskLoc& loc) = 0; @@ -136,6 +166,12 @@ namespace transition { int direction, DiskLoc* bucketOut, int* keyOffsetOut) = 0; + + // + // Index creation + // + + virtual Status initAsEmpty() = 0; }; } // namespace transition diff --git a/src/mongo/db/structure/btree/btree_logic.cpp b/src/mongo/db/structure/btree/btree_logic.cpp index bbc437cd85d..b9fd42319d0 100644 --- a/src/mongo/db/structure/btree/btree_logic.cpp +++ b/src/mongo/db/structure/btree/btree_logic.cpp @@ -28,18 +28,180 @@ #include "mongo/db/diskloc.h" -#include "mongo/db/storage/mmap_v1/dur.h" -#include "mongo/db/storage/mmap_v1/dur_commitjob.h" #include "mongo/db/index/btree_index_cursor.h" // for aboutToDeleteBucket #include "mongo/db/jsobj.h" +#include "mongo/db/kill_current_op.h" +#include "mongo/db/storage/mmap_v1/dur.h" +#include "mongo/db/storage/mmap_v1/dur_commitjob.h" #include "mongo/db/storage/record.h" -#include "mongo/db/structure/record_store.h" #include "mongo/db/structure/btree/btree_logic.h" #include "mongo/db/structure/btree/key.h" +#include "mongo/db/structure/record_store.h" namespace mongo { namespace transition { + // + // Public Builder logic + // + + template <class BtreeLayout> + typename BtreeLogic<BtreeLayout>::Builder* + BtreeLogic<BtreeLayout>::newBuilder(bool dupsAllowed) { + return new Builder(this, dupsAllowed); + } + + template <class BtreeLayout> + BtreeLogic<BtreeLayout>::Builder::Builder(BtreeLogic* logic, bool dupsAllowed) + : _logic(logic), + _dupsAllowed(dupsAllowed), + _numAdded(0) { + + _first = _cur = _logic->addBucket(); + _b = _getModifiableBucket(_cur); + _committed = false; + } + + template <class BtreeLayout> + Status BtreeLogic<BtreeLayout>::Builder::addKey(const BSONObj& keyObj, const DiskLoc& loc) { + auto_ptr<KeyDataOwnedType> key(new KeyDataOwnedType(keyObj)); + + if (key->dataSize() > BtreeLayout::KeyMax) { + string msg = str::stream() << "Btree::insert: key too large to index, failing " + << _logic->_recordStore->name() + << ' ' << key->dataSize() << ' ' << key->toString(); + problem() << msg << endl; + return Status(ErrorCodes::KeyTooLong, msg); + } + + // If we have a previous key to compare to... + if (_numAdded > 0) { + int cmp = _keyLast->woCompare(*key, _logic->_ordering); + + // This shouldn't happen ever. We expect keys in sorted order. + if (cmp > 0) { + return Status(ErrorCodes::InternalError, "Bad key order in btree builder"); + } + + // This could easily happen.. + if (!_dupsAllowed && (cmp == 0)) { + return Status(ErrorCodes::DuplicateKey, _logic->dupKeyError(*_keyLast)); + } + } + + if (!_logic->_pushBack(_b, loc, *key, DiskLoc())) { + // bucket was full + newBucket(); + _logic->pushBack(_b, loc, *key, DiskLoc()); + } + + _keyLast = key; + _numAdded++; + mayCommitProgressDurably(); + return Status::OK(); + } + + template <class BtreeLayout> + unsigned long long BtreeLogic<BtreeLayout>::Builder::commit(bool mayInterrupt) { + buildNextLevel(_first, mayInterrupt); + _committed = true; + return _numAdded; + } + + // + // Private Builder logic + // + + template <class BtreeLayout> + void BtreeLogic<BtreeLayout>::Builder::newBucket() { + DiskLoc newBucketLoc = _logic->addBucket(); + _b->parent = newBucketLoc; + _cur = newBucketLoc; + _b = _getModifiableBucket(_cur); + } + + template <class BtreeLayout> + void BtreeLogic<BtreeLayout>::Builder::buildNextLevel(DiskLoc loc, bool mayInterrupt) { + for (;;) { + if (_getBucket(loc)->parent.isNull()) { + // only 1 bucket at this level. we are done. + _logic->_headManager->setHead(loc); + break; + } + + DiskLoc upLoc = _logic->addBucket(); + DiskLoc upStart = upLoc; + BucketType* up = _getModifiableBucket(upLoc); + + DiskLoc xloc = loc; + while (!xloc.isNull()) { + if (getDur().commitIfNeeded()) { + _b = _getModifiableBucket(_cur); + up = _getModifiableBucket(upLoc); + } + + if (mayInterrupt) { + killCurrentOp.checkForInterrupt(); + } + + BucketType* x = _getModifiableBucket(xloc); + KeyDataType k; + DiskLoc r; + _logic->popBack(x, &r, &k); + bool keepX = (x->n != 0); + DiskLoc keepLoc = keepX ? xloc : x->nextChild; + + if (!_logic->_pushBack(up, r, k, keepLoc)) { + // current bucket full + DiskLoc n = _logic->addBucket(); + up->parent = n; + upLoc = n; + up = _getModifiableBucket(upLoc); + _logic->pushBack(up, r, k, keepLoc); + } + + DiskLoc nextLoc = x->parent; + if (keepX) { + x->parent = upLoc; + } + else { + if (!x->nextChild.isNull()) { + DiskLoc ll = x->nextChild; + _getModifiableBucket(ll)->parent = upLoc; + } + _logic->deallocBucket(x, xloc); + } + xloc = nextLoc; + } + + loc = upStart; + mayCommitProgressDurably(); + } + } + + template <class BtreeLayout> + void BtreeLogic<BtreeLayout>::Builder::mayCommitProgressDurably() { + if (getDur().commitIfNeeded()) { + _b = _getModifiableBucket(_cur); + } + } + + template <class BtreeLayout> + typename BtreeLogic<BtreeLayout>::BucketType* + BtreeLogic<BtreeLayout>::Builder::_getModifiableBucket(DiskLoc loc) { + return _logic->btreemod(_logic->getBucket(loc)); + } + + template <class BtreeLayout> + typename BtreeLogic<BtreeLayout>::BucketType* + BtreeLogic<BtreeLayout>::Builder::_getBucket(DiskLoc loc) { + return _logic->getBucket(loc); + } + + // + // BtreeLogic logic + // + // static template <class BtreeLayout> typename BtreeLogic<BtreeLayout>::FullKey @@ -175,8 +337,8 @@ namespace transition { template <class BtreeLayout> void BtreeLogic<BtreeLayout>::popBack(BucketType* bucket, - DiskLoc* recordLocOut, - KeyDataType *keyDataOut) { + DiskLoc* recordLocOut, + KeyDataType *keyDataOut) { massert(17435, "n==0 in btree popBack()", bucket->n > 0 ); @@ -1632,6 +1794,16 @@ namespace transition { }; template <class BtreeLayout> + Status BtreeLogic<BtreeLayout>::initAsEmpty() { + if (!_headManager->getHead().isNull()) { + return Status(ErrorCodes::InternalError, "index already initialized"); + } + + _headManager->setHead(addBucket()); + return Status::OK(); + } + + template <class BtreeLayout> DiskLoc BtreeLogic<BtreeLayout>::addBucket() { DummyDocWriter docWriter(BtreeLayout::BucketSize); StatusWith<DiskLoc> loc = _recordStore->insertRecord(&docWriter, 0); diff --git a/src/mongo/db/structure/btree/btree_logic.h b/src/mongo/db/structure/btree/btree_logic.h index 4238d07d443..c5808b17ce3 100644 --- a/src/mongo/db/structure/btree/btree_logic.h +++ b/src/mongo/db/structure/btree/btree_logic.h @@ -71,6 +71,48 @@ namespace transition { // Public-facing // + class Builder { + public: + typedef typename BtreeLayout::KeyOwnedType KeyDataOwnedType; + typedef typename BtreeLayout::KeyType KeyDataType; + + Status addKey(const BSONObj& key, const DiskLoc& loc); + + // XXX: status, outparam for # keys? + unsigned long long commit(bool mayInterrupt); + + private: + friend class BtreeLogic; + + Builder(BtreeLogic* logic, bool dupsAllowed); + + // Direct ports of functionality + void newBucket(); + void buildNextLevel(DiskLoc loc, bool mayInterrupt); + void mayCommitProgressDurably(); + BucketType* _getModifiableBucket(DiskLoc loc); + BucketType* _getBucket(DiskLoc loc); + // Direct ports of functionality + + // Not owned. + BtreeLogic* _logic; + + // Direct port of names. + DiskLoc _cur; + DiskLoc _first; + BucketType* _b; + bool _committed; + bool _dupsAllowed; + long long _numAdded; + auto_ptr<KeyDataOwnedType> _keyLast; + }; + + /** + * Caller owns the returned pointer. + * 'this' must outlive the returned pointer. + */ + Builder* newBuilder(bool dupsAllowed); + Status dupKeyCheck(const BSONObj& key, const DiskLoc& loc) const; Status insert(const BSONObj& rawKey, const DiskLoc& value, bool dupsAllowed); @@ -137,9 +179,19 @@ namespace transition { const DiskLoc& savedLoc, BucketType* bucket, int keyPos) const; - + + // + // Creation and deletion + // + + /** + * Returns OK if the index was uninitialized before, error status otherwise. + */ + Status initAsEmpty(); private: + friend class BtreeLogic::Builder; + /** * This is an in memory wrapper for the variable length data associated with a * KeyHeaderType. It points to on-disk data but is not itself on-disk data. diff --git a/src/mongo/db/structure/btree/btreebuilder.cpp b/src/mongo/db/structure/btree/btreebuilder.cpp deleted file mode 100644 index fe750ecb234..00000000000 --- a/src/mongo/db/structure/btree/btreebuilder.cpp +++ /dev/null @@ -1,197 +0,0 @@ -// btreebuilder.cpp - -/** -* Copyright (C) 2008 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/>. -* -* As a special exception, the copyright holders give permission to link the -* code of portions of this program with the OpenSSL library under certain -* conditions as described in each individual source file and distribute -* linked combinations including the program with the OpenSSL library. You -* must comply with the GNU Affero General Public License in all respects for -* all of the code used other than as permitted herein. If you modify file(s) -* with this exception, you may extend this exception to your version of the -* file(s), but you are not obligated to do so. If you do not wish to do so, -* delete this exception statement from your version. If you delete this -* exception statement from all source files in the program, then also delete -* it in the license file. -*/ - -#include "mongo/pch.h" - -#include "mongo/db/structure/btree/btreebuilder.h" - -#include "mongo/db/client.h" -#include "mongo/db/clientcursor.h" -#include "mongo/db/curop-inl.h" -#include "mongo/db/db.h" -#include "mongo/db/dbhelpers.h" -#include "mongo/db/storage/mmap_v1/dur_commitjob.h" -#include "mongo/db/json.h" -#include "mongo/db/kill_current_op.h" -#include "mongo/db/pdfile.h" -#include "mongo/db/repl/is_master.h" -#include "mongo/db/stats/counters.h" -#include "mongo/db/structure/btree/btree.h" - -namespace mongo { - - void keyTooLongAssert( int code, const string& msg ); - - /* --- BtreeBuilder --- */ - - template<class V> - BtreeBuilder<V>::BtreeBuilder(bool dupsAllowed, IndexCatalogEntry* btreeState ): - _dupsAllowed(dupsAllowed), - _btreeState(btreeState), - _numAdded(0) { - first = cur = BtreeBucket<V>::addBucket(btreeState); - b = _getModifiableBucket( cur ); - committed = false; - } - - template<class V> - BtreeBucket<V>* BtreeBuilder<V>::_getModifiableBucket( DiskLoc loc ) { - return BtreeBucket<V>::asVersionMod( _btreeState->recordStore()->recordFor( loc ) ); - } - - template<class V> - const BtreeBucket<V>* BtreeBuilder<V>::_getBucket( DiskLoc loc ) { - return BtreeBucket<V>::asVersion( _btreeState->recordStore()->recordFor( loc ) ); - } - - template<class V> - void BtreeBuilder<V>::newBucket() { - DiskLoc L = BtreeBucket<V>::addBucket(_btreeState); - b->setTempNext(L); - cur = L; - b = _getModifiableBucket( cur ); - } - - template<class V> - void BtreeBuilder<V>::mayCommitProgressDurably() { - if ( getDur().commitIfNeeded() ) { - b = _getModifiableBucket( cur ); - } - } - - template<class V> - void BtreeBuilder<V>::addKey(BSONObj& _key, DiskLoc loc) { - auto_ptr< KeyOwned > key( new KeyOwned(_key) ); - if ( key->dataSize() > BtreeBucket<V>::KeyMax ) { - string msg = str::stream() << "Btree::insert: key too large to index, failing " - << _btreeState->descriptor()->indexNamespace() - << ' ' << key->dataSize() << ' ' << key->toString(); - problem() << msg << endl; - keyTooLongAssert( 17282, msg ); - return; - } - - if( !_dupsAllowed ) { - if( _numAdded > 0 ) { - int cmp = keyLast->woCompare(*key, _btreeState->ordering()); - massert( 10288 , "bad key order in BtreeBuilder - server internal error", cmp <= 0 ); - if( cmp == 0 ) { - //if( !dupsAllowed ) - uasserted( ASSERT_ID_DUPKEY, BtreeBucket<V>::dupKeyError( _btreeState->descriptor(), - *keyLast ) ); - } - } - } - - if ( ! b->_pushBack(loc, *key, _btreeState->ordering(), DiskLoc()) ) { - // bucket was full - newBucket(); - b->pushBack(loc, *key, _btreeState->ordering(), DiskLoc()); - } - keyLast = key; - _numAdded++; - mayCommitProgressDurably(); - } - - template<class V> - void BtreeBuilder<V>::buildNextLevel(DiskLoc loc, bool mayInterrupt) { - int levels = 1; - while( 1 ) { - if( _getBucket(loc)->tempNext().isNull() ) { - // only 1 bucket at this level. we are done. - _btreeState->setHead( loc ); - break; - } - levels++; - - DiskLoc upLoc = BtreeBucket<V>::addBucket(_btreeState); - DiskLoc upStart = upLoc; - BtreeBucket<V> *up = _getModifiableBucket( upLoc ); - - DiskLoc xloc = loc; - while( !xloc.isNull() ) { - - if ( getDur().commitIfNeeded() ) { - b = _getModifiableBucket( cur ); - up = _getModifiableBucket( upLoc ); - } - RARELY if ( mayInterrupt ) killCurrentOp.checkForInterrupt(); - - BtreeBucket<V> *x = _getModifiableBucket( xloc ); - Key k; - DiskLoc r; - x->popBack(r,k); - bool keepX = ( x->n != 0 ); - DiskLoc keepLoc = keepX ? xloc : x->nextChild; - - if ( ! up->_pushBack(r, k, _btreeState->ordering(), keepLoc) ) { - // current bucket full - DiskLoc n = BtreeBucket<V>::addBucket(_btreeState); - up->setTempNext(n); - upLoc = n; - up = _getModifiableBucket( upLoc ); - up->pushBack(r, k, _btreeState->ordering(), keepLoc); - } - - DiskLoc nextLoc = x->tempNext(); // get next in chain at current level - if ( keepX ) { - x->parent = upLoc; - } - else { - if ( !x->nextChild.isNull() ) { - DiskLoc ll = x->nextChild; - _getModifiableBucket(ll)->parent = upLoc; - //(x->nextChild.btreemod<V>())->parent = upLoc; - } - x->deallocBucket( _btreeState, xloc ); - } - xloc = nextLoc; - } - - loc = upStart; - mayCommitProgressDurably(); - } - - if( levels > 1 ) { - LOG(2) << "btree levels: " << levels << endl; - } - } - - /** when all addKeys are done, we then build the higher levels of the tree */ - template<class V> - void BtreeBuilder<V>::commit(bool mayInterrupt) { - buildNextLevel(first, mayInterrupt); - committed = true; - } - - template class BtreeBuilder<V0>; - template class BtreeBuilder<V1>; - -} diff --git a/src/mongo/db/structure/btree/btreebuilder.h b/src/mongo/db/structure/btree/btreebuilder.h deleted file mode 100644 index 833fbaabaff..00000000000 --- a/src/mongo/db/structure/btree/btreebuilder.h +++ /dev/null @@ -1,85 +0,0 @@ -/** -* 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/>. -* -* As a special exception, the copyright holders give permission to link the -* code of portions of this program with the OpenSSL library under certain -* conditions as described in each individual source file and distribute -* linked combinations including the program with the OpenSSL library. You -* must comply with the GNU Affero General Public License in all respects for -* all of the code used other than as permitted herein. If you modify file(s) -* with this exception, you may extend this exception to your version of the -* file(s), but you are not obligated to do so. If you do not wish to do so, -* delete this exception statement from your version. If you delete this -* exception statement from all source files in the program, then also delete -* it in the license file. -*/ - -#pragma once - -#include "mongo/db/structure/btree/btree.h" - -namespace mongo { - - class IndexCatalogEntry; - - /** - * build btree from the bottom up - */ - template< class V > - class BtreeBuilder { - typedef typename V::KeyOwned KeyOwned; - typedef typename V::Key Key; - - bool _dupsAllowed; - IndexCatalogEntry* _btreeState; - /** Number of keys added to btree. */ - unsigned long long _numAdded; - - /** Last key passed to addKey(). */ - auto_ptr< typename V::KeyOwned > keyLast; - - /** true iff commit() completed successfully. */ - bool committed; - - DiskLoc cur, first; - BtreeBucket<V> *b; - - void newBucket(); - void buildNextLevel(DiskLoc loc, bool mayInterrupt); - void mayCommitProgressDurably(); - - BtreeBucket<V>* _getModifiableBucket( DiskLoc loc ); - const BtreeBucket<V>* _getBucket( DiskLoc loc ); - - - public: - BtreeBuilder(bool dupsAllowed, IndexCatalogEntry* idx); - - /** - * Preconditions: 'key' is > or >= last key passed to this function (depends on _dupsAllowed) - * Postconditions: 'key' is added to intermediate storage. - */ - void addKey(BSONObj& key, DiskLoc loc); - - /** - * commit work. if not called, destructor will clean up partially completed work - * (in case exception has happened). - */ - void commit(bool mayInterrupt); - - unsigned long long getn() { return _numAdded; } - }; - -} diff --git a/src/mongo/dbtests/btreebuildertests.cpp b/src/mongo/dbtests/btreebuildertests.cpp index fd7f49900ee..9ff1378ce4e 100644 --- a/src/mongo/dbtests/btreebuildertests.cpp +++ b/src/mongo/dbtests/btreebuildertests.cpp @@ -28,7 +28,7 @@ * then also delete it in the license file. */ -#include "mongo/db/structure/btree/btreebuilder.h" +// #include "mongo/db/structure/btree/btreebuilder.h" #include "mongo/db/catalog/index_catalog.h" #include "mongo/db/pdfile.h" diff --git a/src/mongo/dbtests/extsorttests.cpp b/src/mongo/dbtests/extsorttests.cpp index dc807bdd28b..aec478aadc4 100644 --- a/src/mongo/dbtests/extsorttests.cpp +++ b/src/mongo/dbtests/extsorttests.cpp @@ -32,7 +32,7 @@ #include "mongo/db/catalog/database.h" #include "mongo/db/extsort.h" -#include "mongo/db/index/btree_based_access_method.h" +#include "mongo/db/index/btree_based_bulk_access_method.h" #include "mongo/db/catalog/collection.h" #include "mongo/dbtests/dbtests.h" #include "mongo/platform/cstdint.h" @@ -52,8 +52,8 @@ namespace ExtSortTests { static const char* const _ns = "unittests.extsort"; DBDirectClient _client; - ExternalSortComparison* _arbitrarySort = BtreeBasedAccessMethod::getComparison(time(0)%2, BSONObj()); - ExternalSortComparison* _aFirstSort = BtreeBasedAccessMethod::getComparison(0, BSON("a" << 1)); + ExternalSortComparison* _arbitrarySort = BtreeBasedBulkAccessMethod::getComparison(time(0)%2, BSONObj()); + ExternalSortComparison* _aFirstSort = BtreeBasedBulkAccessMethod::getComparison(0, BSON("a" << 1)); /** Sort four values. */ class SortFour { @@ -320,7 +320,7 @@ namespace ExtSortTests { coll->insertDocument( b.obj(), true ); // Create a sorter with a max file size of only 10k, to trigger a file flush after a // relatively small number of inserts. - auto_ptr<ExternalSortComparison> cmp(BtreeBasedAccessMethod::getComparison(0, + auto_ptr<ExternalSortComparison> cmp(BtreeBasedBulkAccessMethod::getComparison(0, BSON("a" << 1))); BSONObjExternalSorter sorter(cmp.get(), 10 * 1024 ); // Register a request to kill the current operation. diff --git a/src/mongo/dbtests/indexupdatetests.cpp b/src/mongo/dbtests/indexupdatetests.cpp index a1d594fb201..d28edbf2ab4 100644 --- a/src/mongo/dbtests/indexupdatetests.cpp +++ b/src/mongo/dbtests/indexupdatetests.cpp @@ -31,10 +31,9 @@ #include "mongo/db/structure/btree/btree.h" #include "mongo/db/catalog/index_catalog.h" #include "mongo/db/dbhelpers.h" -#include "mongo/db/index/btree_based_access_method.h" +#include "mongo/db/index/btree_based_bulk_access_method.h" #include "mongo/db/index/index_descriptor.h" #include "mongo/db/kill_current_op.h" -#include "mongo/db/sort_phase_one.h" #include "mongo/db/catalog/collection.h" #include "mongo/platform/cstdint.h" @@ -44,7 +43,7 @@ namespace IndexUpdateTests { static const char* const _ns = "unittests.indexupdate"; DBDirectClient _client; - ExternalSortComparison* _aFirstSort = BtreeBasedAccessMethod::getComparison(0, BSON("a" << 1)); + ExternalSortComparison* _aFirstSort = BtreeBasedBulkAccessMethod::getComparison(0, BSON("a" << 1)); /** * Test fixture for a write locked test using collection _ns. Includes functionality to |