SERVER-12213: use new index creation method, including bulk operation support on IndexAccessMethod

7 files changed, 299 insertions, 388 deletions

diff --git a/src/mongo/db/index/btree_based_access_method.cpp b/src/mongo/db/index/btree_based_access_method.cpp
index a15729a1339..134084229f7 100644
--- a/src/mongo/db/index/btree_based_access_method.cpp
+++ b/src/mongo/db/index/btree_based_access_method.cpp
@@ -31,12 +31,17 @@
 #include <vector>
 
 #include "mongo/base/status.h"
+#include "mongo/db/extsort.h"
 #include "mongo/db/index/btree_index_cursor.h"
 #include "mongo/db/index/btree_interface.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/keypattern.h"
+#include "mongo/db/kill_current_op.h"
 #include "mongo/db/pdfile.h"
 #include "mongo/db/pdfile_private.h"
+#include "mongo/db/repl/rs.h"
+#include "mongo/db/sort_phase_one.h"
+#include "mongo/db/structure/btree/btreebuilder.h"
 
 namespace mongo {
 
@@ -178,7 +183,6 @@ namespace mongo {
         return Status::OK();
     }
 
-
     Status BtreeBasedAccessMethod::touch(const BSONObj& obj) {
         BSONObjSet keys;
         getKeys(obj, &keys);
@@ -295,4 +299,255 @@ 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 this;
+        }
+
+        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 killCurrentOp.checkForInterrupt( !mayInterrupt );
+                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( e.interrupted() ) {
+                        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 ( _interface->nKeys( _btreeState,
+                                _btreeState->head() ) > 0 )
+            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();
+    }
+
+    Status BtreeBasedAccessMethod::commitBulk( IndexAccessMethod* bulkRaw,
+                                               bool mayInterrupt,
+                                               set<DiskLoc>* dupsToDrop ) {
+
+        if ( _interface->nKeys( _btreeState,
+                                _btreeState->head() ) > 0 ) {
+            return Status( ErrorCodes::InternalError, "trying to commit, but has data already" );
+        }
+
+        {
+            DiskLoc oldHead = _btreeState->head();
+            _btreeState->setHead( DiskLoc() );
+            _btreeState->recordStore()->deleteRecord( oldHead );
+        }
+
+        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();
+    }
+
+
 }  // 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 f541d302f60..cf3b82c2828 100644
