SERVER-10471 covering and sort analysis. split projection parse from exec

17 files changed, 556 insertions, 208 deletions

diff --git a/src/mongo/db/exec/SConscript b/src/mongo/db/exec/SConscript
index 9b974356f90..96ab04eccea 100644
--- a/src/mongo/db/exec/SConscript
+++ b/src/mongo/db/exec/SConscript
@@ -44,13 +44,13 @@ env.StaticLibrary(
         "merge_sort.cpp",
         "or.cpp",
         "projection.cpp",
-        "query_projection.cpp",
+        "projection_executor.cpp",
         "skip.cpp",
         "sort.cpp",
         "stagedebug_cmd.cpp",
         "working_set_common.cpp",
     ],
     LIBDEPS = [
-        "$BUILD_DIR/mongo/bson"
+        "$BUILD_DIR/mongo/bson",
     ],
 )
diff --git a/src/mongo/db/exec/projection.cpp b/src/mongo/db/exec/projection.cpp
index f7e0edde052..fc2b81f6604 100644
--- a/src/mongo/db/exec/projection.cpp
+++ b/src/mongo/db/exec/projection.cpp
@@ -26,16 +26,18 @@
  *    it in the license file.
  */
 
+#include "mongo/db/exec/projection.h"
+
 #include "mongo/db/diskloc.h"
 #include "mongo/db/exec/plan_stage.h"
