diff options
| -rw-r--r-- | src/mongo/db/query/SConscript | 29 | ||||
| -rw-r--r-- | src/mongo/db/query/cached_plan_runner.h | 6 | ||||
| -rw-r--r-- | src/mongo/db/query/canonical_query.cpp | 8 | ||||
| -rw-r--r-- | src/mongo/db/query/canonical_query.h | 8 | ||||
| -rw-r--r-- | src/mongo/db/query/index_bounds.cpp | 40 | ||||
| -rw-r--r-- | src/mongo/db/query/index_bounds.h | 2 | ||||
| -rw-r--r-- | src/mongo/db/query/lite_parsed_query.cpp | 207 | ||||
| -rw-r--r-- | src/mongo/db/query/lite_parsed_query.h | 116 | ||||
| -rw-r--r-- | src/mongo/db/query/multi_plan_runner.cpp | 7 | ||||
| -rw-r--r-- | src/mongo/db/query/multi_plan_runner.h | 2 | ||||
| -rw-r--r-- | src/mongo/db/query/new_find.cpp | 10 | ||||
| -rw-r--r-- | src/mongo/db/query/plan_executor.h | 7 | ||||
| -rw-r--r-- | src/mongo/db/query/query_planner.cpp | 120 | ||||
| -rw-r--r-- | src/mongo/db/query/query_planner.h | 10 | ||||
| -rw-r--r-- | src/mongo/db/query/query_planner_test.cpp | 78 | ||||
| -rw-r--r-- | src/mongo/db/query/query_solution.h | 31 | ||||
| -rw-r--r-- | src/mongo/db/query/runner.h | 3 | ||||
| -rw-r--r-- | src/mongo/db/query/simple_plan_runner.h | 111 | ||||
| -rw-r--r-- | src/mongo/db/query/single_solution_runner.h | 7 |
19 files changed, 665 insertions, 137 deletions
diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript index 3b48d11ba5f..1617cefad32 100644 --- a/src/mongo/db/query/SConscript +++ b/src/mongo/db/query/SConscript @@ -3,16 +3,41 @@ Import("env") env.StaticLibrary( - target = 'query', + target = 'query_planner', source = [ "canonical_query.cpp", + "lite_parsed_query.cpp", + "query_planner.cpp", + ], + LIBDEPS = [ + "index_bounds", + "$BUILD_DIR/mongo/bson", + "$BUILD_DIR/mongo/expressions", + "$BUILD_DIR/mongo/expressions_geo", + "$BUILD_DIR/mongo/query_parsing", + ], +) + +env.CppUnitTest( + target = "query_planner_test", + source = [ + "query_planner_test.cpp" + ], + LIBDEPS = [ + "query_planner", + ], +) + +env.StaticLibrary( + target = 'query', + source = [ "multi_plan_runner.cpp", "new_find.cpp", "plan_ranker.cpp", - "query_planner.cpp", "stage_builder.cpp", ], LIBDEPS = [ + "query_planner", "$BUILD_DIR/mongo/db/exec/exec" ], ) diff --git a/src/mongo/db/query/cached_plan_runner.h b/src/mongo/db/query/cached_plan_runner.h index ef6c1c5882b..7770b8913d0 100644 --- a/src/mongo/db/query/cached_plan_runner.h +++ b/src/mongo/db/query/cached_plan_runner.h @@ -16,8 +16,8 @@ #pragma once -#include "mongo/db/parsed_query.h" #include "mongo/db/query/canonical_query.h" +#include "mongo/db/query/lite_parsed_query.h" #include "mongo/db/query/plan_cache.h" #include "mongo/db/query/plan_executor.h" #include "mongo/db/query/runner.h" @@ -49,6 +49,8 @@ namespace mongo { Runner::RunnerState state = _exec->getNext(objOut); if (Runner::RUNNER_EOF == state && !_updatedCache) { + _updatedCache = true; + // We're done. Update the cache. PlanCache* cache = PlanCache::get(_canonicalQuery->ns()); @@ -62,8 +64,8 @@ namespace mongo { if (!cache->remove(*_canonicalQuery, *_cachedQuery->solution)) { warning() << "Cached plan runner couldn't remove plan from cache. Maybe" " somebody else did already?"; + return Runner::RUNNER_EOF; } - return Runner::RUNNER_EOF; } // We're done running. Update cache. diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp index ee546150adc..4e4aec737ee 100644 --- a/src/mongo/db/query/canonical_query.cpp +++ b/src/mongo/db/query/canonical_query.cpp @@ -25,8 +25,8 @@ namespace mongo { Status CanonicalQuery::canonicalize(QueryMessage& qm, CanonicalQuery** out) { auto_ptr<CanonicalQuery> cq(new CanonicalQuery()); - // TODO: ParsedQuery throws. Fix it to return error. - cq->_pq.reset(new ParsedQuery(qm)); + // TODO: LiteParsedQuery throws. Fix it to return error. + cq->_pq.reset(new LiteParsedQuery(qm)); // TODO: If pq.hasOption(QueryOption_CursorTailable) make sure it's a capped collection and // make sure the order(??) is $natural: 1. @@ -49,11 +49,11 @@ namespace mongo { CanonicalQuery** out) { auto_ptr<CanonicalQuery> cq(new CanonicalQuery()); - // ParsedQuery saves the pointer to the NS that we provide it. It's not going to remain + // LiteParsedQuery saves the pointer to the NS that we provide it. It's not going to remain // valid unless we cache it ourselves. cq->_ns = ns; - cq->_pq.reset(new ParsedQuery(cq->_ns.c_str(), 0, 0, 0, query, BSONObj())); + cq->_pq.reset(new LiteParsedQuery(cq->_ns.c_str(), 0, 0, 0, query)); StatusWithMatchExpression swme = MatchExpressionParser::parse(cq->_pq->getFilter()); if (!swme.isOK()) { return swme.getStatus(); } diff --git a/src/mongo/db/query/canonical_query.h b/src/mongo/db/query/canonical_query.h index 219e527e4db..5631c0a2f8e 100644 --- a/src/mongo/db/query/canonical_query.h +++ b/src/mongo/db/query/canonical_query.h @@ -20,13 +20,13 @@ #include "mongo/db/dbmessage.h" #include "mongo/db/jsobj.h" #include "mongo/db/matcher/expression.h" -#include "mongo/db/parsed_query.h" +#include "mongo/db/query/lite_parsed_query.h" namespace mongo { class CanonicalQuery { public: - // TODO: qm is mutable because ParsedQuery wants it mutable. FIX. + // TODO: qm is mutable because LiteParsedQuery wants it mutable. FIX. static Status canonicalize(QueryMessage& qm, CanonicalQuery** out); // This is for testing, when we don't have a QueryMessage. @@ -40,7 +40,7 @@ namespace mongo { // MatchExpression* root() const { return _root.get(); } BSONObj getQueryObj() const { return _pq->getFilter(); } - const ParsedQuery& getParsed() const { return *_pq; } + const LiteParsedQuery& getParsed() const { return *_pq; } string toString() const; @@ -48,7 +48,7 @@ namespace mongo { // You must go through canonicalize to create a CanonicalQuery. CanonicalQuery() { } - scoped_ptr<ParsedQuery> _pq; + scoped_ptr<LiteParsedQuery> _pq; // _root points into _pq->getFilter() scoped_ptr<MatchExpression> _root; diff --git a/src/mongo/db/query/index_bounds.cpp b/src/mongo/db/query/index_bounds.cpp index b6e953f4d7a..e72e51ccf1f 100644 --- a/src/mongo/db/query/index_bounds.cpp +++ b/src/mongo/db/query/index_bounds.cpp @@ -29,6 +29,39 @@ namespace { namespace mongo { + // For debugging. + string IndexBounds::toString() const { + stringstream ss; + for (size_t i = 0; i < fields.size(); ++i) { + if (i > 0) { + ss << ", "; + } + const OrderedIntervalList& oil = fields[i]; + ss << "field #" << i << "['" << oil.name << "']: "; + for (size_t j = 0; j < oil.intervals.size(); ++j) { + const Interval& iv = oil.intervals[j]; + if (iv.startInclusive) { + ss << "["; + } + else { + ss << "("; + } + // false means omit the field name + ss << iv.start.toString(false); + ss << ", "; + ss << iv.end.toString(false); + if (iv.endInclusive) { + ss << "]"; + } + else { + ss << ")"; + } + } + } + + return ss.str(); + } + // // Validity checking for bounds // @@ -54,12 +87,17 @@ namespace mongo { for (size_t j = 0; j < field.intervals.size(); ++j) { // false means don't consider field name. int cmp = sgn(field.intervals[j].end.woCompare(field.intervals[j].start, false)); + + if (cmp == 0 && field.intervals[j].startInclusive + && field.intervals[j].endInclusive) { continue; } + if (cmp != expectedOrientation) { return false; } } // Make sure each interval is oriented correctly with respect to its neighbors. for (size_t j = 1; j < field.intervals.size(); ++j) { - int cmp = sgn(field.intervals[j].start.woCompare(field.intervals[j - 1].end, false)); + int cmp = sgn(field.intervals[j].start.woCompare(field.intervals[j - 1].end, + false)); if (cmp == 0) { // The end of one interval is the start of another. This is only valid if diff --git a/src/mongo/db/query/index_bounds.h b/src/mongo/db/query/index_bounds.h index c8d43ed6f85..fd0ce078a81 100644 --- a/src/mongo/db/query/index_bounds.h +++ b/src/mongo/db/query/index_bounds.h @@ -59,6 +59,8 @@ namespace mongo { // For each indexed field, the values that the field is allowed to take on. vector<OrderedIntervalList> fields; + string toString() const; + // Debugging check. // We must have as many fields the key pattern does. // The fields must be oriented in the direction we'd encounter them given the indexing diff --git a/src/mongo/db/query/lite_parsed_query.cpp b/src/mongo/db/query/lite_parsed_query.cpp new file mode 100644 index 00000000000..ff2d27e2792 --- /dev/null +++ b/src/mongo/db/query/lite_parsed_query.cpp @@ -0,0 +1,207 @@ +/* Copyright 2013 10gen Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "mongo/db/query/lite_parsed_query.h" + +#include "mongo/db/dbmessage.h" +#include "mongo/util/assert_util.h" + +namespace mongo { + + // XXX: THIS DOESNT BELONG HERE + /* We cut off further objects once we cross this threshold; thus, you might get + a little bit more than this, it is a threshold rather than a limit. + */ + static const int32_t MaxBytesToReturnToClientAtOnce = 4 * 1024 * 1024; + + LiteParsedQuery::LiteParsedQuery( QueryMessage& qm ) : + _ns( qm.ns ), + _ntoskip( qm.ntoskip ), + _ntoreturn( qm.ntoreturn ), + _options( qm.queryOptions ) { + init( qm.query ); + } + + LiteParsedQuery::LiteParsedQuery( const char* ns, + int ntoskip, + int ntoreturn, + int queryoptions, + const BSONObj& query) : + _ns( ns ), + _ntoskip( ntoskip ), + _ntoreturn( ntoreturn ), + _options( queryoptions ) { + init( query ); + } + + bool LiteParsedQuery::hasIndexSpecifier() const { + return ! _hint.isEmpty() || ! _min.isEmpty() || ! _max.isEmpty(); + } + + // XXX THIS DOESNT BELONG HERE + bool LiteParsedQuery::enoughForFirstBatch( int n , int len ) const { + if ( _ntoreturn == 0 ) + return ( len > 1024 * 1024 ) || n >= 101; + return n >= _ntoreturn || len > MaxBytesToReturnToClientAtOnce; + } + + bool LiteParsedQuery::enough( int n ) const { + if ( _ntoreturn == 0 ) + return false; + return n >= _ntoreturn; + } + + bool LiteParsedQuery::enoughForExplain( long long n ) const { + if ( _wantMore || _ntoreturn == 0 ) { + return false; + } + return n >= _ntoreturn; + } + + void LiteParsedQuery::init( const BSONObj& q ) { + _reset(); + uassert(17032, "bad skip value in query", _ntoskip >= 0); + + if ( _ntoreturn < 0 ) { + /* _ntoreturn greater than zero is simply a hint on how many objects to send back per + "cursor batch". + A negative number indicates a hard limit. + */ + _wantMore = false; + _ntoreturn = -_ntoreturn; + } + + + BSONElement e = q["query"]; + if ( ! e.isABSONObj() ) + e = q["$query"]; + + if ( e.isABSONObj() ) { + _filter = e.embeddedObject().getOwned(); + _initTop( q ); + } + else { + _filter = q.getOwned(); + } + + // + // Parse options that are valid for both queries and commands + // + + // $readPreference + _hasReadPref = q.hasField("$readPreference"); + + // $maxTimeMS + BSONElement maxTimeMSElt = q.getField("$maxTimeMS"); + if (!maxTimeMSElt.eoo()) { + uassert(17033, + mongoutils::str::stream() << + "$maxTimeMS must be a number type, instead found type: " << + maxTimeMSElt.type(), + maxTimeMSElt.isNumber()); + } + // If $maxTimeMS was not specified, _maxTimeMS is set to 0 (special value for "allow to + // run indefinitely"). + long long maxTimeMSLongLong = maxTimeMSElt.safeNumberLong(); + uassert(17034, + "$maxTimeMS out of range [0,2147483647]", + maxTimeMSLongLong >= 0 && maxTimeMSLongLong <= INT_MAX); + _maxTimeMS = static_cast<int>(maxTimeMSLongLong); + } + + void LiteParsedQuery::_reset() { + _wantMore = true; + _explain = false; + _snapshot = false; + _returnKey = false; + _showDiskLoc = false; + _maxScan = 0; + } + + /* This is for languages whose "objects" are not well ordered (JSON is well ordered). + [ { a : ... } , { b : ... } ] -> { a : ..., b : ... } + */ + static BSONObj transformOrderFromArrayFormat(BSONObj order) { + /* note: this is slow, but that is ok as order will have very few pieces */ + BSONObjBuilder b; + char p[2] = "0"; + + while ( 1 ) { + BSONObj j = order.getObjectField(p); + if ( j.isEmpty() ) + break; + BSONElement e = j.firstElement(); + uassert(17035, "bad order array", !e.eoo()); + uassert(17036, "bad order array [2]", e.isNumber()); + b.append(e); + (*p)++; + uassert(17037, "too many ordering elements", *p <= '9'); + } + + return b.obj(); + } + + void LiteParsedQuery::_initTop( const BSONObj& top ) { + BSONObjIterator i( top ); + while ( i.more() ) { + BSONElement e = i.next(); + const char * name = e.fieldName(); + + if ( strcmp( "$orderby" , name ) == 0 || + strcmp( "orderby" , name ) == 0 ) { + if ( e.type() == Object ) { + _order = e.embeddedObject(); + } + else if ( e.type() == Array ) { + _order = transformOrderFromArrayFormat( _order ); + } + else { + uasserted(17038, "sort must be an object or array"); + } + continue; + } + + if( *name == '$' ) { + name++; + if ( strcmp( "explain" , name ) == 0 ) + _explain = e.trueValue(); + else if ( strcmp( "snapshot" , name ) == 0 ) + _snapshot = e.trueValue(); + else if ( strcmp( "min" , name ) == 0 ) + _min = e.embeddedObject(); + else if ( strcmp( "max" , name ) == 0 ) + _max = e.embeddedObject(); + else if ( strcmp( "hint" , name ) == 0 ) + _hint = e.wrap(); + else if ( strcmp( "returnKey" , name ) == 0 ) + _returnKey = e.trueValue(); + else if ( strcmp( "maxScan" , name ) == 0 ) + _maxScan = e.numberInt(); + else if ( strcmp( "showDiskLoc" , name ) == 0 ) + _showDiskLoc = e.trueValue(); + else if ( strcmp( "comment" , name ) == 0 ) { + ; // no-op + } + } + } + + if ( _snapshot ) { + uassert(17039, "E12001 can't sort with $snapshot", _order.isEmpty() ); + uassert(17050, "E12002 can't use hint with $snapshot", _hint.isEmpty() ); + } + + } + +} // namespace mongo diff --git a/src/mongo/db/query/lite_parsed_query.h b/src/mongo/db/query/lite_parsed_query.h new file mode 100644 index 00000000000..e84112872a8 --- /dev/null +++ b/src/mongo/db/query/lite_parsed_query.h @@ -0,0 +1,116 @@ +/* Copyright 2013 10gen Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#include "mongo/db/jsobj.h" + +namespace mongo { + + class QueryMessage; + + /** + * Parses the QueryMessage received from the user and makes the various fields more easily + * accessible. + * + * TODO: This is ported from mongo/db/parsed_query.cpp. It needs some clean-up. In particular + * it should be parse-only. No query logic. + * + * Notably missing is a projection. + */ + + /** + * this represents a total user query + * includes fields from the query message, both possible query levels + * parses everything up front + */ + class LiteParsedQuery { + public: + LiteParsedQuery(QueryMessage& qm); + + LiteParsedQuery(const char* ns, + int ntoskip, + int ntoreturn, + int queryoptions, + const BSONObj& query); + + const char* ns() const { return _ns; } + bool isLocalDB() const { return strncmp( _ns, "local.", 6 ) == 0; } + + const BSONObj& getFilter() const { return _filter; } + + int getSkip() const { return _ntoskip; } + int getNumToReturn() const { return _ntoreturn; } + bool wantMore() const { return _wantMore; } + int getOptions() const { return _options; } + bool hasOption(int x) const { return ( x & _options ) != 0; } + bool hasReadPref() const { return _hasReadPref; } + + bool isExplain() const { return _explain; } + bool isSnapshot() const { return _snapshot; } + bool returnKey() const { return _returnKey; } + bool showDiskLoc() const { return _showDiskLoc; } + + const BSONObj& getMin() const { return _min; } + const BSONObj& getMax() const { return _max; } + const BSONObj& getOrder() const { return _order; } + const BSONObj& getHint() const { return _hint; } + int getMaxScan() const { return _maxScan; } + int getMaxTimeMS() const { return _maxTimeMS; } + + bool hasIndexSpecifier() const; + + /* if ntoreturn is zero, we return up to 101 objects. on the subsequent getmore, there + is only a size limit. The idea is that on a find() where one doesn't use much results, + we don't return much, but once getmore kicks in, we start pushing significant quantities. + + The n limit (vs. size) is important when someone fetches only one small field from big + objects, which causes massive scanning server-side. + */ + bool enoughForFirstBatch( int n, int len ) const; + + bool enough( int n ) const; + + bool enoughForExplain( long long n ) const; + + private: + void init( const BSONObj& q ); + + void _reset(); + + void _initTop( const BSONObj& top ); + + void initFields( const BSONObj& fields ); + + const char* const _ns; + const int _ntoskip; + int _ntoreturn; + BSONObj _filter; + BSONObj _order; + const int _options; + bool _wantMore; + bool _explain; + bool _snapshot; + bool _returnKey; + bool _showDiskLoc; + bool _hasReadPref; + BSONObj _min; + BSONObj _max; + BSONObj _hint; + int _maxScan; + int _maxTimeMS; + }; + +} // namespace mongo diff --git a/src/mongo/db/query/multi_plan_runner.cpp b/src/mongo/db/query/multi_plan_runner.cpp index 34882ca5338..a982a35a356 100644 --- a/src/mongo/db/query/multi_plan_runner.cpp +++ b/src/mongo/db/query/multi_plan_runner.cpp @@ -79,7 +79,12 @@ namespace mongo { bool MultiPlanRunner::forceYield() { saveState(); ClientCursor::registerRunner(this); - ClientCursor::staticYield(ClientCursor::suggestYieldMicros(), getQuery().getParsed().ns(), NULL); + ClientCursor::staticYield(ClientCursor::suggestYieldMicros(), + getQuery().getParsed().ns(), + NULL); + // During the yield, the database we're operating over or any collection we're relying on + // may be dropped. When this happens all cursors and runners on that database and + // collection are killed or deleted in some fashion. (This is how the _killed gets set.) ClientCursor::deregisterRunner(this); if (!_killed) { restoreState(); } return !_killed; diff --git a/src/mongo/db/query/multi_plan_runner.h b/src/mongo/db/query/multi_plan_runner.h index 248713e3109..ec35d8ffde5 100644 --- a/src/mongo/db/query/multi_plan_runner.h +++ b/src/mongo/db/query/multi_plan_runner.h @@ -23,8 +23,8 @@ #include "mongo/db/exec/working_set.h" #include "mongo/db/exec/plan_stage.h" #include "mongo/db/jsobj.h" -#include "mongo/db/parsed_query.h" #include "mongo/db/query/canonical_query.h" +#include "mongo/db/query/lite_parsed_query.h" #include "mongo/db/query/plan_ranker.h" #include "mongo/db/query/plan_executor.h" #include "mongo/db/query/runner.h" diff --git a/src/mongo/db/query/new_find.cpp b/src/mongo/db/query/new_find.cpp index cb9b0b3be13..4c5d050c6b4 100644 --- a/src/mongo/db/query/new_find.cpp +++ b/src/mongo/db/query/new_find.cpp @@ -121,7 +121,8 @@ namespace mongo { Client::ReadContext ctx(ns); // TODO: Document. - replVerifyReadsOk(); + // TODO: do this when we can pass in our own parsed query + //replVerifyReadsOk(); ClientCursorPin ccPin(cursorid); ClientCursor* cc = ccPin.c(); @@ -162,7 +163,7 @@ namespace mongo { startingResult = cc->pos(); Runner* runner = cc->getRunner(); - const ParsedQuery& pq = runner->getQuery().getParsed(); + const LiteParsedQuery& pq = runner->getQuery().getParsed(); // Get results out of the runner. // TODO: There may be special handling required for tailable cursors? @@ -244,10 +245,11 @@ namespace mongo { const ChunkVersion shardingVersionAtStart = shardingState.getVersion(q.ns); // We use this a lot below. - const ParsedQuery& pq = runner->getQuery().getParsed(); + const LiteParsedQuery& pq = runner->getQuery().getParsed(); // TODO: Document why we do this. - replVerifyReadsOk(&pq); + // TODO: do this when we can pass in our own parsed query + //replVerifyReadsOk(&pq); // If this exists, the collection is sharded. // If it doesn't exist, we can assume we're not sharded. diff --git a/src/mongo/db/query/plan_executor.h b/src/mongo/db/query/plan_executor.h index e4e3bf47997..f140fac7e12 100644 --- a/src/mongo/db/query/plan_executor.h +++ b/src/mongo/db/query/plan_executor.h @@ -25,6 +25,11 @@ namespace mongo { /** + * + * A PlanExecutor is the abstraction that knows how to crank a tree of stages into execution. + * The executor is usually part of a larger abstraction that is interacting with the cache + * and/or the query optimizer. + * * Executes a plan. Used by a runner. Calls work() on a plan until a result is produced. * Stops when the plan is EOF or if the plan errors. * @@ -40,7 +45,7 @@ namespace mongo { WorkingSet* getWorkingSet() { return _workingSet.get(); } /** - * Takes ownership of root. + * Takes ownership of root (and therefore the entire tree). */ void setRoot(PlanStage* root) { verify(root); diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp index e09749e59aa..3e26e0d1b51 100644 --- a/src/mongo/db/query/query_planner.cpp +++ b/src/mongo/db/query/query_planner.cpp @@ -46,9 +46,125 @@ namespace mongo { // Add this solution to the list of solutions. soln->root.reset(csn); out->push_back(soln.release()); + } + } + + void getIndicesStartingWith(const StringData& field, const BSONObjSet& kps, BSONObjSet* out) { + for (BSONObjSet::const_iterator i = kps.begin(); i != kps.end(); ++i) { + const BSONObj& obj = *i; + if (field == obj.firstElement().fieldName()) { + out->insert(obj); + } + } + } + + BSONObj objFromElement(const BSONElement& elt) { + BSONObjBuilder bob; + bob.append(elt); + return bob.obj(); + } + + /** + * Make a point interval from the provided object. + * The object must have exactly one field which is the value of the point interval. + */ + Interval makePointInterval(const BSONObj& obj) { + Interval ret; + ret._intervalData = obj; + ret.startInclusive = ret.endInclusive = true; + ret.start = ret.end = obj.firstElement(); + return ret; + } + + /** + * Make a range interval from the provided object. + * The object must have exactly two fields. The first field is the start, the second the end. + * The two inclusive flags indicate whether or not the start/end fields are included in the + * interval (closed interval if included, open if not). + */ + Interval makeRangeInterval(const BSONObj& obj, bool startInclusive, bool endInclusive) { + Interval ret; + ret._intervalData = obj; + ret.startInclusive = startInclusive; + ret.endInclusive = endInclusive; + BSONObjIterator it(obj); + verify(it.more()); + ret.start = it.next(); + verify(it.more()); + ret.end = it.next(); + return ret; + } - // TODO: limit and skip - // TODO: sort. + void QueryPlanner::planWithIndices(const CanonicalQuery& query, + const BSONObjSet& indexKeyPatterns, + vector<QuerySolution*>* out) { + const MatchExpression* root = query.root(); + + if (MatchExpression::EQ == root->matchType()) { + const EqualityMatchExpression* node = static_cast<const EqualityMatchExpression*>(root); + + // TODO: this is going to be cached/precomputed in a smarter way. + BSONObjSet overField; + getIndicesStartingWith(node->path(), indexKeyPatterns, &overField); + + // No indices over the field, can't do anything here. + if (overField.empty()) { return; } + + // We have to copy the data out of the parse tree and stuff it into the index bounds. + // BSONValue will be useful here. + BSONObj dataObj = objFromElement(node->getData()); + verify(dataObj.isOwned()); + + // Every index that we're using to satisfy this query has these bounds. It may also + // have other fields + OrderedIntervalList oil(node->path().toString()); + oil.intervals.push_back(makePointInterval(dataObj)); + IndexBounds commonBounds; + commonBounds.fields.push_back(oil); + + // For every index that we can use... + for (BSONObjSet::iterator it = overField.begin(); it != overField.end(); ++it) { + const BSONObj& indexKeyPattern = *it; + + // Create an index scan solution node. + IndexScanNode* ixscan = new IndexScanNode(); + ixscan->indexKeyPattern = indexKeyPattern; + // Copy the common bounds. + ixscan->bounds = commonBounds; + // And add min/max key bounds to any trailing fields. + BSONObjIterator it(indexKeyPattern); + // Skip the field we're indexed on. + it.next(); + // And for every other field. + while (it.more()) { + BSONElement elt = it.next(); + + // ARGH, BSONValue would make this shorter. + BSONObjBuilder bob; + if (-1 == elt.number()) { + // Index should go from MaxKey to MinKey + bob.appendMaxKey(""); + bob.appendMinKey(""); + } + else { + // Index goes from MinKey to MaxKey + bob.appendMinKey(""); + bob.appendMaxKey(""); + } + OrderedIntervalList oil(elt.fieldName()); + oil.intervals.push_back(makeRangeInterval(bob.obj(), true, true)); + ixscan->bounds.fields.push_back(oil); + } + + // TODO: This can be a debug check eventually. + // TODO: We might change the direction depending on the requested sort. + verify(ixscan->bounds.isValidFor(indexKeyPattern, 1)); + + // Wrap the ixscan in a solution node. + QuerySolution* soln = new QuerySolution(); + soln->root.reset(ixscan); + out->push_back(soln); + } } } diff --git a/src/mongo/db/query/query_planner.h b/src/mongo/db/query/query_planner.h index dcfc5ecf9d2..1210365c9b7 100644 --- a/src/mongo/db/query/query_planner.h +++ b/src/mongo/db/query/query_planner.h @@ -35,6 +35,16 @@ namespace mongo { */ static void plan(const CanonicalQuery& query, vector<QuerySolution*>* out); + /** + * Outputs a series of possible solutions for the provided 'query' into 'out'. Uses the + * provided indices to generate a solution. + * + * Caller owns pointers in *out. + */ + static void planWithIndices(const CanonicalQuery& query, + const BSONObjSet& indexKeyPatterns, + vector<QuerySolution*>* out); + private: /** * Returns true if the tree rooted at 'node' requires an index to answer the query. There diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp new file mode 100644 index 00000000000..5ae32ac0a4d --- /dev/null +++ b/src/mongo/db/query/query_planner_test.cpp @@ -0,0 +1,78 @@ +/** + * 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/>. + */ + +/** + * This file contains tests for mongo/db/query/query_planner.cpp + */ + +#include "mongo/db/query/query_planner.h" +#include "mongo/db/query/query_solution.h" +#include "mongo/db/matcher/expression_parser.h" +#include "mongo/db/json.h" +#include "mongo/db/jsobj.h" +#include "mongo/unittest/unittest.h" +#include "mongo/util/assert_util.h" + +using namespace mongo; + +namespace { + + static const char* ns = "somebogusns"; + + // Test the most basic index-using functionality. + TEST(QueryPlannerTest, EqualityIndexScan) { + // Get the canonical query. + BSONObj queryObj = BSON("x" << 5); + CanonicalQuery* cq; + ASSERT(CanonicalQuery::canonicalize(ns, queryObj, &cq).isOK()); + + // This is our index. It's the simplest index we can use. + BSONObjSet indices; + indices.insert(BSON("x" << 1)); + + // If we can't get this right... + vector<QuerySolution*> solns; + QueryPlanner::planWithIndices(*cq, indices, &solns); + ASSERT_EQUALS(size_t(1), solns.size()); + + QuerySolutionNode* node = solns[0]->root.get(); + ASSERT_EQUALS(STAGE_IXSCAN, node->getType()); + + // TODO: Check bounds. + } + + TEST(QueryPlannerTest, EqualityIndexScanWithTrailingFields) { + BSONObj queryObj = BSON("x" << 5); + + CanonicalQuery* cq; + ASSERT(CanonicalQuery::canonicalize(ns, queryObj, &cq).isOK()); + + BSONObjSet indices; + indices.insert(BSON("x" << 1 << "y" << 1)); + + vector<QuerySolution*> solns; + QueryPlanner::planWithIndices(*cq, indices, &solns); + + // Available index is prefixed by our equality, use it. + ASSERT_EQUALS(size_t(1), solns.size()); + + QuerySolutionNode* node = solns[0]->root.get(); + ASSERT_EQUALS(STAGE_IXSCAN, node->getType()); + + // TODO: Check bounds. + } + +} // namespace diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h index bc57a3c969f..82ee2d5295e 100644 --- a/src/mongo/db/query/query_solution.h +++ b/src/mongo/db/query/query_solution.h @@ -17,6 +17,7 @@ #pragma once #include "mongo/db/matcher/expression.h" +#include "mongo/db/query/index_bounds.h" #include "mongo/db/query/stage_types.h" namespace mongo { @@ -89,7 +90,37 @@ namespace mongo { // Not owned. // This is a sub-tree of the filter in the QuerySolution that owns us. + // TODO: This may change in the future. MatchExpression* filter; }; + struct IndexScanNode : public QuerySolutionNode { + IndexScanNode() : filter(NULL), limit(0), direction(1) { } + + virtual StageType getType() const { return STAGE_IXSCAN; } + + virtual void appendToString(stringstream* ss) const { + *ss << "IXSCAN kp=" << indexKeyPattern; + if (NULL != filter) { + *ss << " filter= " << filter->toString(); + } + *ss << " dir = " << direction; + *ss << " bounds = " << bounds.toString(); + } + + BSONObj indexKeyPattern; + + // Not owned. + // This is a sub-tree of the filter in the QuerySolution that owns us. + // TODO: This may change in the future. + MatchExpression* filter; + + // Only set for 2d. + int limit; + + int direction; + + IndexBounds bounds; + }; + } // namespace mongo diff --git a/src/mongo/db/query/runner.h b/src/mongo/db/query/runner.h index 66fff915c8d..33b54e2875b 100644 --- a/src/mongo/db/query/runner.h +++ b/src/mongo/db/query/runner.h @@ -69,7 +69,8 @@ namespace mongo { /** * Mark the Runner as no longer valid. Can happen when a runner yields and the underlying - * database is dropped/indexes removed/etc. + * database is dropped/indexes removed/etc. All future to calls to getNext return + * RUNNER_DEAD. Every other call is a NOOP. */ virtual void kill() = 0; diff --git a/src/mongo/db/query/simple_plan_runner.h b/src/mongo/db/query/simple_plan_runner.h deleted file mode 100644 index 92d2645777d..00000000000 --- a/src/mongo/db/query/simple_plan_runner.h +++ /dev/null @@ -1,111 +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/>. - */ - -#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 { - - /** - * A placeholder for a full-featured plan runner. Calls work() on a plan until a result is - * produced. Stops when the plan is EOF or if the plan errors. - * - * TODO: Yielding policy - * TODO: Graceful error handling - * TODO: Stats, diagnostics, instrumentation, etc. - * TODO: Rename. It's not a full runner. It just holds the stage/WS and handles yielding. - */ - class SimplePlanRunner { - public: - SimplePlanRunner() : _workingSet(new WorkingSet()) { } - SimplePlanRunner(WorkingSet* ws, PlanStage* rt) : _workingSet(ws), _root(rt) { } - - WorkingSet* getWorkingSet() { return _workingSet.get(); } - - /** - * Takes ownership of root. - */ - void setRoot(PlanStage* root) { - verify(root); - _root.reset(root); - } - - void saveState() { _root->prepareToYield(); } - void restoreState() { _root->recoverFromYield(); } - void invalidate(const DiskLoc& dl) { _root->invalidate(dl); } - - PlanStageStats* getStats() { return _root->getStats(); } - - bool getNext(BSONObj* objOut) { - for (;;) { - WorkingSetID id; - PlanStage::StageState code = _root->work(&id); - - if (PlanStage::ADVANCED == code) { - WorkingSetMember* member = _workingSet->get(id); - uassert(16912, "Couldn't fetch obj from query plan", - WorkingSetCommon::fetch(member)); - *objOut = member->obj; - _workingSet->free(id); - return true; - } - else if (code == PlanStage::NEED_TIME) { - // TODO: Runners can't yield themselves until we rework ClientCursor to not - // delete itself. - } - else if (PlanStage::NEED_FETCH == code) { - // id has a loc and refers to an obj we need to fetch. - WorkingSetMember* member = _workingSet->get(id); - - // This must be true for somebody to request a fetch and can only change when an - // invalidation happens, which is when we give up a lock. Don't give up the - // lock between receiving the NEED_FETCH and actually fetching(?). - verify(member->hasLoc()); - - // Actually bring record into memory. - Record* record = member->loc.rec(); - // TODO: We would yield ourselves here and call ClientCursor::staticYield once - // we rework ClientCursor to not delete itself. - record->touch(); - - // Record should be in memory now. Log if it's not. - if (!Record::likelyInPhysicalMemory(record->dataNoThrowing())) { - OCCASIONALLY { - warning() << "Record wasn't in memory immediately after fetch: " - << member->loc.toString() << endl; - } - } - - // Note that we're not freeing id. Fetch semantics say that we shouldn't. - } - else { - // IS_EOF, FAILURE. We just stop here. - return false; - } - } - } - - private: - scoped_ptr<WorkingSet> _workingSet; - scoped_ptr<PlanStage> _root; - }; - -} // namespace mongo diff --git a/src/mongo/db/query/single_solution_runner.h b/src/mongo/db/query/single_solution_runner.h index f1e43db92ee..246ef12d4e4 100644 --- a/src/mongo/db/query/single_solution_runner.h +++ b/src/mongo/db/query/single_solution_runner.h @@ -17,8 +17,8 @@ #pragma once #include "mongo/db/clientcursor.h" -#include "mongo/db/parsed_query.h" #include "mongo/db/query/canonical_query.h" +#include "mongo/db/query/lite_parsed_query.h" #include "mongo/db/query/plan_cache.h" #include "mongo/db/query/plan_executor.h" #include "mongo/db/query/runner.h" @@ -63,7 +63,6 @@ namespace mongo { virtual void invalidate(const DiskLoc& dl) { if (!_killed) { - cout << "Sending invalidate to exec\n"; _exec->invalidate(dl); } } @@ -75,7 +74,9 @@ namespace mongo { virtual bool forceYield() { saveState(); ClientCursor::registerRunner(this); - ClientCursor::staticYield(ClientCursor::suggestYieldMicros(), getQuery().getParsed().ns(), NULL); + ClientCursor::staticYield(ClientCursor::suggestYieldMicros(), + getQuery().getParsed().ns(), + NULL); ClientCursor::deregisterRunner(this); if (!_killed) { restoreState(); } return !_killed; |