--- a/src/mongo/db/index/btree_based_access_method.h
+++ b/src/mongo/db/index/btree_based_access_method.h
@@ -40,6 +40,9 @@
 
 namespace mongo {
 
+    class BtreeBulk;
+    class ExternalSortComparison;
+
     /**
      * Any access method that is Btree based subclasses from this.
      *
@@ -77,6 +80,12 @@ namespace mongo {
 
         virtual Status initializeAsEmpty();
 
+        virtual IndexAccessMethod* initiateBulk() ;
+
+        virtual Status commitBulk( IndexAccessMethod* bulk,
+                                   bool mayInterrupt,
+                                   std::set<DiskLoc>* dups );
+
         virtual Status touch(const BSONObj& obj);
 
         virtual Status validate(int64_t* numKeys);
@@ -84,9 +93,13 @@ namespace mongo {
         // XXX: consider migrating callers to use IndexCursor instead
         virtual DiskLoc findSingle( const BSONObj& key );
 
+        // exposed for testing, used for bulk commit
+        static ExternalSortComparison* getComparison(int version,
+                                                     const BSONObj& keyPattern);
+
     protected:
         // Friends who need getKeys.
-        friend class BtreeBasedBuilder;
+        friend class BtreeBulk;
 
         // See below for body.
         class BtreeBasedPrivateUpdateData;
diff --git a/src/mongo/db/index/btree_based_builder.cpp b/src/mongo/db/index/btree_based_builder.cpp
deleted file mode 100644
index c2e452fcc7d..00000000000
--- a/src/mongo/db/index/btree_based_builder.cpp
+++ /dev/null
@@ -1,283 +0,0 @@
-/**
-*    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_builder.h"
-
-#include "mongo/db/structure/btree/btreebuilder.h"
-#include "mongo/db/index/btree_access_method.h"
-#include "mongo/db/index/index_descriptor.h"
-#include "mongo/db/index/index_access_method.h"
-#include "mongo/db/kill_current_op.h"
-#include "mongo/db/pdfile_private.h"
-#include "mongo/db/query/internal_plans.h"
-#include "mongo/db/repl/is_master.h"
-#include "mongo/db/repl/oplog.h"
-#include "mongo/db/repl/rs.h"
-#include "mongo/db/sort_phase_one.h"
-#include "mongo/util/processinfo.h"
-
-namespace mongo {
-
-    int oldCompare(const BSONObj& l,const BSONObj& r, const Ordering &o); // key.cpp
-
-    class ExternalSortComparisonV0 : public ExternalSortComparison {
-    public:
-        ExternalSortComparisonV0(const BSONObj& ordering) : _ordering(Ordering::make(ordering)) { }
-        virtual ~ExternalSortComparisonV0() { }
-
-        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 ExternalSortComparisonV1 : public ExternalSortComparison {
-    public:
-        ExternalSortComparisonV1(const BSONObj& ordering) : _ordering(Ordering::make(ordering)) { }
-        virtual ~ExternalSortComparisonV1() { }
-
-        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;
-    };
-
-    template< class V >
-    void buildBottomUpPhases2And3( bool dupsAllowed,
-                                   IndexCatalogEntry* btreeState,
-                                   BSONObjExternalSorter& sorter,
-                                   bool dropDups,
-                                   set<DiskLoc>& dupsToDrop,
-                                   CurOp* op,
-                                   SortPhaseOne* phase1,
-                                   ProgressMeterHolder& pm,
-                                   Timer& t,
-                                   bool mayInterrupt ) {
-        BtreeBuilder<V> btBuilder(dupsAllowed, btreeState);
-        BSONObj keyLast;
-        auto_ptr<BSONObjExternalSorter::Iterator> i = sorter.iterator();
-        // verifies that pm and op refer to the same ProgressMeter
-        verify(pm == op->setMessage("index: (2/3) btree bottom up",
-                                    "Index: (2/3) BTree Bottom Up Progress",
-                                    phase1->nkeys,
-                                    10));
-        while( i->more() ) {
-            RARELY killCurrentOp.checkForInterrupt( !mayInterrupt );
-            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( e.interrupted() ) {
-                    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.
-                */
-                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: (3/3) btree-middle", "Index: (3/3) BTree Middle Progress");
-        LOG(t.seconds() > 10 ? 0 : 1 ) << "\t done building bottom layer, going to commit" << endl;
-        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;
-        }
-    }
-
-    ExternalSortComparison* BtreeBasedBuilder::getComparison(int version,
-                                                             const BSONObj& keyPattern) {
-        if (0 == version) {
-            return new ExternalSortComparisonV0(keyPattern);
-        } else {
-            verify(1 == version);
-            return new ExternalSortComparisonV1(keyPattern);
-        }
-    }
-
-    void BtreeBasedBuilder::addKeysToPhaseOne(Collection* collection,
-                                              const IndexDescriptor* idx,
-                                              const BSONObj& order,
-                                              SortPhaseOne* phaseOne,
-                                              ProgressMeter* progressMeter,
-                                              bool mayInterrupt ) {
-
-
-        phaseOne->sortCmp.reset(getComparison(idx->version(), idx->keyPattern()));
-        phaseOne->sorter.reset(new BSONObjExternalSorter(phaseOne->sortCmp.get()));
-        phaseOne->sorter->hintNumObjects( collection->numRecords() );
-
-        BtreeBasedAccessMethod* iam =collection->getIndexCatalog()->getBtreeBasedIndex( idx );
-
-        auto_ptr<Runner> runner(InternalPlanner::collectionScan(collection->ns().ns()));
-        BSONObj o;
-        DiskLoc loc;
-        Runner::RunnerState state;
-        while (Runner::RUNNER_ADVANCED == (state = runner->getNext(&o, &loc))) {
-            RARELY killCurrentOp.checkForInterrupt( !mayInterrupt );
-            BSONObjSet keys;
-            iam->getKeys(o, &keys);
-            phaseOne->addKeys(keys, loc, mayInterrupt);
-            progressMeter->hit();
-            if (logger::globalLogDomain()->shouldLog(logger::LogSeverity::Debug(2))
-                && phaseOne->n % 10000 == 0 ) {
-                printMemInfo( "\t iterating objects" );
-            }
-        }
-
-        uassert(17050, "Internal error reading docs from collection", Runner::RUNNER_EOF == state);
-
-    }
-
-    uint64_t BtreeBasedBuilder::fastBuildIndex( Collection* collection,
-                                                IndexCatalogEntry* btreeState,
-                                                bool mayInterrupt ) {
-        CurOp * op = cc().curop();
-        Timer t;
-
-        const IndexDescriptor* descriptor = btreeState->descriptor();
-
-        MONGO_TLOG(1) << "fastBuildIndex " << collection->ns() << ' ' << descriptor->toString();
-
-        bool dupsAllowed = !descriptor->unique() || ignoreUniqueIndex(descriptor);
-        bool dropDups = descriptor->dropDups() || inDBRepair;
-        BSONObj order = descriptor->keyPattern();
-
-        {
-            DiskLoc myNull;
-            myNull.Null();
-            btreeState->setHead( myNull );
-        }
-
-        if ( logger::globalLogDomain()->shouldLog(logger::LogSeverity::Debug(2) ) )
-            printMemInfo( "before index start" );
-
-        /* get and sort all the keys ----- */
-        ProgressMeterHolder pm(op->setMessage("index: (1/3) external sort",
-                                              "Index: (1/3) External Sort Progress",
-                                              collection->numRecords(),
-                                              10));
-        SortPhaseOne phase1;
-        addKeysToPhaseOne(collection, descriptor, order, &phase1, pm.get(), mayInterrupt );
-        pm.finished();
-
-        BSONObjExternalSorter& sorter = *(phase1.sorter);
-
-        if( phase1.multi ) {
-            btreeState->setMultikey();
-        }
-
-        if ( logger::globalLogDomain()->shouldLog(logger::LogSeverity::Debug(2) ) )
-            printMemInfo( "before final sort" );
-        phase1.sorter->sort( mayInterrupt );
-        if ( logger::globalLogDomain()->shouldLog(logger::LogSeverity::Debug(2) ) )
-            printMemInfo( "after final sort" );
-
-        LOG(t.seconds() > 5 ? 0 : 1) << "\t external sort used : " << sorter.numFiles()
-                                     << " files " << " in " << t.seconds() << " secs" << endl;
-
-        set<DiskLoc> dupsToDrop;
-
-        /* build index --- */
-        if( descriptor->version() == 0 )
-            buildBottomUpPhases2And3<V0>(dupsAllowed,
-                                         btreeState,
-                                         sorter,
-                                         dropDups,
-                                         dupsToDrop,
-                                         op,
-                                         &phase1,
-                                         pm,
-                                         t,
-                                         mayInterrupt);
-        else if( descriptor->version() == 1 )
-            buildBottomUpPhases2And3<V1>(dupsAllowed,
-                                         btreeState,
-                                         sorter,
-                                         dropDups,
-                                         dupsToDrop,
-                                         op,
-                                         &phase1,
-                                         pm,
-                                         t,
-                                         mayInterrupt);
-        else
-            verify(false);
-
-        if( dropDups )
-            log() << "\t fastBuildIndex dupsToDrop:" << dupsToDrop.size() << endl;
-
-        doDropDups(collection, dupsToDrop, mayInterrupt);
-
-        return phase1.n;
-    }
-
-    void BtreeBasedBuilder::doDropDups(Collection* collection,
-                                       const set<DiskLoc>& dupsToDrop, bool mayInterrupt) {
-        string ns = collection->ns().ns();
-        for( set<DiskLoc>::const_iterator i = dupsToDrop.begin(); i != dupsToDrop.end(); ++i ) {
-            RARELY killCurrentOp.checkForInterrupt( !mayInterrupt );
-            BSONObj toDelete;
-            collection->deleteDocument( *i,
-                                        false /* cappedOk */,
-                                        true /* noWarn */,
-                                        &toDelete );
-            getDur().commitIfNeeded();
-            if ( isMaster( ns.c_str() ) ) {
-                logOp( "d", ns.c_str(), toDelete );
-            }
-        }
-    }
-
-}  // namespace mongo
diff --git a/src/mongo/db/index/btree_based_builder.h b/src/mongo/db/index/btree_based_builder.h
deleted file mode 100644
index 967c17bb2b5..00000000000
--- a/src/mongo/db/index/btree_based_builder.h
+++ /dev/null
@@ -1,100 +0,0 @@
-/**
-*    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.
-*/
-
-#pragma once
-
-#include <set>
-
-#include "mongo/db/jsobj.h"
-#include "mongo/db/pdfile.h"
-
-namespace IndexUpdateTests {
-    class AddKeysToPhaseOne;
-    class InterruptAddKeysToPhaseOne;
-    class DoDropDups;
-    class InterruptDoDropDups;
-}
-
-namespace mongo {
-
-    class Collection;
-    class BSONObjExternalSorter;
-    class IndexCatalogEntry;
-    class ExternalSortComparison;
-    class IndexDescriptor;
-    class IndexDetails;
-    class NamespaceDetails;
-    class ProgressMeter;
-    class ProgressMeterHolder;
-    struct SortPhaseOne;
-
-    class BtreeBasedBuilder {
-    public:
-        /**
-         * Want to build an index?  Call this.  Throws DBException.
-         */
-        static uint64_t fastBuildIndex(Collection* collection,
-                                       IndexCatalogEntry* descriptor,
-                                       bool mayInterrupt);
-
-        static ExternalSortComparison* getComparison(int version,
-                                                     const BSONObj& keyPattern);
-
-    private:
-        friend class IndexUpdateTests::AddKeysToPhaseOne;
-        friend class IndexUpdateTests::InterruptAddKeysToPhaseOne;
-        friend class IndexUpdateTests::DoDropDups;
-        friend class IndexUpdateTests::InterruptDoDropDups;
-
-
-        static void addKeysToPhaseOne(Collection* collection,
-                                      const IndexDescriptor* idx,
-                                      const BSONObj& order,
-                                      SortPhaseOne* phaseOne,
-                                      ProgressMeter* progressMeter,
-                                      bool mayInterrupt );
-
-        static void doDropDups(Collection* collection,
-                               const set<DiskLoc>& dupsToDrop,
-                               bool mayInterrupt );
-    };
-
-    // Exposed for testing purposes.
-    template< class V >
-    void buildBottomUpPhases2And3( bool dupsAllowed,
-                                   IndexCatalogEntry* btreeState,
-                                   BSONObjExternalSorter& sorter,
-                                   bool dropDups,
-                                   set<DiskLoc>& dupsToDrop,
-                                   CurOp* op,
-                                   SortPhaseOne* phase1,
-                                   ProgressMeterHolder& pm,
-                                   Timer& t,
-                                   bool mayInterrupt );
-
-}  // namespace mongo
diff --git a/src/mongo/db/index/btree_interface.cpp b/src/mongo/db/index/btree_interface.cpp
index 2db19964598..ce257314ef1 100644
--- a/src/mongo/db/index/btree_interface.cpp
+++ b/src/mongo/db/index/btree_interface.cpp
@@ -145,6 +145,12 @@ namespace mongo {
         }
 
 
