SERVER-10026 skeleton of query parsing & planning, cache

14 files changed, 526 insertions, 11 deletions

diff --git a/src/mongo/db/exec/stagedebug_cmd.cpp b/src/mongo/db/exec/stagedebug_cmd.cpp
index 28ef5fed31d..f93c001c51a 100644
--- a/src/mongo/db/exec/stagedebug_cmd.cpp
+++ b/src/mongo/db/exec/stagedebug_cmd.cpp
@@ -28,7 +28,7 @@
 #include "mongo/db/exec/or.h"
 #include "mongo/db/exec/skip.h"
 #include "mongo/db/exec/sort.h"
-#include "mongo/db/exec/simple_plan_runner.h"
+#include "mongo/db/query/simple_plan_runner.h"
 #include "mongo/db/index/catalog_hack.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/matcher/matcher.h"
diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript
index d1c8d24f477..1885c68e4db 100644
--- a/src/mongo/db/query/SConscript
+++ b/src/mongo/db/query/SConscript
@@ -6,6 +6,7 @@ env.StaticLibrary(
     target = 'query',
     source = [
         "multi_plan_runner.cpp",
+        "new_find.cpp",
         "plan_ranker.cpp",
     ],
     LIBDEPS = [
diff --git a/src/mongo/db/query/cached_plan_runner.h b/src/mongo/db/query/cached_plan_runner.h
new file mode 100644
index 00000000000..23faee9412c
--- /dev/null
+++ b/src/mongo/db/query/cached_plan_runner.h
@@ -0,0 +1,81 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/db/query/canonical_query.h"
+#include "mongo/db/query/plan_cache.h"
+#include "mongo/db/query/runner.h"
+#include "mongo/db/query/simple_plan_runner.h"
+#include "mongo/db/query/stage_builder.h"
+
+namespace mongo {
+
+    /**
+     * CachedPlanRunner runs a plan retrieved from the cache.
+     *
+     * Cached plans are bundled with information describing why the plan is in the cache.
+     *
+     * If we run a plan from the cache and behavior wildly deviates from expected behavior, we may
+     * remove the plan from the cache.  See plan_cache.h.
+     */
+    class CachedPlanRunner : public Runner {
+    public:
+        /**
+         * Takes ownership of both arguments.
+         */
+        CachedPlanRunner(CanonicalQuery* canonicalQuery, CachedSolution* cached,
+                         PlanStage* root, WorkingSet* ws)
+            : _canonicalQuery(canonicalQuery), _cachedQuery(cached),
+              _runner(new SimplePlanRunner(ws, root)) { }
+
+        bool getNext(BSONObj* objOut) {
+            // Use the underlying runner until it's exhausted.
+            if (_runner->getNext(objOut)) {
+                return true;
+            }
+
+            // We're done.  Update the cache.
+            PlanCache* cache = PlanCache::get(_canonicalQuery->ns());
+
+            // TODO: is this a verify?
+            if (NULL == cache) { return false; }
+
+            // TODO: How do we decide this?
+            bool shouldRemovePlan = false;
+
+            if (shouldRemovePlan) {
+                if (!cache->remove(*_canonicalQuery, *_cachedQuery->solution)) {
+                    warning() << "Cached plan runner couldn't remove plan from cache.  Maybe"
+                                 " somebody else did already?";
+                }
+                return false;
+            }
+
+            // We're done running.  Update cache.
+            auto_ptr<CachedSolutionFeedback> feedback(new CachedSolutionFeedback());
+            feedback->stats = _runner->getStats();
+            cache->feedback(*_canonicalQuery, *_cachedQuery->solution, feedback.release());
+            return false;
+        }
+
+    private:
+        scoped_ptr<CanonicalQuery> _canonicalQuery;
+        scoped_ptr<CachedSolution> _cachedQuery;
+        scoped_ptr<SimplePlanRunner> _runner;
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/canonical_query.h b/src/mongo/db/query/canonical_query.h
new file mode 100644
index 00000000000..f6aed1be503
--- /dev/null
+++ b/src/mongo/db/query/canonical_query.h
@@ -0,0 +1,43 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/db/dbmessage.h"
+
+namespace mongo {
+
+    class CanonicalQuery {
+    public:
+        static CanonicalQuery* canonicalize(const QueryMessage& qm) {
+            auto_ptr<CanonicalQuery> cq(new CanonicalQuery());
+            return cq.release();
+        }
+
+        const string& ns() {
+            return _ns;
+        }
+
+    private:
+        CanonicalQuery() { }
+
+        string _ns;
+        BSONObj _sort;
+        int limit;
+        // TODO: Other query arguments.
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/multi_plan_runner.h b/src/mongo/db/query/multi_plan_runner.h
index 00bb0d60c84..d365a843e0b 100644
--- a/src/mongo/db/query/multi_plan_runner.h
+++ b/src/mongo/db/query/multi_plan_runner.h
@@ -20,11 +20,13 @@
 #include <queue>
 #include <vector>
 
-#include "mongo/db/exec/simple_plan_runner.h"
 #include "mongo/db/exec/working_set.h"
 #include "mongo/db/exec/plan_stage.h"
 #include "mongo/db/jsobj.h"
+#include "mongo/db/query/canonical_query.h"
 #include "mongo/db/query/plan_ranker.h"
+#include "mongo/db/query/runner.h"
+#include "mongo/db/query/simple_plan_runner.h"
 #include "mongo/platform/cstdint.h"
 
 namespace mongo {
@@ -33,20 +35,16 @@ namespace mongo {
     using std::size_t;
     using std::vector;
 
-    // Place holder.
-    class CanonicalQuery {
-    };
-
     /**
      * Runs several plans in parallel and picks the best one.  Caches the selection for future use.
      */
-    class MultiPlanRunner {
+    class MultiPlanRunner : public Runner {
     public:
         /**
          * Takes ownership of query.
          */
         MultiPlanRunner(CanonicalQuery* query);
-        ~MultiPlanRunner();
+        virtual ~MultiPlanRunner();
 
         /**
          * Takes ownership of all arguments
diff --git a/src/mongo/db/query/new_find.cpp b/src/mongo/db/query/new_find.cpp
new file mode 100644
index 00000000000..18e4426250c
--- /dev/null
+++ b/src/mongo/db/query/new_find.cpp
@@ -0,0 +1,99 @@
+/**
+ *    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/>.
+ */
+
+#include "mongo/db/query/new_find.h"
+
+#include "mongo/db/query/cached_plan_runner.h"
+#include "mongo/db/query/canonical_query.h"
+#include "mongo/db/query/multi_plan_runner.h"
+#include "mongo/db/query/plan_cache.h"
+#include "mongo/db/query/query_planner.h"
+#include "mongo/db/query/simple_plan_runner.h"
+#include "mongo/db/query/stage_builder.h"
+
+namespace mongo {
+
+    Runner* getRunner(Message& m, QueryMessage& q, CurOp& curop, Message &result) {
+        // Turn the query into something clean we can work with.
+        auto_ptr<CanonicalQuery> canonicalQuery(CanonicalQuery::canonicalize(q));
+
+        if (NULL == canonicalQuery.get()) { return NULL; }
+
+        PlanCache* localCache = PlanCache::get(canonicalQuery->ns());
+        CachedSolution* cs = localCache->get(*canonicalQuery);
+        if (NULL != cs) {
+            // Hand the canonical query and cached solution off to the cached plan runner, which
+            // takes ownership of both.
+            WorkingSet* ws;
+            PlanStage* root;
+            verify(StageBuilder::build(*cs->solution, &root, &ws));
+            return new CachedPlanRunner(canonicalQuery.release(), cs, root, ws);
+        }
+
+        // No entry in cache.  We have to pick a best plan.
+        // TODO: Can the cache have negative data?
+        vector<QuerySolution*> solutions;
+        QueryPlanner::plan(*canonicalQuery, &solutions);
+
+        if (1 == solutions.size()) {
+            // Only one possible plan.  Run it.  Cache it as well.  If we only found one solution
+            // now, we're only going to find one solution later.
+            auto_ptr<PlanRankingDecision> why(new PlanRankingDecision());
+            why->onlyOneSolution = true;
+
+            // Build the stages from the solution.
+            WorkingSet* ws;
+            PlanStage* root;
+            verify(StageBuilder::build(*solutions[0], &root, &ws));
+
+            // Cache the solution.  Takes ownership of all arguments.
+            localCache->add(canonicalQuery.release(), solutions[0], why.release());
+
+            // And, run the plan.
+            return new SimplePlanRunner(ws, root);
+        }
+        else {
+            // Many solutions.  Let the MultiPlanRunner pick the best, update the cache, and so on.
+            auto_ptr<MultiPlanRunner> mpr(new MultiPlanRunner(canonicalQuery.release()));
+            for (size_t i = 0; i < solutions.size(); ++i) {
+                WorkingSet* ws;
+                PlanStage* root;
+                verify(StageBuilder::build(*solutions[i], &root, &ws));
+                // Takes ownership of all arguments.
+                mpr->addPlan(solutions[i], root, ws);
+            }
+            return mpr.release();
+        }
+    }
+
+    string newRunQuery(Message& m, QueryMessage& q, CurOp& curop, Message &result) {
+        auto_ptr<Runner> runner(getRunner(m, q, curop, result));
+
+        if (NULL == runner.get()) {
+            // TODO: Complain coherently to the user.
+        }
+
+        BSONObj obj;
+        while (runner->getNext(&obj)) {
+            // TODO: append result to output.
+        }
+
+        // TODO: what's this?
+        return "";
+    }
+
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/new_find.h b/src/mongo/db/query/new_find.h
new file mode 100644
index 00000000000..0a4087a4afe
--- /dev/null
+++ b/src/mongo/db/query/new_find.h
@@ -0,0 +1,29 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include <string>
+
+#include "mongo/db/curop.h"
+#include "mongo/db/dbmessage.h"
+#include "mongo/util/net/message.h"
+
+namespace mongo {
+
+    string newRunQuery(Message& m, QueryMessage& q, CurOp& curop, Message &result);
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/plan_cache.h b/src/mongo/db/query/plan_cache.h
new file mode 100644
index 00000000000..9fb01f973b0
--- /dev/null
+++ b/src/mongo/db/query/plan_cache.h
@@ -0,0 +1,121 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/db/exec/plan_stats.h"
+#include "mongo/db/query/plan_ranker.h"
+#include "mongo/db/query/query_solution.h"
+
+namespace mongo {
+
+    /**
+     * TODO: Debug commands:
+     * 1. show canonical form of query
+     * 2. show plans generated for query without (and with) cache
+     * 3. print out cache.
+     * 4. clear all elements from cache / otherwise manipulate cache.
+     */
+
+    /**
+     * When the CachedPlanRunner runs a cached query, it can provide feedback to the cache.  This
+     * feedback is available to anyone who retrieves that query in the future.
+     */
+    struct CachedSolutionFeedback {
+        PlanStageStats* stats;
+    };
+
+    /**
+     * A cached solution to a query.
+     */
+    struct CachedSolution {
+        ~CachedSolution() {
+            for (size_t i = 0; i < feedback.size(); ++i) {
+                delete feedback[i];
+            }
+        }
+
+        // The best solution for the CanonicalQuery.
+        scoped_ptr<QuerySolution> solution;
+
+        // Why the best solution was picked.
+        scoped_ptr<PlanRankingDecision> decision;
+
+        // Annotations from cached runs.
+        // TODO: How many of these do we really want to keep?
+        vector<CachedSolutionFeedback*> feedback;
+    private:
+        MONGO_DISALLOW_COPYING(CachedSolution);
+    };
+
+    /**
+     * Caches the best solution to a query.  Aside from the (CanonicalQuery -> QuerySolution)
+     * mapping, the cache contains information on why that mapping was made, and statistics on the
+     * cache entry's actual performance on subsequent runs.
+     */
+    class PlanCache {
+    public:
+        /**
+         * Get the (global) cache for the provided namespace.  Must not be held across yields.
+         * As such, there is no locking required.
+         */
+        static PlanCache* get(const string& ns) { return NULL; }
+
+        /**
+         * Record 'solution' as the best plan for 'query' which was picked for reasons detailed in
+         * 'why'.
+         *
+         * Takes ownership of all arguments.
+         *
+         * If the mapping was added successfully, returns true.
+         * If the mapping already existed or some other error occurred, returns false;
+         */
+        bool add(CanonicalQuery* query, QuerySolution* solution, PlanRankingDecision* why) {
+            return false;
+        }
+
+        /**
+         * Look up the cached solution for the provided query.  If a cached solution exists, return
+         * a copy of it which the caller then owns.  If no cached solution exists, returns NULL.
+         *
+         * TODO: Allow querying for exact query and querying for the shape of the query.
+         */
+        CachedSolution* get(const CanonicalQuery& query) {
+            return NULL;
+        }
+
+        /**
+         * When the CachedPlanRunner runs a plan out of the cache, we want to record data about the
+         * plan's performance.  Cache takes ownership of 'feedback'.
+         *
+         * If the (query, solution) pair isn't in the cache, the cache deletes feedback and returns
+         * false.  Otherwise, returns true.
+         */
+        bool feedback(const CanonicalQuery& query, const QuerySolution& solution,
+                      const CachedSolutionFeedback* feedback) {
+            return false;
+        }
+
+        /**
+         * Remove the (query, solution) pair from our cache.  Returns true if the plan was removed,
+         * false if it wasn't found.
+         */
+        bool remove(const CanonicalQuery& query, const QuerySolution& solution) {
+            return false;
+        }
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/plan_ranker.h b/src/mongo/db/query/plan_ranker.h
index e4a980a713d..bcbe17f33f8 100644
--- a/src/mongo/db/query/plan_ranker.h
+++ b/src/mongo/db/query/plan_ranker.h
@@ -68,9 +68,13 @@ namespace mongo {
      * and used by the CachedPlanRunner to compare expected performance with actual.
      */
     struct PlanRankingDecision {
+        PlanRankingDecision() : statsOfWinner(NULL), onlyOneSolution(false) { }
+
         // Owned by us.
         PlanStageStats* statsOfWinner;
 
+        bool onlyOneSolution;
+
         // TODO: We can place anything we want here.  What's useful to the cache?  What's useful to
         // planning and optimization?
     };
diff --git a/src/mongo/db/query/query_planner.h b/src/mongo/db/query/query_planner.h
new file mode 100644
index 00000000000..beec11f136c
--- /dev/null
+++ b/src/mongo/db/query/query_planner.h
@@ -0,0 +1,39 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/db/query/query_solution.h"
+
+namespace mongo {
+
+    /**
+     * QueryPlanner's job is to provide an entry point to the query planning and optimization
+     * process.
+     */
+    class QueryPlanner {
+    public:
+        /**
+         * Outputs a series of possible solutions for the provided 'query' into 'out'.  Caller must
+         * then decide which to run, if any.
+         *
+         * Caller owns the pointers in *out.
+         */
+        static void plan(const CanonicalQuery& query, vector<QuerySolution*> *out) {
+        }
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h
index 1de849c0f36..bd89e8f1c48 100644
--- a/src/mongo/db/query/query_solution.h
+++ b/src/mongo/db/query/query_solution.h
@@ -28,19 +28,26 @@ namespace mongo {
         virtual ~QuerySolutionNode() { }
 
         /**
-         * What stage should this be transcribed to?
-         * See stage_types.h.
+         * What stage should this be transcribed to?  See stage_types.h.
          */
         virtual StageType getType() const = 0;
 
+        /**
+         * Output a human-readable string representing the plan.
+         */
         string toString() {
             stringstream ss;
             appendToString(&ss);
             return ss.str();
         }
 
+        /**
+         * Internal function called by toString()
+         */
         virtual void appendToString(stringstream* ss) const = 0;
     };
+
+    // The root of the tree is the solution.
     typedef QuerySolutionNode QuerySolution;
 
     struct EmptyNode : public QuerySolutionNode {
diff --git a/src/mongo/db/query/runner.h b/src/mongo/db/query/runner.h
new file mode 100644
index 00000000000..148a956f861
--- /dev/null
+++ b/src/mongo/db/query/runner.h
@@ -0,0 +1,39 @@
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+namespace mongo {
+
+    /**
+     * A runner runs a query.  All yielding, fetching, and other query details are taken care of by
+     * the runner.
+     *
+     * TODO: Do we want to expand the interface to allow yielding?  IE, if update is running a query
+     * and updating at the same time?
+     */
+    class Runner {
+    public:
+        /**
+         * Get the next result from the query.
+         */
+        // TODO: This is inefficient and should probably append to some message buffer or similar.
+        virtual bool getNext(BSONObj* objOut) = 0;
+
+        virtual ~Runner() { }
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/db/exec/simple_plan_runner.h b/src/mongo/db/query/simple_plan_runner.h
index c9c9d8d5c38..f1ca6902736 100644
--- a/src/mongo/db/exec/simple_plan_runner.h
+++ b/src/mongo/db/query/simple_plan_runner.h
@@ -17,8 +17,11 @@
 #include "mongo/db/exec/plan_stage.h"
 #include "mongo/db/exec/working_set.h"
 #include "mongo/db/exec/working_set_common.h"
+#include "mongo/db/query/runner.h"
 #include "mongo/db/pdfile.h"
 
+#pragma once
+
 namespace mongo {
 
     /**
@@ -29,7 +32,7 @@ namespace mongo {
      * TODO: Graceful error handling
      * TODO: Stats, diagnostics, instrumentation, etc.
      */
-    class SimplePlanRunner {
+    class SimplePlanRunner : public Runner {
     public:
         SimplePlanRunner() : _workingSet(new WorkingSet()) { }
         SimplePlanRunner(WorkingSet* ws, PlanStage* rt) : _workingSet(ws), _root(rt) { }
@@ -44,6 +47,10 @@ namespace mongo {
             _root.reset(root);
         }
 
+        PlanStageStats* getStats() {
+            return _root->getStats();
+        }
+
         bool getNext(BSONObj* objOut) {
             for (;;) {
                 WorkingSetID id;
diff --git a/src/mongo/db/query/stage_builder.h b/src/mongo/db/query/stage_builder.h
new file mode 100644
index 00000000000..8b4f3016a24
--- /dev/null
+++ b/src/mongo/db/query/stage_builder.h
@@ -0,0 +1,47 @@
+/**
+ *    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/>.
+ */
+
+#include "mongo/db/exec/and_hash.h"
+#include "mongo/db/exec/and_sorted.h"
+#include "mongo/db/exec/collection_scan.h"
+#include "mongo/db/exec/fetch.h"
+#include "mongo/db/exec/index_scan.h"
+#include "mongo/db/exec/limit.h"
+#include "mongo/db/exec/or.h"
+#include "mongo/db/exec/skip.h"
+#include "mongo/db/index/catalog_hack.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/db/matcher/matcher.h"
+#include "mongo/db/namespace_details.h"
+#include "mongo/db/pdfile.h"
+#include "mongo/db/query/query_solution.h"
+
+#pragma once
+
+namespace mongo {
+
+    /**
+     * The StageBuilder converts a QuerySolution to an executable tree of PlanStage(s).
+     */
+    class StageBuilder {
+    public:
+        static bool build(const QuerySolution& solution, PlanStage** rootOut, WorkingSet** wsOut) {
+            return false;
+            // TODO: Implement.
+        }
+    };
+
+}  // namespace mongo