SERVER-10026 sort queries now go through new system

5 files changed, 263 insertions, 176 deletions

diff --git a/src/mongo/db/query/new_find.cpp b/src/mongo/db/query/new_find.cpp
index e38a3ef0cac..a5a81bbd12e 100644
--- a/src/mongo/db/query/new_find.cpp
+++ b/src/mongo/db/query/new_find.cpp
@@ -126,16 +126,6 @@ namespace mongo {
 
         // Things we know we fail at:
 
-        // Sort.
-        if (!pq.getSort().isEmpty()) {
-            // We can deal with this 'cuz it means do a collscan.
-            BSONElement natural = pq.getSort().getFieldDotted("$natural");
-            if (natural.eoo()) {
-                QLOG() << "rejecting query w/sort: " << pq.getSort().toString() << endl;
-                return false;
-            }
-        }
-
         // Projections.
         if (!pq.getProj().isEmpty()) {
             QLOG() << "rejecting query w/proj\n";
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 82e24e92bc7..2a8f26487ec 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -106,11 +106,7 @@ namespace mongo {
             ixtype = elt.String();
         }
 
-        // we know elt.fieldname() == node->path()
-
-        // XXX: Our predicate may be normal and it may be over a geo index (compounding).  Detect
-        // this at some point.
-
+        // We know elt.fieldname() == node->path().
         MatchExpression::MatchType exprtype = node->matchType();
 
         // TODO: use indexnames
@@ -332,59 +328,60 @@ namespace mongo {
     void QueryPlanner::mergeWithLeafNode(MatchExpression* expr, const IndexEntry& index,
                                          size_t pos, bool* exactOut, QuerySolutionNode* node,
                                          MatchExpression::MatchType mergeType) {
+
         const StageType type = node->getType();
+        verify(STAGE_GEO_NEAR_2D != type);
 
-        if (STAGE_GEO_2D == type || STAGE_GEO_NEAR_2D == type) {
-            warning() << "About to screw up 2d geo compound";
-            // This keeps the pred as a matcher but the limit argument to 2d indices applies
-            // post-match so this is wrong.
+        if (STAGE_GEO_2D == type) {
+            // XXX: 'expr' is possibly indexed by 'node'.  Right now we don't take advantage
+            // of covering for 2d indices.
             *exactOut = false;
+            return;
         }
-        else {
-            IndexBounds* boundsToFillOut = NULL;
 
-            if (STAGE_GEO_NEAR_2DSPHERE == type) {
-                GeoNear2DSphereNode* gn = static_cast<GeoNear2DSphereNode*>(node);
-                boundsToFillOut = &gn->baseBounds;
-            }
-            else {
-                verify(type == STAGE_IXSCAN);
-                IndexScanNode* scan = static_cast<IndexScanNode*>(node);
-                boundsToFillOut = &scan->bounds;
-            }
+        IndexBounds* boundsToFillOut = NULL;
 
-            // Get the ixtag->pos-th element of the index key pattern.
-            // TODO: cache this instead/with ixtag->pos?
-            BSONObjIterator it(index.keyPattern);
-            BSONElement keyElt = it.next();
-            for (size_t i = 0; i < pos; ++i) {
-                verify(it.more());
-                keyElt = it.next();
-            }
-            verify(!keyElt.eoo());
-            *exactOut = false;
+        if (STAGE_GEO_NEAR_2DSPHERE == type) {
+            GeoNear2DSphereNode* gn = static_cast<GeoNear2DSphereNode*>(node);
+            boundsToFillOut = &gn->baseBounds;
+        }
+        else {
+            verify(type == STAGE_IXSCAN);
+            IndexScanNode* scan = static_cast<IndexScanNode*>(node);
+            boundsToFillOut = &scan->bounds;
+        }
 
-            //QLOG() << "current bounds are " << currentScan->bounds.toString() << endl;
-            //QLOG() << "node merging in " << child->toString() << endl;
-            //QLOG() << "merging with field " << keyElt.toString(true, true) << endl;
-            //QLOG() << "taking advantage of compound index "
-                 //<< indices[currentIndexNumber].keyPattern.toString() << endl;
+        // Get the ixtag->pos-th element of the index key pattern.
+        // TODO: cache this instead/with ixtag->pos?
+        BSONObjIterator it(index.keyPattern);
+        BSONElement keyElt = it.next();
+        for (size_t i = 0; i < pos; ++i) {
+            verify(it.more());
+            keyElt = it.next();
+        }
+        verify(!keyElt.eoo());
+        *exactOut = false;
 
-            verify(boundsToFillOut->fields.size() > pos);
+        //QLOG() << "current bounds are " << currentScan->bounds.toString() << endl;
+        //QLOG() << "node merging in " << child->toString() << endl;
+        //QLOG() << "merging with field " << keyElt.toString(true, true) << endl;
+        //QLOG() << "taking advantage of compound index "
+        //<< indices[currentIndexNumber].keyPattern.toString() << endl;
 
-            OrderedIntervalList* oil = &boundsToFillOut->fields[pos];
+        verify(boundsToFillOut->fields.size() > pos);
 
-            if (boundsToFillOut->fields[pos].name.empty()) {
-                IndexBoundsBuilder::translate(expr, keyElt, oil, exactOut);
+        OrderedIntervalList* oil = &boundsToFillOut->fields[pos];
+
+        if (boundsToFillOut->fields[pos].name.empty()) {
+            IndexBoundsBuilder::translate(expr, keyElt, oil, exactOut);
+        }
+        else {
+            if (MatchExpression::AND == mergeType) {
+                IndexBoundsBuilder::translateAndIntersect(expr, keyElt, oil, exactOut);
             }
             else {
-                if (MatchExpression::AND == mergeType) {
-                    IndexBoundsBuilder::translateAndIntersect(expr, keyElt, oil, exactOut);
-                }
-                else {
-                    verify(MatchExpression::OR == mergeType);
-                    IndexBoundsBuilder::translateAndUnion(expr, keyElt, oil, exactOut);
-                }
+                verify(MatchExpression::OR == mergeType);
+                IndexBoundsBuilder::translateAndUnion(expr, keyElt, oil, exactOut);
             }
         }
     }
@@ -421,77 +418,77 @@ namespace mongo {
     // static
     void QueryPlanner::finishLeafNode(QuerySolutionNode* node, const IndexEntry& index) {
         const StageType type = node->getType();
+        verify(STAGE_GEO_NEAR_2D != type);
 
-        if (STAGE_GEO_2D == type || STAGE_GEO_NEAR_2D == type || STAGE_TEXT == type) {
-            // XXX: do we do anything here?
+        if (STAGE_GEO_2D == type || STAGE_TEXT == type) {
             return;
         }
-        else {
-            IndexBounds* bounds = NULL;
-
-            if (STAGE_GEO_NEAR_2DSPHERE == type) {
-                GeoNear2DSphereNode* gnode = static_cast<GeoNear2DSphereNode*>(node);
-                bounds = &gnode->baseBounds;
-            }
-            else {
-                verify(type == STAGE_IXSCAN);
-                IndexScanNode* scan = static_cast<IndexScanNode*>(node);
-                bounds = &scan->bounds;
-            }
 
-            // XXX: this currently fills out minkey/maxkey bounds for near queries, fix that.  just
-            // set the field name of the near query field when starting a near scan.
+        IndexBounds* bounds = NULL;
 
-            // Find the first field in the scan's bounds that was not filled out.
-            // TODO: could cache this.
-            size_t firstEmptyField = 0;
-            for (firstEmptyField = 0; firstEmptyField < bounds->fields.size(); ++firstEmptyField) {
-                if ("" == bounds->fields[firstEmptyField].name) {
-                    verify(bounds->fields[firstEmptyField].intervals.empty());
-                    break;
-                }
-            }
-
-            // All fields are filled out with bounds, nothing to do.
-            if (firstEmptyField == bounds->fields.size()) {
-                alignBounds(bounds, index.keyPattern);
-                return;
-            }
+        if (STAGE_GEO_NEAR_2DSPHERE == type) {
+            GeoNear2DSphereNode* gnode = static_cast<GeoNear2DSphereNode*>(node);
+            bounds = &gnode->baseBounds;
+        }
+        else {
+            verify(type == STAGE_IXSCAN);
+            IndexScanNode* scan = static_cast<IndexScanNode*>(node);
+            bounds = &scan->bounds;
+        }
 
-            // Skip ahead to the firstEmptyField-th element, where we begin filling in bounds.
-            BSONObjIterator it(index.keyPattern);
-            for (size_t i = 0; i < firstEmptyField; ++i) {
-                verify(it.more());
-                it.next();
-            }
+        // XXX: this currently fills out minkey/maxkey bounds for near queries, fix that.  just
+        // set the field name of the near query field when starting a near scan.
 
-            // For each field in the key...
-            while (it.more()) {
-                BSONElement kpElt = it.next();
-                // There may be filled-in fields to the right of the firstEmptyField.
-                // Example:
-                // The index {loc:"2dsphere", x:1}
-                // With a predicate over x and a near search over loc.
-                if ("" == bounds->fields[firstEmptyField].name) {
-                    verify(bounds->fields[firstEmptyField].intervals.empty());
-                    // ...build the "all values" interval.
-                    IndexBoundsBuilder::allValuesForField(kpElt,
-                                                          &bounds->fields[firstEmptyField]);
-                }
-                ++firstEmptyField;
+        // Find the first field in the scan's bounds that was not filled out.
+        // TODO: could cache this.
+        size_t firstEmptyField = 0;
+        for (firstEmptyField = 0; firstEmptyField < bounds->fields.size(); ++firstEmptyField) {
+            if ("" == bounds->fields[firstEmptyField].name) {
+                verify(bounds->fields[firstEmptyField].intervals.empty());
+                break;
             }
+        }
 
-            // Make sure that the length of the key is the length of the bounds we started.
-            verify(firstEmptyField == bounds->fields.size());
-
-            // We create bounds assuming a forward direction but can easily reverse bounds to align
-            // according to our desired direction.
+        // All fields are filled out with bounds, nothing to do.
+        if (firstEmptyField == bounds->fields.size()) {
             alignBounds(bounds, index.keyPattern);
+            return;
+        }
+
+        // Skip ahead to the firstEmptyField-th element, where we begin filling in bounds.
+        BSONObjIterator it(index.keyPattern);
+        for (size_t i = 0; i < firstEmptyField; ++i) {
+            verify(it.more());
+            it.next();
         }
+
+        // For each field in the key...
+        while (it.more()) {
+            BSONElement kpElt = it.next();
+            // There may be filled-in fields to the right of the firstEmptyField.
+            // Example:
+            // The index {loc:"2dsphere", x:1}
+            // With a predicate over x and a near search over loc.
+            if ("" == bounds->fields[firstEmptyField].name) {
+                verify(bounds->fields[firstEmptyField].intervals.empty());
+                // ...build the "all values" interval.
+                IndexBoundsBuilder::allValuesForField(kpElt,
+                                                      &bounds->fields[firstEmptyField]);
+            }
+            ++firstEmptyField;
+        }
+
+        // Make sure that the length of the key is the length of the bounds we started.
+        verify(firstEmptyField == bounds->fields.size());
+
+        // We create bounds assuming a forward direction but can easily reverse bounds to align
+        // according to our desired direction.
+        alignBounds(bounds, index.keyPattern);
     }
 
     // static
-    bool QueryPlanner::processIndexScans(MatchExpression* root,
+    bool QueryPlanner::processIndexScans(const CanonicalQuery& query,
+                                         MatchExpression* root,
                                          bool inArrayOperator,
                                          const vector<IndexEntry>& indices,
                                          vector<QuerySolutionNode*>* out) {
@@ -536,7 +533,8 @@ namespace mongo {
 
                 // If inArrayOperator: takes ownership of child, which is OK, since we detached
                 // child from root.
-                QuerySolutionNode* childSolution = buildIndexedDataAccess(child,
+                QuerySolutionNode* childSolution = buildIndexedDataAccess(query,
+                                                                          child,
                                                                           inArrayOperator,
                                                                           indices);
                 if (NULL == childSolution) { return false; }
@@ -658,7 +656,8 @@ namespace mongo {
     }
 
     // static
-    QuerySolutionNode* QueryPlanner::buildIndexedAnd(MatchExpression* root,
+    QuerySolutionNode* QueryPlanner::buildIndexedAnd(const CanonicalQuery& query,
+                                                     MatchExpression* root,
                                                      bool inArrayOperator,
                                                      const vector<IndexEntry>& indices) {
         auto_ptr<MatchExpression> autoRoot;
@@ -667,7 +666,7 @@ namespace mongo {
         }
 
         vector<QuerySolutionNode*> ixscanNodes;
-        if (!processIndexScans(root, inArrayOperator, indices, &ixscanNodes)) {
+        if (!processIndexScans(query, root, inArrayOperator, indices, &ixscanNodes)) {
             return NULL;
         }
 
@@ -732,7 +731,8 @@ namespace mongo {
     }
 
     // static
-    QuerySolutionNode* QueryPlanner::buildIndexedOr(MatchExpression* root,
+    QuerySolutionNode* QueryPlanner::buildIndexedOr(const CanonicalQuery& query,
+                                                    MatchExpression* root,
                                                     bool inArrayOperator,
                                                     const vector<IndexEntry>& indices) {
         auto_ptr<MatchExpression> autoRoot;
@@ -741,7 +741,7 @@ namespace mongo {
         }
 
         vector<QuerySolutionNode*> ixscanNodes;
-        if (!processIndexScans(root, inArrayOperator, indices, &ixscanNodes)) {
+        if (!processIndexScans(query, root, inArrayOperator, indices, &ixscanNodes)) {
             return NULL;
         }
 
@@ -763,35 +763,40 @@ namespace mongo {
             orResult = ixscanNodes[0];
         }
         else {
-            // XXX XXX XXX TODO: we shouldn't always merge sort, only if it gives us an order that
-            // we want.
-
-            // If there exists a sort order that is present in each child, we can merge them and
-            // maintain that sort order / those sort orders.
-            ixscanNodes[0]->computeProperties();
-            BSONObjSet sharedSortOrders = ixscanNodes[0]->getSort();
-
-            if (!sharedSortOrders.empty()) {
-                for (size_t i = 1; i < ixscanNodes.size(); ++i) {
-                    ixscanNodes[i]->computeProperties();
-                    BSONObjSet isect;
-                    set_intersection(sharedSortOrders.begin(),
-                                     sharedSortOrders.end(),
-                                     ixscanNodes[i]->getSort().begin(),
-                                     ixscanNodes[i]->getSort().end(),
-                                     std::inserter(isect, isect.end()),
-                                     BSONObjCmp());
-                    sharedSortOrders = isect;
-                    if (sharedSortOrders.empty()) {
-                        break;
+            bool shouldMergeSort = false;
+
+            if (!query.getParsed().getSort().isEmpty()) {
+                const BSONObj& desiredSort = query.getParsed().getSort();
+
+                // If there exists a sort order that is present in each child, we can merge them and
+                // maintain that sort order / those sort orders.
+                ixscanNodes[0]->computeProperties();
+                BSONObjSet sharedSortOrders = ixscanNodes[0]->getSort();
+
+                if (!sharedSortOrders.empty()) {
+                    for (size_t i = 1; i < ixscanNodes.size(); ++i) {
+                        ixscanNodes[i]->computeProperties();
+                        BSONObjSet isect;
+                        set_intersection(sharedSortOrders.begin(),
+                                sharedSortOrders.end(),
+                                ixscanNodes[i]->getSort().begin(),
+                                ixscanNodes[i]->getSort().end(),
+                                std::inserter(isect, isect.end()),
+                                BSONObjCmp());
+                        sharedSortOrders = isect;
+                        if (sharedSortOrders.empty()) {
+                            break;
+                        }
                     }
                 }
+
+                // XXX: consider reversing?
+                shouldMergeSort = (sharedSortOrders.end() != sharedSortOrders.find(desiredSort));
             }
 
-            if (!sharedSortOrders.empty()) {
+            if (shouldMergeSort) {
                 MergeSortNode* msn = new MergeSortNode();
-                // XXX: which sort order do we choose?  Does it matter?  I don't think it does.
-                msn->sort = *sharedSortOrders.begin();
+                msn->sort = query.getParsed().getSort();
                 msn->children.swap(ixscanNodes);
                 orResult = msn;
             }
@@ -810,17 +815,18 @@ namespace mongo {
     }
 
     // static
-    QuerySolutionNode* QueryPlanner::buildIndexedDataAccess(MatchExpression* root,
+    QuerySolutionNode* QueryPlanner::buildIndexedDataAccess(const CanonicalQuery& query,
+                                                            MatchExpression* root,
                                                             bool inArrayOperator,
                                                             const vector<IndexEntry>& indices) {
         if (root->isLogical()) {
             if (MatchExpression::AND == root->matchType()) {
                 // Takes ownership of root.
-                return buildIndexedAnd(root, inArrayOperator, indices);
+                return buildIndexedAnd(query, root, inArrayOperator, indices);
             }
             else if (MatchExpression::OR == root->matchType()) {
                 // Takes ownership of root.
-                return buildIndexedOr(root, inArrayOperator, indices);
+                return buildIndexedOr(query, root, inArrayOperator, indices);
             }
             else {
                 // Can't do anything with negated logical nodes index-wise.
@@ -881,7 +887,9 @@ namespace mongo {
                     auto_ptr<AndHashNode> ahn(new AndHashNode());
 
                     for (size_t i = 0; i < root->numChildren(); ++i) {
-                        QuerySolutionNode* node = buildIndexedDataAccess(root->getChild(i), true,
+                        QuerySolutionNode* node = buildIndexedDataAccess(query,
+                                                                         root->getChild(i),
+                                                                         true,
                                                                          indices);
                         if (NULL != node) {
                             ahn->children.push_back(node);
@@ -906,7 +914,7 @@ namespace mongo {
                     verify(MatchExpression::ELEM_MATCH_OBJECT);
                     // The child is an AND.
                     verify(1 == root->numChildren());
-                    solution = buildIndexedDataAccess(root->getChild(0), true, indices);
+                    solution = buildIndexedDataAccess(query, root->getChild(0), true, indices);
                     if (NULL == solution) { return NULL; }
                 }
 
@@ -943,13 +951,18 @@ namespace mongo {
         plan(*queryForSort, indices, NO_TABLE_SCAN, &solns);
         if (old) { qlogOn(); }
         //QLOG() << "Exit planning for bounds for sort\n";
+
+        // TODO: are there ever >1 solns?
         if (1 == solns.size()) {
             IndexScanNode* ixScan = NULL;
             QuerySolutionNode* rootNode = solns[0]->root.get();
 
             if (rootNode->getType() == STAGE_FETCH) {
                 FetchNode* fetchNode = static_cast<FetchNode*>(rootNode);
-                verify(fetchNode->children[0]->getType() == STAGE_IXSCAN);
+                if (fetchNode->children[0]->getType() != STAGE_IXSCAN) {
+                    // No bounds.
+                    return;
+                }
                 ixScan = static_cast<IndexScanNode*>(fetchNode->children[0]);
             }
             else if (rootNode->getType() == STAGE_IXSCAN) {
@@ -1004,6 +1017,7 @@ namespace mongo {
             verify(STAGE_SORT != type);
             // This shouldn't be here...
         }
+
         for (size_t i = 0; i < node->children.size(); ++i) {
             reverseScans(node->children[i]);
         }
@@ -1423,7 +1437,9 @@ namespace mongo {
                      << endl;
 
                 // This can fail if enumeration makes a mistake.
-                QuerySolutionNode* solnRoot = buildIndexedDataAccess(rawTree, false,
+                QuerySolutionNode* solnRoot = buildIndexedDataAccess(query,
+                                                                     rawTree,
+                                                                     false,
                                                                      relevantIndices);
                 if (NULL == solnRoot) { continue; }
 
diff --git a/src/mongo/db/query/query_planner.h b/src/mongo/db/query/query_planner.h
index 26e4293459b..5803ab405af 100644
--- a/src/mongo/db/query/query_planner.h
+++ b/src/mongo/db/query/query_planner.h
@@ -141,21 +141,24 @@ namespace mongo {
         /**
          * If 'inArrayOperator' is false, takes ownership of 'root'.
          */
-        static QuerySolutionNode* buildIndexedDataAccess(MatchExpression* root,
+        static QuerySolutionNode* buildIndexedDataAccess(const CanonicalQuery& query,
+                                                         MatchExpression* root,
                                                          bool inArrayOperator,
                                                          const vector<IndexEntry>& indices);
 
         /**
          * Takes ownership of 'root'.
          */
-        static QuerySolutionNode* buildIndexedAnd(MatchExpression* root,
+        static QuerySolutionNode* buildIndexedAnd(const CanonicalQuery& query,
+                                                  MatchExpression* root,
                                                   bool inArrayOperator,
                                                   const vector<IndexEntry>& indices);
 
         /**
          * Takes ownership of 'root'.
          */
-        static QuerySolutionNode* buildIndexedOr(MatchExpression* root,
+        static QuerySolutionNode* buildIndexedOr(const CanonicalQuery& query,
+                                                 MatchExpression* root,
                                                  bool inArrayOperator,
                                                  const vector<IndexEntry>& indices);
 
@@ -172,7 +175,8 @@ namespace mongo {
          *
          * Does not take ownership of 'root' but may remove children from it.
          */
-        static bool processIndexScans(MatchExpression* root,
+        static bool processIndexScans(const CanonicalQuery& query,
+                                      MatchExpression* root,
                                       bool inArrayOperator,
                                       const vector<IndexEntry>& indices,
                                       vector<QuerySolutionNode*>* out);
@@ -187,7 +191,8 @@ namespace mongo {
          * If the node is an index scan, the bounds for 'expr' are computed and placed into the
          * first field's OIL position.  The rest of the OILs are allocated but uninitialized.
          *
-         * If the node is a geo node, XXX.
+         * If the node is a geo node, grab the geo data from 'expr' and stuff it into the
+         * geo solution node of the appropriate type.
          */
         static QuerySolutionNode* makeLeafNode(const IndexEntry& index,
                                                MatchExpression* expr,
@@ -201,23 +206,14 @@ namespace mongo {
                                       MatchExpression::MatchType mergeType);
 
         /**
-         * If index scan, fill in any bounds that are missing in 'node' with the "all values for
-         * this field" interval.
+         * If index scan (regular or expression index), fill in any bounds that are missing in
+         * 'node' with the "all values for this field" interval.
          *
-         * If geo, XXX.
+         * If geo, do nothing.
          */
         static void finishLeafNode(QuerySolutionNode* node, const IndexEntry& index);
 
         //
-        // Helpers for creating a sort.
-        //
-
-        /**
-         * XXX
-         */
-        static void getBoundsForSort(const CanonicalQuery& query, SortNode* node);
-
-        //
         // Analysis of Data Access
         //
 
@@ -246,7 +242,7 @@ namespace mongo {
                                              const CanonicalQuery& query);
 
         /**
-         * XXX
+         * Traverse the tree rooted at 'root' reversing ixscans and other sorts.
          */
         static void reverseScans(QuerySolutionNode* root);
 
@@ -257,7 +253,16 @@ namespace mongo {
          */
         static void alignBounds(IndexBounds* bounds, const BSONObj& kp, int scanDir = 1);
 
+        /**
+         * Does the index with key pattern 'kp' provide the sort that 'query' wants?
+         */
         static bool providesSort(const CanonicalQuery& query, const BSONObj& kp);
+
+        /**
+         * Get the bounds for the sort in 'query' used by the sort stage.  Output the bounds
+         * in 'node'.
+         */
+        static void getBoundsForSort(const CanonicalQuery& query, SortNode* node);
     };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 8fc97c07614..e6dbf556792 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -33,6 +33,7 @@
 #include "mongo/db/jsobj.h"
 #include "mongo/db/json.h"
 #include "mongo/db/matcher/expression_parser.h"
+#include "mongo/db/query/qlog.h"
 #include "mongo/db/query/query_planner.h"
 #include "mongo/db/query/query_solution.h"
 #include "mongo/unittest/unittest.h"
@@ -651,6 +652,50 @@ namespace {
         ASSERT_EQUALS(getNumSolutions(), 3U);
     }
 
+    //
+    // Sort orders
+    //
+
+    // SERVER-1205.
+    TEST_F(IndexAssignmentTest, MergeSort) {
+        addIndex(BSON("a" << 1 << "c" << 1));
+        addIndex(BSON("b" << 1 << "c" << 1));
+        runDetailedQuery(fromjson("{$or: [{a:1}, {b:1}]}"), fromjson("{c:1}"), BSONObj());
+        dumpSolutions();
+    }
+
+    // SERVER-1205 as well.
+    TEST_F(IndexAssignmentTest, NoMergeSortIfNoSortWanted) {
+        addIndex(BSON("a" << 1 << "c" << 1));
+        addIndex(BSON("b" << 1 << "c" << 1));
+        runDetailedQuery(fromjson("{$or: [{a:1}, {b:1}]}"), BSONObj(), BSONObj());
+        dumpSolutions();
+    }
+
+    // SERVER-10801
+    TEST_F(IndexAssignmentTest, SortOnGeoQuery) {
+        addIndex(BSON("timestamp" << -1 << "position" << "2dsphere"));
+        BSONObj query = fromjson("{position: {$geoWithin: {$geometry: {type: \"Polygon\", coordinates: [[[1, 1], [1, 90], [180, 90], [180, 1], [1, 1]]]}}}}");
+        BSONObj sort = fromjson("{timestamp: -1}");
+        runDetailedQuery(query, sort, BSONObj());
+        dumpSolutions();
+    }
+
+    // SERVER-9257
+    TEST_F(IndexAssignmentTest, CompoundGeoNoGeoPredicate) {
+        addIndex(BSON("creationDate" << 1 << "foo.bar" << "2dsphere"));
+        runDetailedQuery(fromjson("{creationDate: { $gt: 7}}"),
+                         fromjson("{creationDate: 1}"), BSONObj());
+        dumpSolutions();
+    }
+
+    // Basic "keep sort in mind with an OR"
+    TEST_F(IndexAssignmentTest, MergeSortEvenIfSameIndex) {
+        addIndex(BSON("a" << 1 << "b" << 1));
+        runDetailedQuery(fromjson("{$or: [{a:1}, {a:7}]}"), fromjson("{b:1}"), BSONObj());
+        dumpSolutions();
+    }
+
     // STOPPED HERE - need to hook up machinery for multiple indexed predicates
     //                second is not working (until the machinery is in place)
     //
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index b75ae100a4f..4cb3ea938db 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -404,15 +404,18 @@ namespace mongo {
         }
         _sorts.insert(sortPattern);
 
-        // We're sorted not only by sortPattern but also by all prefixes of it.
-        for (int i = 0; i < sortPattern.nFields(); ++i) {
-            // Make obj out of fields [0,i]
-            BSONObjIterator it(sortPattern);
-            BSONObjBuilder prefixBob;
-            for (int j = 0; j <= i; ++j) {
-                prefixBob.append(it.next());
+        const int nFields = sortPattern.nFields();
+        if (nFields > 1) {
+            // We're sorted not only by sortPattern but also by all prefixes of it.
+            for (int i = 0; i < nFields; ++i) {
+                // Make obj out of fields [0,i]
+                BSONObjIterator it(sortPattern);
+                BSONObjBuilder prefixBob;
+                for (int j = 0; j <= i; ++j) {
+                    prefixBob.append(it.next());
+                }
+                _sorts.insert(prefixBob.obj());
             }
-            _sorts.insert(prefixBob.obj());
         }
 
         // If we are using the index {a:1, b:1} to answer the predicate {a: 10}, it's sorted
@@ -436,11 +439,39 @@ namespace mongo {
             }
         }
 
+        if (equalityFields.empty()) {
+            return;
+        }
+
         // TODO: Each field in equalityFields could be dropped from the sort order since it is
-        // a point interval.
+        // a point interval.  The full set of sort orders is as follows:
         // For each sort in _sorts:
         //    For each drop in powerset(equalityFields):
         //        Remove fields in 'drop' from 'sort' and add resulting sort to output.
+
+        // Since this involves a powerset, we only remove point intervals that the prior sort
+        // planning code removed, namely the contiguous prefix of the key pattern.
+        BSONObjIterator it(sortPattern);
+        BSONObjBuilder prefixBob;
+        while (it.more()) {
+            BSONElement elt = it.next();
+            // XXX string slowness.  fix when bounds are stringdata not string.
+            if (equalityFields.end() == equalityFields.find(string(elt.fieldName()))) {
+                prefixBob.append(elt);
+                // This field isn't a point interval, can't drop.
+                break;
+            }
+        }
+
+        while (it.more()) {
+            prefixBob.append(it.next());
+        }
+
+        // If we have an index {a:1} and an equality on 'a' don't append an empty sort order.
+        BSONObj filterPointsObj = prefixBob.obj();
+        if (!filterPointsObj.isEmpty()) {
+            _sorts.insert(filterPointsObj);
+        }
     }
 
     //