SERVER-10026 sort with improved sort analysis

20 files changed, 808 insertions, 392 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index fa9a7cb8e9d..bdae3ffdc4f 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -19,6 +19,7 @@ env.SConscript(['base/SConscript',
                 'db/auth/SConscript',
                 'db/exec/SConscript',
                 'db/fts/SConscript',
+                'db/index/SConscript',
                 'db/ops/SConscript',
                 'db/query/SConscript',
                 'db/sorter/SConscript',
@@ -342,7 +343,6 @@ env.StaticLibrary("coredb", [
         "db/pipeline/pipeline.cpp",
         "db/dbcommands_generic.cpp",
         "db/index_names.cpp",
-        "db/index/btree_key_generator.cpp",
         "db/keypattern.cpp",
         "db/matcher/matcher.cpp",
         "db/pipeline/accumulator_add_to_set.cpp",
@@ -387,6 +387,7 @@ env.StaticLibrary("coredb", [
                            'expressions_where',
                            'expressions_text',
                            'db/exec/working_set',
+                           'db/index/key_generator',
                            '$BUILD_DIR/mongo/foundation',
                            '$BUILD_DIR/third_party/shim_snappy',
                            'server_options',
diff --git a/src/mongo/db/exec/sort.cpp b/src/mongo/db/exec/sort.cpp
index e38b960e357..2f5d645fe9c 100644
--- a/src/mongo/db/exec/sort.cpp
+++ b/src/mongo/db/exec/sort.cpp
@@ -30,51 +30,60 @@
 
 #include <algorithm>
 
-#include "mongo/db/exec/working_set.h"
 #include "mongo/db/exec/working_set_common.h"
+#include "mongo/db/index/btree_key_generator.h"
 
 namespace mongo {
 
     const size_t kMaxBytes = 32 * 1024 * 1024;
 
-    // Used in STL sort.
-    struct WorkingSetComparison {
-        WorkingSetComparison(WorkingSet* ws, BSONObj pattern) : _ws(ws), _pattern(pattern) { }
-
-        bool operator()(const WorkingSetID& lhs, const WorkingSetID& rhs) const {
-            WorkingSetMember* lhsMember = _ws->get(lhs);
-            WorkingSetMember* rhsMember = _ws->get(rhs);
-
-            BSONObjIterator it(_pattern);
-            while (it.more()) {
-                BSONElement patternElt = it.next();
-                string fn = patternElt.fieldName();
-
-                BSONElement lhsElt;
-                verify(lhsMember->getFieldDotted(fn, &lhsElt));
-
-                BSONElement rhsElt;
-                verify(rhsMember->getFieldDotted(fn, &rhsElt));
-
-                // false means don't compare field name.
-                int x = lhsElt.woCompare(rhsElt, false);
-                if (-1 == patternElt.number()) { x = -x; }
-                if (x != 0) { return x < 0; }
+    namespace {
+        void dumpKeys(const BSONObjSet& keys) {
+            for (BSONObjSet::const_iterator it = keys.begin(); it != keys.end(); ++it) {
+                std::cout << "key: " << it->toString() << std::endl;
             }
+        }
+    }  // namespace
 
-            // A comparator for use with sort is required to model a strict weak ordering, so
-            // to satisfy irreflexivity we must return 'false' for elements that we consider
-            // equivalent under the pattern.
-            return false;
+    struct SortStage::WorkingSetComparator {
+        explicit WorkingSetComparator(BSONObj p) : pattern(p) { }
+
+        bool operator()(const SortableDataItem& lhs, const SortableDataItem rhs) const {
+            return lhs.sortKey.woCompare(rhs.sortKey, pattern, false /* ignore field names */) < 0;
         }
 
-        WorkingSet* _ws;
-        BSONObj _pattern;
+        BSONObj pattern;
     };
 
     SortStage::SortStage(const SortStageParams& params, WorkingSet* ws, PlanStage* child)
-        : _ws(ws), _child(child), _pattern(params.pattern), _sorted(false),
-          _resultIterator(_data.end()), _memUsage(0) { }
+        : _ws(ws),
+          _child(child),
+          _pattern(params.pattern),
+          _sorted(false),
+          _resultIterator(_data.end()),
+          _bounds(params.bounds),
+          _hasBounds(params.hasBounds),
+          _memUsage(0) {
+
+        _cmp.reset(new WorkingSetComparator(_pattern));
+
+        // We'll need to treat arrays as if we were to create an index over them. that is,
+        // we may need to unnest the first level and consider each array element to decide
+        // the sort order.
+        std::vector<const char *> fieldNames;
+        std::vector<BSONElement> fixed;
+        BSONObjIterator it(_pattern);
+        while (it.more()) {
+            BSONElement patternElt = it.next();
+            fieldNames.push_back(patternElt.fieldName());
+            fixed.push_back(BSONElement());
+        }
+        _keyGen.reset(new BtreeKeyGeneratorV1(fieldNames, fixed, false /* not sparse */));
+
+        // See comment on the operator() call about sort semantics and why we need a
+        // to use a bounds checker here.
+        _boundsChecker.reset(new IndexBoundsChecker(&_bounds, _pattern, 1 /* == order */));
+    }
 
     SortStage::~SortStage() { }
 
@@ -99,9 +108,6 @@ namespace mongo {
             StageState code = _child->work(&id);
 
             if (PlanStage::ADVANCED == code) {
-                // We let the data stay in the WorkingSet and sort using the IDs.
-                _data.push_back(id);
-
                 // Add it into the map for quick invalidation if it has a valid DiskLoc.
                 // A DiskLoc may be invalidated at any time (during a yield).  We need to get into
                 // the WorkingSet as quickly as possible to handle it.
@@ -115,17 +121,65 @@ namespace mongo {
                     _memUsage += sizeof(DiskLoc);
                 }
 
-                if (member->hasObj()) {
-                    _memUsage += member->obj.objsize();
+                // We are not supposed (yet) to sort over anything other than objects.  In other
+                // words, the query planner wouldn't put a sort atop anything that wouldn't have a
+                // collection scan as a leaf.
+                verify(member->hasObj());
+                _memUsage += member->obj.objsize();
+
+                // We will sort '_data' in the same order an index over '_pattern' would
+                // have. This has very nuanced implications. Consider the sort pattern {a:1}
+                // and the document {a:[1,10]}. We have potentially two keys we could use to
+                // sort on. Here we extract these keys. In the next step we decide which one to
+                // use.
+                BSONObjCmp patternCmp(_pattern);
+                BSONObjSet keys(patternCmp);
+                // XXX keyGen will throw on a "parallel array"
+                _keyGen->getKeys(member->obj, &keys);
+                // dumpKeys(keys);
+
+                // To decide which key to use in sorting, we consider not only the sort pattern
+                // but also if a given key, matches the query. Assume a query {a: {$gte: 5}} and
+                // a document {a:1}. That document wouldn't match. In the same sense, the key '1'
+                // in an array {a: [1,10]} should not be considered as being part of the result
+                // set and thus that array should sort based on the '10' key. To find such key,
+                // we use the bounds for the query.
+                BSONObj sortKey;
+                for (BSONObjSet::const_iterator it = keys.begin(); it != keys.end(); ++it) {
+                    if (!_hasBounds) {
+                        sortKey = *it;
+                        break;
+                    }
+
+                    if (_boundsChecker->isValidKey(*it)) {
+                        sortKey = *it;
+                        break;
+                    }
                 }
 
+                if (sortKey.isEmpty()) {
+                    // We assume that if the document made it throught the sort stage, than it
+                    // matches the query and thus should contain at least on array item that
+                    // is within the query bounds.
+                    cout << "can't find bounds for obj " << member->obj.toString() << endl;
+                    cout << "bounds are " << _bounds.toString() << endl;
+                    verify(0);
+                }
+
+                // We let the data stay in the WorkingSet and sort using the selected portion
+                // of the object in that working set member.
+                SortableDataItem item;
+                item.wsid = id;
+                item.sortKey = sortKey;
+                _data.push_back(item);
+
                 ++_commonStats.needTime;
                 return PlanStage::NEED_TIME;
             }
             else if (PlanStage::IS_EOF == code) {
                 // TODO: We don't need the lock for this.  We could ask for a yield and do this work
                 // unlocked.  Also, this is performing a lot of work for one call to work(...)
-                std::sort(_data.begin(), _data.end(), WorkingSetComparison(_ws, _pattern));
+                std::sort(_data.begin(), _data.end(), *_cmp);
                 _resultIterator = _data.begin();
                 _sorted = true;
                 ++_commonStats.needTime;
@@ -146,7 +200,8 @@ namespace mongo {
         // Returning results.
         verify(_resultIterator != _data.end());
         verify(_sorted);
-        *out = *_resultIterator++;
+        *out = _resultIterator->wsid;
+        _resultIterator++;
 
         // If we're returning something, take it out of our DL -> WSID map so that future
         // calls to invalidate don't cause us to take action for a DL we're done with.
@@ -183,7 +238,6 @@ namespace mongo {
         // _data contains indices into the WorkingSet, not actual data.  If a WorkingSetMember in
         // the WorkingSet needs to change state as a result of a DiskLoc invalidation, it will still
         // be at the same spot in the WorkingSet.  As such, we don't need to modify _data.
-
         DataMap::iterator it = _wsidByDiskLoc.find(dl);
 
         // If we're holding on to data that's got the DiskLoc we're invalidating...
diff --git a/src/mongo/db/exec/sort.h b/src/mongo/db/exec/sort.h
index 90a60609e4f..abb7973746a 100644
--- a/src/mongo/db/exec/sort.h
+++ b/src/mongo/db/exec/sort.h
@@ -28,16 +28,21 @@
 
 #pragma once
 
+#include <boost/scoped_ptr.hpp>
 #include <vector>
 
 #include "mongo/db/diskloc.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/matcher.h"
 #include "mongo/db/exec/plan_stage.h"
+#include "mongo/db/exec/working_set.h"
+#include "mongo/db/query/index_bounds.h"
 #include "mongo/platform/unordered_map.h"
 
 namespace mongo {
 
+    class BtreeKeyGenerator;
+
     // External params for the sort stage.  Declared below.
     class SortStageParams;
 
@@ -72,20 +77,49 @@ namespace mongo {
         // Our sort pattern.
         BSONObj _pattern;
 
-        // We read the child into this.
-        vector<WorkingSetID> _data;
-
-        // Have we sorted our data?
+        // Have we sorted our data? If so, we can access _resultIterator. If not,
+        // we're still populating _data.
         bool _sorted;
 
+        // Collection of working set members to sort with their respective sort key.
+        struct SortableDataItem {
+            WorkingSetID wsid;
+            BSONObj sortKey;
+        };
+        vector<SortableDataItem> _data;
+
         // Iterates through _data post-sort returning it.
-        vector<WorkingSetID>::iterator _resultIterator;
+        vector<SortableDataItem>::iterator _resultIterator;
 
         // We buffer a lot of data and we want to look it up by DiskLoc quickly upon invalidation.
         typedef unordered_map<DiskLoc, WorkingSetID, DiskLoc::Hasher> DataMap;
         DataMap _wsidByDiskLoc;
 
+        //
+        // Sort Apparatus
+        //
+
+        // A comparator for SortableDataItems.
+        struct WorkingSetComparator;
+        boost::scoped_ptr<WorkingSetComparator> _cmp;
+
+        // Bounds we should consider before sorting.
+        IndexBounds _bounds;
+
+        bool _hasBounds;
+
+        // Helper to extract sorting keys from documents containing dotted fields, arrays,
+        // or both.
+        boost::scoped_ptr<BtreeKeyGenerator> _keyGen;
+
+        // Helper to filter keys, thus enforcing _bounds over whatever keys generated with
+        // _keyGen.
+        boost::scoped_ptr<IndexBoundsChecker> _boundsChecker;
+
+        //
         // Stats
+        //
+
         CommonStats _commonStats;
         SortStats _specificStats;
 
@@ -96,11 +130,15 @@ namespace mongo {
     // Parameters that must be provided to a SortStage
     class SortStageParams {
     public:
-        //SortStageParams() : limit(0) { }
+        SortStageParams() : hasBounds(false) { }
 
         // How we're sorting.
         BSONObj pattern;
 
+        IndexBounds bounds;
+
+        bool hasBounds;
+
         // TODO: Implement this.
         // Must be >= 0.  Equal to 0 for no limit.
         // int limit;
diff --git a/src/mongo/db/exec/stagedebug_cmd.cpp b/src/mongo/db/exec/stagedebug_cmd.cpp
index 22d6fe633e5..4b1a9a23bf5 100644
--- a/src/mongo/db/exec/stagedebug_cmd.cpp
+++ b/src/mongo/db/exec/stagedebug_cmd.cpp
@@ -307,6 +307,8 @@ namespace mongo {
 
                 return new CollectionScan(params, workingSet, matcher);
             }
+            // sort is disabled for now.
+#if 0
             else if ("sort" == nodeName) {
                 uassert(16969, "Node argument must be provided to sort",
                         nodeArgs["node"].isABSONObj());
@@ -317,6 +319,7 @@ namespace mongo {
                 params.pattern = nodeArgs["pattern"].Obj();
                 return new SortStage(params, workingSet, subNode);
             }
+#endif
             else if ("mergeSort" == nodeName) {
                 uassert(16971, "Nodes argument must be provided to sort",
                         nodeArgs["nodes"].isABSONObj());
diff --git a/src/mongo/db/index/SConscript b/src/mongo/db/index/SConscript
new file mode 100644
index 00000000000..5fc97a1c488
--- /dev/null
+++ b/src/mongo/db/index/SConscript
@@ -0,0 +1,13 @@
+# -*- mode: python -*-
+
+Import("env")
+
+env.StaticLibrary(
+        target='key_generator',
+        source=[
+            'btree_key_generator.cpp',
+        ],
+        LIBDEPS=[
+            '$BUILD_DIR/mongo/bson',
+        ],
+)
diff --git a/src/mongo/db/query/explain_plan.cpp b/src/mongo/db/query/explain_plan.cpp
index d194ca28119..5ebcd805a96 100644
--- a/src/mongo/db/query/explain_plan.cpp
+++ b/src/mongo/db/query/explain_plan.cpp
@@ -159,7 +159,7 @@ namespace mongo {
         else if (leaf->stageType == STAGE_IXSCAN) {
             IndexScanStats* indexStats = static_cast<IndexScanStats*>(leaf->specific.get());
             dassert(indexStats);
-            string direction = indexStats > 0 ? "" : " reverse";
+            string direction = indexStats->direction > 0 ? "" : " reverse";
             res->setCursor(indexStats->indexType + " " + indexStats->indexName + direction);
             res->setNScanned(indexStats->keysExamined);
 
diff --git a/src/mongo/db/query/index_bounds.cpp b/src/mongo/db/query/index_bounds.cpp
index 5d4228e793f..f9190976a9f 100644
--- a/src/mongo/db/query/index_bounds.cpp
+++ b/src/mongo/db/query/index_bounds.cpp
@@ -288,6 +288,21 @@ namespace mongo {
         return false;
     }
 
+    bool IndexBoundsChecker::isValidKey(const BSONObj& key) {
+        BSONObjIterator it(key);
+        size_t curOil = 0;
+        while (it.more()) {
+            BSONElement elt = it.next();
+            size_t whichInterval;
+            Location loc = findIntervalForField(elt, _bounds->fields[curOil], _expectedDirection[curOil], &whichInterval);
+            if (WITHIN != loc) {
+                return false;
+            }
+            ++curOil;
+        }
+        return true;
+    }
+
     IndexBoundsChecker::KeyState IndexBoundsChecker::checkKey(const BSONObj& key,
                                                                 int* keyEltsToUse,
                                                                 bool* movePastKeyElts,
diff --git a/src/mongo/db/query/index_bounds.h b/src/mongo/db/query/index_bounds.h
index 2b0ba90cee6..c5c49aa5b55 100644
--- a/src/mongo/db/query/index_bounds.h
+++ b/src/mongo/db/query/index_bounds.h
@@ -122,6 +122,12 @@ namespace mongo {
         };
 
         /**
+         * Is 'key' a valid key?  Note that this differs from checkKey, which assumes that it
+         * receives keys in sorted order.
+         */
+        bool isValidKey(const BSONObj& key);
+
+        /**
          * This function checks if the key is within the bounds we're iterating over and updates any
          * internal state required to efficiently determine if the key is within our bounds.
          *
diff --git a/src/mongo/db/query/interval.h b/src/mongo/db/query/interval.h
index b5a2e33ed7e..da4020d4d2a 100644
--- a/src/mongo/db/query/interval.h
+++ b/src/mongo/db/query/interval.h
@@ -76,6 +76,10 @@ namespace mongo {
         /** Returns true if an empty-constructed interval hasn't been init()-ialized yet */
         bool isEmpty() const;
 
+        bool isPoint() const {
+            return startInclusive && endInclusive && 0 == start.woCompare(end, false);
+        }
+
         /**
          * Swap start and end points of interval.
          */
diff --git a/src/mongo/db/query/multi_plan_runner.cpp b/src/mongo/db/query/multi_plan_runner.cpp
index cee86fe8899..e60f83290bc 100644
--- a/src/mongo/db/query/multi_plan_runner.cpp
+++ b/src/mongo/db/query/multi_plan_runner.cpp
@@ -42,8 +42,13 @@
 namespace mongo {
 
     MultiPlanRunner::MultiPlanRunner(CanonicalQuery* query)
-        : _killed(false), _failure(false), _failureCount(0), _policy(Runner::YIELD_MANUAL),
-          _query(query) { }
+        : _killed(false),
+          _failure(false),
+          _failureCount(0),
+          _policy(Runner::YIELD_MANUAL),
+          _query(query),
+          _backupSolution(NULL),
+          _backupPlan(NULL) { }
 
     MultiPlanRunner::~MultiPlanRunner() {
         for (size_t i = 0; i < _candidates.size(); ++i) {
@@ -53,6 +58,14 @@ namespace mongo {
             delete _candidates[i].ws;
         }
 
+        if (NULL != _backupSolution) {
+            delete _backupSolution;
+        }
+
+        if (NULL != _backupPlan) {
+            delete _backupPlan;
+        }
+
         for (vector<PlanStageStats*>::iterator it = _candidateStats.begin();
              it != _candidateStats.end();
              ++it) {
@@ -71,6 +84,9 @@ namespace mongo {
 
         if (NULL != _bestPlan) {
             _bestPlan->setYieldPolicy(policy);
+            if (NULL != _backupPlan) {
+                _backupPlan->setYieldPolicy(policy);
+            }
         } else {
             // Still running our candidates and doing our own yielding.
             if (Runner::YIELD_MANUAL == policy) {
@@ -87,6 +103,9 @@ namespace mongo {
 
         if (NULL != _bestPlan) {
             _bestPlan->saveState();
+            if (NULL != _backupPlan) {
+                _backupPlan->saveState();
+            }
         }
         else {
             allPlansSaveState();
@@ -98,6 +117,9 @@ namespace mongo {
 
         if (NULL != _bestPlan) {
             return _bestPlan->restoreState();
+            if (NULL != _backupPlan) {
+                _backupPlan->restoreState();
+            }
         }
         else {
             allPlansRestoreState();
@@ -110,22 +132,41 @@ namespace mongo {
 
         if (NULL != _bestPlan) {
             _bestPlan->invalidate(dl);
-            for (deque<WorkingSetID>::iterator it = _alreadyProduced.begin();
-                 it != _alreadyProduced.end(); ++it) {
+            for (list<WorkingSetID>::iterator it = _alreadyProduced.begin();
+                 it != _alreadyProduced.end();) {
                 WorkingSetMember* member = _bestPlan->getWorkingSet()->get(*it);
                 if (member->hasLoc() && member->loc == dl) {
+                    list<WorkingSetID>::iterator next = it;
+                    next++;
                     WorkingSetCommon::fetchAndInvalidateLoc(member);
+                    _bestPlan->getWorkingSet()->flagForReview(*it);
+                    _alreadyProduced.erase(it);
+                    it = next;
+                }
+                else {
+                    it++;
                 }
             }
+            if (NULL != _backupPlan) {
+                _backupPlan->invalidate(dl);
+            }
         }
         else {
             for (size_t i = 0; i < _candidates.size(); ++i) {
                 _candidates[i].root->invalidate(dl);
-                for (deque<WorkingSetID>::iterator it = _candidates[i].results.begin();
-                     it != _candidates[i].results.end(); ++it) {
+                for (list<WorkingSetID>::iterator it = _candidates[i].results.begin();
+                     it != _candidates[i].results.end();) {
                     WorkingSetMember* member = _candidates[i].ws->get(*it);
                     if (member->hasLoc() && member->loc == dl) {
+                        list<WorkingSetID>::iterator next = it;
+                        next++;
                         WorkingSetCommon::fetchAndInvalidateLoc(member);
+                        _candidates[i].ws->flagForReview(*it);
+                        _candidates[i].results.erase(it);
+                        it = next;
+                    }
+                    else {
+                        it++;
                     }
                 }
             }
@@ -199,7 +240,26 @@ namespace mongo {
             return Runner::RUNNER_ADVANCED;
         }
 
-        return _bestPlan->getNext(objOut, dlOut);
+        RunnerState state = _bestPlan->getNext(objOut, dlOut);
+
+        if (Runner::RUNNER_ERROR == state && (NULL != _backupSolution)) {
+            QLOG() << "Best plan errored out switching to backup\n";
+            _bestPlan.reset(_backupPlan);
+            _backupPlan = NULL;
+            _bestSolution.reset(_backupSolution);
+            _backupSolution = NULL;
+            return _bestPlan->getNext(objOut, dlOut);
+        }
+
+        if (NULL != _backupSolution && Runner::RUNNER_ADVANCED == state) {
+            QLOG() << "Best plan had a blocking sort, became unblocked, deleting backup plan\n";
+            delete _backupSolution;
+            delete _backupPlan;
+            _backupSolution = NULL;
+            _backupPlan = NULL;
+        }
+
+        return state;
     }
 
     bool MultiPlanRunner::pickBestPlan(size_t* out) {
@@ -224,6 +284,23 @@ namespace mongo {
 
         QLOG() << "Winning solution:\n" << _bestSolution->toString() << endl;
 
+        size_t backupChild = bestChild;
+        if (_bestSolution->hasSortStage && (0 == _alreadyProduced.size())) {
+            QLOG() << "Winner has blocked sort, looking for backup plan...\n";
+            for (size_t i = 0; i < _candidates.size(); ++i) {
+                // TODO: if we drastically change plan ranking, this will die.
+                verify(0 == _candidates[i].results.size());
+                if (!_candidates[i].solution->hasSortStage) {
+                    QLOG() << "Candidate " << i << " is backup child\n";
+                    backupChild = i;
+                    _backupSolution = _candidates[i].solution;
+                    _backupPlan = new PlanExecutor(_candidates[i].ws, _candidates[i].root);
+                    _backupPlan->setYieldPolicy(_policy);
+                    break;
+                }
+            }
+        }
+
         // TODO:
         // Store the choice we just made in the cache.
         // QueryPlanCache* cache = PlanCache::get(somenamespace);
@@ -233,6 +310,8 @@ namespace mongo {
         // Clear out the candidate plans, leaving only stats as we're all done w/them.
         for (size_t i = 0; i < _candidates.size(); ++i) {
             if (i == bestChild) { continue; }
+            if (i == backupChild) { continue; }
+
             delete _candidates[i].solution;
 
             // Remember the stats for the candidate plan because we always show it on an
diff --git a/src/mongo/db/query/multi_plan_runner.h b/src/mongo/db/query/multi_plan_runner.h
index ecbe48b04bb..d045aa0f49e 100644
--- a/src/mongo/db/query/multi_plan_runner.h
+++ b/src/mongo/db/query/multi_plan_runner.h
@@ -29,7 +29,7 @@
 #pragma once
 
 #include <boost/scoped_ptr.hpp>
-#include <deque>
+#include <list>
 #include <vector>
 
 #include "mongo/base/status.h"
@@ -133,7 +133,7 @@ namespace mongo {
         boost::scoped_ptr<PlanExecutor> _bestPlan;
 
         // ...and any results it produced while working toward winning.
-        std::deque<WorkingSetID> _alreadyProduced;
+        std::list<WorkingSetID> _alreadyProduced;
 
         // ...and the solution, for caching.
         boost::scoped_ptr<QuerySolution> _bestSolution;
@@ -149,6 +149,13 @@ namespace mongo {
 
         // The query that we're trying to figure out the best solution to.
         boost::scoped_ptr<CanonicalQuery> _query;
+
+        //
+        // Backup plan for sort
+        //
+
+        QuerySolution* _backupSolution;
+        PlanExecutor* _backupPlan;
     };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/plan_ranker.cpp b/src/mongo/db/query/plan_ranker.cpp
index ec2777bf0cf..c1589bf8727 100644
--- a/src/mongo/db/query/plan_ranker.cpp
+++ b/src/mongo/db/query/plan_ranker.cpp
@@ -52,8 +52,9 @@ namespace mongo {
         double maxScore = 0;
         size_t bestChild = numeric_limits<size_t>::max();
         for (size_t i = 0; i < statTrees.size(); ++i) {
+            QLOG() << "scoring plan " << i << ":\n" << candidates[i].solution->toString();
             double score = scoreTree(statTrees[i]);
-            QLOG() << "score of plan " << i << " is " << score << endl;
+            QLOG() << "score = " << score << endl;
             if (score > maxScore) {
                 maxScore = score;
                 bestChild = i;
@@ -95,6 +96,18 @@ namespace mongo {
         }
     }
 
+    bool hasSort(const PlanStageStats* stats) {
+        if (STAGE_SORT == stats->stageType) {
+            return true;
+        }
+        for (size_t i = 0; i < stats->children.size(); ++i) {
+            if (hasSort(stats->children[i])) {
+                return true;
+            }
+        }
+        return false;
+    }
+
     // static 
     double PlanRanker::scoreTree(const PlanStageStats* stats) {
         // We start all scores at 1.  Our "no plan selected" score is 0 and we want all plans to
@@ -102,14 +115,24 @@ namespace mongo {
         double baseScore = 1;
 
         // How much did a plan produce?
+        // Range: [0, 1]
         double productivity = static_cast<double>(stats->common.advanced)
                             / static_cast<double>(stats->common.works);
 
+        // Does a plan have a sort?
+        // bool sort = hasSort(stats);
+
         // How selective do we think an index is?
         //double selectivity = computeSelectivity(stats);
-
-        return baseScore + productivity;
         //return baseScore + productivity + selectivity;
+
+        //double sortPenalty = sort ? 0.5 : 0;
+        //double score = baseScore + productivity - sortPenalty;
+        double score = baseScore + productivity;
+
+        QLOG() << "score (" << score << ") = baseScore (" << baseScore << ") + productivity(" << productivity << ")\n";
+
+        return score;
     }
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/plan_ranker.h b/src/mongo/db/query/plan_ranker.h
index a0fd0d696da..d9c90bec97f 100644
--- a/src/mongo/db/query/plan_ranker.h
+++ b/src/mongo/db/query/plan_ranker.h
@@ -28,7 +28,7 @@
 
 #pragma once
 
-#include <deque>
+#include <list>
 #include <vector>
 
 #include "mongo/db/exec/plan_stage.h"
@@ -72,7 +72,7 @@ namespace mongo {
         WorkingSet* ws;
 
         // Any results produced during the plan's execution prior to ranking are retained here.
-        std::deque<WorkingSetID> results;
+        std::list<WorkingSetID> results;
 
         bool failed;
     };
diff --git a/src/mongo/db/query/qlog.cpp b/src/mongo/db/query/qlog.cpp
index 1af813705c9..0dd6a658f12 100644
--- a/src/mongo/db/query/qlog.cpp
+++ b/src/mongo/db/query/qlog.cpp
@@ -41,6 +41,18 @@ namespace mongo {
 
     static nullstream theNullStream;
 
+    bool qlogOff() {
+        bool old = verboseQueryLogging;
+        verboseQueryLogging = false;
+        return old;
+    }
+
+    bool qlogOn() {
+        bool old = verboseQueryLogging;
+        verboseQueryLogging = true;
+        return old;
+    }
+
     std::ostream& QLOG() {
         if (verboseQueryLogging) {
             return std::cout;
diff --git a/src/mongo/db/query/qlog.h b/src/mongo/db/query/qlog.h
index 418ada05acb..1f1673371b1 100644
--- a/src/mongo/db/query/qlog.h
+++ b/src/mongo/db/query/qlog.h
@@ -34,4 +34,7 @@ namespace mongo {
 
     std::ostream& QLOG();
 
+    bool qlogOff();
+    bool qlogOn();
+
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 7504a526494..82e24e92bc7 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -34,6 +34,7 @@
 #include <vector>
 
 // For QueryOption_foobar
+#include "mongo/bson/bsonmisc.h"
 #include "mongo/client/dbclientinterface.h"
 #include "mongo/db/geo/core.h"
 #include "mongo/db/matcher/expression_array.h"
@@ -230,7 +231,8 @@ namespace mongo {
     }
 
     // static
-    QuerySolution* QueryPlanner::makeCollectionScan(const CanonicalQuery& query, bool tailable) {
+    QuerySolution* QueryPlanner::makeCollectionScan(const CanonicalQuery& query, bool tailable,
+                                                    size_t options) {
         // Make the (only) node, a collection scan.
         CollectionScanNode* csn = new CollectionScanNode();
         csn->name = query.ns();
@@ -255,7 +257,7 @@ namespace mongo {
         }
 
         // QLOG() << "Outputting collscan " << soln->toString() << endl;
-        return analyzeDataAccess(query, csn);
+        return analyzeDataAccess(query, options, csn);
     }
 
     // static
@@ -387,32 +389,31 @@ namespace mongo {
         }
     }
 
-    /**
-     * Assumes each OIL in bounds is increasing.
-     * Reverses any OILs that are indexed according to '-1'.
-     */
-    void alignBounds(IndexBounds* bounds, const BSONObj& kp) {
+    // static
+    void QueryPlanner::alignBounds(IndexBounds* bounds, const BSONObj& kp, int scanDir) {
         BSONObjIterator it(kp);
         size_t oilIdx = 0;
         while (it.more()) {
             BSONElement elt = it.next();
             int direction = (elt.numberInt() >= 0) ? 1 : -1;
+            direction *= scanDir;
             if (-1 == direction) {
                 vector<Interval>& iv = bounds->fields[oilIdx].intervals;
                 // Step 1: reverse the list.
                 std::reverse(iv.begin(), iv.end());
                 // Step 2: reverse each interval.
                 for (size_t i = 0; i < iv.size(); ++i) {
-                    // QLOG() << "reversing " << iv[i].toString() << endl;
+                    QLOG() << "reversing " << iv[i].toString() << endl;
                     iv[i].reverse();
                 }
             }
             ++oilIdx;
         }
 
-        // XXX: some day we'll maybe go backward to pull a sort out
-        if (!bounds->isValidFor(kp, 1)) {
+        if (!bounds->isValidFor(kp, scanDir)) {
             QLOG() << "INVALID BOUNDS: " << bounds->toString() << endl;
+            QLOG() << "kp = " << kp.toString() << endl;
+            QLOG() << "scanDir = " << scanDir << endl;
             verify(0);
         }
     }
@@ -720,7 +721,7 @@ namespace mongo {
             // Takes ownership.
             fetch->filter.reset(autoRoot.release());
             // takes ownership
-            fetch->child.reset(andResult);
+            fetch->children.push_back(andResult);
             andResult = fetch;
         }
         else {
@@ -762,25 +763,35 @@ namespace mongo {
             orResult = ixscanNodes[0];
         }
         else {
-            // If each child is sorted by the same predicate, we can merge them and maintain
-            // sorted order.
-            bool haveSameSort;
-            if (ixscanNodes[0]->getSort().isEmpty()) {
-                haveSameSort = false;
-            }
-            else {
-                haveSameSort = true;
+            // 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) {
-                    if (0 != ixscanNodes[0]->getSort().woCompare(ixscanNodes[i]->getSort())) {
-                        haveSameSort = false;
+                    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;
                     }
                 }
             }
 
-            if (haveSameSort) {
+            if (!sharedSortOrders.empty()) {
                 MergeSortNode* msn = new MergeSortNode();
-                msn->sort = ixscanNodes[0]->getSort();
+                // XXX: which sort order do we choose?  Does it matter?  I don't think it does.
+                msn->sort = *sharedSortOrders.begin();
                 msn->children.swap(ixscanNodes);
                 orResult = msn;
             }
@@ -859,7 +870,7 @@ namespace mongo {
                 FetchNode* fetch = new FetchNode();
                 verify(NULL != autoRoot.get());
                 fetch->filter.reset(autoRoot.release());
-                fetch->child.reset(soln);
+                fetch->children.push_back(soln);
                 return fetch;
             }
             else if (Indexability::arrayUsesIndexOnChildren(root)) {
@@ -906,7 +917,7 @@ namespace mongo {
                 // Takes ownership of 'root'.
                 verify(NULL != autoRoot.get());
                 fetch->filter.reset(autoRoot.release());
-                fetch->child.reset(solution);
+                fetch->children.push_back(solution);
                 return fetch;
             }
         }
@@ -915,16 +926,106 @@ namespace mongo {
     }
 
     // static
+    void QueryPlanner::getBoundsForSort(const CanonicalQuery& query, SortNode* node) {
+        IndexEntry sortOrder(query.getParsed().getSort(), true, false, "doesnt_matter");
+        vector<IndexEntry> indices;
+        indices.push_back(sortOrder);
+
+        CanonicalQuery* rawQueryForSort;
+        verify(CanonicalQuery::canonicalize(query.ns(),
+                                            query.getQueryObj(),
+                                            &rawQueryForSort).isOK());
+        auto_ptr<CanonicalQuery> queryForSort(rawQueryForSort);
+
+        vector<QuerySolution*> solns;
+        //QLOG() << "Trying to get bounds for sort\n";
+        bool old = qlogOff();
+        plan(*queryForSort, indices, NO_TABLE_SCAN, &solns);
+        if (old) { qlogOn(); }
+        //QLOG() << "Exit planning for bounds for sort\n";
+        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);
+                ixScan = static_cast<IndexScanNode*>(fetchNode->children[0]);
+            }
+            else if (rootNode->getType() == STAGE_IXSCAN) {
+                ixScan = static_cast<IndexScanNode*>(rootNode);
+            }
+            verify(ixScan);
+
+            node->bounds = ixScan->bounds;
+            node->hasBounds = true;
+        }
+    }
+
+    BSONObj reverseSortObj(const BSONObj& sortObj) {
+        BSONObjBuilder reverseBob;
+        BSONObjIterator it(sortObj);
+        while (it.more()) {
+            BSONElement elt = it.next();
+            reverseBob.append(elt.fieldName(), elt.numberInt() * -1);
+        }
+        return reverseBob.obj();
+    }
+
+    void QueryPlanner::reverseScans(QuerySolutionNode* node) {
+        StageType type = node->getType();
+
+        if (STAGE_IXSCAN == type) {
+            IndexScanNode* isn = static_cast<IndexScanNode*>(node);
+            QLOG() << " Bounds before reversing: " << isn->bounds.toString() << endl;
+            isn->direction *= -1;
+
+            for (size_t i = 0; i < isn->bounds.fields.size(); ++i) {
+                vector<Interval>& iv = isn->bounds.fields[i].intervals;
+                // Step 1: reverse the list.
+                std::reverse(iv.begin(), iv.end());
+                // Step 2: reverse each interval.
+                for (size_t j = 0; j < iv.size(); ++j) {
+                    iv[j].reverse();
+                }
+            }
+            if (!isn->bounds.isValidFor(isn->indexKeyPattern, isn->direction)) {
+                verify(0);
+            }
+            // TODO: we can just negate every value in the already computed properties.
+            isn->computeProperties();
+        }
+        else if (STAGE_SORT_MERGE == type) {
+            // reverse direction of comparison for merge
+            MergeSortNode* msn = static_cast<MergeSortNode*>(node);
+            msn->sort = reverseSortObj(msn->sort);
+        }
+        else {
+            verify(STAGE_SORT != type);
+            // This shouldn't be here...
+        }
+        for (size_t i = 0; i < node->children.size(); ++i) {
+            reverseScans(node->children[i]);
+        }
+
+    }
+
+    // static
     QuerySolution* QueryPlanner::analyzeDataAccess(const CanonicalQuery& query,
+                                                   size_t options,
                                                    QuerySolutionNode* solnRoot) {
         auto_ptr<QuerySolution> soln(new QuerySolution());
         soln->filterData = query.getQueryObj();
         verify(soln->filterData.isOwned());
         soln->ns = query.ns();
 
+        solnRoot->computeProperties();
+
         // solnRoot finds all our results.  Let's see what transformations we must perform to the
         // data.
 
+        bool blockingSort = false;
+
         // Sort the results, if there is a sort specified.
         if (!query.getParsed().getSort().isEmpty()) {
             const BSONObj& sortObj = query.getParsed().getSort();
@@ -933,36 +1034,32 @@ namespace mongo {
             // outputted a collscan to satisfy the desired order.
             BSONElement natural = sortObj.getFieldDotted("$natural");
             if (natural.eoo()) {
+                BSONObjSet sorts = solnRoot->getSort();
                 // See if solnRoot gives us the sort.  If so, we're done.
-                if (0 == sortObj.woCompare(solnRoot->getSort())) {
-                    // Sort is already provided!
-                }
-                else {
-                    // If solnRoot isn't already sorted, let's see if it has the fields we're
-                    // sorting on.  If it's fetched, it has all the fields by definition.  If it's
-                    // not, we check sort field by sort field.
-                    if (!solnRoot->fetched()) {
-                        bool sortCovered = true;
-                        BSONObjIterator it(sortObj);
-                        while (it.more()) {
-                            if (!solnRoot->hasField(it.next().fieldName())) {
-                                sortCovered = false;
-                                break;
-                            }
-                        }
-
-                        if (!sortCovered) {
+                if (sorts.end() == sorts.find(sortObj)) {
+                    // Sort is not provided.  See if we provide the reverse of our sort pattern.
+                    // If so, we can reverse the scan direction(s).
+                    BSONObj reverseSort = reverseSortObj(sortObj);
+                    if (sorts.end() != sorts.find(reverseSort)) {
+                        reverseScans(solnRoot);
+                        QLOG() << "Reversing ixscan to provide sort.  Result: "
+                               << solnRoot->toString() << endl;
+                    }
+                    else {
+                        if (!solnRoot->fetched()) {
                             FetchNode* fetch = new FetchNode();
-                            fetch->child.reset(solnRoot);
+                            fetch->children.push_back(solnRoot);
                             solnRoot = fetch;
                         }
-                    }
 
-                    soln->hasSortStage = true;
-                    SortNode* sort = new SortNode();
-                    sort->pattern = sortObj;
-                    sort->child.reset(solnRoot);
-                    solnRoot = sort;
+                        soln->hasSortStage = true;
+                        SortNode* sort = new SortNode();
+                        sort->pattern = sortObj;
+                        getBoundsForSort(query, sort);
+                        sort->children.push_back(solnRoot);
+                        solnRoot = sort;
+                        blockingSort = true;
+                    }
                 }
             }
         }
@@ -976,7 +1073,7 @@ namespace mongo {
                 // If the projection requires the entire document, somebody must fetch.
                 if (!solnRoot->fetched()) {
                     FetchNode* fetch = new FetchNode();
-                    fetch->child.reset(solnRoot);
+                    fetch->children.push_back(solnRoot);
                     solnRoot = fetch;
                 }
             }
@@ -996,7 +1093,7 @@ namespace mongo {
                 // a fetch is required.
                 if (!covered) {
                     FetchNode* fetch = new FetchNode();
-                    fetch->child.reset(solnRoot);
+                    fetch->children.push_back(solnRoot);
                     solnRoot = fetch;
                 }
             }
@@ -1004,14 +1101,14 @@ namespace mongo {
             // We now know we have whatever data is required for the projection.
             ProjectionNode* projNode = new ProjectionNode();
             projNode->projection = query.getProj();
-            projNode->child.reset(solnRoot);
+            projNode->children.push_back(solnRoot);
             solnRoot = projNode;
         }
         else {
             // If there's no projection, we must fetch, as the user wants the entire doc.
             if (!solnRoot->fetched()) {
                 FetchNode* fetch = new FetchNode();
-                fetch->child.reset(solnRoot);
+                fetch->children.push_back(solnRoot);
                 solnRoot = fetch;
             }
         }
@@ -1019,14 +1116,16 @@ namespace mongo {
         if (0 != query.getParsed().getSkip()) {
             SkipNode* skip = new SkipNode();
             skip->skip = query.getParsed().getSkip();
-            skip->child.reset(solnRoot);
+            skip->children.push_back(solnRoot);
             solnRoot = skip;
         }
 
-        if (0 != query.getParsed().getNumToReturn() && !query.getParsed().wantMore()) {
+        if (0 != query.getParsed().getNumToReturn() &&
+            (blockingSort || !query.getParsed().wantMore())) {
+
             LimitNode* limit = new LimitNode();
             limit->limit = query.getParsed().getNumToReturn();
-            limit->child.reset(solnRoot);
+            limit->children.push_back(solnRoot);
             solnRoot = limit;
         }
 
@@ -1058,10 +1157,49 @@ namespace mongo {
         return false;
     }
 
+    QuerySolution* QueryPlanner::scanWholeIndex(const IndexEntry& index, size_t options, const CanonicalQuery& query) {
+        QuerySolutionNode* solnRoot = NULL;
+
+        // Build an ixscan over the id index, use it, and return it.
+        IndexScanNode* isn = new IndexScanNode();
+        isn->indexKeyPattern = index.keyPattern;
+        isn->indexIsMultiKey = index.multikey;
+        isn->bounds.fields.resize(index.keyPattern.nFields());
+
+        // TODO: can we use simple bounds with this compound idx?
+        BSONObjIterator it(isn->indexKeyPattern);
+        int field = 0;
+        while (it.more()) {
+            IndexBoundsBuilder::allValuesForField(it.next(), &isn->bounds.fields[field]);
+            ++field;
+        }
+        alignBounds(&isn->bounds, isn->indexKeyPattern);
+
+        MatchExpression* filter = query.root()->shallowClone();
+
+        // If it's find({}) remove the no-op root.
+        if (MatchExpression::AND == filter->matchType() && (0 == filter->numChildren())) {
+            delete filter;
+            solnRoot = isn;
+        }
+        else {
+            // TODO: We may not need to do the fetch if the predicates in root are covered.  But
+            // for now it's safe (though *maybe* slower).
+            FetchNode* fetch = new FetchNode();
+            fetch->filter.reset(filter);
+            fetch->children.push_back(isn);
+            solnRoot = fetch;
+        }
+
+        QuerySolution* soln = analyzeDataAccess(query, options, solnRoot);
+        verify(NULL != soln);
+        return soln;
+    }
+
     // static
     void QueryPlanner::plan(const CanonicalQuery& query, const vector<IndexEntry>& indices,
                             size_t options, vector<QuerySolution*>* out) {
-        QLOG() << "============================="
+        QLOG() << "=============================\n"
                << "Beginning planning.\n"
                << "query = " << query.toString()
                << "============================="
@@ -1081,7 +1219,7 @@ namespace mongo {
             if (!QueryPlannerCommon::hasNode(query.root(), MatchExpression::GEO_NEAR)
                 && canTableScan) {
 
-                out->push_back(makeCollectionScan(query, true));
+                out->push_back(makeCollectionScan(query, true, options));
             }
             return;
         }
@@ -1093,7 +1231,7 @@ namespace mongo {
             if (!natural.eoo()) {
                 QLOG() << "forcing a table scan due to hinted $natural\n";
                 if (canTableScan) {
-                    out->push_back(makeCollectionScan(query, false));
+                    out->push_back(makeCollectionScan(query, false, options));
                 }
                 return;
             }
@@ -1112,7 +1250,7 @@ namespace mongo {
             }
             QLOG() << "NOT/NOR in plan, just outtping a collscan\n";
             if (canTableScan) {
-                out->push_back(makeCollectionScan(query, false));
+                out->push_back(makeCollectionScan(query, false, options));
             }
             return;
         }
@@ -1253,11 +1391,7 @@ namespace mongo {
                 // only be first for gnNode.
                 tag->first.erase(tag->first.begin() + i);
 
-                QuerySolution* soln = new QuerySolution();
-                soln->root.reset(solnRoot);
-                soln->ns = query.ns();
-                soln->filterData = query.getQueryObj();
-                out->push_back(soln);
+                out->push_back(analyzeDataAccess(query, options, solnRoot));
             }
 
             // Continue planning w/non-2d indices tagged for this pred.
@@ -1294,7 +1428,7 @@ namespace mongo {
                 if (NULL == solnRoot) { continue; }
 
                 // This shouldn't ever fail.
-                QuerySolution* soln = analyzeDataAccess(query, solnRoot);
+                QuerySolution* soln = analyzeDataAccess(query, options, solnRoot);
                 verify(NULL != soln);
 
                 QLOG() << "Planner: adding solution:\n" << soln->toString() << endl;
@@ -1308,42 +1442,8 @@ namespace mongo {
         // scan the entire index to provide results and output that as our plan.  This is the
         // desired behavior when an index is hinted that is not relevant to the query.
         if (!hintIndex.isEmpty() && (0 == out->size())) {
-            QuerySolutionNode* solnRoot = NULL;
-
-            // Build an ixscan over the id index, use it, and return it.
-            IndexScanNode* isn = new IndexScanNode();
-            isn->indexKeyPattern = hintIndex;
-            isn->indexIsMultiKey = indices[hintIndexNumber].multikey;
-            isn->bounds.fields.resize(hintIndex.nFields());
-
-            // TODO: can we use simple bounds with this compound idx?
-            BSONObjIterator it(isn->indexKeyPattern);
-            int field = 0;
-            while (it.more()) {
-                IndexBoundsBuilder::allValuesForField(it.next(), &isn->bounds.fields[field]);
-                ++field;
-            }
-
-            MatchExpression* filter = query.root()->shallowClone();
-            // If it's find({}) remove the no-op root.
-            if (MatchExpression::AND == filter->matchType() && (0 == filter->numChildren())) {
-                delete filter;
-                solnRoot = isn;
-            }
-            else {
-                // TODO: We may not need to do the fetch if the predicates in root are covered.  But
-                // for now it's safe (though *maybe* slower).
-                FetchNode* fetch = new FetchNode();
-                fetch->filter.reset(filter);
-                fetch->child.reset(isn);
-                solnRoot = fetch;
-            }
-
-            QuerySolution* soln = analyzeDataAccess(query, solnRoot);
-            verify(NULL != soln);
-            out->push_back(soln);
-
-            QLOG() << "Planner: using hinted index as scan, soln = " << soln->toString() << endl;
+            QLOG() << "Planner: outputting soln that uses hinted index as scan." << endl;
+            out->push_back(scanWholeIndex(indices[hintIndexNumber], options, query));
             return;
         }
 
@@ -1367,30 +1467,10 @@ namespace mongo {
             if (!usingIndexToSort) {
                 for (size_t i = 0; i < indices.size(); ++i) {
                     const BSONObj& kp = indices[i].keyPattern;
-                    if (0 == kp.woCompare(query.getParsed().getSort())) {
-                        IndexScanNode* isn = new IndexScanNode();
-                        isn->indexKeyPattern = kp;
-                        isn->indexIsMultiKey = indices[i].multikey;
-                        isn->bounds.fields.resize(kp.nFields());
-
-                        // TODO: can we use simple bounds if compound?
-                        BSONObjIterator it(isn->indexKeyPattern);
-                        size_t field = 0;
-                        while (it.more()) {
-                            IndexBoundsBuilder::allValuesForField(it.next(),
-                                                                  &isn->bounds.fields[field]);
-                        }
-
-                        // TODO: We may not need to do the fetch if the predicates in root are
-                        // covered.  But for now it's safe (though *maybe* slower).
-                        FetchNode* fetch = new FetchNode();
-                        fetch->filter.reset(query.root()->shallowClone());
-                        fetch->child.reset(isn);
-
-                        QuerySolution* soln = analyzeDataAccess(query, fetch);
-                        verify(NULL != soln);
-                        out->push_back(soln);
-                        QLOG() << "Planner: using index to provide sort, soln = " << soln->toString() << endl;
+                    if (providesSort(query, kp)) {
+                        QLOG() << "Planner: outputting soln that uses index to provide sort."
+                               << endl;
+                        out->push_back(scanWholeIndex(indices[i], options, query));
                         break;
                     }
                 }
@@ -1403,10 +1483,28 @@ namespace mongo {
              && !QueryPlannerCommon::hasNode(query.root(), MatchExpression::TEXT)
              && ((options & QueryPlanner::INCLUDE_COLLSCAN) || (0 == out->size() && canTableScan)))
         {
-            QuerySolution* collscan = makeCollectionScan(query, false);
+            QuerySolution* collscan = makeCollectionScan(query, false, options);
             out->push_back(collscan);
-            QLOG() << "Planner: outputting a collscan\n";
+            QLOG() << "Planner: outputting a collscan:\n";
+            QLOG() << collscan->toString() << endl;
         }
     }
 
+    // static
+    bool QueryPlanner::providesSort(const CanonicalQuery& query, const BSONObj& kp) {
+        BSONObjIterator sortIt(query.getParsed().getSort());
+        BSONObjIterator kpIt(kp);
+
+        while (sortIt.more() && kpIt.more()) {
+            // We want the field name to be the same as well (so we pass true).
+            // TODO: see if we can pull a reverse sort out...
+            if (0 != sortIt.next().woCompare(kpIt.next(), true)) {
+                return false;
+            }
+        }
+
+        // every elt in sort matched kp
+        return !sortIt.more();
+    }
+
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_planner.h b/src/mongo/db/query/query_planner.h
index 3bb7409c511..26e4293459b 100644
--- a/src/mongo/db/query/query_planner.h
+++ b/src/mongo/db/query/query_planner.h
@@ -120,7 +120,7 @@ namespace mongo {
         /**
          * Return a CollectionScanNode that scans as requested in 'query'.
          */
-        static QuerySolution* makeCollectionScan(const CanonicalQuery& query, bool tailable);
+        static QuerySolution* makeCollectionScan(const CanonicalQuery& query, bool tailable, size_t options);
 
         //
         // Indexed Data Access methods.
@@ -209,6 +209,15 @@ namespace mongo {
         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
         //
 
@@ -227,7 +236,28 @@ namespace mongo {
          * Caller owns the returned QuerySolution.
          */
         static QuerySolution* analyzeDataAccess(const CanonicalQuery& query,
+                                                size_t options,
                                                 QuerySolutionNode* solnRoot);
+
+        /**
+         * Return a plan that uses the provided index as a proxy for a collection scan.
+         */
+        static QuerySolution* scanWholeIndex(const IndexEntry& index, size_t options,
+                                             const CanonicalQuery& query);
+
+        /**
+         * XXX
+         */
+        static void reverseScans(QuerySolutionNode* root);
+
+        /**
+         * Assumes each OIL in bounds is increasing.
+         *
+         * Aligns OILs (and bounds) according to the kp direction * the scanDir.
+         */
+        static void alignBounds(IndexBounds* bounds, const BSONObj& kp, int scanDir = 1);
+
+        static bool providesSort(const CanonicalQuery& query, const BSONObj& kp);
     };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index 4e732e1d6f1..b75ae100a4f 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -30,6 +30,32 @@
 
 namespace mongo {
 
+    string QuerySolutionNode::toString() const {
+        stringstream ss;
+        appendToString(&ss, 0);
+        return ss.str();
+    }
+
+    // static
+    void QuerySolutionNode::addIndent(stringstream* ss, int level) {
+        for (int i = 0; i < level; ++i) {
+            *ss << "---";
+        }
+    }
+
+    void QuerySolutionNode::addCommon(stringstream* ss, int indent) const {
+        addIndent(ss, indent + 1);
+        *ss << "fetched = " << fetched() << endl;
+        addIndent(ss, indent + 1);
+        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
+        addIndent(ss, indent + 1);
+        *ss << "getSort = [";
+        for (BSONObjSet::const_iterator it = getSort().begin(); it != getSort().end(); it++) {
+            *ss << it->toString() << ", ";
+        }
+        *ss << "]" << endl;
+    }
+
     //
     // TextNode
     //
@@ -42,22 +68,17 @@ namespace mongo {
         addIndent(ss, indent + 1);
         *ss << "keyPattern = " << _indexKeyPattern.toString() << endl;
         addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
-        addIndent(ss, indent + 1);
         *ss << "query = " << _query << endl;
         addIndent(ss, indent + 1);
         *ss << "language = " << _language << endl;
+        addCommon(ss, indent);
     }
 
     //
     // CollectionScanNode
     //
 
-    CollectionScanNode::CollectionScanNode() : tailable(false), direction(1), filter(NULL) { }
+    CollectionScanNode::CollectionScanNode() : tailable(false), direction(1) { }
 
     void CollectionScanNode::appendToString(stringstream* ss, int indent) const {
         addIndent(ss, indent);
@@ -68,19 +89,14 @@ namespace mongo {
             addIndent(ss, indent + 1);
             *ss << " filter = " << filter->toString();
         }
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
+        addCommon(ss, indent);
     }
 
     //
     // AndHashNode
     //
 
-    AndHashNode::AndHashNode() : filter(NULL) { }
+    AndHashNode::AndHashNode() { }
 
     AndHashNode::~AndHashNode() {
         for (size_t i = 0; i < children.size(); ++i) {
@@ -95,12 +111,7 @@ namespace mongo {
             addIndent(ss, indent + 1);
             *ss << " filter = " << filter->toString() << endl;
         }
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
+        addCommon(ss, indent);
         for (size_t i = 0; i < children.size(); ++i) {
             addIndent(ss, indent + 1);
             *ss << "Child " << i << ":\n";
@@ -134,7 +145,7 @@ namespace mongo {
     // AndSortedNode
     //
 
-    AndSortedNode::AndSortedNode() : filter(NULL) { }
+    AndSortedNode::AndSortedNode() { }
 
     AndSortedNode::~AndSortedNode() {
         for (size_t i = 0; i < children.size(); ++i) {
@@ -149,12 +160,7 @@ namespace mongo {
             addIndent(ss, indent + 1);
             *ss << " filter = " << filter->toString() << endl;
         }
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
+        addCommon(ss, indent);
         for (size_t i = 0; i < children.size(); ++i) {
             *ss << "Child " << i << ": ";
             children[i]->appendToString(ss, indent + 1);
@@ -187,7 +193,7 @@ namespace mongo {
     // OrNode
     //
 
-    OrNode::OrNode() : dedup(true), filter(NULL) { }
+    OrNode::OrNode() : dedup(true) { }
 
     OrNode::~OrNode() {
         for (size_t i = 0; i < children.size(); ++i) {
@@ -202,12 +208,7 @@ namespace mongo {
             addIndent(ss, indent + 1);
             *ss << " filter = " << filter->toString() << endl;
         }
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
+        addCommon(ss, indent);
         for (size_t i = 0; i < children.size(); ++i) {
             addIndent(ss, indent + 1);
             *ss << "Child " << i << ":\n";
@@ -246,7 +247,7 @@ namespace mongo {
     // MergeSortNode
     //
 
-    MergeSortNode::MergeSortNode() : dedup(true), filter(NULL) { }
+    MergeSortNode::MergeSortNode() : dedup(true) { }
 
     MergeSortNode::~MergeSortNode() {
         for (size_t i = 0; i < children.size(); ++i) {
@@ -261,12 +262,7 @@ namespace mongo {
             addIndent(ss, indent + 1);
             *ss << " filter = " << filter->toString() << endl;
         }
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
+        addCommon(ss, indent);
         for (size_t i = 0; i < children.size(); ++i) {
             addIndent(ss, indent + 1);
             *ss << "Child " << i << ":\n";
@@ -305,7 +301,7 @@ namespace mongo {
     // FetchNode
     //
 
-    FetchNode::FetchNode() : filter(NULL) { }
+    FetchNode::FetchNode() { }
 
     void FetchNode::appendToString(stringstream* ss, int indent) const {
         addIndent(ss, indent);
@@ -317,15 +313,10 @@ namespace mongo {
             filter->debugString(sb, indent + 2);
             *ss << sb.str();
         }
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
+        addCommon(ss, indent);
         addIndent(ss, indent + 1);
         *ss << "Child:" << endl;
-        child->appendToString(ss, indent + 2);
+        children[0]->appendToString(ss, indent + 2);
     }
 
     //
@@ -333,7 +324,7 @@ namespace mongo {
     //
 
     IndexScanNode::IndexScanNode()
-        : indexIsMultiKey(false), filter(NULL), limit(0), direction(1) { }
+        : indexIsMultiKey(false), limit(0), direction(1) { }
 
     void IndexScanNode::appendToString(stringstream* ss, int indent) const {
         addIndent(ss, indent);
@@ -350,10 +341,7 @@ namespace mongo {
         *ss << "bounds = " << bounds.toString() << endl;
         addIndent(ss, indent + 1);
         *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
+        addCommon(ss, indent);
     }
 
     bool IndexScanNode::hasField(const string& field) const {
@@ -395,6 +383,66 @@ namespace mongo {
         return true;
     }
 
+    void IndexScanNode::computeProperties() {
+        _sorts.clear();
+
+        BSONObj sortPattern;
+        {
+            BSONObjBuilder sortBob;
+            BSONObjIterator it(indexKeyPattern);
+            while (it.more()) {
+                BSONElement elt = it.next();
+                // Zero is returned if elt is not a number.  This happens when elt is hashed or
+                // 2dsphere, our two projection indices.  We want to drop those from the sort
+                // pattern.
+                int val = elt.numberInt() * direction;
+                if (0 != val) {
+                    sortBob.append(elt.fieldName(), val);
+                }
+            }
+            sortPattern = sortBob.obj();
+        }
+        _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());
+            }
+            _sorts.insert(prefixBob.obj());
+        }
+
+        // If we are using the index {a:1, b:1} to answer the predicate {a: 10}, it's sorted
+        // both by the index key pattern and by the pattern {b: 1}.
+
+        // See if there are any fields with equalities for bounds.  We can drop these
+        // from any sort orders created.
+        set<string> equalityFields;
+        if (!bounds.isSimpleRange) {
+            // Figure out how many fields are point intervals.
+            for (size_t i = 0; i < bounds.fields.size(); ++i) {
+                const OrderedIntervalList& oil = bounds.fields[i];
+                if (oil.intervals.size() != 1) {
+                    continue;
+                }
+                const Interval& ival = oil.intervals[0];
+                if (!ival.isPoint()) {
+                    continue;
+                }
+                equalityFields.insert(oil.name);
+            }
+        }
+
+        // TODO: Each field in equalityFields could be dropped from the sort order since it is
+        // a point interval.
+        // For each sort in _sorts:
+        //    For each drop in powerset(equalityFields):
+        //        Remove fields in 'drop' from 'sort' and add resulting sort to output.
+    }
+
     //
     // ProjectionNode
     //
@@ -405,15 +453,9 @@ namespace mongo {
         verify(NULL != projection);
         addIndent(ss, indent + 1);
         *ss << "proj = " << projection->toString() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
-        addIndent(ss, indent + 1);
+        addCommon(ss, indent);
         *ss << "Child:" << endl;
-        child->appendToString(ss, indent + 2);
+        children[0]->appendToString(ss, indent + 2);
     }
 
     //
@@ -425,15 +467,9 @@ namespace mongo {
         *ss << "SORT\n";
         addIndent(ss, indent + 1);
         *ss << "pattern = " << pattern.toString() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
-        addIndent(ss, indent + 1);
+        addCommon(ss, indent);
         *ss << "Child:" << endl;
-        child->appendToString(ss, indent + 2);
+        children[0]->appendToString(ss, indent + 2);
     }
 
     //
@@ -447,14 +483,9 @@ namespace mongo {
         addIndent(ss, indent + 1);
         *ss << "limit = " << limit << endl;
         addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
-        addIndent(ss, indent + 1);
+        addCommon(ss, indent);
         *ss << "Child:" << endl;
-        child->appendToString(ss, indent + 2);
+        children[0]->appendToString(ss, indent + 2);
     }
 
     //
@@ -466,15 +497,9 @@ namespace mongo {
         *ss << "SKIP\n";
         addIndent(ss, indent + 1);
         *ss << "skip= " << skip << endl;
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
-        addIndent(ss, indent + 1);
+        addCommon(ss, indent);
         *ss << "Child:" << endl;
-        child->appendToString(ss, indent + 2);
+        children[0]->appendToString(ss, indent + 2);
     }
 
     //
@@ -486,13 +511,7 @@ namespace mongo {
         *ss << "GEO_NEAR_2D\n";
         addIndent(ss, indent + 1);
         *ss << "keyPattern = " << indexKeyPattern.toString() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
-        addIndent(ss, indent + 1);
+        addCommon(ss, indent);
         *ss << "nearQuery = " << nq.toString() << endl;
         if (NULL != filter) {
             addIndent(ss, indent + 1);
@@ -509,13 +528,7 @@ namespace mongo {
         *ss << "GEO_NEAR_2DSPHERE\n";
         addIndent(ss, indent + 1);
         *ss << "keyPattern = " << indexKeyPattern.toString() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
-        addIndent(ss, indent + 1);
+        addCommon(ss, indent);
         *ss << "baseBounds = " << baseBounds.toString() << endl;
         addIndent(ss, indent + 1);
         *ss << "nearQuery = " << nq.toString() << endl;
@@ -534,14 +547,7 @@ namespace mongo {
         *ss << "GEO_2D\n";
         addIndent(ss, indent + 1);
         *ss << "keyPattern = " << indexKeyPattern.toString() << endl;
-        addIndent(ss, indent + 1);
-        //*ss << "seek = " << seek.toString() << endl;
-        //addIndent(ss, indent + 1);
-        *ss << "fetched = " << fetched() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "sortedByDiskLoc = " << sortedByDiskLoc() << endl;
-        addIndent(ss, indent + 1);
-        *ss << "getSort = " << getSort().toString() << endl;
+        addCommon(ss, indent);
     }
 
     bool Geo2DNode::hasField(const string& field) const {
diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h
index 375b9629e52..f407b64c584 100644
--- a/src/mongo/db/query/query_solution.h
+++ b/src/mongo/db/query/query_solution.h
@@ -28,6 +28,7 @@
 
 #pragma once
 
+#include "mongo/db/jsobj.h"
 #include "mongo/db/matcher/expression.h"
 #include "mongo/db/geo/geoquery.h"
 #include "mongo/db/fts/fts_query.h"
@@ -48,16 +49,15 @@ namespace mongo {
         virtual ~QuerySolutionNode() { }
 
         /**
+         * Return a string representation of this node and any children.
+         */
+        string toString() const;
+
+        /**
          * What stage should this be transcribed to?  See stage_types.h.
          */
         virtual StageType getType() const = 0;
 
-        string toString() const {
-            stringstream ss;
-            appendToString(&ss, 0);
-            return ss.str();
-        }
-
         /**
          * Internal function called by toString()
          *
@@ -65,6 +65,19 @@ namespace mongo {
          */
         virtual void appendToString(stringstream* ss, int indent) const = 0;
 
+        //
+        // Computed properties
+        //
+
+        /**
+         * Must be called before any properties are examined.
+         */
+        virtual void computeProperties() {
+            for (size_t i = 0; i < children.size(); ++i) {
+                children[i]->computeProperties();
+            }
+        }
+
         /**
          * If true, one of these are true:
          *          1. All outputs are already fetched, or
@@ -98,24 +111,31 @@ namespace mongo {
         virtual bool sortedByDiskLoc() const = 0;
 
         /**
-         * Return a BSONObj representing the sort order of the data stream from this node.  If the data
-         * is not sorted in any particular fashion, returns BSONObj().
-         *
-         * TODO: Is BSONObj really the best way to represent this?
+         * Return a BSONObjSet representing the possible sort orders of the data stream from this
+         * node.  If the data is not sorted in any particular fashion, returns an empty set.
          *
          * Usage:
          * 1. If our plan gives us a sort order, we don't have to add a sort stage.
          * 2. If all the children of an OR have the same sort order, we can maintain that
          *    sort order with a STAGE_SORT_MERGE instead of STAGE_OR.
          */
-        virtual BSONObj getSort() const = 0;
+        virtual const BSONObjSet& getSort() const = 0;
+
+        vector<QuerySolutionNode*> children;
+
+        scoped_ptr<MatchExpression> filter;
 
     protected:
-        static void addIndent(stringstream* ss, int level) {
-            for (int i = 0; i < level; ++i) {
-                *ss << "---";
-            }
-        }
+        /**
+         * Formatting helper used by toString().
+         */
+        static void addIndent(stringstream* ss, int level);
+
+        /**
+         * Every solution node has properties and this adds the debug info for the
+         * properties.
+         */
+        void addCommon(stringstream* ss, int indent) const;
 
     private:
         MONGO_DISALLOW_COPYING(QuerySolutionNode);
@@ -169,13 +189,14 @@ namespace mongo {
         bool fetched() const { return false; }
         bool hasField(const string& field) const { return false; }
         bool sortedByDiskLoc() const { return false; }
-        BSONObj getSort() const { return _indexKeyPattern; }
+        const BSONObjSet& getSort() const { return _sort; }
+
+        BSONObjSet _sort;
 
         uint32_t _numWanted;
         BSONObj  _indexKeyPattern;
         std::string _query;
         std::string _language;
-        scoped_ptr<MatchExpression> _filter;
     };
 
     struct CollectionScanNode : public QuerySolutionNode {
@@ -189,7 +210,9 @@ namespace mongo {
         bool fetched() const { return true; }
         bool hasField(const string& field) const { return true; }
         bool sortedByDiskLoc() const { return false; }
-        BSONObj getSort() const { return BSONObj(); }
+        const BSONObjSet& getSort() const { return _sort; }
+
+        BSONObjSet _sort;
 
         // Name of the namespace.
         string name;
@@ -198,8 +221,6 @@ namespace mongo {
         bool tailable;
 
         int direction;
-
-        scoped_ptr<MatchExpression> filter;
     };
 
     struct AndHashNode : public QuerySolutionNode {
@@ -213,10 +234,9 @@ namespace mongo {
         bool fetched() const;
         bool hasField(const string& field) const;
         bool sortedByDiskLoc() const { return false; }
-        BSONObj getSort() const { return BSONObj(); }
+        const BSONObjSet& getSort() const { return _sort; }
 
-        scoped_ptr<MatchExpression> filter;
-        vector<QuerySolutionNode*> children;
+        BSONObjSet _sort;
     };
 
     struct AndSortedNode : public QuerySolutionNode {
@@ -230,10 +250,9 @@ namespace mongo {
         bool fetched() const;
         bool hasField(const string& field) const;
         bool sortedByDiskLoc() const { return true; }
-        BSONObj getSort() const { return BSONObj(); }
+        const BSONObjSet& getSort() const { return _sort; }
 
-        scoped_ptr<MatchExpression> filter;
-        vector<QuerySolutionNode*> children;
+        BSONObjSet _sort;
     };
 
     struct OrNode : public QuerySolutionNode {
@@ -251,12 +270,11 @@ namespace mongo {
             // any order on the output.
             return false;
         }
-        BSONObj getSort() const { return BSONObj(); }
+        const BSONObjSet& getSort() const { return _sort; }
+
+        BSONObjSet _sort;
 
         bool dedup;
-        // XXX why is this here
-        scoped_ptr<MatchExpression> filter;
-        vector<QuerySolutionNode*> children;
     };
 
     struct MergeSortNode : public QuerySolutionNode {
@@ -270,13 +288,21 @@ namespace mongo {
         bool fetched() const;
         bool hasField(const string& field) const;
         bool sortedByDiskLoc() const { return false; }
-        BSONObj getSort() const { return sort; }
+
+        const BSONObjSet& getSort() const { return _sorts; }
+
+        virtual void computeProperties() {
+            for (size_t i = 0; i < children.size(); ++i) {
+                children[i]->computeProperties();
+            }
+            _sorts.clear();
+            _sorts.insert(sort);
+        }
+
+        BSONObjSet _sorts;
 
         BSONObj sort;
         bool dedup;
-        // XXX why is this here
-        scoped_ptr<MatchExpression> filter;
-        vector<QuerySolutionNode*> children;
     };
 
     struct FetchNode : public QuerySolutionNode {
@@ -289,17 +315,18 @@ namespace mongo {
 
         bool fetched() const { return true; }
         bool hasField(const string& field) const { return true; }
-        bool sortedByDiskLoc() const { return child->sortedByDiskLoc(); }
-        BSONObj getSort() const { return child->getSort(); }
+        bool sortedByDiskLoc() const { return children[0]->sortedByDiskLoc(); }
+        const BSONObjSet& getSort() const { return children[0]->getSort(); }
 
-        scoped_ptr<MatchExpression> filter;
-        scoped_ptr<QuerySolutionNode> child;
+        BSONObjSet _sorts;
     };
 
     struct IndexScanNode : public QuerySolutionNode {
         IndexScanNode();
         virtual ~IndexScanNode() { }
 
+        virtual void computeProperties();
+
         virtual StageType getType() const { return STAGE_IXSCAN; }
 
         virtual void appendToString(stringstream* ss, int indent) const;
@@ -307,26 +334,13 @@ namespace mongo {
         bool fetched() const { return false; }
         bool hasField(const string& field) const;
         bool sortedByDiskLoc() const;
+        const BSONObjSet& getSort() const { return _sorts; }
 
-        // XXX: We need a better way of dealing with sorting and equalities on a prefix of the key
-        // pattern.  If we are using the index {a:1, b:1} to answer the predicate {a: 10}, it's
-        // sorted both by the index key pattern and by the pattern {b: 1}.  How do we expose this?
-        // Perhaps migrate to sortedBy(...) instead of getSort().  In this case, the ixscan can
-        // return true for both of those sort orders.
-        //
-
-        // This doesn't work for detecting that we can use a merge sort, though.  Perhaps we should
-        // just pick one sort order and miss out on the other case?  For the golden query we want
-        // our sort order to be {b: 1}.
-
-        BSONObj getSort() const { return indexKeyPattern; }
+        BSONObjSet _sorts;
 
         BSONObj indexKeyPattern;
-
         bool indexIsMultiKey;
 
-        scoped_ptr<MatchExpression> filter;
-
         // Only set for 2d.
         int limit;
 
@@ -364,39 +378,51 @@ namespace mongo {
             //
             // Perhaps this should be false to not imply that there *is* a DiskLoc?  Kind of a
             // corner case.
-            return child->sortedByDiskLoc();
+            return children[0]->sortedByDiskLoc();
         }
 
-        BSONObj getSort() const {
+        const BSONObjSet& getSort() const {
             // TODO: If we're applying a projection that maintains sort order, the prefix of the
             // sort order we project is the sort order.
-            return BSONObj();
+            return _sorts;
         }
 
+        BSONObjSet _sorts;
+
         // Points into the CanonicalQuery.
         ParsedProjection* projection;
-
-        scoped_ptr<QuerySolutionNode> child;
-
-        // TODO: Filter
     };
 
     struct SortNode : public QuerySolutionNode {
-        SortNode() { }
+        SortNode() : hasBounds(false) { }
         virtual ~SortNode() { }
 
         virtual StageType getType() const { return STAGE_SORT; }
 
         virtual void appendToString(stringstream* ss, int indent) const;
-        
-        bool fetched() const { return child->fetched(); }
-        bool hasField(const string& field) const { return child->hasField(field); }
+
+        bool fetched() const { return children[0]->fetched(); }
+        bool hasField(const string& field) const { return children[0]->hasField(field); }
         bool sortedByDiskLoc() const { return false; }
-        BSONObj getSort() const { return pattern; }
+
+        const BSONObjSet& getSort() const { return _sorts; }
+
+        virtual void computeProperties() {
+            for (size_t i = 0; i < children.size(); ++i) {
+                children[i]->computeProperties();
+            }
+            _sorts.clear();
+            _sorts.insert(pattern);
+        }
+
+        BSONObjSet _sorts;
 
         BSONObj pattern;
-        scoped_ptr<QuerySolutionNode> child;
-        // TODO: Filter
+
+        bool hasBounds;
+
+        // XXX
+        IndexBounds bounds;
     };
 
     struct LimitNode : public QuerySolutionNode {
@@ -407,13 +433,12 @@ namespace mongo {
 
         virtual void appendToString(stringstream* ss, int indent) const;
 
-        bool fetched() const { return child->fetched(); }
-        bool hasField(const string& field) const { return child->hasField(field); }
-        bool sortedByDiskLoc() const { return child->sortedByDiskLoc(); }
-        BSONObj getSort() const { return child->getSort(); }
+        bool fetched() const { return children[0]->fetched(); }
+        bool hasField(const string& field) const { return children[0]->hasField(field); }
+        bool sortedByDiskLoc() const { return children[0]->sortedByDiskLoc(); }
+        const BSONObjSet& getSort() const { return children[0]->getSort(); }
 
         int limit;
-        scoped_ptr<QuerySolutionNode> child;
     };
 
     struct SkipNode : public QuerySolutionNode {
@@ -423,13 +448,12 @@ namespace mongo {
         virtual StageType getType() const { return STAGE_SKIP; }
         virtual void appendToString(stringstream* ss, int indent) const;
 
-        bool fetched() const { return child->fetched(); }
-        bool hasField(const string& field) const { return child->hasField(field); }
-        bool sortedByDiskLoc() const { return child->sortedByDiskLoc(); }
-        BSONObj getSort() const { return child->getSort(); }
+        bool fetched() const { return children[0]->fetched(); }
+        bool hasField(const string& field) const { return children[0]->hasField(field); }
+        bool sortedByDiskLoc() const { return children[0]->sortedByDiskLoc(); }
+        const BSONObjSet& getSort() const { return children[0]->getSort(); }
 
         int skip;
-        scoped_ptr<QuerySolutionNode> child;
     };
 
     //
@@ -448,13 +472,11 @@ namespace mongo {
         bool fetched() const { return false; }
         bool hasField(const string& field) const;
         bool sortedByDiskLoc() const { return false; }
-        BSONObj getSort() const { return BSONObj(); }
+        const BSONObjSet& getSort() const { return _sorts; }
+        BSONObjSet _sorts;
 
         BSONObj indexKeyPattern;
         GeoQuery gq;
-
-        // TODO: Actually try to use this for covering
-        scoped_ptr<MatchExpression> filter;
     };
 
     // This is a standalone stage.
@@ -468,10 +490,10 @@ namespace mongo {
         bool fetched() const { return true; }
         bool hasField(const string& field) const { return true; }
         bool sortedByDiskLoc() const { return false; }
-        BSONObj getSort() const { return BSONObj(); }
+        const BSONObjSet& getSort() const { return _sorts; }
+        BSONObjSet _sorts;
 
         NearQuery nq;
-        scoped_ptr<MatchExpression> filter;
         int numWanted;
         BSONObj indexKeyPattern;
     };
@@ -487,14 +509,14 @@ namespace mongo {
         bool fetched() const { return true; }
         bool hasField(const string& field) const { return true; }
         bool sortedByDiskLoc() const { return false; }
-        BSONObj getSort() const { return BSONObj(); }
+        const BSONObjSet& getSort() const { return _sorts; }
+
+        BSONObjSet _sorts;
 
         NearQuery nq;
         IndexBounds baseBounds;
 
         BSONObj indexKeyPattern;
-        scoped_ptr<MatchExpression> filter;
     };
 
-
 }  // namespace mongo
diff --git a/src/mongo/db/query/stage_builder.cpp b/src/mongo/db/query/stage_builder.cpp
index 1536a289fe3..253d37a641d 100644
--- a/src/mongo/db/query/stage_builder.cpp
+++ b/src/mongo/db/query/stage_builder.cpp
@@ -90,33 +90,35 @@ namespace mongo {
         }
         else if (STAGE_FETCH == root->getType()) {
             const FetchNode* fn = static_cast<const FetchNode*>(root);
-            PlanStage* childStage = buildStages(ns, fn->child.get(), ws);
+            PlanStage* childStage = buildStages(ns, fn->children[0], ws);
             if (NULL == childStage) { return NULL; }
             return new FetchStage(ws, childStage, fn->filter.get());
         }
         else if (STAGE_SORT == root->getType()) {
             const SortNode* sn = static_cast<const SortNode*>(root);
-            PlanStage* childStage = buildStages(ns, sn->child.get(), ws);
+            PlanStage* childStage = buildStages(ns, sn->children[0], ws);
             if (NULL == childStage) { return NULL; }
             SortStageParams params;
             params.pattern = sn->pattern;
+            params.bounds = sn->bounds;
+            params.hasBounds = sn->hasBounds;
             return new SortStage(params, ws, childStage);
         }
         else if (STAGE_PROJECTION == root->getType()) {
             const ProjectionNode* pn = static_cast<const ProjectionNode*>(root);
-            PlanStage* childStage = buildStages(ns, pn->child.get(), ws);
+            PlanStage* childStage = buildStages(ns, pn->children[0], ws);
             if (NULL == childStage) { return NULL; }
             return new ProjectionStage(pn->projection, ws, childStage, NULL);
         }
         else if (STAGE_LIMIT == root->getType()) {
             const LimitNode* ln = static_cast<const LimitNode*>(root);
-            PlanStage* childStage = buildStages(ns, ln->child.get(), ws);
+            PlanStage* childStage = buildStages(ns, ln->children[0], ws);
             if (NULL == childStage) { return NULL; }
             return new LimitStage(ln->limit, ws, childStage);
         }
         else if (STAGE_SKIP == root->getType()) {
             const SkipNode* sn = static_cast<const SkipNode*>(root);
-            PlanStage* childStage = buildStages(ns, sn->child.get(), ws);
+            PlanStage* childStage = buildStages(ns, sn->children[0], ws);
             if (NULL == childStage) { return NULL; }
             return new SkipStage(sn->skip, ws, childStage);
         }
@@ -219,7 +221,7 @@ namespace mongo {
             if (!parseStatus.isOK()) { return NULL; }
             params.query = ftsq;
 
-            return new TextStage(params, ws, node->_filter.get());
+            return new TextStage(params, ws, node->filter.get());
         }
         else {
             stringstream ss;