diff options
Diffstat (limited to 'src/mongo/db')
-rw-r--r-- | src/mongo/db/exec/stagedebug_cmd.cpp | 2 | ||||
-rw-r--r-- | src/mongo/db/query/SConscript | 1 | ||||
-rw-r--r-- | src/mongo/db/query/cached_plan_runner.h | 81 | ||||
-rw-r--r-- | src/mongo/db/query/canonical_query.h | 43 | ||||
-rw-r--r-- | src/mongo/db/query/multi_plan_runner.h | 12 | ||||
-rw-r--r-- | src/mongo/db/query/new_find.cpp | 99 | ||||
-rw-r--r-- | src/mongo/db/query/new_find.h | 29 | ||||
-rw-r--r-- | src/mongo/db/query/plan_cache.h | 121 | ||||
-rw-r--r-- | src/mongo/db/query/plan_ranker.h | 4 | ||||
-rw-r--r-- | src/mongo/db/query/query_planner.h | 39 | ||||
-rw-r--r-- | src/mongo/db/query/query_solution.h | 11 | ||||
-rw-r--r-- | src/mongo/db/query/runner.h | 39 | ||||
-rw-r--r-- | src/mongo/db/query/simple_plan_runner.h (renamed from src/mongo/db/exec/simple_plan_runner.h) | 9 | ||||
-rw-r--r-- | src/mongo/db/query/stage_builder.h | 47 |
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 |