From 222862b67b7cf49075e72457808d297d8438f5d0 Mon Sep 17 00:00:00 2001 From: Hari Khalsa Date: Wed, 6 Nov 2013 14:29:30 -0500 Subject: SERVER-10026 full projection support --- src/mongo/db/query/SConscript | 2 +- src/mongo/db/query/canonical_query.cpp | 11 +- src/mongo/db/query/canonical_query.h | 8 +- src/mongo/db/query/explain_plan.cpp | 1 + src/mongo/db/query/lite_parsed_query.cpp | 2 +- src/mongo/db/query/lite_projection.cpp | 492 +++++++++++++++++++++++++++++++ src/mongo/db/query/lite_projection.h | 188 ++++++++++++ src/mongo/db/query/multi_plan_runner.cpp | 23 +- src/mongo/db/query/multi_plan_runner.h | 1 + src/mongo/db/query/new_find.cpp | 10 +- src/mongo/db/query/parsed_projection.h | 111 ------- src/mongo/db/query/plan_ranker.cpp | 35 ++- src/mongo/db/query/projection_parser.cpp | 80 ----- src/mongo/db/query/projection_parser.h | 48 --- src/mongo/db/query/query_planner.cpp | 16 +- src/mongo/db/query/query_solution.cpp | 4 +- src/mongo/db/query/query_solution.h | 12 +- src/mongo/db/query/stage_builder.cpp | 3 +- 18 files changed, 763 insertions(+), 284 deletions(-) create mode 100644 src/mongo/db/query/lite_projection.cpp create mode 100644 src/mongo/db/query/lite_projection.h delete mode 100644 src/mongo/db/query/parsed_projection.h delete mode 100644 src/mongo/db/query/projection_parser.cpp delete mode 100644 src/mongo/db/query/projection_parser.h (limited to 'src/mongo/db/query') diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript index 204ea5bb060..9dda96b8efb 100644 --- a/src/mongo/db/query/SConscript +++ b/src/mongo/db/query/SConscript @@ -8,8 +8,8 @@ env.StaticLibrary( "canonical_query.cpp", "index_bounds_builder.cpp", "index_tag.cpp", + "lite_projection.cpp", "plan_enumerator.cpp", - "projection_parser.cpp", "qlog.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 642f36a471d..5e8bb6e41fd 100644 --- a/src/mongo/db/query/canonical_query.cpp +++ b/src/mongo/db/query/canonical_query.cpp @@ -30,7 +30,6 @@ #include "mongo/db/jsobj.h" #include "mongo/db/matcher/expression_parser.h" -#include "mongo/db/query/projection_parser.h" namespace mongo { @@ -242,12 +241,12 @@ namespace mongo { _root.reset(root); if (!_pq->getProj().isEmpty()) { - ParsedProjection* proj; - Status projStatus = ProjectionParser::parseFindSyntax(_pq->getProj(), &proj); - if (!projStatus.isOK()) { - return projStatus; + LiteProjection* liteProj = NULL; + Status liteProjStatus = LiteProjection::make(_pq->getFilter(), _pq->getProj(), &liteProj); + if (!liteProjStatus.isOK()) { + return liteProjStatus; } - _proj.reset(proj); + _liteProj.reset(liteProj); } return Status::OK(); diff --git a/src/mongo/db/query/canonical_query.h b/src/mongo/db/query/canonical_query.h index 3b20fc12a92..676827fdfa3 100644 --- a/src/mongo/db/query/canonical_query.h +++ b/src/mongo/db/query/canonical_query.h @@ -33,7 +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" +#include "mongo/db/query/lite_projection.h" namespace mongo { @@ -61,7 +61,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(); } + LiteProjection* getLiteProj() const { return _liteProj.get(); } string toString() const; @@ -74,10 +74,10 @@ namespace mongo { scoped_ptr _pq; - scoped_ptr _proj; - // _root points into _pq->getFilter() scoped_ptr _root; + + scoped_ptr _liteProj; }; } // namespace mongo diff --git a/src/mongo/db/query/explain_plan.cpp b/src/mongo/db/query/explain_plan.cpp index 5ebcd805a96..8731f02e995 100644 --- a/src/mongo/db/query/explain_plan.cpp +++ b/src/mongo/db/query/explain_plan.cpp @@ -135,6 +135,7 @@ namespace mongo { res->setCursor("BasicCursor"); res->setNScanned(csStats->docsTested); res->setNScannedObjects(csStats->docsTested); + res->setIndexOnly(false); } else if (leaf->stageType == STAGE_GEO_NEAR_2DSPHERE) { // TODO: This is kind of a lie for STAGE_GEO_NEAR_2DSPHERE. diff --git a/src/mongo/db/query/lite_parsed_query.cpp b/src/mongo/db/query/lite_parsed_query.cpp index 456ea198ffe..2a46f4a7c4a 100644 --- a/src/mongo/db/query/lite_parsed_query.cpp +++ b/src/mongo/db/query/lite_parsed_query.cpp @@ -95,7 +95,7 @@ namespace mongo { _ntoskip = ntoskip; _ntoreturn = ntoreturn; _options = queryOptions; - _proj = proj; + _proj = proj.getOwned(); if (_ntoskip < 0) { return Status(ErrorCodes::BadValue, "bad skip value in query"); diff --git a/src/mongo/db/query/lite_projection.cpp b/src/mongo/db/query/lite_projection.cpp new file mode 100644 index 00000000000..5e9f999992f --- /dev/null +++ b/src/mongo/db/query/lite_projection.cpp @@ -0,0 +1,492 @@ +/** + * 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 . + * + * 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/lite_projection.h" + +#include "mongo/db/matcher/expression_parser.h" +#include "mongo/db/matcher/expression.h" +#include "mongo/util/mongoutils/str.h" + +namespace mongo { + + // static + Status LiteProjection::make(const BSONObj& query, + const BSONObj& projObj, + LiteProjection** out) { + + auto_ptr proj(new LiteProjection()); + + Status initStatus = proj->init(projObj, query); + if (!initStatus.isOK()) { + return initStatus; + } + + *out = proj.release(); + return Status::OK(); + } + + LiteProjection::LiteProjection() + : _include(true), + _special(false), + _includeID(true), + _skip(0), + _limit(-1), + _arrayOpType(ARRAY_OP_NORMAL), + _hasNonSimple(false), + _hasDottedField(false) { } + + LiteProjection::~LiteProjection() { + for (FieldMap::const_iterator it = _fields.begin(); it != _fields.end(); ++it) { + delete it->second; + } + + for (Matchers::const_iterator it = _matchers.begin(); it != _matchers.end(); ++it) { + delete it->second; + } + } + + Status LiteProjection::init(const BSONObj& spec, const BSONObj& query) { + verify(_source.isEmpty()); + // Save the raw obj. + _source = spec; + verify(_source.isOwned()); + + // Are we including or excluding fields? + // -1 when we haven't initialized it. + // 1 when we're including + // 0 when we're excluding. + int include_exclude = -1; + + BSONObjIterator it(_source); + while (it.more()) { + BSONElement e = it.next(); + + if (!e.isNumber()) { _hasNonSimple = true; } + + if (Object == e.type()) { + BSONObj obj = e.embeddedObject(); + BSONElement e2 = obj.firstElement(); + if (mongoutils::str::equals(e2.fieldName(), "$slice")) { + if (e2.isNumber()) { + int i = e2.numberInt(); + if (i < 0) { + add(e.fieldName(), i, -i); // limit is now positive + } + else { + add(e.fieldName(), 0, i); + } + } + else if (e2.type() == Array) { + BSONObj arr = e2.embeddedObject(); + if (2 != arr.nFields()) { + return Status(ErrorCodes::BadValue, "$slice array wrong size"); + } + + BSONObjIterator it(arr); + int skip = it.next().numberInt(); + int limit = it.next().numberInt(); + if (limit <= 0) { + return Status(ErrorCodes::BadValue, "$slice limit must be positive"); + } + + add(e.fieldName(), skip, limit); + } + else { + return Status(ErrorCodes::BadValue, + "$slice only supports numbers and [skip, limit] arrays"); + } + } + else if (mongoutils::str::equals(e2.fieldName(), "$elemMatch")) { + // Validate $elemMatch arguments and dependencies. + if (Object != e2.type()) { + return Status(ErrorCodes::BadValue, + "elemMatch: Invalid argument, object required."); + } + + if (ARRAY_OP_POSITIONAL == _arrayOpType) { + return Status(ErrorCodes::BadValue, + "Cannot specify positional operator and $elemMatch."); + } + + if (mongoutils::str::contains(e.fieldName(), '.')) { + return Status(ErrorCodes::BadValue, + "Cannot use $elemMatch projection on a nested field."); + } + + _arrayOpType = ARRAY_OP_ELEM_MATCH; + + // Create a MatchExpression for the elemMatch. + BSONObj elemMatchObj = e.wrap(); + verify(elemMatchObj.isOwned()); + _elemMatchObjs.push_back(elemMatchObj); + StatusWithMatchExpression swme = MatchExpressionParser::parse(elemMatchObj); + if (!swme.isOK()) { + return swme.getStatus(); + } + // And store it in _matchers. + _matchers[mongoutils::str::before(e.fieldName(), '.').c_str()] + = swme.getValue(); + + add(e.fieldName(), true); + } + else { + return Status(ErrorCodes::BadValue, + string("Unsupported projection option: ") + e.toString()); + } + } + else if (mongoutils::str::equals(e.fieldName(), "_id") && !e.trueValue()) { + _includeID = false; + } + else { + add(e.fieldName(), e.trueValue()); + + // Projections of dotted fields aren't covered. + if (mongoutils::str::contains(e.fieldName(), '.')) { + _hasDottedField = true; + } + + // Validate input. + if (include_exclude == -1) { + // If we haven't specified an include/exclude, initialize include_exclude. + // We expect further include/excludes to match it. + include_exclude = e.trueValue(); + _include = !e.trueValue(); + } + else if (static_cast(include_exclude) != e.trueValue()) { + // Make sure that the incl./excl. matches the previous. + return Status(ErrorCodes::BadValue, + "Projection cannot have a mix of inclusion and exclusion."); + } + } + + if (mongoutils::str::contains(e.fieldName(), ".$")) { + // Validate the positional op. + if (!e.trueValue()) { + return Status(ErrorCodes::BadValue, + "Cannot exclude array elements with the positional operator."); + } + + if (ARRAY_OP_POSITIONAL == _arrayOpType) { + return Status(ErrorCodes::BadValue, + "Cannot specify more than one positional proj. per query."); + } + + if (ARRAY_OP_ELEM_MATCH == _arrayOpType) { + return Status(ErrorCodes::BadValue, + "Cannot specify positional operator and $elemMatch."); + } + + _arrayOpType = ARRAY_OP_POSITIONAL; + } + } + + if (ARRAY_OP_POSITIONAL != _arrayOpType) { + return Status::OK(); + } + + // Validates positional operator ($) projections. + + // XXX: This is copied from how it was validated before. It should probably walk the + // expression tree...but we maintain this for now. TODO: Remove this and/or make better. + + BSONObjIterator querySpecIter(query); + while (querySpecIter.more()) { + BSONElement queryElement = querySpecIter.next(); + if (mongoutils::str::equals(queryElement.fieldName(), "$and")) { + // don't check $and to avoid deep comparison of the arguments. + // TODO: can be replaced with Matcher::FieldSink when complete (SERVER-4644) + return Status::OK(); + } + + BSONObjIterator projectionSpecIter(_source); + while ( projectionSpecIter.more() ) { + // for each projection element + BSONElement projectionElement = projectionSpecIter.next(); + if ( mongoutils::str::contains( projectionElement.fieldName(), ".$" ) && + mongoutils::str::before( queryElement.fieldName(), '.' ) == + mongoutils::str::before( projectionElement.fieldName(), "." ) ) { + return Status::OK(); + } + } + } + + return Status(ErrorCodes::BadValue, + "Positional operator does not match the query specifier."); + } + + // TODO: stringdata + void LiteProjection::getRequiredFields(vector* fields) const { + if (_includeID) { + fields->push_back("_id"); + } + + // The only way we could be here is if _source is only simple non-dotted-field projections. + // Therefore we can iterate over _source to get the fields required. + BSONObjIterator srcIt(_source); + while (srcIt.more()) { + BSONElement elt = srcIt.next(); + if (elt.trueValue()) { + fields->push_back(elt.fieldName()); + } + } + } + + void LiteProjection::add(const string& field, bool include) { + if (field.empty()) { // this is the field the user referred to + _include = include; + } + else { + // XXX document + _include = !include; + + const size_t dot = field.find('.'); + const string subfield = field.substr(0,dot); + const string rest = (dot == string::npos ? "" : field.substr(dot + 1, string::npos)); + + LiteProjection*& fm = _fields[subfield.c_str()]; + + if (NULL == fm) { + fm = new LiteProjection(); + } + + fm->add(rest, include); + } + } + + void LiteProjection::add(const string& field, int skip, int limit) { + _special = true; // can't include or exclude whole object + + if (field.empty()) { // this is the field the user referred to + _skip = skip; + _limit = limit; + } + else { + const size_t dot = field.find('.'); + const string subfield = field.substr(0,dot); + const string rest = (dot == string::npos ? "" : field.substr(dot + 1, string::npos)); + + LiteProjection*& fm = _fields[subfield.c_str()]; + + if (NULL == fm) { + fm = new LiteProjection(); + } + + fm->add(rest, skip, limit); + } + } + + // + // Execution + // + + Status LiteProjection::transform(const BSONObj& in, + BSONObj* out, + const MatchDetails* details) const { + BSONObjBuilder bob; + Status status = transform(in, &bob, details); + if (!status.isOK()) { + return status; + } + *out = bob.obj(); + return Status::OK(); + } + + Status LiteProjection::transform(const BSONObj& in, + BSONObjBuilder* bob, + const MatchDetails* details) const { + + const ArrayOpType& arrayOpType = _arrayOpType; + + BSONObjIterator it(in); + while (it.more()) { + BSONElement elt = it.next(); + + // Case 1: _id + if (mongoutils::str::equals("_id", elt.fieldName())) { + if (_includeID) { + bob->append(elt); + } + continue; + } + + // Case 2: no array projection for this field. + Matchers::const_iterator matcher = _matchers.find(elt.fieldName()); + if (_matchers.end() == matcher) { + append(bob, elt, details, arrayOpType); + continue; + } + + // Case 3: field has array projection with $elemMatch specified. + if (ARRAY_OP_ELEM_MATCH != arrayOpType) { + return Status(ErrorCodes::BadValue, + "Matchers are only supported for $elemMatch"); + } + + MatchDetails arrayDetails; + arrayDetails.requestElemMatchKey(); + + if (matcher->second->matchesBSON(in, &arrayDetails)) { + FieldMap::const_iterator fieldIt = _fields.find(elt.fieldName()); + if (_fields.end() == fieldIt) { + return Status(ErrorCodes::BadValue, + "$elemMatch specified, but projection field not found."); + } + + BSONArrayBuilder arrBuilder; + BSONObjBuilder subBob; + + if (in.getField(elt.fieldName()).eoo()) { + return Status(ErrorCodes::InternalError, + "$elemMatch called on document element with eoo"); + } + + if (in.getField(elt.fieldName()).Obj().getField(arrayDetails.elemMatchKey()).eoo()) { + return Status(ErrorCodes::InternalError, + "$elemMatch called on array element with eoo"); + } + + arrBuilder.append( + in.getField(elt.fieldName()).Obj().getField(arrayDetails.elemMatchKey())); + subBob.appendArray(matcher->first, arrBuilder.arr()); + Status status = append(bob, subBob.done().firstElement(), details, arrayOpType); + if (!status.isOK()) { + return status; + } + } + } + + return Status::OK(); + } + + void LiteProjection::appendArray(BSONObjBuilder* bob, const BSONObj& array, bool nested) const { + int skip = nested ? 0 : _skip; + int limit = nested ? -1 : _limit; + + if (skip < 0) { + skip = max(0, skip + array.nFields()); + } + + int index = 0; + BSONObjIterator it(array); + while (it.more()) { + BSONElement elt = it.next(); + + if (skip) { + skip--; + continue; + } + + if (limit != -1 && (limit-- == 0)) { + break; + } + + switch(elt.type()) { + case Array: { + BSONObjBuilder subBob; + appendArray(&subBob, elt.embeddedObject(), true); + bob->appendArray(bob->numStr(index++), subBob.obj()); + break; + } + case Object: { + BSONObjBuilder subBob; + BSONObjIterator jt(elt.embeddedObject()); + while (jt.more()) { + append(&subBob, jt.next()); + } + bob->append(bob->numStr(index++), subBob.obj()); + break; + } + default: + if (_include) { + bob->appendAs(elt, bob->numStr(index++)); + } + } + } + } + + Status LiteProjection::append(BSONObjBuilder* bob, + const BSONElement& elt, + const MatchDetails* details, + const ArrayOpType arrayOpType) const { + + FieldMap::const_iterator field = _fields.find(elt.fieldName()); + if (field == _fields.end()) { + if (_include) { + bob->append(elt); + } + return Status::OK(); + } + + LiteProjection& subfm = *field->second; + if ((subfm._fields.empty() && !subfm._special) + || !(elt.type() == Object || elt.type() == Array)) { + // field map empty, or element is not an array/object + if (subfm._include) { + bob->append(elt); + } + } + else if (elt.type() == Object) { + BSONObjBuilder subBob; + BSONObjIterator it(elt.embeddedObject()); + while (it.more()) { + subfm.append(&subBob, it.next(), details, arrayOpType); + } + bob->append(elt.fieldName(), subBob.obj()); + } + else { + // Array + BSONObjBuilder matchedBuilder; + if (details && arrayOpType == ARRAY_OP_POSITIONAL) { + // $ positional operator specified + if (!details->hasElemMatchKey()) { + stringstream error; + error << "positional operator (" << elt.fieldName() + << ".$) requires corresponding field" + << " in query specifier"; + return Status(ErrorCodes::BadValue, error.str()); + } + + if (elt.embeddedObject()[details->elemMatchKey()].eoo()) { + return Status(ErrorCodes::BadValue, + "positional operator element mismatch"); + } + + // append as the first and only element in the projected array + matchedBuilder.appendAs( elt.embeddedObject()[details->elemMatchKey()], "0" ); + } + else { + // append exact array; no subarray matcher specified + subfm.appendArray(&matchedBuilder, elt.embeddedObject()); + } + bob->appendArray(elt.fieldName(), matchedBuilder.obj()); + } + + return Status::OK(); + } + +} // namespace mongo diff --git a/src/mongo/db/query/lite_projection.h b/src/mongo/db/query/lite_projection.h new file mode 100644 index 00000000000..7958b55c85a --- /dev/null +++ b/src/mongo/db/query/lite_projection.h @@ -0,0 +1,188 @@ +/** + * 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 . + * + * 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/jsobj.h" +#include "mongo/db/matcher/expression.h" +#include "mongo/util/string_map.h" + +namespace mongo { + + class LiteProjection { + public: + typedef StringMap FieldMap; + typedef StringMap Matchers; + + enum ArrayOpType { + ARRAY_OP_NORMAL = 0, + ARRAY_OP_ELEM_MATCH, + ARRAY_OP_POSITIONAL + }; + + /** + * Use this to create a LiteProjection. + * + * 'query' is the user's query, used to ensure that the query is consistent with any + * positional operators in the projection. + * + * 'projObj' is the projection. + * + * If 'projObj' is valid (with respect to 'query'), returns Status::OK() and populates *out. + * Caller owns the pointer. + * + * Otherwise, returns an error. + */ + static Status make(const BSONObj& query, const BSONObj& projObj, LiteProjection** out); + + ~LiteProjection(); + + /** + * Is the full document required to compute this projection? + */ + bool requiresDocument() const { + return _include || _hasNonSimple || _hasDottedField; + } + + /** + * Return the fields required to compute the projection in 'fields'. + * + * Assumes that requiresDocument() is false and may produce bogus results if + * requiresDocument() is true. + */ + void getRequiredFields(vector* fields) const; + + /** + * Apply the projection that 'this' represents to the object 'in'. 'details' is the result + * of a match evaluation of the full query on the object 'in'. This is only required + * if the projection is positional. + * + * If the projection is successfully computed, returns Status::OK() and populates 'out'. + * Otherwise, returns error. + */ + Status transform(const BSONObj& in, BSONObj* out, const MatchDetails* details = NULL) const; + + /** + * See transform(...) above. + */ + bool transformRequiresDetails() const { + return ARRAY_OP_POSITIONAL == _arrayOpType; + } + + /** + * Used for debugging. + */ + const BSONObj& getProjectionSpec() const { return _source; } + + private: + friend class ProjectionStage; + + // + // Initialization + // + + /** + * We keep this private so that one must call ::make to create a new instance. + */ + LiteProjection(); + + /** + * Initialize the projection from the provided BSONObj. + * Returns Status::OK() if the provided projection spec is valid. + * Otherwise, returns an error. + */ + Status init(const BSONObj& spec, const BSONObj& query); + + /** + * Add 'field' to the set of things to be projected. + * 'include' specifies whether or not 'field' is to be included or dropped. + * 'skip' and 'limit' are for $slice. + */ + void add(const string& field, bool include); + void add(const string& field, int skip, int limit); + + // + // Execution + // TODO: Move into exec/projection.cpp or elsewhere. + // + + /** + * See transform(...) above. + */ + Status transform(const BSONObj& in, + BSONObjBuilder* bob, + const MatchDetails* details = NULL) const; + + /** + * Appends the element 'e' to the builder 'bob', possibly descending into sub-fields of 'e' + * if needed. + */ + Status append(BSONObjBuilder* bob, + const BSONElement& elt, + const MatchDetails* details = NULL, + const ArrayOpType arrayOpType = ARRAY_OP_NORMAL) const; + + // XXX document + void appendArray(BSONObjBuilder* bob, const BSONObj& array, bool nested = false) const; + + // True if default at this level is to include. + bool _include; + + // True if this level can't be skipped or included without recursing. + bool _special; + + // TODO: benchmark vector vs map + // XXX: document + FieldMap _fields; + + // The raw projection spec. that is passed into init(...) + BSONObj _source; + + // Should we include the _id field? + bool _includeID; + + // Arguments from the $slice operator. + int _skip; + int _limit; + + // Used for $elemMatch and positional operator ($) + Matchers _matchers; + + // The matchers above point into BSONObjs and this is where those objs live. + vector _elemMatchObjs; + + ArrayOpType _arrayOpType; + + // Is there an elemMatch or positional operator? + bool _hasNonSimple; + + // Is there a projection over a dotted field? + bool _hasDottedField; + }; + +} // namespace mongo diff --git a/src/mongo/db/query/multi_plan_runner.cpp b/src/mongo/db/query/multi_plan_runner.cpp index e60f83290bc..6f0da6c7731 100644 --- a/src/mongo/db/query/multi_plan_runner.cpp +++ b/src/mongo/db/query/multi_plan_runner.cpp @@ -149,6 +149,21 @@ namespace mongo { } if (NULL != _backupPlan) { _backupPlan->invalidate(dl); + for (list::iterator it = _backupAlreadyProduced.begin(); + it != _backupAlreadyProduced.end();) { + WorkingSetMember* member = _backupPlan->getWorkingSet()->get(*it); + if (member->hasLoc() && member->loc == dl) { + list::iterator next = it; + next++; + WorkingSetCommon::fetchAndInvalidateLoc(member); + _backupPlan->getWorkingSet()->flagForReview(*it); + _backupAlreadyProduced.erase(it); + it = next; + } + else { + it++; + } + } } } else { @@ -248,7 +263,8 @@ namespace mongo { _backupPlan = NULL; _bestSolution.reset(_backupSolution); _backupSolution = NULL; - return _bestPlan->getNext(objOut, dlOut); + _alreadyProduced = _backupAlreadyProduced; + return getNext(objOut, dlOut); } if (NULL != _backupSolution && Runner::RUNNER_ADVANCED == state) { @@ -257,6 +273,8 @@ namespace mongo { delete _backupPlan; _backupSolution = NULL; _backupPlan = NULL; + // TODO: free from WS? + _backupAlreadyProduced.clear(); } return state; @@ -288,12 +306,11 @@ namespace mongo { if (_bestSolution->hasSortStage && (0 == _alreadyProduced.size())) { QLOG() << "Winner has blocked sort, looking for backup plan...\n"; for (size_t i = 0; i < _candidates.size(); ++i) { - // TODO: if we drastically change plan ranking, this will die. - verify(0 == _candidates[i].results.size()); if (!_candidates[i].solution->hasSortStage) { QLOG() << "Candidate " << i << " is backup child\n"; backupChild = i; _backupSolution = _candidates[i].solution; + _backupAlreadyProduced = _candidates[i].results; _backupPlan = new PlanExecutor(_candidates[i].ws, _candidates[i].root); _backupPlan->setYieldPolicy(_policy); break; diff --git a/src/mongo/db/query/multi_plan_runner.h b/src/mongo/db/query/multi_plan_runner.h index d045aa0f49e..db643d3ac55 100644 --- a/src/mongo/db/query/multi_plan_runner.h +++ b/src/mongo/db/query/multi_plan_runner.h @@ -156,6 +156,7 @@ namespace mongo { QuerySolution* _backupSolution; PlanExecutor* _backupPlan; + std::list _backupAlreadyProduced; }; } // namespace mongo diff --git a/src/mongo/db/query/new_find.cpp b/src/mongo/db/query/new_find.cpp index ef0cc4cebfa..d340e0db21c 100644 --- a/src/mongo/db/query/new_find.cpp +++ b/src/mongo/db/query/new_find.cpp @@ -124,15 +124,7 @@ namespace mongo { const LiteParsedQuery& pq = cq->getParsed(); - // Things we know we fail at: - - // Projections. - if (!pq.getProj().isEmpty()) { - QLOG() << "rejecting query w/proj\n"; - return false; - } - - // Obscure arguments to .find(). + // We fail to deal well with obscure arguments to .find(). if (pq.returnKey() || pq.showDiskLoc() || (0 != pq.getMaxScan()) || !pq.getMin().isEmpty() || !pq.getMax().isEmpty()) { QLOG() << "rejecting wacky query args query\n"; diff --git a/src/mongo/db/query/parsed_projection.h b/src/mongo/db/query/parsed_projection.h deleted file mode 100644 index 883320de631..00000000000 --- a/src/mongo/db/query/parsed_projection.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 . - * - * 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 -#include -#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& 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. - return _excludedFields.size() > 0; - } - - virtual const vector& requiredFields() const { - 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 _excludedFields; - - // ...or you include other fields, which can be ordered. - // UNITTEST 11738048 - vector _includedFields; - }; - -} // namespace mongo diff --git a/src/mongo/db/query/plan_ranker.cpp b/src/mongo/db/query/plan_ranker.cpp index c1589bf8727..f5b9ec543d9 100644 --- a/src/mongo/db/query/plan_ranker.cpp +++ b/src/mongo/db/query/plan_ranker.cpp @@ -96,12 +96,12 @@ namespace mongo { } } - bool hasSort(const PlanStageStats* stats) { - if (STAGE_SORT == stats->stageType) { + bool hasStage(const StageType type, const PlanStageStats* stats) { + if (type == stats->stageType) { return true; } for (size_t i = 0; i < stats->children.size(); ++i) { - if (hasSort(stats->children[i])) { + if (hasStage(type, stats->children[i])) { return true; } } @@ -119,18 +119,35 @@ namespace mongo { double productivity = static_cast(stats->common.advanced) / static_cast(stats->common.works); + // double score = baseScore + productivity; + // Does a plan have a sort? // bool sort = hasSort(stats); + // double sortPenalty = sort ? 0.5 : 0; + // double score = baseScore + productivity - sortPenalty; // How selective do we think an index is? - //double selectivity = computeSelectivity(stats); - //return baseScore + productivity + selectivity; + // double selectivity = computeSelectivity(stats); + // return baseScore + productivity + selectivity; + + // If we have to perform a fetch, that's not great. + // + // We only do this when we have a projection stage because we have so many jstests that + // check bounds even when a collscan plan is just as good as the ixscan'd plan :( + double noFetchBonus = 1; + + // We prefer covered projections. + if (hasStage(STAGE_PROJECTION, stats) && hasStage(STAGE_FETCH, stats)) { + // Just enough to break a tie. + noFetchBonus = 1 - 0.001; + } - //double sortPenalty = sort ? 0.5 : 0; - //double score = baseScore + productivity - sortPenalty; - double score = baseScore + productivity; + double score = baseScore + productivity + noFetchBonus; - QLOG() << "score (" << score << ") = baseScore (" << baseScore << ") + productivity(" << productivity << ")\n"; + QLOG() << "score (" << score << ") = baseScore (" << baseScore << ")" + << " + productivity(" << productivity << ")" + << " + noFetchBonus(" << noFetchBonus << ")" + << endl; return score; } diff --git a/src/mongo/db/query/projection_parser.cpp b/src/mongo/db/query/projection_parser.cpp deleted file mode 100644 index 4af01732e37..00000000000 --- a/src/mongo/db/query/projection_parser.cpp +++ /dev/null @@ -1,80 +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 . - * - * 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 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()); - } - } - } - - if (qp->_includeID) { - qp->_includedFields.push_back(string("_id")); - } - - *out = qp.release(); - return Status::OK(); - } - -} // namespace mongo diff --git a/src/mongo/db/query/projection_parser.h b/src/mongo/db/query/projection_parser.h deleted file mode 100644 index ab24ca750af..00000000000 --- a/src/mongo/db/query/projection_parser.h +++ /dev/null @@ -1,48 +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 . - * - * 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/jsobj.h" -#include "mongo/db/query/parsed_projection.h" - -namespace mongo { - - /** - * Parses each of the various projection syntaxes that exist. - */ - class ProjectionParser { - public: - /** - * 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 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 c2ec36d3025..c53992789e9 100644 --- a/src/mongo/db/query/query_planner.cpp +++ b/src/mongo/db/query/query_planner.cpp @@ -1066,6 +1066,9 @@ namespace mongo { << solnRoot->toString() << endl; } else { + // XXX TODO: Can we pull values out of the key and if so in what + // cases? (covered_index_sort_3.js) + if (!solnRoot->fetched()) { FetchNode* fetch = new FetchNode(); fetch->children.push_back(solnRoot); @@ -1085,10 +1088,10 @@ namespace mongo { } // Project the results. - if (NULL != query.getProj()) { + if (NULL != query.getLiteProj()) { QLOG() << "PROJECTION: fetched status: " << solnRoot->fetched() << endl; - QLOG() << "PROJECTION: Current plan is " << solnRoot->toString() << endl; - if (query.getProj()->requiresDocument()) { + QLOG() << "PROJECTION: Current plan is:\n" << solnRoot->toString() << endl; + if (query.getLiteProj()->requiresDocument()) { QLOG() << "PROJECTION: claims to require doc adding fetch.\n"; // If the projection requires the entire document, somebody must fetch. if (!solnRoot->fetched()) { @@ -1099,7 +1102,8 @@ namespace mongo { } else { QLOG() << "PROJECTION: requires fields\n"; - const vector& fields = query.getProj()->requiredFields(); + vector fields; + query.getLiteProj()->getRequiredFields(&fields); bool covered = true; for (size_t i = 0; i < fields.size(); ++i) { if (!solnRoot->hasField(fields[i])) { @@ -1109,6 +1113,7 @@ namespace mongo { break; } } + cout << "PROJECTION: fields provided = " << covered << endl; // If any field is missing from the list of fields the projection wants, // a fetch is required. if (!covered) { @@ -1120,8 +1125,9 @@ namespace mongo { // We now know we have whatever data is required for the projection. ProjectionNode* projNode = new ProjectionNode(); - projNode->projection = query.getProj(); + projNode->liteProjection = query.getLiteProj(); projNode->children.push_back(solnRoot); + projNode->fullExpression = query.root(); solnRoot = projNode; } else { diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp index afa01a87499..8dd0b0f4064 100644 --- a/src/mongo/db/query/query_solution.cpp +++ b/src/mongo/db/query/query_solution.cpp @@ -465,9 +465,9 @@ namespace mongo { void ProjectionNode::appendToString(stringstream* ss, int indent) const { addIndent(ss, indent); *ss << "PROJ\n"; - verify(NULL != projection); + verify(NULL != liteProjection); addIndent(ss, indent + 1); - *ss << "proj = " << projection->toString() << endl; + *ss << "proj = " << liteProjection->getProjectionSpec().toString() << endl; addCommon(ss, indent); *ss << "Child:" << endl; children[0]->appendToString(ss, indent + 2); diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h index 032911c63da..9fd98711165 100644 --- a/src/mongo/db/query/query_solution.h +++ b/src/mongo/db/query/query_solution.h @@ -33,7 +33,7 @@ #include "mongo/db/geo/geoquery.h" #include "mongo/db/fts/fts_query.h" #include "mongo/db/query/index_bounds.h" -#include "mongo/db/query/projection_parser.h" +#include "mongo/db/query/lite_projection.h" #include "mongo/db/query/stage_types.h" namespace mongo { @@ -359,7 +359,7 @@ namespace mongo { }; struct ProjectionNode : public QuerySolutionNode { - ProjectionNode() : projection(NULL) { } + ProjectionNode() : liteProjection(NULL) { } virtual ~ProjectionNode() { } virtual StageType getType() const { return STAGE_PROJECTION; } @@ -394,8 +394,12 @@ namespace mongo { BSONObjSet _sorts; - // Points into the CanonicalQuery. - ParsedProjection* projection; + // Points into the CanonicalQuery, not owned here. + LiteProjection* liteProjection; + + // The full query tree. Needed when we have positional operators. + // Owned in the CanonicalQuery, not here. + MatchExpression* fullExpression; }; struct SortNode : public QuerySolutionNode { diff --git a/src/mongo/db/query/stage_builder.cpp b/src/mongo/db/query/stage_builder.cpp index 253d37a641d..c64531ba488 100644 --- a/src/mongo/db/query/stage_builder.cpp +++ b/src/mongo/db/query/stage_builder.cpp @@ -108,7 +108,8 @@ namespace mongo { const ProjectionNode* pn = static_cast(root); PlanStage* childStage = buildStages(ns, pn->children[0], ws); if (NULL == childStage) { return NULL; } - return new ProjectionStage(pn->projection, ws, childStage, NULL); + bool covered = !pn->children[0]->fetched(); + return new ProjectionStage(pn->liteProjection, covered, pn->fullExpression, ws, childStage, NULL); } else if (STAGE_LIMIT == root->getType()) { const LimitNode* ln = static_cast(root); -- cgit v1.2.1