SERVER-14973 consolidate shard key parsing, cleanup shard key patterns

27 files changed, 1356 insertions, 423 deletions

diff --git a/src/mongo/db/SConscript b/src/mongo/db/SConscript
index 83c30a6711d..4b2a739d80c 100644
--- a/src/mongo/db/SConscript
+++ b/src/mongo/db/SConscript
@@ -15,11 +15,13 @@ env.Library(
         'field_ref_set.cpp',
         'field_parser.cpp',
         'get_status_from_command_result.cpp',
+        'keypattern.cpp',
         'write_concern_options.cpp'
     ],
     LIBDEPS=[
         '$BUILD_DIR/mongo/bson',
         '$BUILD_DIR/mongo/foundation',
+        '$BUILD_DIR/mongo/index_names'
     ],
 )
 
@@ -59,6 +61,14 @@ env.CppUnitTest(
 )
 
 env.CppUnitTest(
+    target= 'keypattern_test',
+    source= 'keypattern_test.cpp',
+    LIBDEPS=[
+        'common'
+    ],
+)
+
+env.CppUnitTest(
     target="dbmessage_test",
     source=[
         "dbmessage_test.cpp"
diff --git a/src/mongo/db/auth/authorization_manager_test.cpp b/src/mongo/db/auth/authorization_manager_test.cpp
index 64ca474ec48..2f29749722a 100644
--- a/src/mongo/db/auth/authorization_manager_test.cpp
+++ b/src/mongo/db/auth/authorization_manager_test.cpp
@@ -152,7 +152,8 @@ namespace {
     class AuthorizationManagerTest : public ::mongo::unittest::Test {
     public:
         virtual ~AuthorizationManagerTest() {
-            authzManager->invalidateUserCache();
+            if (authzManager)
+                authzManager->invalidateUserCache();
         }
 
         void setUp() {
diff --git a/src/mongo/db/auth/authz_manager_external_state_mock.cpp b/src/mongo/db/auth/authz_manager_external_state_mock.cpp
index 638e6f9465a..377be4b36ea 100644
--- a/src/mongo/db/auth/authz_manager_external_state_mock.cpp
+++ b/src/mongo/db/auth/authz_manager_external_state_mock.cpp
@@ -204,7 +204,7 @@ namespace {
             if (query.hasField("_id")) {
                 document.root().appendElement(query["_id"]);
             }
-            status = driver.populateDocumentWithQueryFields(query, document);
+            status = driver.populateDocumentWithQueryFields(query, NULL, document);
             if (!status.isOK()) {
                 return status;
             }
diff --git a/src/mongo/db/auth/role_graph_update.cpp b/src/mongo/db/auth/role_graph_update.cpp
index 6236bcc50ae..71e9370ec61 100644
--- a/src/mongo/db/auth/role_graph_update.cpp
+++ b/src/mongo/db/auth/role_graph_update.cpp
@@ -181,7 +181,8 @@ namespace {
         status = AuthorizationManager::getBSONForRole(
                 roleGraph, roleToUpdate, roleDocument.root());
         if (status == ErrorCodes::RoleNotFound) {
-            status = driver.populateDocumentWithQueryFields(queryPattern, roleDocument);
+            // The query pattern will only contain _id, no other immutable fields are present
+            status = driver.populateDocumentWithQueryFields(queryPattern, NULL, roleDocument);
         }
         if (!status.isOK())
             return status;
diff --git a/src/mongo/db/commands/create_indexes.cpp b/src/mongo/db/commands/create_indexes.cpp
index c978b5ec046..353d8979690 100644
--- a/src/mongo/db/commands/create_indexes.cpp
+++ b/src/mongo/db/commands/create_indexes.cpp
@@ -214,11 +214,12 @@ namespace mongo {
                         shardingState.getCollectionMetadata( ns.toString() ));
 
                 if ( metadata ) {
-                    BSONObj shardKey(metadata->getKeyPattern());
-                    if ( !isUniqueIndexCompatible( shardKey, newIdxKey )) {
+                    ShardKeyPattern shardKeyPattern(metadata->getKeyPattern());
+                    if (!shardKeyPattern.isUniqueIndexCompatible(newIdxKey)) {
                         return Status(ErrorCodes::CannotCreateIndex,
-                                str::stream() << "cannot create unique index over " << newIdxKey
-                                              << " with shard key pattern " << shardKey);
+                            str::stream() << "cannot create unique index over " << newIdxKey
+                                          << " with shard key pattern "
+                                          << shardKeyPattern.toBSON());
                     }
                 }
             }
diff --git a/src/mongo/db/commands/mr.cpp b/src/mongo/db/commands/mr.cpp
index 4717eea89c7..d4ced8c5806 100644
--- a/src/mongo/db/commands/mr.cpp
+++ b/src/mongo/db/commands/mr.cpp
@@ -58,6 +58,7 @@
 #include "mongo/s/collection_metadata.h"
 #include "mongo/s/d_state.h"
 #include "mongo/s/grid.h"
+#include "mongo/s/shard_key_pattern.h"
 #include "mongo/s/stale_exception.h"
 #include "mongo/util/log.h"
 #include "mongo/util/scopeguard.h"
@@ -1371,7 +1372,7 @@ namespace mongo {
                             // check to see if this is a new object we don't own yet
                             // because of a chunk migration
                             if ( collMetadata ) {
-                                KeyPattern kp( collMetadata->getKeyPattern() );
+                                ShardKeyPattern kp( collMetadata->getKeyPattern() );
                                 if (!collMetadata->keyBelongsToMe(kp.extractShardKeyFromDoc(o))) {
                                     continue;
                                 }
diff --git a/src/mongo/db/commands/write_commands/batch_executor.cpp b/src/mongo/db/commands/write_commands/batch_executor.cpp
index b71978dc5a6..4e0eac5a579 100644
--- a/src/mongo/db/commands/write_commands/batch_executor.cpp
+++ b/src/mongo/db/commands/write_commands/batch_executor.cpp
@@ -486,8 +486,8 @@ namespace mongo {
             CollectionMetadataPtr metadata = shardingState->getCollectionMetadata( nss.ns() );
 
             if ( metadata ) {
-                if ( !isUniqueIndexCompatible( metadata->getKeyPattern(),
-                                               request.getIndexKeyPattern() ) ) {
+                ShardKeyPattern shardKeyPattern(metadata->getKeyPattern());
+                if (!shardKeyPattern.isUniqueIndexCompatible(request.getIndexKeyPattern())) {
 
                     result->setError(new WriteErrorDetail);
                     buildUniqueIndexError(metadata->getKeyPattern(),
diff --git a/src/mongo/db/dbhelpers.cpp b/src/mongo/db/dbhelpers.cpp
index e0c7cfaaa8e..334e87895d8 100644
--- a/src/mongo/db/dbhelpers.cpp
+++ b/src/mongo/db/dbhelpers.cpp
@@ -43,6 +43,7 @@
 #include "mongo/db/db.h"
 #include "mongo/db/exec/working_set_common.h"
 #include "mongo/db/json.h"
+#include "mongo/db/keypattern.h"
 #include "mongo/db/index/btree_access_method.h"
 #include "mongo/db/ops/delete.h"
 #include "mongo/db/ops/update.h"
@@ -60,6 +61,7 @@
 #include "mongo/db/storage_options.h"
 #include "mongo/db/catalog/collection.h"
 #include "mongo/s/d_state.h"
+#include "mongo/s/shard_key_pattern.h"
 #include "mongo/util/log.h"
 
 namespace mongo {
@@ -420,7 +422,7 @@ namespace mongo {
 
                     bool docIsOrphan;
                     if ( metadataNow ) {
-                        KeyPattern kp( metadataNow->getKeyPattern() );
+                        ShardKeyPattern kp( metadataNow->getKeyPattern() );
                         BSONObj key = kp.extractShardKeyFromDoc(obj);
                         docIsOrphan = !metadataNow->keyBelongsToMe( key )
                             && !metadataNow->keyIsPending( key );
diff --git a/src/mongo/db/exec/shard_filter.cpp b/src/mongo/db/exec/shard_filter.cpp
index 1680c67e1ed..d27cce9ad6b 100644
--- a/src/mongo/db/exec/shard_filter.cpp
+++ b/src/mongo/db/exec/shard_filter.cpp
@@ -33,8 +33,7 @@
 #include "mongo/db/exec/filter.h"
 #include "mongo/db/exec/scoped_timer.h"
 #include "mongo/db/exec/working_set_common.h"
-#include "mongo/db/keypattern.h"
-#include "mongo/s/stale_exception.h"
+#include "mongo/s/shard_key_pattern.h"
 #include "mongo/util/log.h"
 
 namespace mongo {
@@ -69,7 +68,7 @@ namespace mongo {
             // aborted migrations
             if (_metadata) {
 
-                KeyPattern shardKeyPattern(_metadata->getKeyPattern());
+                ShardKeyPattern shardKeyPattern(_metadata->getKeyPattern());
                 WorkingSetMember* member = _ws->get(*out);
                 WorkingSetMatchableDocument matchable(member);
                 BSONObj shardKey = shardKeyPattern.extractShardKeyFromMatchable(matchable);
diff --git a/src/mongo/db/exec/update.cpp b/src/mongo/db/exec/update.cpp
index aa5a895df70..391d09126f0 100644
--- a/src/mongo/db/exec/update.cpp
+++ b/src/mongo/db/exec/update.cpp
@@ -347,8 +347,7 @@ namespace mongo {
                         return Status(ErrorCodes::ImmutableField,
                                       mongoutils::str::stream()
                                       << "After applying the update to the document {"
-                                      << (oldIdElem.ok() ? oldIdElem.toString() :
-                                                           newIdElem.toString())
+                                      << oldElem.toString()
                                       << " , ...}, the (immutable) field '" << current.dottedField()
                                       << "' was found to have been altered to "
                                       << newElem.toString());
@@ -592,24 +591,23 @@ namespace mongo {
         // Reset the document we will be writing to
         _doc.reset();
 
-        // This remains the empty object in the case of an object replacement, but in the case
-        // of an upsert where we are creating a base object from the query and applying mods,
-        // we capture the query as the original so that we can detect immutable field mutations.
-        BSONObj original = BSONObj();
+        // The original document we compare changes to - immutable paths must not change
+        BSONObj original;
+
+        bool isInternalRequest = request->isFromReplication() || request->isFromMigration();
+
+        const vector<FieldRef*>* immutablePaths = NULL;
+        if (!isInternalRequest && lifecycle)
+            immutablePaths = lifecycle->getImmutableFields();
 
         // Calling populateDocumentWithQueryFields will populate the '_doc' with fields from the
         // query which creates the base of the update for the inserted doc (because upsert
         // was true).
         if (cq) {
-            uassertStatusOK(driver->populateDocumentWithQueryFields(cq, _doc));
-            if (!driver->isDocReplacement()) {
+            uassertStatusOK(driver->populateDocumentWithQueryFields(cq, immutablePaths, _doc));
+            if (driver->isDocReplacement())
                 _specificStats.fastmodinsert = true;
-                // We need all the fields from the query to compare against for validation below.
-                original = _doc.getObject();
-            }
-            else {
-                original = request->getQuery();
-            }
+            original = _doc.getObject();
         }
         else {
             fassert(17354, CanonicalQuery::isSimpleIdQuery(request->getQuery()));
@@ -630,17 +628,13 @@ namespace mongo {
         // Validate that the object replacement or modifiers resulted in a document
         // that contains all the immutable keys and can be stored if it isn't coming
         // from a migration or via replication.
-        if (!(request->isFromReplication() || request->isFromMigration())){
-            const std::vector<FieldRef*>* immutableFields = NULL;
-            if (lifecycle)
-                immutableFields = lifecycle->getImmutableFields();
-
+        if (!isInternalRequest){
             FieldRefSet noFields;
             // This will only validate the modified fields if not a replacement.
             uassertStatusOK(validate(original,
                                      noFields,
                                      _doc,
-                                     immutableFields,
+                                     immutablePaths,
                                      driver->modOptions()) );
         }
 
diff --git a/src/mongo/db/field_ref.cpp b/src/mongo/db/field_ref.cpp
index b6ad89c5938..840a62cdc7b 100644
--- a/src/mongo/db/field_ref.cpp
+++ b/src/mongo/db/field_ref.cpp
@@ -198,25 +198,36 @@ namespace mongo {
     }
 
     StringData FieldRef::dottedField( size_t offset ) const {
-        if (_size == 0 || offset >= numParts() )
+        return dottedSubstring(offset, numParts());
+    }
+
+    StringData FieldRef::dottedSubstring(size_t startPart, size_t endPart) const {
+        if (_size == 0 || startPart >= endPart || endPart > numParts())
             return StringData();
 
         if (!_replacements.empty())
             reserialize();
         dassert(_replacements.empty());
 
-        // Assume we want the whole thing
         StringData result(_dotted);
 
-        // Strip off any leading parts we were asked to ignore
-        for (size_t i = 0; i < offset; ++i) {
-            const StringData part = getPart(i);
-            result = StringData(
-                result.rawData() + part.size() + 1,
-                result.size() - part.size() - 1);
+        // Fast-path if we want the whole thing
+        if (startPart == 0 && endPart == numParts())
+            return result;
+
+        size_t startChar = 0;
+        for (size_t i = 0; i < startPart; ++i) {
+            startChar += getPart(i).size() + 1; // correct for '.'
+        }
+        size_t endChar = startChar;
+        for (size_t i = startPart; i < endPart; ++i) {
+            endChar += getPart(i).size() + 1;
         }
+        // correct for last '.'
+        if (endPart != numParts())
+            --endChar;
 
-        return result;
+        return result.substr(startChar, endChar - startChar);
     }
 
     bool FieldRef::equalsDottedField( const StringData& other ) const {
diff --git a/src/mongo/db/field_ref.h b/src/mongo/db/field_ref.h
index d35a94d284d..51b3f642985 100644
--- a/src/mongo/db/field_ref.h
+++ b/src/mongo/db/field_ref.h
@@ -89,12 +89,18 @@ namespace mongo {
         size_t commonPrefixSize( const FieldRef& other ) const;
 
         /**
-         * Returns a copy of the full dotted field in its current state (i.e., some parts may
+         * Returns a StringData of the full dotted field in its current state (i.e., some parts may
          * have been replaced since the parse() call).
          */
         StringData dottedField( size_t offsetFromStart = 0 ) const;
 
         /**
+         * Returns a StringData of parts of the dotted field from startPart to endPart in its
+         * current state (i.e., some parts may have been replaced since the parse() call).
+         */
+        StringData dottedSubstring(size_t startPart, size_t endPart) const;
+
+        /**
          * Compares the full dotted path represented by this FieldRef to other
          */
         bool equalsDottedField( const StringData& other ) const;
diff --git a/src/mongo/db/field_ref_set.cpp b/src/mongo/db/field_ref_set.cpp
index 509de2845fc..efc49f2dd1d 100644
--- a/src/mongo/db/field_ref_set.cpp
+++ b/src/mongo/db/field_ref_set.cpp
@@ -33,6 +33,8 @@
 
 namespace mongo {
 
+    using std::vector;
+    using std::string;
     namespace str = mongoutils::str;
 
     namespace {
@@ -59,6 +61,10 @@ namespace mongo {
     FieldRefSet::FieldRefSet() {
     }
 
+    FieldRefSet::FieldRefSet(const vector<FieldRef*>& paths) {
+        fillFrom(paths);
+    }
+
     bool FieldRefSet::findConflicts(const FieldRef* toCheck, FieldRefSet* conflicts) const {
         bool foundConflict = false;
 
diff --git a/src/mongo/db/field_ref_set.h b/src/mongo/db/field_ref_set.h
index e7258c2a184..0403f9265b2 100644
--- a/src/mongo/db/field_ref_set.h
+++ b/src/mongo/db/field_ref_set.h
@@ -29,6 +29,7 @@
 #pragma once
 
 #include <set>
+#include <vector>
 
 #include "mongo/base/disallow_copying.h"
 #include "mongo/base/owned_pointer_vector.h"
@@ -38,9 +39,14 @@
 namespace mongo {
 
     /**
-     * A FieldRefSet holds a set of FieldRefs's that do not conflict with one another, that is,
-     * they target different subtrees of a given document. Two fieldRef's would conflict if they
-     * are equal or one is prefix of the other.
+     * A FieldRefSet holds a number of unique FieldRefs - a set of dotted paths into a document.
+     *
+     * The FieldRefSet provides helpful functions for efficiently finding conflicts between field
+     * ref paths - field ref paths conflict if they are equal to each other or if one is a prefix.
+     * To maintain a FieldRefSet of non-conflicting paths, always use the insert method which
+     * returns conflicting FieldRefs.
+     *
+     * FieldRefSets do not own the FieldRef paths they contain.
      */
     class FieldRefSet {
         MONGO_DISALLOW_COPYING(FieldRefSet);
@@ -57,6 +63,8 @@ namespace mongo {
 
         FieldRefSet();
 
+        FieldRefSet(const std::vector<FieldRef*>& paths);
+
         /** Returns 'true' if the set is empty */
         bool empty() const {
             return _fieldSet.empty();
@@ -71,6 +79,15 @@ namespace mongo {
         }
 
         /**
+         * Returns true if the path does not already exist in the set, false otherwise.
+         *
+         * Note that *no* conflict resolution occurs - any path can be inserted into a set.
+         */
+        inline bool insert(const FieldRef* path) {
+            return _fieldSet.insert(path).second;
+        }
+
+        /**
          * Returns true if the field 'toInsert' can be added in the set without
          * conflicts. Otherwise returns false and fill in '*conflict' with the field 'toInsert'
          * clashed with.
@@ -83,6 +100,8 @@ namespace mongo {
 
         /**
          * Fills the set with the supplied FieldRef*s
+         *
+         * Note that *no* conflict resolution occurs here.
          */
         void fillFrom(const std::vector<FieldRef*>& fields);
 
diff --git a/src/mongo/db/field_ref_test.cpp b/src/mongo/db/field_ref_test.cpp
index 5ea2009ac25..02390302190 100644
--- a/src/mongo/db/field_ref_test.cpp
+++ b/src/mongo/db/field_ref_test.cpp
@@ -277,4 +277,46 @@ namespace {
         ASSERT_EQUALS( "", a.dottedField(6) );
     }
 
+    TEST(DottedSubstring, Short) {
+        FieldRef path("a");
+        ASSERT_EQUALS(1u, path.numParts());
+        ASSERT_EQUALS("a", path.dottedSubstring(0, path.numParts()));
+        ASSERT_EQUALS("", path.dottedSubstring(1, path.numParts()));
+        ASSERT_EQUALS("", path.dottedSubstring(0, 0));
+    }
+
+    TEST(DottedSubstring, Empty) {
+        FieldRef path("");
+        ASSERT_EQUALS(0u, path.numParts());
+        ASSERT_EQUALS("", path.dottedSubstring(0, path.numParts()));
+        ASSERT_EQUALS("", path.dottedSubstring(1, path.numParts()));
+        ASSERT_EQUALS("", path.dottedSubstring(0, 0));
+    }
+
+    TEST(DottedSubstring, Nested) {
+        FieldRef path("a.b.c.d.e");
+        ASSERT_EQUALS(5u, path.numParts());
+
+        ASSERT_EQUALS("b.c.d.e", path.dottedSubstring(1, path.numParts()));
+        ASSERT_EQUALS("c.d.e", path.dottedSubstring(2, path.numParts()));
+        ASSERT_EQUALS("d.e", path.dottedSubstring(3, path.numParts()));
+        ASSERT_EQUALS("e", path.dottedSubstring(4, path.numParts()));
+        ASSERT_EQUALS("", path.dottedSubstring(5, path.numParts()));
+        ASSERT_EQUALS("", path.dottedSubstring(6, path.numParts()));
+
+        ASSERT_EQUALS("a.b.c.d.e", path.dottedSubstring(0, path.numParts()));
+        ASSERT_EQUALS("a.b.c.d", path.dottedSubstring(0, path.numParts() - 1));
+        ASSERT_EQUALS("a.b.c", path.dottedSubstring(0, path.numParts() - 2));
+        ASSERT_EQUALS("a.b", path.dottedSubstring(0, path.numParts() - 3));
+        ASSERT_EQUALS("a", path.dottedSubstring(0, path.numParts() - 4));
+        ASSERT_EQUALS("", path.dottedSubstring(0, path.numParts() - 5));
+        ASSERT_EQUALS("", path.dottedSubstring(0, path.numParts() - 6));
+
+        ASSERT_EQUALS("b.c.d", path.dottedSubstring(1, path.numParts() - 1));
+        ASSERT_EQUALS("b.c", path.dottedSubstring(1, path.numParts() - 2));
+        ASSERT_EQUALS("b", path.dottedSubstring(1, path.numParts() - 3));
+        ASSERT_EQUALS("", path.dottedSubstring(1, path.numParts() - 4));
+        ASSERT_EQUALS("", path.dottedSubstring(1, path.numParts() - 5));
+    }
+
 } // namespace
diff --git a/src/mongo/db/keypattern.cpp b/src/mongo/db/keypattern.cpp
index e0476f94358..b62885b97d1 100644
--- a/src/mongo/db/keypattern.cpp
+++ b/src/mongo/db/keypattern.cpp
@@ -30,7 +30,6 @@
 
 #include "mongo/db/keypattern.h"
 
-#include "mongo/db/hasher.h"
 #include "mongo/db/index_names.h"
 #include "mongo/util/mongoutils/str.h"
 
@@ -49,64 +48,12 @@ namespace mongo {
                && i.next().eoo();
     }
 
-    BSONObj KeyPattern::extractShardKeyFromQuery(const BSONObj& query) const {
-
-        if (_pattern.isEmpty())
-            return BSONObj();
-
-        if (mongoutils::str::equals(_pattern.firstElement().valuestrsafe(), "hashed")) {
-            BSONElement fieldVal = query.getFieldDotted(_pattern.firstElementFieldName());
-            return BSON(_pattern.firstElementFieldName() <<
-                        BSONElementHasher::hash64(fieldVal , BSONElementHasher::DEFAULT_HASH_SEED));
-        }
-
-        return query.extractFields(_pattern);
-    }
-
     bool KeyPattern::isOrderedKeyPattern(const BSONObj& pattern) {
         return IndexNames::BTREE == IndexNames::findPluginName(pattern);
     }
 
-    BSONObj KeyPattern::extractShardKeyFromDoc(const BSONObj& doc) const {
-        BSONMatchableDocument matchable(doc);
-        return extractShardKeyFromMatchable(matchable);
-    }
-
-    BSONObj KeyPattern::extractShardKeyFromMatchable(const MatchableDocument& matchable) const {
-
-        if ( _pattern.isEmpty() )
-            return BSONObj();
-
-        BSONObjBuilder keyBuilder;
-
-        BSONObjIterator patternIt(_pattern);
-        while (patternIt.more()) {
-
-            BSONElement patternEl = patternIt.next();
-            ElementPath path;
-            path.init(patternEl.fieldName());
-
-            MatchableDocument::IteratorHolder matchIt(&matchable, &path);
-            if (!matchIt->more())
-                return BSONObj();
-            BSONElement matchEl = matchIt->next().element();
-            // We sometimes get eoo(), apparently
-            if (matchEl.eoo() || matchIt->more())
-                return BSONObj();
-
-            if (mongoutils::str::equals(patternEl.valuestrsafe(), "hashed")) {
-                keyBuilder.append(patternEl.fieldName(),
-                                  BSONElementHasher::hash64(matchEl,
-                                                            BSONElementHasher::DEFAULT_HASH_SEED));
-            }
-            else {
-                // NOTE: The matched element may *not* have the same field name as the path -
-                // index keys don't contain field names, for example
-                keyBuilder.appendAs(matchEl, patternEl.fieldName());
-            }
-        }
-
-        return keyBuilder.obj();
+    bool KeyPattern::isHashedKeyPattern(const BSONObj& pattern) {
+        return IndexNames::HASHED == IndexNames::findPluginName(pattern);
     }
 
     BSONObj KeyPattern::extendRangeBound( const BSONObj& bound , bool makeUpperInclusive ) const {
@@ -144,95 +91,12 @@ namespace mongo {
         return newBound.obj();
     }
 
-    BoundList KeyPattern::flattenBounds( const BSONObj& keyPattern, const IndexBounds& indexBounds ) {
-        invariant(indexBounds.fields.size() == (size_t)keyPattern.nFields());
-
-        // If any field is unsatisfied, return empty bound list.
-        for (vector<OrderedIntervalList>::const_iterator it = indexBounds.fields.begin();
-                it != indexBounds.fields.end(); it++) {
-            if (it->intervals.size() == 0) {
-                return BoundList();
-            }
-        }
-        // To construct our bounds we will generate intervals based on bounds for
-        // the first field, then compound intervals based on constraints for the first
-        // 2 fields, then compound intervals for the first 3 fields, etc.
-        // As we loop through the fields, we start generating new intervals that will later
-        // get extended in another iteration of the loop.  We define these partially constructed
-        // intervals using pairs of BSONObjBuilders (shared_ptrs, since after one iteration of the
-        // loop they still must exist outside their scope).
-        typedef vector< pair< shared_ptr<BSONObjBuilder> ,
-                              shared_ptr<BSONObjBuilder> > > BoundBuilders;
-        BoundBuilders builders;
-        builders.push_back( make_pair( shared_ptr<BSONObjBuilder>( new BSONObjBuilder() ),
-                                       shared_ptr<BSONObjBuilder>( new BSONObjBuilder() ) ) );
-        BSONObjIterator keyIter( keyPattern );
-        // until equalityOnly is false, we are just dealing with equality (no range or $in queries).
-        bool equalityOnly = true;
-
-        for (size_t i = 0; i < indexBounds.fields.size(); i++) {
-            BSONElement e = keyIter.next();
-
-            StringData fieldName = e.fieldNameStringData();
-
-            // get the relevant intervals for this field, but we may have to transform the
-            // list of what's relevant according to the expression for this field
-            const OrderedIntervalList& oil = indexBounds.fields[i];
-            const vector<Interval>& intervals = oil.intervals;
-
-            if ( equalityOnly ) {
-                if ( intervals.size() == 1 && intervals.front().isPoint() ){
-                    // this field is only a single point-interval
-                    BoundBuilders::const_iterator j;
-                    for( j = builders.begin(); j != builders.end(); ++j ) {
-                        j->first->appendAs( intervals.front().start, fieldName );
-                        j->second->appendAs( intervals.front().end, fieldName );
-                    }
-                }
-                else {
-                    // This clause is the first to generate more than a single point.
-                    // We only execute this clause once. After that, we simplify the bound
-                    // extensions to prevent combinatorial explosion.
-                    equalityOnly = false;
-
-                    BoundBuilders newBuilders;
-
-                    for(BoundBuilders::const_iterator it = builders.begin(); it != builders.end(); ++it ) {
-                        BSONObj first = it->first->obj();
-                        BSONObj second = it->second->obj();
+    BSONObj KeyPattern::globalMin() const {
+        return extendRangeBound(BSONObj(), false);
+    }
 
-                        for ( vector<Interval>::const_iterator interval = intervals.begin();
-                                interval != intervals.end(); ++interval )
-                        {
-                            uassert( 17439,
-                                     "combinatorial limit of $in partitioning of results exceeded" ,
-                                     newBuilders.size() < MAX_IN_COMBINATIONS );
-                            newBuilders.push_back(
-                                     make_pair( shared_ptr<BSONObjBuilder>( new BSONObjBuilder() ),
-                                                shared_ptr<BSONObjBuilder>( new BSONObjBuilder())));
-                            newBuilders.back().first->appendElements( first );
-                            newBuilders.back().second->appendElements( second );
-                            newBuilders.back().first->appendAs( interval->start, fieldName );
-                            newBuilders.back().second->appendAs( interval->end, fieldName );
-                        }
-                    }
-                    builders = newBuilders;
-                }
-            }
-            else {
-                // if we've already generated a range or multiple point-intervals
-                // just extend what we've generated with min/max bounds for this field
-                BoundBuilders::const_iterator j;
-                for( j = builders.begin(); j != builders.end(); ++j ) {
-                    j->first->appendAs( intervals.front().start, fieldName );
-                    j->second->appendAs( intervals.back().end, fieldName );
-                }
-            }
-        }
-        BoundList ret;
-        for( BoundBuilders::const_iterator i = builders.begin(); i != builders.end(); ++i )
-            ret.push_back( make_pair( i->first->obj(), i->second->obj() ) );
-        return ret;
+    BSONObj KeyPattern::globalMax() const {
+        return extendRangeBound(BSONObj(), true);
     }
 
 } // namespace mongo
diff --git a/src/mongo/db/keypattern.h b/src/mongo/db/keypattern.h
index 77e30b883d2..78e1f3d59bf 100644
--- a/src/mongo/db/keypattern.h
+++ b/src/mongo/db/keypattern.h
@@ -1,5 +1,3 @@
-// @file keypattern.h - Utilities for manipulating index/shard key patterns.
-
 /**
 *    Copyright (C) 2012 10gen Inc.
 *
@@ -32,27 +30,18 @@
 
 #include "mongo/base/string_data.h"
 #include "mongo/db/jsobj.h"
-#include "mongo/platform/unordered_set.h"
-#include "mongo/util/mongoutils/str.h"
-#include "mongo/db/query/index_bounds.h"
-#include "mongo/db/matcher/matchable.h"
 
 namespace mongo {
 
     /**
-     * A BoundList contains intervals specified by inclusive start
-     * and end bounds.  The intervals should be nonoverlapping and occur in
-     * the specified direction of traversal.  For example, given a simple index {i:1}
-     * and direction +1, one valid BoundList is: (1, 2); (4, 6).  The same BoundList
-     * would be valid for index {i:-1} with direction -1.
-     */
-    typedef std::vector<std::pair<BSONObj,BSONObj> > BoundList;
-
-    /** A KeyPattern is an expression describing a transformation of a document into a
-     *  document key.  Document keys are used to store documents in indices and to target
-     *  sharded queries.
+     * A KeyPattern is an expression describing a transformation of a document into a
+     * document key.  Document keys are used to store documents in indices and to target
+     * sharded queries.
      *
-     *  Examples:
+     * The root field names of KeyPatterns are always (potentially-dotted) paths, and the values of
+     * the fields describe the type of indexing over the found elements.
+     *
+     * Examples:
      *    { a : 1 }
      *    { a : 1 , b  : -1 }
      *    { a : "hashed" }
@@ -60,19 +49,6 @@ namespace mongo {
     class KeyPattern {
     public:
 
-        //maximum number of intervals produced by $in queries.
-        static const unsigned MAX_IN_COMBINATIONS = 4000000;
-
-        /*
-         * We are allowing implicit conversion from BSON
-         */
-        KeyPattern( const BSONObj& pattern );
-
-        /*
-         *  Returns a BSON representation of this KeyPattern.
-         */
-        BSONObj toBSON() const { return _pattern; }
-
         /**
          * Is the provided key pattern the index over the ID field?
          * The always required ID index is always {_id: 1} or {_id: -1}.
@@ -84,6 +60,27 @@ namespace mongo {
          */
         static bool isOrderedKeyPattern(const BSONObj& pattern);
 
+        /**
+         * Does the provided key pattern hash its keys?
+         */
+        static bool isHashedKeyPattern(const BSONObj& pattern);
+
+        /**
+         * Constructs a new key pattern based on a BSON document
+         */
+        KeyPattern(const BSONObj& pattern);
+
+        /**
+         * Returns a BSON representation of this KeyPattern.
+         */
+        const BSONObj& toBSON() const { return _pattern; }
+
+        /**
+         * Returns a string representation of this KeyPattern
+         */
+        std::string toString() const{ return toBSON().toString(); }
+
+
         /* Takes a BSONObj whose field names are a prefix of the fields in this keyPattern, and
          * outputs a new bound with MinKey values appended to match the fields in this keyPattern
          * (or MaxKey values for descending -1 fields). This is useful in sharding for
@@ -109,66 +106,9 @@ namespace mongo {
          */
         BSONObj extendRangeBound( const BSONObj& bound , bool makeUpperInclusive ) const;
 
-        std::string toString() const{ return toBSON().toString(); }
-
-        /**
-         * Given a document, extracts the shard key corresponding to the key pattern.
-         * Warning: assumes that there is a *single* key to be extracted!
-         *
-         * Examples:
-         *  If 'this' KeyPattern is { a  : 1 }
-         *   { a: "hi" , b : 4} --> returns { a : "hi" }
-         *   { c : 4 , a : 2 } -->  returns { a : 2 }
-         *   { b : 2 }  (bad input, don't call with this)
-         *   { a : [1,2] }  (bad input, don't call with this)
-         *  If 'this' KeyPattern is { a  : "hashed" }
-         *   { a: 1 } --> returns { a : NumberLong("5902408780260971510")  }
-         *  If 'this' KeyPattern is { 'a.b' : 1 }
-         *   { a : { b : "hi" } } --> returns { a : "hi" }
-         */
-        BSONObj extractShardKeyFromDoc(const BSONObj& doc) const;
+        BSONObj globalMin() const;
 
-        /**
-         * Given a MatchableDocument, extracts the shard key corresponding to the key pattern.
-         * See above.
-         */
-        BSONObj extractShardKeyFromMatchable(const MatchableDocument& matchable) const;
-
-        /**
-         * Given a query expression, extracts the shard key corresponding to the key pattern.
-         *
-         * NOTE: This generally is similar to the above, however "a.b" fields in the query (which
-         * are invalid document fields) may match "a.b" fields in the shard key pattern.
-         *
-         * Examples:
-         *  If the key pattern is { a : 1 }
-         *   { a : "hi", b : 4 } --> returns { a : "hi" }
-         *  If the key pattern is { 'a.b' : 1 }
-         *   { a : { b : "hi" } } --> returns { 'a.b' : "hi" }
-         *   { 'a.b' : "hi" } --> returns { 'a.b' : "hi" }
-         */
-        BSONObj extractShardKeyFromQuery(const BSONObj& query) const;
-
-        /**
-         * Return an ordered list of bounds generated using this KeyPattern and the
-         * bounds from the IndexBounds.  This function is used in sharding to
-         * determine where to route queries according to the shard key pattern.
-         *
-         * Examples:
-         *
-         * Key { a: 1 }, Bounds a: [0] => { a: 0 } -> { a: 0 }
-         * Key { a: 1 }, Bounds a: [2, 3) => { a: 2 } -> { a: 3 }  // bound inclusion ignored.
-         *
-         * The bounds returned by this function may be a superset of those defined
-         * by the constraints.  For instance, if this KeyPattern is {a : 1, b: 1}
-         * Bounds: { a : {$in : [1,2]} , b : {$in : [3,4,5]} }
-         *         => {a : 1 , b : 3} -> {a : 1 , b : 5}, {a : 2 , b : 3} -> {a : 2 , b : 5}
-         *
-         * If the IndexBounds are not defined for all the fields in this keypattern, which
-         * means some fields are unsatisfied, an empty BoundList could return.
-         *
-         */
-        static BoundList flattenBounds( const BSONObj& keyPattern, const IndexBounds& indexBounds );
+        BSONObj globalMax() const;
 
     private:
         BSONObj _pattern;
diff --git a/src/mongo/db/keypattern_test.cpp b/src/mongo/db/keypattern_test.cpp
new file mode 100644
index 00000000000..63b9b325d75
--- /dev/null
+++ b/src/mongo/db/keypattern_test.cpp
@@ -0,0 +1,142 @@
+/*    Copyright 2014 MongoDB 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/keypattern.h"
+
+#include "mongo/unittest/unittest.h"
+
+namespace {
+
+    using namespace mongo;
+
+    TEST(KeyPattern, ExtendRangeBound) {
+
+        BSONObj bound = BSON("a" << 55);
+        BSONObj longBound = BSON("a" << 55 << "b" << 66);
+
+        //test keyPattern shorter than bound, should fail
+        {
+            KeyPattern keyPat(BSON("a" << 1));
+            ASSERT_THROWS(keyPat.extendRangeBound(longBound, false), MsgAssertionException);
+        }
+
+        //test keyPattern doesn't match bound, should fail
+        {
+            KeyPattern keyPat(BSON("b" << 1));
+            ASSERT_THROWS(keyPat.extendRangeBound(bound, false), MsgAssertionException);
+        }
+        {
+            KeyPattern keyPat(BSON("a" << 1 << "c" << 1));
+            ASSERT_THROWS(keyPat.extendRangeBound(longBound, false), MsgAssertionException);
+        }
+
+        //test keyPattern same as bound
+        {
+            KeyPattern keyPat(BSON("a" << 1));
+            BSONObj newB = keyPat.extendRangeBound(bound, false);
+            ASSERT_EQUALS(newB, BSON("a" << 55));
+        }
+        {
+            KeyPattern keyPat(BSON("a" << 1));
+            BSONObj newB = keyPat.extendRangeBound(bound, false);
+            ASSERT_EQUALS(newB, BSON("a" << 55));
+        }
+
+        //test keyPattern longer than bound, simple
+        {
+            KeyPattern keyPat(BSON("a" << 1 << "b" << 1));
+            BSONObj newB = keyPat.extendRangeBound(bound, false);
+            ASSERT_EQUALS(newB, BSON("a" << 55 << "b" << MINKEY));
+        }
+        {
+            KeyPattern keyPat(BSON("a" << 1 << "b" << 1));
+            BSONObj newB = keyPat.extendRangeBound(bound, true);
+            ASSERT_EQUALS(newB, BSON("a" << 55 << "b" << MAXKEY));
+        }
+
+        //test keyPattern longer than bound, more complex pattern directions
+        {
+            KeyPattern keyPat(BSON("a" << 1 << "b" << -1));
+            BSONObj newB = keyPat.extendRangeBound(bound, false);
+            ASSERT_EQUALS(newB, BSON("a" << 55 << "b" << MAXKEY));
+        }
+        {
+            KeyPattern keyPat(BSON("a" << 1 << "b" << -1));
+            BSONObj newB = keyPat.extendRangeBound(bound, true);
+            ASSERT_EQUALS(newB, BSON("a" << 55 << "b" << MINKEY));
+        }
+        {
+
+            KeyPattern keyPat(BSON("a" << 1 << "b" << -1 << "c" << 1));
+            BSONObj newB = keyPat.extendRangeBound(bound, false);
+            ASSERT_EQUALS(newB, BSON("a" << 55 << "b" << MAXKEY << "c" << MINKEY));
+        }
+        {
+            KeyPattern keyPat(BSON("a" << 1 << "b" << -1 << "c" << 1));
+            BSONObj newB = keyPat.extendRangeBound(bound, true);
+            ASSERT_EQUALS(newB, BSON("a" << 55 << "b" << MINKEY << "c" << MAXKEY));
+        }
+    }
+
+    TEST(KeyPattern, GlobalMinMax) {
+
+        //
+        // Simple KeyPatterns
+        //
+
+        ASSERT_EQUALS(KeyPattern(BSON("a" << 1)).globalMin(), BSON("a" << MINKEY));
+        ASSERT_EQUALS(KeyPattern(BSON("a" << 1)).globalMax(), BSON("a" << MAXKEY));
+
+        ASSERT_EQUALS(KeyPattern(BSON("a" << -1)).globalMin(), BSON("a" << MAXKEY));
+        ASSERT_EQUALS(KeyPattern(BSON("a" << -1)).globalMax(), BSON("a" << MINKEY));
+
+        ASSERT_EQUALS(KeyPattern(BSON("a" << 1 << "b" << 1.0)).globalMin(),
+                      BSON("a" << MINKEY << "b" << MINKEY));
+        ASSERT_EQUALS(KeyPattern(BSON("a" << 1 << "b" << 1.0)).globalMax(),
+                      BSON("a" << MAXKEY << "b" << MAXKEY));
+
+        ASSERT_EQUALS(KeyPattern(BSON("a" << 1 << "b" << -1.0f)).globalMin(),
+                      BSON("a" << MINKEY << "b" << MAXKEY));
+        ASSERT_EQUALS(KeyPattern(BSON("a" << 1 << "b" << -1.0f)).globalMax(),
+                      BSON("a" << MAXKEY << "b" << MINKEY));
+
+        ASSERT_EQUALS(KeyPattern(BSON("a" << "hashed")).globalMin(), BSON("a" << MINKEY));
+        ASSERT_EQUALS(KeyPattern(BSON("a" << "hashed")).globalMax(), BSON("a" << MAXKEY));
+
+        //
+        // Nested KeyPatterns
+        //
+
+        ASSERT_EQUALS(KeyPattern(BSON("a.b" << 1)).globalMin(), BSON("a.b" << MINKEY));
+        ASSERT_EQUALS(KeyPattern(BSON("a.b" << 1)).globalMax(), BSON("a.b" << MAXKEY));
+
+        ASSERT_EQUALS(KeyPattern(BSON("a.b.c" << -1)).globalMin(), BSON("a.b.c" << MAXKEY));
+        ASSERT_EQUALS(KeyPattern(BSON("a.b.c" << -1)).globalMax(), BSON("a.b.c" << MINKEY));
+    }
+
+}
+
diff --git a/src/mongo/db/matcher/path.cpp b/src/mongo/db/matcher/path.cpp
index 048a9ae5700..ce9c9fcbeec 100644
--- a/src/mongo/db/matcher/path.cpp
+++ b/src/mongo/db/matcher/path.cpp
@@ -39,6 +39,7 @@
 namespace mongo {
 
     Status ElementPath::init( const StringData& path ) {
+        _shouldTraverseNonleafArrays = true;
         _shouldTraverseLeafArray = true;
         _fieldRef.parse( path );
         return Status::OK();
@@ -164,6 +165,11 @@ namespace mongo {
                 _subCursorPath.reset( new ElementPath() );
                 _subCursorPath->init( _arrayIterationState.restOfPath.substr( _arrayIterationState.nextPieceOfPath.size() + 1 ) );
                 _subCursorPath->setTraverseLeafArray( _path->shouldTraverseLeafArray() );
+
+                // If we're here, we must be able to traverse nonleaf arrays
+                dassert(_path->shouldTraverseNonleafArrays());
+                dassert(_subCursorPath->shouldTraverseNonleafArrays());
+
                 _subCursor.reset( new BSONElementIterator( _subCursorPath.get(), _arrayIterationState._current.Obj() ) );
                 _arrayIterationState._current = BSONElement();
                 return more();
@@ -192,8 +198,14 @@ namespace mongo {
 
             _arrayIterationState.reset( _path->fieldRef(), idxPath + 1 );
 
-            if ( !_arrayIterationState.hasMore && !_path->shouldTraverseLeafArray() ) {
-                _next.reset( e, BSONElement(), true );
+            if (_arrayIterationState.hasMore && !_path->shouldTraverseNonleafArrays()) {
+                // Don't allow traversing the array
+                _state = DONE;
+                return false;
+            }
+            else if (!_arrayIterationState.hasMore && !_path->shouldTraverseLeafArray()) {
+                // Return the leaf array
+                _next.reset(e, BSONElement(), true);
                 _state = DONE;
                 return true;
             }
diff --git a/src/mongo/db/matcher/path.h b/src/mongo/db/matcher/path.h
index 8fdf8ed2a11..50c963c97ad 100644
--- a/src/mongo/db/matcher/path.h
+++ b/src/mongo/db/matcher/path.h
@@ -44,13 +44,16 @@ namespace mongo {
     public:
         Status init( const StringData& path );
 
+        void setTraverseNonleafArrays( bool b ) { _shouldTraverseNonleafArrays = b; }
         void setTraverseLeafArray( bool b ) { _shouldTraverseLeafArray = b; }
 
         const FieldRef& fieldRef() const { return _fieldRef; }
+        bool shouldTraverseNonleafArrays() const { return _shouldTraverseNonleafArrays; }
         bool shouldTraverseLeafArray() const { return _shouldTraverseLeafArray; }
 
     private:
         FieldRef _fieldRef;
+        bool _shouldTraverseNonleafArrays;
         bool _shouldTraverseLeafArray;
     };
 
diff --git a/src/mongo/db/ops/SConscript b/src/mongo/db/ops/SConscript
index 82f7a214c3c..a56fdcc8441 100644
--- a/src/mongo/db/ops/SConscript
+++ b/src/mongo/db/ops/SConscript
@@ -44,6 +44,7 @@ env.CppUnitTest(
     ],
     LIBDEPS=[
         '$BUILD_DIR/mongo/mutable_bson_test_utils',
+        '$BUILD_DIR/mongo/expressions',
         'update_common',
     ],
 )
diff --git a/src/mongo/db/ops/path_support.cpp b/src/mongo/db/ops/path_support.cpp
index d46ad1aa977..fa72a4aceae 100644
--- a/src/mongo/db/ops/path_support.cpp
+++ b/src/mongo/db/ops/path_support.cpp
@@ -38,6 +38,8 @@
 namespace mongo {
 namespace pathsupport {
 
+    using mongoutils::str::stream;
+
     namespace {
 
         bool isNumeric(const StringData& str, size_t* num) {
@@ -260,5 +262,199 @@ namespace pathsupport {
         return Status::OK();
     }
 
+    Status setElementAtPath(const FieldRef& path,
+                            const BSONElement& value,
+                            mutablebson::Document* doc) {
+
+        size_t deepestElemPathPart;
+        mutablebson::Element deepestElem(doc->end());
+
+        // Get the existing parents of this path
+        Status status = findLongestPrefix(path,
+                                          doc->root(),
+                                          &deepestElemPathPart,
+                                          &deepestElem);
+
+        // TODO: All this is pretty awkward, why not return the position immediately after the
+        // consumed path or use a signed sentinel?  Why is it a special case when we've consumed the
+        // whole path?
+
+        if (!status.isOK() && status.code() != ErrorCodes::NonExistentPath)
+            return status;
+
+        // Inc the path by one *unless* we matched nothing
+        if (status.code() != ErrorCodes::NonExistentPath) {
+            ++deepestElemPathPart;
+        }
+        else {
+            deepestElemPathPart = 0;
+            deepestElem = doc->root();
+        }
+
+        if (deepestElemPathPart == path.numParts()) {
+            // The full path exists already in the document, so just set a value
+            return deepestElem.setValueBSONElement(value);
+        }
+        else {
+            // Construct the rest of the path we need with empty documents and set the value
+            StringData leafFieldName = path.getPart(path.numParts() - 1);
+            mutablebson::Element leafElem = doc->makeElementWithNewFieldName(leafFieldName,
+                                                                             value);
+            dassert(leafElem.ok());
+            return createPathAt(path, deepestElemPathPart, deepestElem, leafElem);
+        }
+    }
+
+    const BSONElement& findParentEqualityElement(const EqualityMatches& equalities,
+                                                 const FieldRef& path,
+                                                 int* parentPathParts) {
+
+        // We may have an equality match to an object at a higher point in the pattern path, check
+        // all path prefixes for equality matches
+        // ex: path: 'a.b', query : { 'a' : { b : <value> } }
+        // ex: path: 'a.b.c', query : { 'a.b' : { c : <value> } }
+        for (int i = static_cast<int>(path.numParts()); i >= 0; --i) {
+
+            // "" element is *not* a parent of anyone but itself
+            if (i == 0 && path.numParts() != 0)
+                continue;
+
+            StringData subPathStr = path.dottedSubstring(0, i);
+            EqualityMatches::const_iterator seenIt = equalities.find(subPathStr);
+            if (seenIt == equalities.end())
+                continue;
+
+            *parentPathParts = i;
+            return seenIt->second->getData();
+        }
+
+        *parentPathParts = -1;
+        static const BSONElement eooElement;
+        return eooElement;
+    }
+
+    /**
+     * Helper function to check if the current equality match paths conflict with a new path.
+     */
+    static Status checkEqualityConflicts(const EqualityMatches& equalities, const FieldRef& path) {
+
+        int parentPathPart = -1;
+        const BSONElement& parentEl = findParentEqualityElement(equalities,
+                                                                path,
+                                                                &parentPathPart);
+
+        if (parentEl.eoo())
+            return Status::OK();
+
+        string errMsg = "cannot infer query fields to set, ";
+
+        StringData pathStr = path.dottedField();
+        StringData prefixStr = path.dottedSubstring(0, parentPathPart);
+        StringData suffixStr = path.dottedSubstring(parentPathPart, path.numParts());
+
+        if (suffixStr.size() != 0)
+            errMsg += stream() << "both paths '" << pathStr << "' and '" << prefixStr
+                               << "' are matched";
+        else
+            errMsg += stream() << "path '" << pathStr << "' is matched twice";
+
+        return Status(ErrorCodes::NotSingleValueField, errMsg);
+    }
+
+    /**
+     * Helper function to check if path conflicts are all prefixes.
+     */
+    static Status checkPathIsPrefixOf(const FieldRef& path, const FieldRefSet& conflictPaths) {
+
+        for (FieldRefSet::const_iterator it = conflictPaths.begin(); it != conflictPaths.end();
+            ++it) {
+
+            const FieldRef* conflictingPath = *it;
+            // Conflicts are always prefixes (or equal to) the path, or vice versa
+            if (path.numParts() > conflictingPath->numParts()) {
+
+                string errMsg = stream() << "field at '" << conflictingPath->dottedField()
+                                         << "' must be exactly specified, field at sub-path '"
+                                         << path.dottedField() << "'found";
+                return Status(ErrorCodes::NotExactValueField, errMsg);
+            }
+        }
+
+        return Status::OK();
+    }
+
+    static Status _extractFullEqualityMatches(const MatchExpression& root,
+                                              const FieldRefSet* fullPathsToExtract,
+                                              EqualityMatches* equalities) {
+
+        if (root.matchType() == MatchExpression::EQ) {
+
+            // Extract equality matches
+            const EqualityMatchExpression& eqChild =
+                static_cast<const EqualityMatchExpression&>(root);
+
+            FieldRef path(eqChild.path());
+
+            if (fullPathsToExtract) {
+
+                FieldRefSet conflictPaths;
+                fullPathsToExtract->findConflicts(&path, &conflictPaths);
+
+                // Ignore if this path is unrelated to the full paths
+                if (conflictPaths.empty())
+                    return Status::OK();
+
+                // Make sure we're a prefix of all the conflict paths
+                Status status = checkPathIsPrefixOf(path, conflictPaths);
+                if (!status.isOK())
+                    return status;
+            }
+
+            Status status = checkEqualityConflicts(*equalities, path);
+            if (!status.isOK())
+                return status;
+
+            equalities->insert(make_pair(eqChild.path(), &eqChild));
+        }
+        else if (root.matchType() == MatchExpression::AND) {
+
+            // Further explore $and matches
+            for (size_t i = 0; i < root.numChildren(); ++i) {
+                MatchExpression* child = root.getChild(i);
+                Status status = _extractFullEqualityMatches(*child, fullPathsToExtract, equalities);
+                if (!status.isOK())
+                    return status;
+            }
+        }
+
+        return Status::OK();
+    }
+
+    Status extractFullEqualityMatches(const MatchExpression& root,
+                                      const FieldRefSet& fullPathsToExtract,
+                                      EqualityMatches* equalities) {
+        return _extractFullEqualityMatches(root, &fullPathsToExtract, equalities);
+    }
+
+    Status extractEqualityMatches(const MatchExpression& root, EqualityMatches* equalities) {
+        return _extractFullEqualityMatches(root, NULL, equalities);
+    }
+
+    Status addEqualitiesToDoc(const EqualityMatches& equalities, mutablebson::Document* doc) {
+
+        for (EqualityMatches::const_iterator it = equalities.begin(); it != equalities.end();
+            ++it) {
+
+            FieldRef path(it->first);
+            const BSONElement& data = it->second->getData();
+
+            Status status = setElementAtPath(path, data, doc);
+            if (!status.isOK())
+                return status;
+        }
+
+        return Status::OK();
+    }
+
 } // namespace pathsupport
 } // namespace mongo
diff --git a/src/mongo/db/ops/path_support.h b/src/mongo/db/ops/path_support.h
index 2641b39f658..ce9d2bcf595 100644
--- a/src/mongo/db/ops/path_support.h
+++ b/src/mongo/db/ops/path_support.h
@@ -33,6 +33,9 @@
 #include "mongo/base/status.h"
 #include "mongo/bson/mutable/element.h"
 #include "mongo/db/field_ref.h"
+#include "mongo/db/field_ref_set.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
 #include "mongo/platform/cstdint.h"
 
 namespace mongo {
@@ -43,6 +46,9 @@ namespace mongo {
         // doesn't exist.
         static const size_t kMaxPaddingAllowed = 1500000;
 
+        // Convenience type to hold equality matches at particular paths from a MatchExpression
+        typedef map<StringData, const EqualityMatchExpression*> EqualityMatches;
+
         /**
          * Finds the longest portion of 'prefix' that exists in document rooted at 'root' and is
          * "viable." A viable path is one that, if fully created on a given doc, would not
@@ -93,6 +99,93 @@ namespace mongo {
                             mutablebson::Element elemFound,
                             mutablebson::Element newElem);
 
+        /**
+         * Uses the above methods to set the given value at the specified path in a mutable
+         * Document, creating parents of the path if necessary.
+         *
+         * Returns PathNotViable if the path cannot be created without modifying the type of another
+         * element, see above.
+         */
+        Status setElementAtPath(const FieldRef& path,
+                                const BSONElement& value,
+                                mutablebson::Document* doc);
+
+        /**
+         * Finds and returns-by-path all the equality matches in a particular MatchExpression.
+         *
+         * This method is meant to be used with the methods below, which allow efficient use of the
+         * equality matches without needing to serialize to a BSONObj.
+         *
+         * Returns NotSingleValueField if the match expression has equality operators for
+         * conflicting paths - equality paths conflict if they are the same or one path is a prefix
+         * of the other.
+         *
+         * Ex:
+         *   { a : 1, b : 1 } -> no conflict
+         *   { a : 1, a.b : 1 } -> conflict
+         *   { _id : { x : 1 }, _id.y : 1 } -> conflict
+         *   { a : 1, a : 1 } -> conflict
+         */
+        Status extractEqualityMatches(const MatchExpression& root, EqualityMatches* equalities);
+
+        /**
+         * Same as the above, but ignores all paths except for paths in a specified set.
+         * Equality matches with paths completely distinct from these paths are ignored.
+         *
+         * For a full equality match, the path of an equality found must not be a suffix of one of
+         * the specified path - otherwise it isn't clear how to construct a full value for a field
+         * at that path.
+         *
+         * Generally this is useful for shard keys and _ids which need unambiguous extraction from
+         * queries.
+         *
+         * Ex:
+         *   { a : 1 }, full path 'a' -> a $eq 1 extracted
+         *   { a : 1 }, full path 'a.b' -> a $eq 1 extracted
+         *   { 'a.b' : 1 }, full path 'a' -> NotExactValueField error
+         *                                   ('a.b' doesn't specify 'a' fully)
+         *   { 'a.b' : 1 }, full path 'a.b' -> 'a.b' $eq 1 extracted
+         *   { '_id' : 1 }, full path '_id' -> '_id' $eq 1 extracted
+         *   { '_id.x' : 1 }, full path '_id' -> NotExactValueFieldError
+         */
+        Status extractFullEqualityMatches(const MatchExpression& root,
+                                          const FieldRefSet& fullPathsToExtract,
+                                          EqualityMatches* equalities);
+
+        /**
+         * Returns the equality match which is at or a parent of the specified path string.  The
+         * path string must be a valid dotted path.
+         *
+         * If a parent equality is found, returns the BSONElement data from that equality (which
+         * includes the BSON value), the path of the parent element (prefixStr), and the remainder
+         * of the path (which may be empty).
+         *
+         * EOO() is returned if there were no equalities at any point along the path.
+         *
+         * Ex:
+         *   Given equality matches of:
+         *      'a.b' : 1, 'c' : 2
+         *   Path 'a' has no equality match parent (EOO)
+         *   Path 'c' has an eqmatch parent of 'c' : 2
+         *   Path 'c.d' has an eqmatch parent of 'c' : 2
+         *   Path 'a.b' has an eqmatch parent of 'a.b' : 1
+         *   Path 'a.b.c' has an eqmatch parent of 'a.b' : 1
+         *
+         */
+        const BSONElement& findParentEqualityElement(const EqualityMatches& equalities,
+                                                     const FieldRef& path,
+                                                     int* parentPathParts);
+
+        /**
+         * Adds the BSON values from equality matches into the given document at the equality match
+         * paths.
+         *
+         * Returns PathNotViable similar to setElementAtPath above.  If equality paths do not
+         * conflict, as is enforced by extractEqualityMatches, this function should return OK.
+         */
+        Status addEqualitiesToDoc(const EqualityMatches& equalities,
+                                  mutablebson::Document* doc);
+
     } // namespace pathsupport
 
 } // namespace mongo
diff --git a/src/mongo/db/ops/path_support_test.cpp b/src/mongo/db/ops/path_support_test.cpp
index 34113bc902b..686d4b46094 100644
--- a/src/mongo/db/ops/path_support_test.cpp
+++ b/src/mongo/db/ops/path_support_test.cpp
@@ -31,6 +31,7 @@
 #include <string>
 
 #include "mongo/base/error_codes.h"
+#include "mongo/base/owned_pointer_vector.h"
 #include "mongo/base/status.h"
 #include "mongo/base/string_data.h"
 #include "mongo/bson/mutable/algorithm.h"
@@ -39,27 +40,18 @@
 #include "mongo/db/field_ref.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/json.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+#include "mongo/db/matcher/expression_parser.h"
 #include "mongo/platform/cstdint.h"
 #include "mongo/unittest/unittest.h"
 #include "mongo/util/mongoutils/str.h"
 
 namespace {
 
-    using mongo::BSONObj;
-    using mongo::ErrorCodes;
-    using mongo::FieldRef;
-    using mongo::fromjson;
-    using mongo::jstNULL;
-    using mongo::NumberInt;
-    using mongo::Object;
-    using mongo::pathsupport::findLongestPrefix;
-    using mongo::pathsupport::createPathAt;
-    using mongo::Status;
-    using mongo::StringData;
-    using mongo::mutablebson::countChildren;
-    using mongo::mutablebson::getNthChild;
-    using mongo::mutablebson::Document;
-    using mongo::mutablebson::Element;
+    using namespace mongo;
+    using namespace mutablebson;
+    using namespace pathsupport;
     using mongoutils::str::stream;
     using std::string;
 
@@ -459,4 +451,431 @@ namespace {
         ASSERT_EQUALS(elemFound.compareWithElement(root()["b"]), 0);
     }
 
+    //
+    // Tests of equality extraction from MatchExpressions
+    // NONGOAL: Testing query/match expression parsing and optimization
+    //
+
+    static MatchExpression* makeExpr(const BSONObj& exprBSON) {
+        static const WhereCallbackNoop callbackNoop;
+        return MatchExpressionParser::parse(exprBSON, callbackNoop).getValue();
+    }
+
+    static void assertContains(const EqualityMatches& equalities, const BSONObj& wrapped) {
+
+        BSONElement value = wrapped.firstElement();
+        StringData path = value.fieldNameStringData();
+
+        EqualityMatches::const_iterator it = equalities.find(path);
+        if (it == equalities.end()) {
+            FAIL(stream() << "Equality matches did not contain path \"" << path << "\"");
+        }
+        if (!it->second->getData().valuesEqual(value)) {
+            FAIL(stream() << "Equality match at path \"" << path << "\" contains value "
+                          << it->second->getData() << ", not value " << value);
+        }
+    }
+
+    static void assertContains(const EqualityMatches& equalities,
+                               const StringData& path,
+                               int value) {
+        assertContains(equalities, BSON(path << value));
+    }
+
+    // NOTE: For tests below, BSONObj expr must exist for lifetime of MatchExpression
+
+    TEST(ExtractEqualities, Basic) {
+        BSONObj exprBSON = fromjson("{a:1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 1u);
+        assertContains(equalities, "a", 1);
+    }
+
+    TEST(ExtractEqualities, Multiple) {
+        BSONObj exprBSON = fromjson("{a:1, b:2}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 2u);
+        assertContains(equalities, "a", 1);
+        assertContains(equalities, "b", 2);
+    }
+
+    TEST(ExtractEqualities, EqOperator) {
+        BSONObj exprBSON = fromjson("{a:{$eq:1}}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 1u);
+        assertContains(equalities, "a", 1);
+    }
+
+    TEST(ExtractEqualities, AndOperator) {
+        BSONObj exprBSON = fromjson("{$and:[{a:{$eq:1}},{b:2}]}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 2u);
+        assertContains(equalities, "a", 1);
+        assertContains(equalities, "b", 2);
+    }
+
+    TEST(ExtractEqualities, NestedAndOperator) {
+        BSONObj exprBSON = fromjson("{$and:[{$and:[{a:{$eq:1}},{b:2}]},{c:3}]}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 3u);
+        assertContains(equalities, "a", 1);
+        assertContains(equalities, "b", 2);
+        assertContains(equalities, "c", 3);
+    }
+
+    TEST(ExtractEqualities, NestedPaths) {
+        BSONObj exprBSON = fromjson("{'a.a':1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 1u);
+        assertContains(equalities, "a.a", 1);
+    }
+
+    TEST(ExtractEqualities, SiblingPaths) {
+        BSONObj exprBSON = fromjson("{'a.a':1,'a.b':{$eq:2}}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 2u);
+        assertContains(equalities, "a.a", 1);
+        assertContains(equalities, "a.b", 2);
+    }
+
+    TEST(ExtractEqualities, NestedAndNestedPaths) {
+        BSONObj exprBSON = fromjson("{$and:[{$and:[{'a.a':{$eq:1}},{'a.b':2}]},{'c.c.c':3}]}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 3u);
+        assertContains(equalities, "a.a", 1);
+        assertContains(equalities, "a.b", 2);
+        assertContains(equalities, "c.c.c", 3);
+    }
+
+    TEST(ExtractEqualities, IdOnly) {
+        BSONObj exprBSON = fromjson("{_id:1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 1u);
+        assertContains(equalities, "_id", 1);
+    }
+
+    /**
+     * Helper class to allow easy construction of immutable paths
+     */
+    class ImmutablePaths {
+    public:
+        ImmutablePaths() {}
+
+        void addPath(const string& path) {
+            _ownedPaths.mutableVector().push_back(new FieldRef(path));
+            FieldRef const* conflictPath = NULL;
+            ASSERT(_immutablePathSet.insert(_ownedPaths.vector().back(), &conflictPath));
+        }
+
+        const FieldRefSet& getPathSet() {
+            return _immutablePathSet;
+        }
+
+    private:
+
+        FieldRefSet _immutablePathSet;
+        OwnedPointerVector<FieldRef> _ownedPaths;
+    };
+
+    TEST(ExtractEqualities, IdOnlyMulti) {
+        BSONObj exprBSON = fromjson("{_id:{$eq:1},a:1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        ImmutablePaths immutablePaths;
+        immutablePaths.addPath("_id");
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractFullEqualityMatches(*expr, immutablePaths.getPathSet(), &equalities));
+        ASSERT_EQUALS(equalities.size(), 1u);
+        assertContains(equalities, "_id", 1);
+    }
+
+    TEST(ExtractEqualities, IdOnlyIgnoreConflict) {
+        BSONObj exprBSON = fromjson("{_id:1,a:1,'a.b':1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        ImmutablePaths immutablePaths;
+        immutablePaths.addPath("_id");
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractFullEqualityMatches(*expr, immutablePaths.getPathSet(), &equalities));
+        ASSERT_EQUALS(equalities.size(), 1u);
+        assertContains(equalities, "_id", 1);
+    }
+
+    TEST(ExtractEqualities, IdOnlyNested) {
+        BSONObj exprBSON = fromjson("{'_id.a':1,'_id.b':{$eq:2},c:3}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        ImmutablePaths immutablePaths;
+        immutablePaths.addPath("_id");
+
+        EqualityMatches equalities;
+        Status status = extractFullEqualityMatches(*expr, immutablePaths.getPathSet(), &equalities);
+        ASSERT_EQUALS(status.code(), ErrorCodes::NotExactValueField);
+    }
+
+    TEST(ExtractEqualities, IdAndOtherImmutable) {
+        BSONObj exprBSON = fromjson("{_id:1,a:1,b:2}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        ImmutablePaths immutablePaths;
+        immutablePaths.addPath("_id");
+        immutablePaths.addPath("a");
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractFullEqualityMatches(*expr, immutablePaths.getPathSet(), &equalities));
+        ASSERT_EQUALS(equalities.size(), 2u);
+        assertContains(equalities, "_id", 1);
+        assertContains(equalities, "a", 1);
+    }
+
+    TEST(ExtractEqualities, IdAndNestedImmutable) {
+        BSONObj exprBSON = fromjson("{_id:1,a:1,'c.d':3}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        ImmutablePaths immutablePaths;
+        immutablePaths.addPath("_id");
+        immutablePaths.addPath("a.b");
+        immutablePaths.addPath("c.d");
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractFullEqualityMatches(*expr, immutablePaths.getPathSet(), &equalities));
+        ASSERT_EQUALS(equalities.size(), 3u);
+        assertContains(equalities, "_id", 1);
+        assertContains(equalities, "a", 1);
+        assertContains(equalities, "c.d", 3);
+    }
+
+    TEST(ExtractEqualities, NonFullImmutable) {
+        BSONObj exprBSON = fromjson("{'a.b':1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        ImmutablePaths immutablePaths;
+        immutablePaths.addPath("a");
+
+        EqualityMatches equalities;
+        Status status = extractFullEqualityMatches(*expr, immutablePaths.getPathSet(), &equalities);
+        ASSERT_EQUALS(status.code(), ErrorCodes::NotExactValueField);
+    }
+
+    TEST(ExtractEqualities, Empty) {
+        BSONObj exprBSON = fromjson("{'':0}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 1u);
+        assertContains(equalities, "", 0);
+    }
+
+    TEST(ExtractEqualities, EmptyMulti) {
+        BSONObj exprBSON = fromjson("{'':0,a:{$eq:1}}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+        ASSERT_EQUALS(equalities.size(), 2u);
+        assertContains(equalities, "", 0);
+        assertContains(equalities, "a", 1);
+    }
+
+    TEST(ExtractEqualities, EqConflict) {
+        BSONObj exprBSON = fromjson("{a:1,a:1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_EQUALS(extractEqualityMatches(*expr, &equalities).code(),
+                      ErrorCodes::NotSingleValueField);
+    }
+
+    TEST(ExtractEqualities, PrefixConflict) {
+        BSONObj exprBSON = fromjson("{a:1,'a.b':{$eq:1}}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_EQUALS(extractEqualityMatches(*expr, &equalities).code(),
+                      ErrorCodes::NotSingleValueField);
+    }
+
+    TEST(ExtractEqualities, AndPrefixConflict) {
+        BSONObj exprBSON = fromjson("{$and:[{a:1},{'a.b':{$eq:1}}]}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_EQUALS(extractEqualityMatches(*expr, &equalities).code(),
+                      ErrorCodes::NotSingleValueField);
+    }
+
+    TEST(ExtractEqualities, EmptyConflict) {
+        BSONObj exprBSON = fromjson("{'':0,'':{$eq:0}}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+
+        EqualityMatches equalities;
+        ASSERT_EQUALS(extractEqualityMatches(*expr, &equalities).code(),
+                      ErrorCodes::NotSingleValueField);
+    }
+
+    //
+    // Tests for finding parent equality from equalities found in expression
+    // NONGOALS: Testing complex equality match extraction - tested above
+    //
+
+    static void assertParent(const EqualityMatches& equalities,
+                             const StringData& pathStr,
+                             const BSONObj& wrapped) {
+
+        FieldRef path(pathStr);
+        BSONElement value = wrapped.firstElement();
+        StringData parentPath = value.fieldNameStringData();
+
+        int parentPathPart;
+        BSONElement parentEl = findParentEqualityElement(equalities, path, &parentPathPart);
+
+        if (parentEl.eoo()) {
+            FAIL(stream() << "Equality matches did not contain parent for \"" << pathStr
+                          << "\"");
+        }
+
+        StringData foundParentPath = path.dottedSubstring(0, parentPathPart);
+        if (foundParentPath != parentPath) {
+            FAIL(stream() << "Equality match parent at path \"" << foundParentPath
+                          << "\" does not match \"" << parentPath << "\"");
+        }
+
+        if (!parentEl.valuesEqual(value)) {
+            FAIL(stream() << "Equality match parent for \"" << pathStr << "\" at path \""
+                          << parentPath << "\" contains value " << parentEl << ", not value "
+                          << value);
+        }
+    }
+
+    static void assertParent(const EqualityMatches& equalities,
+                             const StringData& path,
+                             const StringData& parentPath,
+                             int value) {
+        assertParent(equalities, path, BSON(parentPath << value));
+    }
+
+    static void assertNoParent(const EqualityMatches& equalities, const StringData& pathStr) {
+
+        FieldRef path(pathStr);
+
+        int parentPathPart;
+        BSONElement parentEl = findParentEqualityElement(equalities, path, &parentPathPart);
+
+        if (!parentEl.eoo()) {
+            StringData foundParentPath = path.dottedSubstring(0, parentPathPart);
+            FAIL(stream() << "Equality matches contained parent for \"" << pathStr << "\" at \""
+                          << foundParentPath << "\"");
+        }
+    }
+
+
+    TEST(FindParentEquality, Basic) {
+
+        BSONObj exprBSON = fromjson("{a:1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+
+        assertNoParent(equalities, "");
+        assertParent(equalities, "a", "a", 1);
+        assertParent(equalities, "a.b", "a", 1);
+    }
+
+    TEST(FindParentEquality, Multi) {
+
+        BSONObj exprBSON = fromjson("{a:1,b:2}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+
+        assertNoParent(equalities, "");
+        assertParent(equalities, "a", "a", 1);
+        assertParent(equalities, "a.b", "a", 1);
+        assertParent(equalities, "b", "b", 2);
+        assertParent(equalities, "b.b", "b", 2);
+    }
+
+    TEST(FindParentEquality, Nested) {
+
+        BSONObj exprBSON = fromjson("{'a.a':1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+
+        assertNoParent(equalities, "");
+        assertNoParent(equalities, "a");
+        assertParent(equalities, "a.a", "a.a", 1);
+        assertParent(equalities, "a.a.b", "a.a", 1);
+    }
+
+    TEST(FindParentEquality, NestedMulti) {
+
+        BSONObj exprBSON = fromjson("{'a.a':1,'a.b':2,'c.c':3}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+
+        assertNoParent(equalities, "");
+        assertNoParent(equalities, "a");
+        assertNoParent(equalities, "c");
+        assertParent(equalities, "a.a", "a.a", 1);
+        assertParent(equalities, "a.a.a", "a.a", 1);
+        assertParent(equalities, "a.b", "a.b", 2);
+        assertParent(equalities, "a.b.b", "a.b", 2);
+        assertParent(equalities, "c.c", "c.c", 3);
+        assertParent(equalities, "c.c.c", "c.c", 3);
+    }
+
+    TEST(FindParentEquality, Empty) {
+
+        BSONObj exprBSON = fromjson("{'':0}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+
+        assertParent(equalities, "", "", 0);
+    }
+
+    TEST(FindParentEquality, EmptyMulti) {
+
+        BSONObj exprBSON = fromjson("{'':0,a:1}");
+        auto_ptr<MatchExpression> expr(makeExpr(exprBSON));
+        EqualityMatches equalities;
+        ASSERT_OK(extractEqualityMatches(*expr, &equalities));
+
+        assertParent(equalities, "", "", 0);
+        assertParent(equalities, "a", "a", 1);
+        assertParent(equalities, "a.b", "a", 1);
+    }
+
 } // unnamed namespace
diff --git a/src/mongo/db/ops/update_driver.cpp b/src/mongo/db/ops/update_driver.cpp
index 672aad85d73..df8de62873e 100644
--- a/src/mongo/db/ops/update_driver.cpp
+++ b/src/mongo/db/ops/update_driver.cpp
@@ -46,6 +46,8 @@ namespace mongo {
     namespace str = mongoutils::str;
     namespace mb = mongo::mutablebson;
 
+    using pathsupport::EqualityMatches;
+
     UpdateDriver::UpdateDriver(const Options& opts)
         : _replacementMode(false)
         , _indexedFields(NULL)
@@ -164,6 +166,7 @@ namespace mongo {
     }
 
     Status UpdateDriver::populateDocumentWithQueryFields(const BSONObj& query,
+                                                         const vector<FieldRef*>* immutablePaths,
                                                          mutablebson::Document& doc) const {
         CanonicalQuery* rawCG;
         // We canonicalize the query to collapse $and/$or, and the first arg (ns) is not needed
@@ -173,109 +176,43 @@ namespace mongo {
         if (!s.isOK())
             return s;
         scoped_ptr<CanonicalQuery> cq(rawCG);
-        return populateDocumentWithQueryFields(rawCG, doc);
+        return populateDocumentWithQueryFields(rawCG, immutablePaths, doc);
     }
 
     Status UpdateDriver::populateDocumentWithQueryFields(const CanonicalQuery* query,
+                                                         const vector<FieldRef*>* immutablePathsPtr,
                                                          mutablebson::Document& doc) const {
-
-        MatchExpression* root = query->root();
-
-        MatchExpression::MatchType rootType = root->matchType();
-
-        // These copies are needed until we apply the modifiers at the end.
-        std::vector<BSONObj> copies;
-
-        // We only care about equality and "and"ed equality fields, everything else is ignored
-        if (rootType != MatchExpression::EQ && rootType != MatchExpression::AND)
-            return Status::OK();
+        EqualityMatches equalities;
+        Status status = Status::OK();
 
         if (isDocReplacement()) {
-            BSONElement idElem = query->getQueryObj().getField("_id");
 
-            // Replacement mods need the _id field copied explicitly.
-            if (idElem.ok()) {
-                mb::Element elem = doc.makeElement(idElem);
-                return doc.root().pushFront(elem);
-            }
+            FieldRefSet pathsToExtract;
 
-            return Status::OK();
-        }
+            // TODO: Refactor update logic, make _id just another immutable field
+            static const FieldRef idPath("_id");
+            static const vector<FieldRef*> emptyImmutablePaths;
+            const vector<FieldRef*>& immutablePaths =
+                immutablePathsPtr ? *immutablePathsPtr : emptyImmutablePaths;
 
-        // Create a new UpdateDriver to create the base doc from the query
-        Options opts;
-        opts.logOp = false;
-        opts.modOptions = modOptions();
-
-        UpdateDriver insertDriver(opts);
-        insertDriver.setContext(ModifierInterface::ExecInfo::INSERT_CONTEXT);
-
-        // If we are a single equality match query
-        if (root->matchType() == MatchExpression::EQ) {
-            EqualityMatchExpression* eqMatch =
-                    static_cast<EqualityMatchExpression*>(root);
-
-            const BSONElement matchData = eqMatch->getData();
-            BSONElement childElem = matchData;
-
-            // Make copy to new path if not the same field name (for cases like $all)
-            if (!root->path().empty() && matchData.fieldNameStringData() != root->path()) {
-                BSONObjBuilder copyBuilder;
-                copyBuilder.appendAs(eqMatch->getData(), root->path());
-                const BSONObj copy = copyBuilder.obj();
-                copies.push_back(copy);
-                childElem = copy[root->path()];
-            }
-
-            // Add this element as a $set modifier
-            Status s = insertDriver.addAndParse(modifiertable::MOD_SET,
-                                                childElem);
-            if (!s.isOK())
-                return s;
+            pathsToExtract.fillFrom(immutablePaths);
+            pathsToExtract.insert(&idPath);
 
+            // Extract only immutable fields from replacement-style
+            status = pathsupport::extractFullEqualityMatches(*query->root(),
+                                                             pathsToExtract,
+                                                             &equalities);
         }
         else {
-
-            // parse query $set mods, including only equality stuff
-            for (size_t i = 0; i < root->numChildren(); ++i) {
-                MatchExpression* child = root->getChild(i);
-                if (child->matchType() == MatchExpression::EQ) {
-                    EqualityMatchExpression* eqMatch =
-                            static_cast<EqualityMatchExpression*>(child);
-
-                    const BSONElement matchData = eqMatch->getData();
-                    BSONElement childElem = matchData;
-
-                    // Make copy to new path if not the same field name (for cases like $all)
-                    if (!child->path().empty() &&
-                            matchData.fieldNameStringData() != child->path()) {
-                        BSONObjBuilder copyBuilder;
-                        copyBuilder.appendAs(eqMatch->getData(), child->path());
-                        const BSONObj copy = copyBuilder.obj();
-                        copies.push_back(copy);
-                        childElem = copy[child->path()];
-                    }
-
-                    // Add this element as a $set modifier
-                    Status s = insertDriver.addAndParse(modifiertable::MOD_SET,
-                                                        childElem);
-                    if (!s.isOK())
-                        return s;
-                }
-            }
+            // Extract all fields from op-style
+            status = pathsupport::extractEqualityMatches(*query->root(), &equalities);
         }
 
-        // update the document with base field
-        Status s = insertDriver.update(StringData(), &doc);
-        copies.clear();
-        if (!s.isOK()) {
-            return Status(ErrorCodes::UnsupportedFormat,
-                          str::stream() << "Cannot create base during"
-                                           " insert of update. Caused by :"
-                                        << s.toString());
-        }
+        if (!status.isOK())
+            return status;
 
-        return Status::OK();
+        status = pathsupport::addEqualitiesToDoc(equalities, &doc);
+        return status;
     }
 
     Status UpdateDriver::update(const StringData& matchedField,
diff --git a/src/mongo/db/ops/update_driver.h b/src/mongo/db/ops/update_driver.h
index 0b9fd951cb8..4ac88872e04 100644
--- a/src/mongo/db/ops/update_driver.h
+++ b/src/mongo/db/ops/update_driver.h
@@ -69,9 +69,11 @@ namespace mongo {
          * conflicts along the way then those errors will be returned.
          */
         Status populateDocumentWithQueryFields(const BSONObj& query,
+                                               const vector<FieldRef*>* immutablePaths,
                                                mutablebson::Document& doc) const;
 
         Status populateDocumentWithQueryFields(const CanonicalQuery* query,
+                                               const vector<FieldRef*>* immutablePaths,
                                                mutablebson::Document& doc) const;
 
         /**
diff --git a/src/mongo/db/ops/update_driver_test.cpp b/src/mongo/db/ops/update_driver_test.cpp
index 27f26d9dd3a..22140b5389e 100644
--- a/src/mongo/db/ops/update_driver_test.cpp
+++ b/src/mongo/db/ops/update_driver_test.cpp
@@ -28,21 +28,32 @@
 
 #include "mongo/db/ops/update_driver.h"
 
+#include <boost/scoped_ptr.hpp>
+
+#include <map>
+
+#include "mongo/base/owned_pointer_vector.h"
 #include "mongo/base/string_data.h"
 #include "mongo/bson/mutable/document.h"
 #include "mongo/bson/mutable/mutable_bson_test_utils.h"
-#include "mongo/db/update_index_data.h"
+#include "mongo/db/field_ref.h"
 #include "mongo/db/json.h"
+#include "mongo/db/update_index_data.h"
 #include "mongo/unittest/unittest.h"
 
 namespace {
 
     using mongo::BSONObj;
+    using mongo::BSONElement;
+    using mongo::BSONObjIterator;
+    using mongo::FieldRef;
     using mongo::fromjson;
+    using mongo::OwnedPointerVector;
     using mongo::UpdateIndexData;
     using mongo::mutablebson::Document;
     using mongo::StringData;
     using mongo::UpdateDriver;
+    using mongoutils::str::stream;
 
     TEST(Parse, Normal) {
         UpdateDriver::Options opts;
@@ -115,59 +126,279 @@ namespace {
         ASSERT_FALSE(driver.isDocReplacement());
     }
 
+    //
+    // Tests of creating a base for an upsert from a query document
+    // $or, $and, $all get special handling, as does the _id field
+    //
+    // NONGOAL: Testing all query parsing and nesting combinations
+    //
 
-    // Test the upsert case where we copy the query parts into the new doc
-    TEST(CreateFromQuery, Basic) {
-        UpdateDriver::Options opts;
-        UpdateDriver driver(opts);
-        Document doc;
+    class CreateFromQueryFixture : public mongo::unittest::Test {
+    public:
+
+        CreateFromQueryFixture()
+            : _driverOps(new UpdateDriver(UpdateDriver::Options())),
+              _driverRepl(new UpdateDriver(UpdateDriver::Options())) {
+            _driverOps->parse(fromjson("{$set:{'_':1}}"));
+            _driverRepl->parse(fromjson("{}"));
+        }
+
+        Document& doc() {
+            return _doc;
+        }
+
+        UpdateDriver& driverOps() {
+            return *_driverOps;
+        }
+
+        UpdateDriver& driverRepl() {
+            return *_driverRepl;
+        }
 
-        BSONObj query = fromjson("{a:1, b:1}");
-        ASSERT_OK(driver.populateDocumentWithQueryFields(query, doc));
-        ASSERT_EQUALS(query, doc);
+    private:
+        boost::scoped_ptr<UpdateDriver> _driverOps;
+        boost::scoped_ptr<UpdateDriver> _driverRepl;
+        Document _doc;
+    };
+
+    // Make name nicer to report
+    typedef CreateFromQueryFixture CreateFromQuery;
+
+    static void assertSameFields(const BSONObj& docA, const BSONObj& docB);
+
+    /**
+     * Recursively asserts that two BSONElements contain the same data or sub-elements,
+     * ignoring element order.
+     */
+    static void assertSameElements(const BSONElement& elA, const BSONElement& elB) {
+        if (elA.type() != elB.type() || (!elA.isABSONObj() && !elA.valuesEqual(elB))) {
+            FAIL(stream() << "element " << elA << " not equal to " << elB);
+        }
+        else if (elA.type() == mongo::Array) {
+            std::vector<BSONElement> elsA = elA.Array();
+            std::vector<BSONElement> elsB = elB.Array();
+            if (elsA.size() != elsB.size())
+                FAIL(stream() << "element " << elA << " not equal to " << elB);
+
+            std::vector<BSONElement>::iterator arrItA = elsA.begin();
+            std::vector<BSONElement>::iterator arrItB = elsB.begin();
+            for (; arrItA != elsA.end(); ++arrItA, ++arrItB) {
+                assertSameElements(*arrItA, *arrItB);
+            }
+        }
+        else if (elA.type() == mongo::Object) {
+            assertSameFields(elA.Obj(), elB.Obj());
+        }
     }
 
-    TEST(CreateFromQuery, BasicWithId) {
-        UpdateDriver::Options opts;
-        UpdateDriver driver(opts);
-        Document doc;
+    /**
+     * Recursively asserts that two BSONObjects contain the same elements,
+     * ignoring element order.
+     */
+    static void assertSameFields(const BSONObj& docA, const BSONObj& docB) {
+
+        if (docA.nFields() != docB.nFields())
+            FAIL(stream() << "document " << docA << " has different fields than " << docB);
+
+        std::map<StringData, BSONElement> docAMap;
+        BSONObjIterator itA(docA);
+        while (itA.more()) {
+            BSONElement elA = itA.next();
+            docAMap.insert(std::make_pair(elA.fieldNameStringData(), elA));
+        }
+
+        BSONObjIterator itB(docB);
+        while (itB.more()) {
+            BSONElement elB = itB.next();
 
-        BSONObj query = fromjson("{_id:1, a:1, b:1}");
-        ASSERT_OK(driver.populateDocumentWithQueryFields(query, doc));
-        ASSERT_EQUALS(query, doc);
+            std::map<StringData, BSONElement>::iterator seenIt = docAMap.find(elB
+                .fieldNameStringData());
+            if (seenIt == docAMap.end())
+                FAIL(stream() << "element " << elB << " not found in " << docA);
+
+            BSONElement elA = seenIt->second;
+            assertSameElements(elA, elB);
+        }
     }
 
-    TEST(CreateFromQuery, NestedSharedRoot) {
-        UpdateDriver::Options opts;
-        UpdateDriver driver(opts);
-        Document doc;
+    TEST_F(CreateFromQuery, BasicOp) {
+        BSONObj query = fromjson("{a:1,b:2}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(query, doc().getObject());
+    }
 
-        ASSERT_OK(driver.populateDocumentWithQueryFields(fromjson("{'a.c':1, 'a.b':1}"), doc));
+    TEST_F(CreateFromQuery, BasicOpEq) {
+        BSONObj query = fromjson("{a:{$eq:1}}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{a:1}"), doc().getObject());
     }
 
-    TEST(CreateFromQuery, AllArrayDoesntHaveOrdinalName) {
-        UpdateDriver::Options opts;
-        UpdateDriver driver(opts);
-        Document doc;
+    TEST_F(CreateFromQuery, BasicOpWithId) {
+        BSONObj query = fromjson("{_id:1,a:1,b:2}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(query, doc().getObject());
+    }
 
-        ASSERT_OK(driver.populateDocumentWithQueryFields(fromjson("{a:{$all:[1]}}"), doc));
-        ASSERT_EQUALS(fromjson("{a:1}"), doc);
+    TEST_F(CreateFromQuery, BasicRepl) {
+        BSONObj query = fromjson("{a:1,b:2}");
+        ASSERT_OK(driverRepl().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{}"), doc().getObject());
     }
 
-    // Failures
-    TEST(CreateFromQuery, DupFieldsFail) {
-        UpdateDriver::Options opts;
-        UpdateDriver driver(opts);
-        Document doc;
+    TEST_F(CreateFromQuery, BasicReplWithId) {
+        BSONObj query = fromjson("{_id:1,a:1,b:2}");
+        ASSERT_OK(driverRepl().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{_id:1}"), doc().getObject());
+    }
 
-        ASSERT_NOT_OK(driver.populateDocumentWithQueryFields(fromjson("{a:1, 'a.b':1}"), doc));
+    TEST_F(CreateFromQuery, BasicReplWithIdEq) {
+        BSONObj query = fromjson("{_id:{$eq:1},a:1,b:2}");
+        ASSERT_OK(driverRepl().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{_id:1}"), doc().getObject());
     }
 
-    TEST(CreateFromQuery, AllArrayMultipleVals) {
-        UpdateDriver::Options opts;
-        UpdateDriver driver(opts);
-        Document doc;
+    TEST_F(CreateFromQuery, NoRootIdOp) {
+        BSONObj query = fromjson("{'_id.a':1,'_id.b':2}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{_id:{a:1,b:2}}"), doc().getObject());
+    }
 
-        ASSERT_NOT_OK(driver.populateDocumentWithQueryFields(fromjson("{a:{$all:[1, 2]}}"), doc));
+    TEST_F(CreateFromQuery, NoRootIdRepl) {
+        BSONObj query = fromjson("{'_id.a':1,'_id.b':2}");
+        ASSERT_NOT_OK(driverRepl().populateDocumentWithQueryFields(query, NULL, doc()));
     }
+
+    TEST_F(CreateFromQuery, NestedSharedRootOp) {
+        BSONObj query = fromjson("{'a.c':1,'a.b':{$eq:2}}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{a:{c:1,b:2}}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, OrQueryOp) {
+        BSONObj query = fromjson("{$or:[{a:1}]}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{a:1}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, OrQueryIdRepl) {
+        BSONObj query = fromjson("{$or:[{_id:1}]}");
+        ASSERT_OK(driverRepl().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{_id:1}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, OrQueryNoExtractOps) {
+        BSONObj query = fromjson("{$or:[{a:1}, {b:2}]}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(BSONObj(), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, OrQueryNoExtractIdRepl) {
+        BSONObj query = fromjson("{$or:[{_id:1}, {_id:2}]}");
+        ASSERT_OK(driverRepl().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(BSONObj(), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, AndQueryOp) {
+        BSONObj query = fromjson("{$and:[{'a.c':1},{'a.b':{$eq:2}}]}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{a:{c:1,b:2}}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, AndQueryIdRepl) {
+        BSONObj query = fromjson("{$and:[{_id:1},{a:{$eq:2}}]}");
+        ASSERT_OK(driverRepl().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{_id:1}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, AllArrayOp) {
+        BSONObj query = fromjson("{a:{$all:[1]}}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{a:1}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, AllArrayIdRepl) {
+        BSONObj query = fromjson("{_id:{$all:[1]}, b:2}");
+        ASSERT_OK(driverRepl().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(fromjson("{_id:1}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, ConflictFieldsFailOp) {
+        BSONObj query = fromjson("{a:1,'a.b':1}");
+        ASSERT_NOT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+    }
+
+    TEST_F(CreateFromQuery, ConflictFieldsFailSameValueOp) {
+        BSONObj query = fromjson("{a:{b:1},'a.b':1}");
+        ASSERT_NOT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+    }
+
+    TEST_F(CreateFromQuery, ConflictWithIdRepl) {
+        BSONObj query = fromjson("{_id:1,'_id.a':1}");
+        ASSERT_NOT_OK(driverRepl().populateDocumentWithQueryFields(query, NULL, doc()));
+    }
+
+    TEST_F(CreateFromQuery, ConflictAndQueryOp) {
+        BSONObj query = fromjson("{$and:[{a:{b:1}},{'a.b':{$eq:1}}]}");
+        ASSERT_NOT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+    }
+
+    TEST_F(CreateFromQuery, ConflictAllMultipleValsOp) {
+        BSONObj query = fromjson("{a:{$all:[1, 2]}}");
+        ASSERT_NOT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+    }
+
+    TEST_F(CreateFromQuery, NoConflictOrQueryOp) {
+        BSONObj query = fromjson("{$or:[{a:{b:1}},{'a.b':{$eq:1}}]}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(BSONObj(), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, ImmutableFieldsOp) {
+        BSONObj query = fromjson("{$or:[{a:{b:1}},{'a.b':{$eq:1}}]}");
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query, NULL, doc()));
+        assertSameFields(BSONObj(), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, ShardKeyRepl) {
+        BSONObj query = fromjson("{a:{$eq:1}}, b:2}");
+        OwnedPointerVector<FieldRef> immutablePaths;
+        immutablePaths.push_back(new FieldRef("a"));
+        ASSERT_OK(driverRepl().populateDocumentWithQueryFields(query,
+                                                               &immutablePaths.vector(),
+                                                               doc()));
+        assertSameFields(fromjson("{a:1}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, NestedShardKeyRepl) {
+        BSONObj query = fromjson("{a:{$eq:1},'b.c':2},d:2}");
+        OwnedPointerVector<FieldRef> immutablePaths;
+        immutablePaths.push_back(new FieldRef("a"));
+        immutablePaths.push_back(new FieldRef("b.c"));
+        ASSERT_OK(driverRepl().populateDocumentWithQueryFields(query,
+                                                               &immutablePaths.vector(),
+                                                               doc()));
+        assertSameFields(fromjson("{a:1,b:{c:2}}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, NestedShardKeyOp) {
+        BSONObj query = fromjson("{a:{$eq:1},'b.c':2,d:{$all:[3]}},e:2}");
+        OwnedPointerVector<FieldRef> immutablePaths;
+        immutablePaths.push_back(new FieldRef("a"));
+        immutablePaths.push_back(new FieldRef("b.c"));
+        ASSERT_OK(driverOps().populateDocumentWithQueryFields(query,
+                                                              &immutablePaths.vector(),
+                                                              doc()));
+        assertSameFields(fromjson("{a:1,b:{c:2},d:3}"), doc().getObject());
+    }
+
+    TEST_F(CreateFromQuery, NotFullShardKeyRepl) {
+        BSONObj query = fromjson("{a:{$eq:1}, 'b.c':2}, d:2}");
+        OwnedPointerVector<FieldRef> immutablePaths;
+        immutablePaths.push_back(new FieldRef("a"));
+        immutablePaths.push_back(new FieldRef("b"));
+        ASSERT_NOT_OK(driverRepl().populateDocumentWithQueryFields(query,
+                                                                   &immutablePaths.vector(),
+                                                                   doc()));
+    }
+
 } // unnamed namespace