-#include "mongo/db/exec/projection.h"
+#include "mongo/db/exec/projection_executor.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/matcher/expression.h"
 
 namespace mongo {
 
-    ProjectionStage::ProjectionStage(QueryProjection* projection, WorkingSet* ws, PlanStage* child,
-                    const MatchExpression* filter)
+    ProjectionStage::ProjectionStage(ParsedProjection* projection, WorkingSet* ws, PlanStage* child,
+                                     const MatchExpression* filter)
         : _projection(projection), _ws(ws), _child(child), _filter(filter) { }
 
     ProjectionStage::~ProjectionStage() { }
@@ -51,7 +53,7 @@ namespace mongo {
 
         if (PlanStage::ADVANCED == status) {
             WorkingSetMember* member = _ws->get(id);
-            Status status = _projection->project(member);
+            Status status = ProjectionExecutor::apply(_projection, member);
             if (!status.isOK()) { return PlanStage::FAILURE; }
             *out = id;
         }
diff --git a/src/mongo/db/exec/projection.h b/src/mongo/db/exec/projection.h
index ade2bbfab84..284c7e05956 100644
--- a/src/mongo/db/exec/projection.h
+++ b/src/mongo/db/exec/projection.h
@@ -30,9 +30,9 @@
 
 #include "mongo/db/diskloc.h"
 #include "mongo/db/exec/plan_stage.h"
-#include "mongo/db/exec/query_projection.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/matcher/expression.h"
+#include "mongo/db/query/parsed_projection.h"
 
 namespace mongo {
 
@@ -41,7 +41,7 @@ namespace mongo {
      */
     class ProjectionStage : public PlanStage {
     public:
-        ProjectionStage(QueryProjection* projection, WorkingSet* ws, PlanStage* child,
+        ProjectionStage(ParsedProjection* projection, WorkingSet* ws, PlanStage* child,
                         const MatchExpression* filter);
         virtual ~ProjectionStage();
 
@@ -55,7 +55,8 @@ namespace mongo {
         PlanStageStats* getStats();
 
     private:
-        scoped_ptr<QueryProjection> _projection;
+        // Not owned by us.
+        ParsedProjection* _projection;
 
         // _ws is not owned by us.
         WorkingSet* _ws;
diff --git a/src/mongo/db/exec/projection_executor.cpp b/src/mongo/db/exec/projection_executor.cpp
new file mode 100644
index 00000000000..f6d1bc707d2
--- /dev/null
+++ b/src/mongo/db/exec/projection_executor.cpp
@@ -0,0 +1,96 @@
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/db/exec/projection_executor.h"
+
+#include "mongo/db/exec/working_set.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/db/query/parsed_projection.h"
+#include "mongo/util/mongoutils/str.h"
+
+namespace mongo {
+
+    // static
+    Status ProjectionExecutor::apply(const ParsedProjection* proj, WorkingSetMember* wsm) {
+        if (ParsedProjection::FIND_SYNTAX == proj->getType()) {
+            return applyFindSyntax(static_cast<const FindProjection*>(proj), wsm);
+        }
+        else {
+            return Status(ErrorCodes::BadValue, "trying to apply unknown projection type");
+        }
+    }
+
+    // static
+    Status ProjectionExecutor::applyFindSyntax(const FindProjection* proj, WorkingSetMember* wsm) {
+        BSONObjBuilder bob;
+        if (proj->_includeID) {
+            BSONElement elt;
+            if (!wsm->getFieldDotted("_id", &elt)) {
+                return Status(ErrorCodes::BadValue, "Couldn't get _id field in proj");
+            }
+            bob.append(elt);
+        }
+
+        if (proj->_includedFields.size() > 0) {
+            // We only want stuff in _fields.
+            const vector<string>& fields = proj->_includedFields;
+            for (size_t i = 0; i < fields.size(); ++i) {
+                BSONElement elt;
+                // We can project a field that doesn't exist.  We just ignore it.
+                // UNITTEST 11738048
+                if (wsm->getFieldDotted(fields[i], &elt) && !elt.eoo()) {
+                    bob.append(elt);
+                }
+            }
+        }
+        else {
+            // We want stuff NOT in _fields.  This can't be covered, so we expect an obj.
+            if (!wsm->hasObj()) {
+                return Status(ErrorCodes::BadValue,
+                        "exclusion specified for projection but no obj to iter over");
+            }
+            const unordered_set<string>& fields = proj->_excludedFields;
+            BSONObjIterator it(wsm->obj);
+            while (it.more()) {
+                BSONElement elt = it.next();
+                if (!mongoutils::str::equals("_id", elt.fieldName())) {
+                    if (fields.end() == fields.find(elt.fieldName())) {
+                        bob.append(elt);
+                    }
+                }
+            }
+        }
+
+        wsm->state = WorkingSetMember::OWNED_OBJ;
+        wsm->obj = bob.obj();
+        wsm->keyData.clear();
+        wsm->loc = DiskLoc();
+        return Status::OK();
+    }
+
+}  // namespace mongo
diff --git a/src/mongo/db/exec/projection_executor.h b/src/mongo/db/exec/projection_executor.h
new file mode 100644
index 00000000000..ab1fb40fae0
--- /dev/null
+++ b/src/mongo/db/exec/projection_executor.h
@@ -0,0 +1,53 @@
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#pragma once
+
+#include "mongo/db/exec/working_set.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/db/query/parsed_projection.h"
+
+namespace mongo {
+
+    /**
+     * Executes a pre-parsed projection.
+     *
+     * TODO: Add unit test.
+     */
+    class ProjectionExecutor {
+    public:
+        /**
+         * Compute the projection over the WSM.  Place the output in the provided WSM.
+         */
+        static Status apply(const ParsedProjection* proj, WorkingSetMember* wsm);
+
+    private:
+        static Status applyFindSyntax(const FindProjection* proj, WorkingSetMember* wsm);
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/db/exec/query_projection.cpp b/src/mongo/db/exec/query_projection.cpp
deleted file mode 100644
index 0bb06ca1f4b..00000000000
--- a/src/mongo/db/exec/query_projection.cpp
+++ /dev/null
@@ -1,148 +0,0 @@
-/**
- *    Copyright (C) 2013 10gen Inc.
- *
- *    This program is free software: you can redistribute it and/or  modify
- *    it under the terms of the GNU Affero General Public License, version 3,
- *    as published by the Free Software Foundation.
- *
- *    This program is distributed in the hope that it will be useful,
- *    but WITHOUT ANY WARRANTY; without even the implied warranty of
- *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *    GNU Affero General Public License for more details.
- *
- *    You should have received a copy of the GNU Affero General Public License
- *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
- *
- *    As a special exception, the copyright holders give permission to link the
- *    code of portions of this program with the OpenSSL library under certain
- *    conditions as described in each individual source file and distribute
- *    linked combinations including the program with the OpenSSL library. You
- *    must comply with the GNU Affero General Public License in all respects for
- *    all of the code used other than as permitted herein. If you modify file(s)
- *    with this exception, you may extend this exception to your version of the
- *    file(s), but you are not obligated to do so. If you do not wish to do so,
- *    delete this exception statement from your version. If you delete this
- *    exception statement from all source files in the program, then also delete
- *    it in the license file.
- */
-
-#include "mongo/db/exec/query_projection.h"
-
-#include "mongo/db/exec/working_set.h"
-#include "mongo/db/jsobj.h"
-#include "mongo/util/mongoutils/str.h"
-
-namespace mongo {
-
-    //
-    // .find() syntax incl/excl projection
-    // TODO: Test.
-    //
-
-    class InclExclProjection : public QueryProjection {
-    public:
-        virtual ~InclExclProjection() { }
-
-        Status project(WorkingSetMember* wsm) {
-            BSONObjBuilder bob;
-            if (_includeID) {
-                BSONElement elt;
-                if (!wsm->getFieldDotted("_id", &elt)) {
-                    return Status(ErrorCodes::BadValue, "Couldn't get _id field in proj");
-                }
-                bob.append(elt);
-            }
-
-            if (_fieldsInclusive) {
-                // We only want stuff in _fields.
-                for (vector<string>::const_iterator it = _includedFields.begin();
-                     it != _includedFields.end(); ++it) {
-                    BSONElement elt;
-                    // We can project a field that doesn't exist.  We just ignore it.
-                    // UNITTEST 11738048
-                    if (wsm->getFieldDotted(*it, &elt) && !elt.eoo()) {
-                        bob.append(elt);
-                    }
-                }
-            }
-            else {
-                // We want stuff NOT in _fields.  This can't be covered, so we expect an obj.
-                if (!wsm->hasObj()) {
-                    return Status(ErrorCodes::BadValue,
-                                  "exclusion specified for projection but no obj to iter over");
-                }
-                BSONObjIterator it(wsm->obj);
-                while (it.more()) {
-                    BSONElement elt = it.next();
-                    if (!mongoutils::str::equals("_id", elt.fieldName())) {
-                        if (_excludedFields.end() == _excludedFields.find(elt.fieldName())) {
-                            bob.append(elt);
-                        }
-                    }
-                }
-            }
-
-            wsm->state = WorkingSetMember::OWNED_OBJ;
-            wsm->obj = bob.obj();
-            wsm->keyData.clear();
-            wsm->loc = DiskLoc();
-            return Status::OK();
-        }
-
-    private:
-        friend class QueryProjection;
-
-        // _id can be included/excluded separately and is by default included.
-        bool _includeID;
-
-        // Either we include all of _includedFields or we exclude all of _excludedFields.
-        bool _fieldsInclusive;
-        unordered_set<string> _excludedFields;
-
-        // Fields can be ordered if they're included.
-        // UNITTEST 11738048
-        vector<string> _includedFields;
-    };
-
-    // static
-    Status QueryProjection::newInclusionExclusion(const BSONObj& obj, QueryProjection** out) {
-        auto_ptr<InclExclProjection> qp(new InclExclProjection());
-
-        // Include _id by default.
-        qp->_includeID = true;
-
-        // By default include everything.
-        bool lastNonIDValue = false;
-
-        BSONObjIterator it(obj);
-        while (it.more()) {
-            BSONElement elt = it.next();
-            if (mongoutils::str::equals("_id", elt.fieldName())) {
-                qp->_includeID = elt.trueValue();
-            }
-            else {
-                bool newFieldValue = elt.trueValue();
-                if (qp->_includedFields.size() > 0 || qp->_excludedFields.size() > 0) {
-                    // make sure we're all true or all false otherwise error
-                    if (newFieldValue != lastNonIDValue) {
-                        return Status(ErrorCodes::BadValue, "Inconsistent projection specs");
-                    }
-                }
-                lastNonIDValue = newFieldValue;
-                if (lastNonIDValue) {
-                    // inclusive
-                    qp->_includedFields.push_back(elt.fieldName());
-                }
-                else {
-                    // exclusive
-                    qp->_excludedFields.insert(elt.fieldName());
-                }
-            }
-        }
-
-        qp->_fieldsInclusive = lastNonIDValue;
-        *out = qp.release();
-        return Status::OK();
-    }
-
-}  // namespace mongo
diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript
index 5f8ac2712d5..2847f8ef042 100644
--- a/src/mongo/db/query/SConscript
+++ b/src/mongo/db/query/SConscript
@@ -10,6 +10,7 @@ env.StaticLibrary(
         "index_tag.cpp",
         "lite_parsed_query.cpp",
         "plan_enumerator.cpp",
+        "projection_parser.cpp",
         "query_planner.cpp",
         "query_solution.cpp",
     ],
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index beca421af84..5367816747d 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -30,6 +30,7 @@
 
 #include "mongo/db/jsobj.h"
 #include "mongo/db/matcher/expression_parser.h"
+#include "mongo/db/query/projection_parser.h"
 
 namespace mongo {
 
@@ -64,6 +65,24 @@ namespace mongo {
         return Status::OK();
     }
 
+    // static
+    Status CanonicalQuery::canonicalize(const string& ns, const BSONObj& query,
+                                        const BSONObj& sort, const BSONObj& proj,
+                                        CanonicalQuery** out) {
+        LiteParsedQuery* lpq;
+        // Pass empty sort and projection.
+        BSONObj emptyObj;
+        Status parseStatus = LiteParsedQuery::make(ns, 0, 0, 0, query, proj, sort, &lpq);
+        if (!parseStatus.isOK()) { return parseStatus; }
+
+        auto_ptr<CanonicalQuery> cq(new CanonicalQuery());
+        Status initStatus = cq->init(lpq);
+        if (!initStatus.isOK()) { return initStatus; }
+
+        *out = cq.release();
+        return Status::OK();
+    }
+
     void normalizeTree(MatchExpression* root) {
         // root->isLogical() is true now.  We care about AND and OR.  Negations currently scare us.
         if (MatchExpression::AND == root->matchType() || MatchExpression::OR == root->matchType()) {
@@ -113,6 +132,15 @@ namespace mongo {
         normalizeTree(root);
         _root.reset(root);
 
+        if (!_pq->getProj().isEmpty()) {
+            ParsedProjection* proj;
+            Status projStatus = ProjectionParser::parseFindSyntax(_pq->getProj(), &proj);
+            if (!projStatus.isOK()) {
+                return projStatus;
+            }
+            _proj.reset(proj);
+        }
+
         return Status::OK();
     }
 
diff --git a/src/mongo/db/query/canonical_query.h b/src/mongo/db/query/canonical_query.h
index be51fde183a..3f7c15bb6ff 100644
--- a/src/mongo/db/query/canonical_query.h
+++ b/src/mongo/db/query/canonical_query.h
@@ -33,6 +33,7 @@
 #include "mongo/db/jsobj.h"
 #include "mongo/db/matcher/expression.h"
 #include "mongo/db/query/lite_parsed_query.h"
+#include "mongo/db/query/parsed_projection.h"
 
 namespace mongo {
 
@@ -40,8 +41,10 @@ namespace mongo {
     public:
         static Status canonicalize(const QueryMessage& qm, CanonicalQuery** out);
 
-        // This is for testing, when we don't have a QueryMessage.
+        // These are for testing, when we don't have a QueryMessage.
         static Status canonicalize(const string& ns, const BSONObj& query, CanonicalQuery** out);
+        static Status canonicalize(const string& ns, const BSONObj& query, const BSONObj& sort,
+                                   const BSONObj& proj, CanonicalQuery** out);
 
         // What namespace is this query over?
         const string& ns() const { return _pq->ns(); }
@@ -52,6 +55,7 @@ namespace mongo {
         MatchExpression* root() const { return _root.get(); }
         BSONObj getQueryObj() const { return _pq->getFilter(); }
         const LiteParsedQuery& getParsed() const { return *_pq; }
+        ParsedProjection* getProj() const { return _proj.get(); }
 
         string toString() const;
 
@@ -64,6 +68,8 @@ namespace mongo {
 
         scoped_ptr<LiteParsedQuery> _pq;
 
+        scoped_ptr<ParsedProjection> _proj;
+
         // _root points into _pq->getFilter()
         scoped_ptr<MatchExpression> _root;
     };
diff --git a/src/mongo/db/query/parsed_projection.h b/src/mongo/db/query/parsed_projection.h
new file mode 100644
index 00000000000..6f16cfe3697
--- /dev/null
+++ b/src/mongo/db/query/parsed_projection.h
@@ -0,0 +1,118 @@
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#pragma once
+
+#include <string>
+#include <vector>
+#include "mongo/platform/unordered_set.h"
+
+namespace mongo {
+
+    /**
+     * Superclass for all projections.  Projections are downcased to their specific implementation
+     * and executed.
+     */
+    class ParsedProjection {
+    public:
+        virtual ~ParsedProjection() { }
+
+        enum Type {
+            FIND_SYNTAX,
+        };
+
+        virtual Type getType() const = 0;
+
+        virtual string toString() const = 0;
+
+        //
+        // Properties of a projection.  These allow us to determine if the projection is covered or
+        // not.
+        //
+
+        /**
+         * Does the projection require the entire document?  If so, there must be a fetch before the
+         * projection.
+         */
+        virtual bool requiresDocument() const = 0;
+
+        /**
+         * What fields does the projection require?
+         */
+        virtual const vector<string>& requiredFields() const = 0;
+    };
+
+    //
+    // ParsedProjection implementations
+    //
+    class FindProjection : public ParsedProjection {
+    public:
+        Type getType() const {
+            return ParsedProjection::FIND_SYNTAX;
+        }
+
+        string toString() const {
+            // XXX FIXME
+            return "";
+        }
+
+        bool requiresDocument() const {
+            // If you're excluding fields, you must have something to exclude them from.
+            if (_excludedFields.size() > 0) {
+                verify(0 == _includedFields.size());
+                return true;
+            }
+
+            // If you're including fields, they could come from an index.
+            return false;
+        }
+
+        virtual const vector<string>& requiredFields() const {
+            verify(0 == _excludedFields.size());
+            return _includedFields;
+        }
+
+    private:
+        // ProjectionParser constructs us.
+        friend class ProjectionParser;
+
+        // ProjectionExecutor reads the fields below.
+        friend class ProjectionExecutor;
+
+        // _id can be included/excluded separately and is by default included.
+        bool _includeID;
+
+        // Either you exclude certain fields...
+        unordered_set<string> _excludedFields;
+
+        // ...or you include other fields, which can be ordered.
+        // UNITTEST 11738048
+        vector<string> _includedFields;
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/projection_parser.cpp b/src/mongo/db/query/projection_parser.cpp
new file mode 100644
index 00000000000..37d6804de21
--- /dev/null
+++ b/src/mongo/db/query/projection_parser.cpp
@@ -0,0 +1,76 @@
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/db/query/projection_parser.h"
+
+#include "mongo/db/jsobj.h"
+#include "mongo/util/mongoutils/str.h"
+
+namespace mongo {
+
+    // static
+    Status ProjectionParser::parseFindSyntax(const BSONObj& obj, ParsedProjection** out) {
+        auto_ptr<FindProjection> qp(new FindProjection());
+
+        // Include _id by default.
+        qp->_includeID = true;
+
+        // By default include everything.
+        bool lastNonIDValue = false;
+
+        BSONObjIterator it(obj);
+        while (it.more()) {
+            BSONElement elt = it.next();
+            if (mongoutils::str::equals("_id", elt.fieldName())) {
+                qp->_includeID = elt.trueValue();
+            }
+            else {
+                bool newFieldValue = elt.trueValue();
+                if (qp->_excludedFields.size() + qp->_includedFields.size() > 0) {
+                    // make sure we're all true or all false otherwise error
+                    if (newFieldValue != lastNonIDValue) {
+                        return Status(ErrorCodes::BadValue, "Inconsistent projection specs");
+                    }
+                }
+                lastNonIDValue = newFieldValue;
+                if (lastNonIDValue) {
+                    // inclusive
+                    qp->_includedFields.push_back(elt.fieldName());
+                }
+                else {
+                    // exclusive
+                    qp->_excludedFields.insert(elt.fieldName());
+                }
+            }
+        }
+
+        *out = qp.release();
+        return Status::OK();
+    }
+
+}  // namespace mongo
diff --git a/src/mongo/db/exec/query_projection.h b/src/mongo/db/query/projection_parser.h
index 5a7dcc83e3d..ab24ca750af 100644
--- a/src/mongo/db/exec/query_projection.h
+++ b/src/mongo/db/query/projection_parser.h
@@ -28,29 +28,21 @@
 
 #pragma once
 
-#include "mongo/db/exec/working_set.h"
 #include "mongo/db/jsobj.h"
+#include "mongo/db/query/parsed_projection.h"
 
 namespace mongo {
 
     /**
-     * An interface for projecting (modifying) a WSM.
-     * TODO: Add unit test.
+     * Parses each of the various projection syntaxes that exist.
      */
-    class QueryProjection {
+    class ProjectionParser {
     public:
-        virtual ~QueryProjection() { }
-
-        /**
-         * Compute the projection over the WSM.  Place the output in the provided WSM.
-         */
-        virtual Status project(WorkingSetMember* wsm) = 0;
-
         /**
          * This projection handles the inclusion/exclusion syntax of the .find() command.
          * For details, see http://docs.mongodb.org/manual/reference/method/db.collection.find/
          */
-        static Status newInclusionExclusion(const BSONObj& inclExcl, QueryProjection** out);
+        static Status parseFindSyntax(const BSONObj& inclExcl, ParsedProjection** out);
     };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 0026509400c..819462f102b 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -165,9 +165,9 @@ namespace mongo {
             }
         }
 
-        if (!query.getParsed().getProj().isEmpty()) {
+        if (NULL != query.getProj()) {
             ProjectionNode* proj = new ProjectionNode();
-            proj->projection = query.getParsed().getProj();
+            proj->projection = query.getProj();
             proj->child.reset(solnRoot);
             solnRoot = proj;
         }
@@ -583,35 +583,93 @@ namespace mongo {
         return NULL;
     }
 
+    /**
+     * Order of what happens:
+     * find results
+     * sort results
+     * project results
+     */
+
     QuerySolution* makeSolution(const CanonicalQuery& query, MatchExpression* taggedRoot,
                                 const vector<BSONObj>& indexKeyPatterns) {
         cout << "about to build solntree from tagged tree:\n" << taggedRoot->toString() << endl;
+
         QuerySolutionNode* solnRoot = buildSolutionTree(taggedRoot, indexKeyPatterns);
         if (NULL == solnRoot) { return NULL; }
 
-        // TODO XXX: Solutions need properties, need to use those properties to see when things
-        // covered, sorts provided, etc.
+        // solnRoot finds all our results.
 
-        // Fetch before proj
-        bool addFetch = (STAGE_FETCH != solnRoot->getType());
-        if (addFetch) {
-            FetchNode* fetch = new FetchNode();
-            fetch->child.reset(solnRoot);
-            solnRoot = fetch;
-        }
+        // Sort the results.
+        if (!query.getParsed().getSort().isEmpty()) {
+            // See if solnRoot gives us the sort.  If so, we're done.
+            if (0 == query.getParsed().getSort().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(query.getParsed().getSort());
+                    while (it.more()) {
+                        if (!solnRoot->hasField(it.next().fieldName())) {
+                            sortCovered = false;
+                            break;
+                        }
+                    }
 
-        if (!query.getParsed().getProj().isEmpty()) {
-            ProjectionNode* proj = new ProjectionNode();
-            proj->projection = query.getParsed().getProj();
-            proj->child.reset(solnRoot);
-            solnRoot = proj;
+                    if (!sortCovered) {
+                        FetchNode* fetch = new FetchNode();
+                        fetch->child.reset(solnRoot);
+                        solnRoot = fetch;
+                    }
+                }
+
+                SortNode* sort = new SortNode();
+                sort->pattern = query.getParsed().getSort();
+                sort->child.reset(solnRoot);
+                solnRoot = sort;
+            }
         }
 
-        if (!query.getParsed().getSort().isEmpty()) {
-            SortNode* sort = new SortNode();
-            sort->pattern = query.getParsed().getSort();
-            sort->child.reset(solnRoot);
-            solnRoot = sort;
+        // Project the results.
+        if (NULL != query.getProj()) {
+            if (query.getProj()->requiresDocument()) {
+                if (!solnRoot->fetched()) {
+                    FetchNode* fetch = new FetchNode();
+                    fetch->child.reset(solnRoot);
+                    solnRoot = fetch;
+                }
+            }
+            else {
+                const vector<string>& fields = query.getProj()->requiredFields();
+                bool covered = true;
+                for (size_t i = 0; i < fields.size(); ++i) {
+                    if (!solnRoot->hasField(fields[i])) {
+                        covered = false;
+                        break;
+                    }
+                }
+                if (!covered) {
+                    FetchNode* fetch = new FetchNode();
+                    fetch->child.reset(solnRoot);
+                    solnRoot = fetch;
+                }
+            }
+
+            // We now know we have whatever data is required for the projection.
+            ProjectionNode* projNode = new ProjectionNode();
+            projNode->projection = query.getProj();
+            projNode->child.reset(solnRoot);
+            solnRoot = projNode;
+        }
+        else {
+            if (!solnRoot->fetched()) {
+                FetchNode* fetch = new FetchNode();
+                fetch->child.reset(solnRoot);
+                solnRoot = fetch;
+            }
         }
 
         if (0 != query.getParsed().getSkip()) {
@@ -732,7 +790,6 @@ namespace mongo {
 
         MatchExpression* rawTree;
         while (isp.getNext(&rawTree)) {
-
             //
             // Planner Section 3: Logical Rewrite.  Use the index selection and the tree structure
             // to try to rewrite the tree.  TODO: Do this for real.  We treat the tree as static.
@@ -762,6 +819,12 @@ namespace mongo {
             }
         }
 
+        if (0 == out->size() && !query.getParsed().getSort().isEmpty()) {
+            // There are no indexed plans outputted, but there's a requested sort.  See if we have
+            // an index that is the same as the sort pattern.
+            // XXX: we may want to do this even if an indexed plan is outputted...detect that.
+        }
+
         // TODO: Do we always want to offer a collscan solution?
         if (!hasPredicate(predicates, MatchExpression::GEO_NEAR)) {
             QuerySolution* collscan = makeCollectionScan(query, false);
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index bdc865a6ca8..60595622ee6 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -73,6 +73,12 @@ namespace {
             ASSERT_GREATER_THAN(solns.size(), 0U);;
         }
 
+        void runDetailedQuery(const BSONObj& query, const BSONObj& sort, const BSONObj& proj) {
+            ASSERT_OK(CanonicalQuery::canonicalize(ns, query, sort, proj, &cq));
+            QueryPlanner::plan(*cq, keyPatterns, &solns);
+            ASSERT_GREATER_THAN(solns.size(), 0U);;
+        }
+
         //
         // Introspect solutions.
         //
@@ -91,9 +97,28 @@ namespace {
                     found++;
                 }
             }
+            if (1 != found) {
+                cout << "Can't find requested stage type " << stageType
+                     << ", dump of all solutions:\n";
+                for (vector<QuerySolution*>::const_iterator it = solns.begin();
+                        it != solns.end();
+                        ++it) {
+                    cout << (*it)->toString() << endl;
+                }
+            }
             ASSERT_EQUALS(found, 1U);
         }
 
+        void getAllPlans(StageType stageType, vector<QuerySolution*>* out) const {
+            for (vector<QuerySolution*>::const_iterator it = solns.begin();
+                 it != solns.end();
+                 ++it) {
+                if ((*it)->root->getType() == stageType) {
+                    out->push_back(*it);
+                }
+            }
+        }
+
         // { 'field': [ [min, max, startInclusive, endInclusive], ... ], 'field': ... }
         void boundsEqual(BSONObj boundsObj, IndexBounds bounds) const {
             ASSERT_EQUALS(static_cast<int>(bounds.size()), boundsObj.nFields());
@@ -338,6 +363,43 @@ namespace {
         // TODO check filter
     }
 
+    //
+    // Basic covering
+    //
+
+    TEST_F(SingleIndexTest, BasicCovering) {
+        setIndex(BSON("x" << 1));
+        // query, sort, proj
+        runDetailedQuery(fromjson("{ x : {$gt: 1}}"), BSONObj(), fromjson("{x: 1}"));
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+
+        vector<QuerySolution*> solns;
+        getAllPlans(STAGE_PROJECTION, &solns);
+        ASSERT_EQUALS(solns.size(), 2U);
+
+        for (size_t i = 0; i < solns.size(); ++i) {
+            // cout << solns[i]->toString();
+            ProjectionNode* pn = static_cast<ProjectionNode*>(solns[i]->root.get());
+            ASSERT(STAGE_COLLSCAN == pn->child->getType() || STAGE_IXSCAN == pn->child->getType());
+        }
+    }
+
+    //
+    // Basic sort elimination
+    //
+
+    TEST_F(SingleIndexTest, BasicSortElim) {
+        setIndex(BSON("x" << 1));
+        // query, sort, proj
+        runDetailedQuery(fromjson("{ x : {$gt: 1}}"), fromjson("{x: 1}"), BSONObj());
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+
+        QuerySolution* collScanSolution;
+        getPlanByType(STAGE_SORT, &collScanSolution);
+
+        QuerySolution* indexedSolution;
+        getPlanByType(STAGE_FETCH, &indexedSolution);
+    }
 
     // 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 bb11e3b181b..79bf04c45b7 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -38,12 +38,12 @@ namespace mongo {
 
     void CollectionScanNode::appendToString(stringstream* ss, int indent) const {
         addIndent(ss, indent);
-        *ss << "COLLSCAN";
+        *ss << "COLLSCAN\n";
         addIndent(ss, indent + 1);
-        *ss <<  "ns = " << name;
+        *ss <<  "ns = " << name << endl;
         if (NULL != filter) {
             addIndent(ss, indent + 1);
-            *ss << " filter = " << filter->toString() << endl;
+            *ss << " filter = " << filter->toString();
         }
         addIndent(ss, indent + 1);
         *ss << "fetched = " << fetched() << endl;
@@ -262,8 +262,9 @@ namespace mongo {
     void ProjectionNode::appendToString(stringstream* ss, int indent) const {
         addIndent(ss, indent);
         *ss << "PROJ\n";
+        verify(NULL != projection);
         addIndent(ss, indent + 1);
-        *ss << "proj = " << projection.toString() << endl;
+        *ss << "proj = " << projection->toString() << endl;
         addIndent(ss, indent + 1);
         *ss << "fetched = " << fetched() << endl;
         addIndent(ss, indent + 1);
diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h
index e931775f6c9..5ea9b4fcf8d 100644
--- a/src/mongo/db/query/query_solution.h
+++ b/src/mongo/db/query/query_solution.h
@@ -30,6 +30,7 @@
 
 #include "mongo/db/matcher/expression.h"
 #include "mongo/db/query/index_bounds.h"
+#include "mongo/db/query/projection_parser.h"
 #include "mongo/db/query/stage_types.h"
 
 namespace mongo {
@@ -261,7 +262,7 @@ namespace mongo {
     };
 
     struct ProjectionNode : public QuerySolutionNode {
-        ProjectionNode() { }
+        ProjectionNode() : projection(NULL) { }
         virtual ~ProjectionNode() { }
 
         virtual StageType getType() const { return STAGE_PROJECTION; }
@@ -294,8 +295,11 @@ namespace mongo {
             return BSONObj();
         }
 
-        BSONObj projection;
+        // Points into the CanonicalQuery.
+        ParsedProjection* projection;
+
         scoped_ptr<QuerySolutionNode> child;
+
         // TODO: Filter
     };
 
diff --git a/src/mongo/db/query/stage_builder.cpp b/src/mongo/db/query/stage_builder.cpp
index dc2d59f1ceb..da4c60fadb8 100644
--- a/src/mongo/db/query/stage_builder.cpp
+++ b/src/mongo/db/query/stage_builder.cpp
@@ -95,16 +95,9 @@ namespace mongo {
         }
         else if (STAGE_PROJECTION == root->getType()) {
             const ProjectionNode* pn = static_cast<const ProjectionNode*>(root);
-            QueryProjection* proj;
-            if (!QueryProjection::newInclusionExclusion(pn->projection, &proj).isOK()) {
-                return NULL;
-            }
             PlanStage* childStage = buildStages(ns, pn->child.get(), ws);
-            if (NULL == childStage) {
-                delete proj;
-                return NULL;
-            }
-            return new ProjectionStage(proj, ws, childStage, NULL);
+            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);
@@ -146,7 +139,7 @@ namespace mongo {
         }
     }
 
-    //static
+    // static
     bool StageBuilder::build(const QuerySolution& solution, PlanStage** rootOut,
                              WorkingSet** wsOut) {
         QuerySolutionNode* root = solution.root.get();