+        virtual int nKeys(const IndexCatalogEntry* btreeState,
+                          DiskLoc bucket ) {
+            return getBucket(btreeState,bucket)->nKeys();
+        }
+
+
         virtual bool keyIsUsed(const IndexCatalogEntry* btreeState,
                                DiskLoc bucket, int keyOffset) const {
             return getBucket(btreeState,bucket)->k(keyOffset).isUsed();
diff --git a/src/mongo/db/index/btree_interface.h b/src/mongo/db/index/btree_interface.h
index 64409300f33..3a0d30ced4f 100644
--- a/src/mongo/db/index/btree_interface.h
+++ b/src/mongo/db/index/btree_interface.h
@@ -115,6 +115,9 @@ namespace mongo {
          * two on-disk formats.
          */
 
+        virtual int nKeys(const IndexCatalogEntry* btreeState,
+                          DiskLoc bucket ) = 0;
+
         /**
          * Is the key at (bucket, keyOffset) being used or not?
          * Some keys are marked as not used and skipped.
diff --git a/src/mongo/db/index/index_access_method.h b/src/mongo/db/index/index_access_method.h
index a04e54610ab..5b6227804aa 100644
--- a/src/mongo/db/index/index_access_method.h
+++ b/src/mongo/db/index/index_access_method.h
@@ -140,12 +140,29 @@ namespace mongo {
         virtual Status validate(int64_t* numKeys) = 0;
 
         //
-        // Bulk operations support (TODO)
+        // Bulk operations support
         //
 
-        // virtual Status insertBulk(BulkDocs arg) = 0;
+        /**
+         * Starts a bulk operation.
+         * You work on the returned IndexAccessMethod and then call commitBulk.
+         * This can return NULL, meaning bulk mode is not available.
+         */
+        virtual IndexAccessMethod* initiateBulk() = 0;
 
-        // virtual Status removeBulk(BulkDocs arg) = 0;
+        /**
+         * Call this when you are ready to finish your bulk work.
+         * Pass in the IndexAccessMethod gotten from initiateBulk.
+         * After this method is called, the bulk index access method is invalid
+         * and should not be used.
+         * @param bulk - something created from initiateBulk
+         * @param mayInterrupt - is this commit interruptable (will cancel)
+         * @param dups - if NULL, error out on dups if not allowed
+         *               if not NULL, put the bad DiskLocs there
+         */
+        virtual Status commitBulk( IndexAccessMethod* bulk,
+                                   bool mayInterrupt,
+                                   std::set<DiskLoc>* dups ) = 0;
     };
 
     /**