diff options
Diffstat (limited to 'src/mongo/db/query/get_executor.cpp')
| -rw-r--r-- | src/mongo/db/query/get_executor.cpp | 2408 |
1 files changed, 1175 insertions, 1233 deletions
diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp index 0f5044273ba..189910bbae1 100644 --- a/src/mongo/db/query/get_executor.cpp +++ b/src/mongo/db/query/get_executor.cpp @@ -80,1439 +80,1381 @@ namespace mongo { - using std::unique_ptr; - using std::endl; - using std::string; - using std::vector; - - // static - void filterAllowedIndexEntries(const AllowedIndices& allowedIndices, - std::vector<IndexEntry>* indexEntries) { - invariant(indexEntries); - - // Filter index entries - // Check BSON objects in AllowedIndices::_indexKeyPatterns against IndexEntry::keyPattern. - // Removes IndexEntrys that do not match _indexKeyPatterns. - std::vector<IndexEntry> temp; - for (std::vector<IndexEntry>::const_iterator i = indexEntries->begin(); - i != indexEntries->end(); ++i) { - const IndexEntry& indexEntry = *i; - for (std::vector<BSONObj>::const_iterator j = allowedIndices.indexKeyPatterns.begin(); - j != allowedIndices.indexKeyPatterns.end(); ++j) { - const BSONObj& index = *j; - // Copy index entry to temp vector if found in query settings. - if (0 == indexEntry.keyPattern.woCompare(index)) { - temp.push_back(indexEntry); - break; - } +using std::unique_ptr; +using std::endl; +using std::string; +using std::vector; + +// static +void filterAllowedIndexEntries(const AllowedIndices& allowedIndices, + std::vector<IndexEntry>* indexEntries) { + invariant(indexEntries); + + // Filter index entries + // Check BSON objects in AllowedIndices::_indexKeyPatterns against IndexEntry::keyPattern. + // Removes IndexEntrys that do not match _indexKeyPatterns. + std::vector<IndexEntry> temp; + for (std::vector<IndexEntry>::const_iterator i = indexEntries->begin(); + i != indexEntries->end(); + ++i) { + const IndexEntry& indexEntry = *i; + for (std::vector<BSONObj>::const_iterator j = allowedIndices.indexKeyPatterns.begin(); + j != allowedIndices.indexKeyPatterns.end(); + ++j) { + const BSONObj& index = *j; + // Copy index entry to temp vector if found in query settings. + if (0 == indexEntry.keyPattern.woCompare(index)) { + temp.push_back(indexEntry); + break; } } - - // Update results. - temp.swap(*indexEntries); } - namespace { - // The body is below in the "count hack" section but getExecutor calls it. - bool turnIxscanIntoCount(QuerySolution* soln); - - bool filteredIndexBad(const MatchExpression* filter, CanonicalQuery* query) { - if (!filter) - return false; + // Update results. + temp.swap(*indexEntries); +} - MatchExpression* queryPredicates = query->root(); - if (!queryPredicates) { - // Index is filtered, but query has none. - // Impossible to use index. - return true; - } +namespace { +// The body is below in the "count hack" section but getExecutor calls it. +bool turnIxscanIntoCount(QuerySolution* soln); - return !expression::isSubsetOf(queryPredicates, filter); - } - } // namespace - - - void fillOutPlannerParams(OperationContext* txn, - Collection* collection, - CanonicalQuery* canonicalQuery, - QueryPlannerParams* plannerParams) { - // If it's not NULL, we may have indices. Access the catalog and fill out IndexEntry(s) - IndexCatalog::IndexIterator ii = collection->getIndexCatalog()->getIndexIterator(txn, - false); - while (ii.more()) { - const IndexDescriptor* desc = ii.next(); - - IndexCatalogEntry* ice = ii.catalogEntry(desc); - if (filteredIndexBad(ice->getFilterExpression(), canonicalQuery)) { - continue; - } +bool filteredIndexBad(const MatchExpression* filter, CanonicalQuery* query) { + if (!filter) + return false; - plannerParams->indices.push_back(IndexEntry(desc->keyPattern(), - desc->getAccessMethodName(), - desc->isMultikey(txn), - desc->isSparse(), - desc->unique(), - desc->indexName(), - ice->getFilterExpression(), - desc->infoObj())); - } + MatchExpression* queryPredicates = query->root(); + if (!queryPredicates) { + // Index is filtered, but query has none. + // Impossible to use index. + return true; + } - // If query supports index filters, filter params.indices by indices in query settings. - QuerySettings* querySettings = collection->infoCache()->getQuerySettings(); - AllowedIndices* allowedIndicesRaw; - PlanCacheKey planCacheKey = - collection->infoCache()->getPlanCache()->computeKey(*canonicalQuery); - - // Filter index catalog if index filters are specified for query. - // Also, signal to planner that application hint should be ignored. - if (querySettings->getAllowedIndices(planCacheKey, &allowedIndicesRaw)) { - std::unique_ptr<AllowedIndices> allowedIndices(allowedIndicesRaw); - filterAllowedIndexEntries(*allowedIndices, &plannerParams->indices); - plannerParams->indexFiltersApplied = true; - } + return !expression::isSubsetOf(queryPredicates, filter); +} +} // namespace - // We will not output collection scans unless there are no indexed solutions. NO_TABLE_SCAN - // overrides this behavior by not outputting a collscan even if there are no indexed - // solutions. - if (storageGlobalParams.noTableScan) { - const string& ns = canonicalQuery->ns(); - // There are certain cases where we ignore this restriction: - bool ignore = canonicalQuery->getQueryObj().isEmpty() - || (string::npos != ns.find(".system.")) - || (0 == ns.find("local.")); - if (!ignore) { - plannerParams->options |= QueryPlannerParams::NO_TABLE_SCAN; - } - } - // If the caller wants a shard filter, make sure we're actually sharded. - if (plannerParams->options & QueryPlannerParams::INCLUDE_SHARD_FILTER) { - CollectionMetadataPtr collMetadata = - shardingState.getCollectionMetadata(canonicalQuery->ns()); +void fillOutPlannerParams(OperationContext* txn, + Collection* collection, + CanonicalQuery* canonicalQuery, + QueryPlannerParams* plannerParams) { + // If it's not NULL, we may have indices. Access the catalog and fill out IndexEntry(s) + IndexCatalog::IndexIterator ii = collection->getIndexCatalog()->getIndexIterator(txn, false); + while (ii.more()) { + const IndexDescriptor* desc = ii.next(); - if (collMetadata) { - plannerParams->shardKey = collMetadata->getKeyPattern(); - } - else { - // If there's no metadata don't bother w/the shard filter since we won't know what - // the key pattern is anyway... - plannerParams->options &= ~QueryPlannerParams::INCLUDE_SHARD_FILTER; - } + IndexCatalogEntry* ice = ii.catalogEntry(desc); + if (filteredIndexBad(ice->getFilterExpression(), canonicalQuery)) { + continue; } - if (internalQueryPlannerEnableIndexIntersection) { - plannerParams->options |= QueryPlannerParams::INDEX_INTERSECTION; - } + plannerParams->indices.push_back(IndexEntry(desc->keyPattern(), + desc->getAccessMethodName(), + desc->isMultikey(txn), + desc->isSparse(), + desc->unique(), + desc->indexName(), + ice->getFilterExpression(), + desc->infoObj())); + } - plannerParams->options |= QueryPlannerParams::SPLIT_LIMITED_SORT; + // If query supports index filters, filter params.indices by indices in query settings. + QuerySettings* querySettings = collection->infoCache()->getQuerySettings(); + AllowedIndices* allowedIndicesRaw; + PlanCacheKey planCacheKey = + collection->infoCache()->getPlanCache()->computeKey(*canonicalQuery); + + // Filter index catalog if index filters are specified for query. + // Also, signal to planner that application hint should be ignored. + if (querySettings->getAllowedIndices(planCacheKey, &allowedIndicesRaw)) { + std::unique_ptr<AllowedIndices> allowedIndices(allowedIndicesRaw); + filterAllowedIndexEntries(*allowedIndices, &plannerParams->indices); + plannerParams->indexFiltersApplied = true; + } - // Doc-level locking storage engines cannot answer predicates implicitly via exact index - // bounds for index intersection plans, as this can lead to spurious matches. - // - // Such storage engines do not use the invalidation framework, and therefore - // have no need for KEEP_MUTATIONS. - if (supportsDocLocking()) { - plannerParams->options |= QueryPlannerParams::CANNOT_TRIM_IXISECT; + // We will not output collection scans unless there are no indexed solutions. NO_TABLE_SCAN + // overrides this behavior by not outputting a collscan even if there are no indexed + // solutions. + if (storageGlobalParams.noTableScan) { + const string& ns = canonicalQuery->ns(); + // There are certain cases where we ignore this restriction: + bool ignore = canonicalQuery->getQueryObj().isEmpty() || + (string::npos != ns.find(".system.")) || (0 == ns.find("local.")); + if (!ignore) { + plannerParams->options |= QueryPlannerParams::NO_TABLE_SCAN; } - else { - plannerParams->options |= QueryPlannerParams::KEEP_MUTATIONS; + } + + // If the caller wants a shard filter, make sure we're actually sharded. + if (plannerParams->options & QueryPlannerParams::INCLUDE_SHARD_FILTER) { + CollectionMetadataPtr collMetadata = + shardingState.getCollectionMetadata(canonicalQuery->ns()); + + if (collMetadata) { + plannerParams->shardKey = collMetadata->getKeyPattern(); + } else { + // If there's no metadata don't bother w/the shard filter since we won't know what + // the key pattern is anyway... + plannerParams->options &= ~QueryPlannerParams::INCLUDE_SHARD_FILTER; } } - namespace { - - /** - * Build an execution tree for the query described in 'canonicalQuery'. Does not take - * ownership of arguments. - * - * If an execution tree could be created, then returns Status::OK() and sets 'rootOut' to - * the root of the constructed execution tree, and sets 'querySolutionOut' to the associated - * query solution (if applicable) or NULL. - * - * If an execution tree could not be created, returns a Status indicating why and sets both - * 'rootOut' and 'querySolutionOut' to NULL. - */ - Status prepareExecution(OperationContext* opCtx, - Collection* collection, - WorkingSet* ws, - CanonicalQuery* canonicalQuery, - size_t plannerOptions, - PlanStage** rootOut, - QuerySolution** querySolutionOut) { - invariant(canonicalQuery); - *rootOut = NULL; - *querySolutionOut = NULL; - - // This can happen as we're called by internal clients as well. - if (NULL == collection) { - const string& ns = canonicalQuery->ns(); - LOG(2) << "Collection " << ns << " does not exist." - << " Using EOF plan: " << canonicalQuery->toStringShort(); - *rootOut = new EOFStage(); - return Status::OK(); - } + if (internalQueryPlannerEnableIndexIntersection) { + plannerParams->options |= QueryPlannerParams::INDEX_INTERSECTION; + } - // Fill out the planning params. We use these for both cached solutions and non-cached. - QueryPlannerParams plannerParams; - plannerParams.options = plannerOptions; - fillOutPlannerParams(opCtx, collection, canonicalQuery, &plannerParams); + plannerParams->options |= QueryPlannerParams::SPLIT_LIMITED_SORT; + + // Doc-level locking storage engines cannot answer predicates implicitly via exact index + // bounds for index intersection plans, as this can lead to spurious matches. + // + // Such storage engines do not use the invalidation framework, and therefore + // have no need for KEEP_MUTATIONS. + if (supportsDocLocking()) { + plannerParams->options |= QueryPlannerParams::CANNOT_TRIM_IXISECT; + } else { + plannerParams->options |= QueryPlannerParams::KEEP_MUTATIONS; + } +} - // If we have an _id index we can use an idhack plan. - if (IDHackStage::supportsQuery(*canonicalQuery) && - collection->getIndexCatalog()->findIdIndex(opCtx)) { +namespace { - LOG(2) << "Using idhack: " << canonicalQuery->toStringShort(); +/** + * Build an execution tree for the query described in 'canonicalQuery'. Does not take + * ownership of arguments. + * + * If an execution tree could be created, then returns Status::OK() and sets 'rootOut' to + * the root of the constructed execution tree, and sets 'querySolutionOut' to the associated + * query solution (if applicable) or NULL. + * + * If an execution tree could not be created, returns a Status indicating why and sets both + * 'rootOut' and 'querySolutionOut' to NULL. + */ +Status prepareExecution(OperationContext* opCtx, + Collection* collection, + WorkingSet* ws, + CanonicalQuery* canonicalQuery, + size_t plannerOptions, + PlanStage** rootOut, + QuerySolution** querySolutionOut) { + invariant(canonicalQuery); + *rootOut = NULL; + *querySolutionOut = NULL; + + // This can happen as we're called by internal clients as well. + if (NULL == collection) { + const string& ns = canonicalQuery->ns(); + LOG(2) << "Collection " << ns << " does not exist." + << " Using EOF plan: " << canonicalQuery->toStringShort(); + *rootOut = new EOFStage(); + return Status::OK(); + } - *rootOut = new IDHackStage(opCtx, collection, canonicalQuery, ws); + // Fill out the planning params. We use these for both cached solutions and non-cached. + QueryPlannerParams plannerParams; + plannerParams.options = plannerOptions; + fillOutPlannerParams(opCtx, collection, canonicalQuery, &plannerParams); - // Might have to filter out orphaned docs. - if (plannerParams.options & QueryPlannerParams::INCLUDE_SHARD_FILTER) { - *rootOut = - new ShardFilterStage(shardingState.getCollectionMetadata(collection->ns()), - ws, *rootOut); - } + // If we have an _id index we can use an idhack plan. + if (IDHackStage::supportsQuery(*canonicalQuery) && + collection->getIndexCatalog()->findIdIndex(opCtx)) { + LOG(2) << "Using idhack: " << canonicalQuery->toStringShort(); - // There might be a projection. The idhack stage will always fetch the full - // document, so we don't support covered projections. However, we might use the - // simple inclusion fast path. - if (NULL != canonicalQuery->getProj()) { - ProjectionStageParams params(WhereCallbackReal(opCtx, collection->ns().db())); - params.projObj = canonicalQuery->getProj()->getProjObj(); - - // Stuff the right data into the params depending on what proj impl we use. - if (canonicalQuery->getProj()->requiresDocument() - || canonicalQuery->getProj()->wantIndexKey()) { - params.fullExpression = canonicalQuery->root(); - params.projImpl = ProjectionStageParams::NO_FAST_PATH; - } - else { - params.projImpl = ProjectionStageParams::SIMPLE_DOC; - } + *rootOut = new IDHackStage(opCtx, collection, canonicalQuery, ws); - *rootOut = new ProjectionStage(params, ws, *rootOut); - } + // Might have to filter out orphaned docs. + if (plannerParams.options & QueryPlannerParams::INCLUDE_SHARD_FILTER) { + *rootOut = new ShardFilterStage( + shardingState.getCollectionMetadata(collection->ns()), ws, *rootOut); + } - return Status::OK(); + // There might be a projection. The idhack stage will always fetch the full + // document, so we don't support covered projections. However, we might use the + // simple inclusion fast path. + if (NULL != canonicalQuery->getProj()) { + ProjectionStageParams params(WhereCallbackReal(opCtx, collection->ns().db())); + params.projObj = canonicalQuery->getProj()->getProjObj(); + + // Stuff the right data into the params depending on what proj impl we use. + if (canonicalQuery->getProj()->requiresDocument() || + canonicalQuery->getProj()->wantIndexKey()) { + params.fullExpression = canonicalQuery->root(); + params.projImpl = ProjectionStageParams::NO_FAST_PATH; + } else { + params.projImpl = ProjectionStageParams::SIMPLE_DOC; } - // Tailable: If the query requests tailable the collection must be capped. - if (canonicalQuery->getParsed().isTailable()) { - if (!collection->isCapped()) { - return Status(ErrorCodes::BadValue, - "error processing query: " + canonicalQuery->toString() + - " tailable cursor requested on non capped collection"); - } + *rootOut = new ProjectionStage(params, ws, *rootOut); + } - // If a sort is specified it must be equal to expectedSort. - const BSONObj expectedSort = BSON("$natural" << 1); - const BSONObj& actualSort = canonicalQuery->getParsed().getSort(); - if (!actualSort.isEmpty() && !(actualSort == expectedSort)) { - return Status(ErrorCodes::BadValue, - "error processing query: " + canonicalQuery->toString() + - " invalid sort specified for tailable cursor: " - + actualSort.toString()); - } - } + return Status::OK(); + } - // Try to look up a cached solution for the query. - CachedSolution* rawCS; - if (PlanCache::shouldCacheQuery(*canonicalQuery) && - collection->infoCache()->getPlanCache()->get(*canonicalQuery, &rawCS).isOK()) { - // We have a CachedSolution. Have the planner turn it into a QuerySolution. - std::unique_ptr<CachedSolution> cs(rawCS); - QuerySolution *qs; - Status status = QueryPlanner::planFromCache(*canonicalQuery, plannerParams, *cs, - &qs); - - if (status.isOK()) { - verify(StageBuilder::build(opCtx, collection, *qs, ws, rootOut)); - if ((plannerParams.options & QueryPlannerParams::PRIVATE_IS_COUNT) - && turnIxscanIntoCount(qs)) { - - LOG(2) << "Using fast count: " << canonicalQuery->toStringShort() - << ", planSummary: " << Explain::getPlanSummary(*rootOut); - } + // Tailable: If the query requests tailable the collection must be capped. + if (canonicalQuery->getParsed().isTailable()) { + if (!collection->isCapped()) { + return Status(ErrorCodes::BadValue, + "error processing query: " + canonicalQuery->toString() + + " tailable cursor requested on non capped collection"); + } - // Add a CachedPlanStage on top of the previous root. - // - // 'decisionWorks' is used to determine whether the existing cache entry should - // be evicted, and the query replanned. - // - // Takes ownership of '*rootOut'. - *rootOut = new CachedPlanStage(opCtx, - collection, - ws, - canonicalQuery, - plannerParams, - cs->decisionWorks, - *rootOut); - *querySolutionOut = qs; - return Status::OK(); - } + // If a sort is specified it must be equal to expectedSort. + const BSONObj expectedSort = BSON("$natural" << 1); + const BSONObj& actualSort = canonicalQuery->getParsed().getSort(); + if (!actualSort.isEmpty() && !(actualSort == expectedSort)) { + return Status(ErrorCodes::BadValue, + "error processing query: " + canonicalQuery->toString() + + " invalid sort specified for tailable cursor: " + + actualSort.toString()); + } + } + + // Try to look up a cached solution for the query. + CachedSolution* rawCS; + if (PlanCache::shouldCacheQuery(*canonicalQuery) && + collection->infoCache()->getPlanCache()->get(*canonicalQuery, &rawCS).isOK()) { + // We have a CachedSolution. Have the planner turn it into a QuerySolution. + std::unique_ptr<CachedSolution> cs(rawCS); + QuerySolution* qs; + Status status = QueryPlanner::planFromCache(*canonicalQuery, plannerParams, *cs, &qs); + + if (status.isOK()) { + verify(StageBuilder::build(opCtx, collection, *qs, ws, rootOut)); + if ((plannerParams.options & QueryPlannerParams::PRIVATE_IS_COUNT) && + turnIxscanIntoCount(qs)) { + LOG(2) << "Using fast count: " << canonicalQuery->toStringShort() + << ", planSummary: " << Explain::getPlanSummary(*rootOut); } - if (internalQueryPlanOrChildrenIndependently - && SubplanStage::canUseSubplanning(*canonicalQuery)) { + // Add a CachedPlanStage on top of the previous root. + // + // 'decisionWorks' is used to determine whether the existing cache entry should + // be evicted, and the query replanned. + // + // Takes ownership of '*rootOut'. + *rootOut = new CachedPlanStage( + opCtx, collection, ws, canonicalQuery, plannerParams, cs->decisionWorks, *rootOut); + *querySolutionOut = qs; + return Status::OK(); + } + } - LOG(2) << "Running query as sub-queries: " << canonicalQuery->toStringShort(); + if (internalQueryPlanOrChildrenIndependently && + SubplanStage::canUseSubplanning(*canonicalQuery)) { + LOG(2) << "Running query as sub-queries: " << canonicalQuery->toStringShort(); - *rootOut = new SubplanStage(opCtx, collection, ws, plannerParams, canonicalQuery); - return Status::OK(); - } + *rootOut = new SubplanStage(opCtx, collection, ws, plannerParams, canonicalQuery); + return Status::OK(); + } - vector<QuerySolution*> solutions; - Status status = QueryPlanner::plan(*canonicalQuery, plannerParams, &solutions); - if (!status.isOK()) { - return Status(ErrorCodes::BadValue, - "error processing query: " + canonicalQuery->toString() + - " planner returned error: " + status.reason()); - } + vector<QuerySolution*> solutions; + Status status = QueryPlanner::plan(*canonicalQuery, plannerParams, &solutions); + if (!status.isOK()) { + return Status(ErrorCodes::BadValue, + "error processing query: " + canonicalQuery->toString() + + " planner returned error: " + status.reason()); + } - // We cannot figure out how to answer the query. Perhaps it requires an index - // we do not have? - if (0 == solutions.size()) { - return Status(ErrorCodes::BadValue, - str::stream() - << "error processing query: " - << canonicalQuery->toString() - << " No query solutions"); - } + // We cannot figure out how to answer the query. Perhaps it requires an index + // we do not have? + if (0 == solutions.size()) { + return Status(ErrorCodes::BadValue, + str::stream() << "error processing query: " << canonicalQuery->toString() + << " No query solutions"); + } - // See if one of our solutions is a fast count hack in disguise. - if (plannerParams.options & QueryPlannerParams::PRIVATE_IS_COUNT) { - for (size_t i = 0; i < solutions.size(); ++i) { - if (turnIxscanIntoCount(solutions[i])) { - // Great, we can use solutions[i]. Clean up the other QuerySolution(s). - for (size_t j = 0; j < solutions.size(); ++j) { - if (j != i) { - delete solutions[j]; - } - } - - // We're not going to cache anything that's fast count. - verify(StageBuilder::build(opCtx, collection, *solutions[i], ws, rootOut)); - - LOG(2) << "Using fast count: " << canonicalQuery->toStringShort() - << ", planSummary: " << Explain::getPlanSummary(*rootOut); - - *querySolutionOut = solutions[i]; - return Status::OK(); + // See if one of our solutions is a fast count hack in disguise. + if (plannerParams.options & QueryPlannerParams::PRIVATE_IS_COUNT) { + for (size_t i = 0; i < solutions.size(); ++i) { + if (turnIxscanIntoCount(solutions[i])) { + // Great, we can use solutions[i]. Clean up the other QuerySolution(s). + for (size_t j = 0; j < solutions.size(); ++j) { + if (j != i) { + delete solutions[j]; } } - } - if (1 == solutions.size()) { - // Only one possible plan. Run it. Build the stages from the solution. - verify(StageBuilder::build(opCtx, collection, *solutions[0], ws, rootOut)); + // We're not going to cache anything that's fast count. + verify(StageBuilder::build(opCtx, collection, *solutions[i], ws, rootOut)); - LOG(2) << "Only one plan is available; it will be run but will not be cached. " - << canonicalQuery->toStringShort() + LOG(2) << "Using fast count: " << canonicalQuery->toStringShort() << ", planSummary: " << Explain::getPlanSummary(*rootOut); - *querySolutionOut = solutions[0]; + *querySolutionOut = solutions[i]; return Status::OK(); } - else { - // Many solutions. Create a MultiPlanStage to pick the best, update the cache, - // and so on. The working set will be shared by all candidate plans. - MultiPlanStage* multiPlanStage = new MultiPlanStage(opCtx, collection, canonicalQuery); - - for (size_t ix = 0; ix < solutions.size(); ++ix) { - if (solutions[ix]->cacheData.get()) { - solutions[ix]->cacheData->indexFilterApplied = - plannerParams.indexFiltersApplied; - } + } + } - // version of StageBuild::build when WorkingSet is shared - PlanStage* nextPlanRoot; - verify(StageBuilder::build(opCtx, collection, *solutions[ix], ws, - &nextPlanRoot)); + if (1 == solutions.size()) { + // Only one possible plan. Run it. Build the stages from the solution. + verify(StageBuilder::build(opCtx, collection, *solutions[0], ws, rootOut)); - // Owns none of the arguments - multiPlanStage->addPlan(solutions[ix], nextPlanRoot, ws); - } + LOG(2) << "Only one plan is available; it will be run but will not be cached. " + << canonicalQuery->toStringShort() + << ", planSummary: " << Explain::getPlanSummary(*rootOut); - *rootOut = multiPlanStage; - return Status::OK(); + *querySolutionOut = solutions[0]; + return Status::OK(); + } else { + // Many solutions. Create a MultiPlanStage to pick the best, update the cache, + // and so on. The working set will be shared by all candidate plans. + MultiPlanStage* multiPlanStage = new MultiPlanStage(opCtx, collection, canonicalQuery); + + for (size_t ix = 0; ix < solutions.size(); ++ix) { + if (solutions[ix]->cacheData.get()) { + solutions[ix]->cacheData->indexFilterApplied = plannerParams.indexFiltersApplied; } - } - } // namespace + // version of StageBuild::build when WorkingSet is shared + PlanStage* nextPlanRoot; + verify(StageBuilder::build(opCtx, collection, *solutions[ix], ws, &nextPlanRoot)); - Status getExecutor(OperationContext* txn, - Collection* collection, - CanonicalQuery* rawCanonicalQuery, - PlanExecutor::YieldPolicy yieldPolicy, - PlanExecutor** out, - size_t plannerOptions) { - unique_ptr<CanonicalQuery> canonicalQuery(rawCanonicalQuery); - unique_ptr<WorkingSet> ws(new WorkingSet()); - PlanStage* root; - QuerySolution* querySolution; - Status status = prepareExecution(txn, collection, ws.get(), canonicalQuery.get(), - plannerOptions, &root, &querySolution); - if (!status.isOK()) { - return status; + // Owns none of the arguments + multiPlanStage->addPlan(solutions[ix], nextPlanRoot, ws); } - invariant(root); - // We must have a tree of stages in order to have a valid plan executor, but the query - // solution may be null. - return PlanExecutor::make(txn, ws.release(), root, querySolution, canonicalQuery.release(), - collection, yieldPolicy, out); - } - Status getExecutor(OperationContext* txn, - Collection* collection, - const std::string& ns, - const BSONObj& unparsedQuery, - PlanExecutor::YieldPolicy yieldPolicy, - PlanExecutor** out, - size_t plannerOptions) { - if (!collection) { - LOG(2) << "Collection " << ns << " does not exist." - << " Using EOF stage: " << unparsedQuery.toString(); - EOFStage* eofStage = new EOFStage(); - WorkingSet* ws = new WorkingSet(); - return PlanExecutor::make(txn, ws, eofStage, ns, yieldPolicy, out); - } + *rootOut = multiPlanStage; + return Status::OK(); + } +} - if (!CanonicalQuery::isSimpleIdQuery(unparsedQuery) || - !collection->getIndexCatalog()->findIdIndex(txn)) { +} // namespace - const WhereCallbackReal whereCallback(txn, collection->ns().db()); - CanonicalQuery* cq; - Status status = CanonicalQuery::canonicalize(collection->ns(), unparsedQuery, &cq, - whereCallback); - if (!status.isOK()) - return status; +Status getExecutor(OperationContext* txn, + Collection* collection, + CanonicalQuery* rawCanonicalQuery, + PlanExecutor::YieldPolicy yieldPolicy, + PlanExecutor** out, + size_t plannerOptions) { + unique_ptr<CanonicalQuery> canonicalQuery(rawCanonicalQuery); + unique_ptr<WorkingSet> ws(new WorkingSet()); + PlanStage* root; + QuerySolution* querySolution; + Status status = prepareExecution( + txn, collection, ws.get(), canonicalQuery.get(), plannerOptions, &root, &querySolution); + if (!status.isOK()) { + return status; + } + invariant(root); + // We must have a tree of stages in order to have a valid plan executor, but the query + // solution may be null. + return PlanExecutor::make(txn, + ws.release(), + root, + querySolution, + canonicalQuery.release(), + collection, + yieldPolicy, + out); +} + +Status getExecutor(OperationContext* txn, + Collection* collection, + const std::string& ns, + const BSONObj& unparsedQuery, + PlanExecutor::YieldPolicy yieldPolicy, + PlanExecutor** out, + size_t plannerOptions) { + if (!collection) { + LOG(2) << "Collection " << ns << " does not exist." + << " Using EOF stage: " << unparsedQuery.toString(); + EOFStage* eofStage = new EOFStage(); + WorkingSet* ws = new WorkingSet(); + return PlanExecutor::make(txn, ws, eofStage, ns, yieldPolicy, out); + } - // Takes ownership of 'cq'. - return getExecutor(txn, collection, cq, yieldPolicy, out, plannerOptions); - } + if (!CanonicalQuery::isSimpleIdQuery(unparsedQuery) || + !collection->getIndexCatalog()->findIdIndex(txn)) { + const WhereCallbackReal whereCallback(txn, collection->ns().db()); + CanonicalQuery* cq; + Status status = + CanonicalQuery::canonicalize(collection->ns(), unparsedQuery, &cq, whereCallback); + if (!status.isOK()) + return status; - LOG(2) << "Using idhack: " << unparsedQuery.toString(); + // Takes ownership of 'cq'. + return getExecutor(txn, collection, cq, yieldPolicy, out, plannerOptions); + } - WorkingSet* ws = new WorkingSet(); - PlanStage* root = new IDHackStage(txn, collection, unparsedQuery["_id"].wrap(), ws); + LOG(2) << "Using idhack: " << unparsedQuery.toString(); - // Might have to filter out orphaned docs. - if (plannerOptions & QueryPlannerParams::INCLUDE_SHARD_FILTER) { - root = new ShardFilterStage(shardingState.getCollectionMetadata(collection->ns()), ws, - root); - } + WorkingSet* ws = new WorkingSet(); + PlanStage* root = new IDHackStage(txn, collection, unparsedQuery["_id"].wrap(), ws); - return PlanExecutor::make(txn, ws, root, collection, yieldPolicy, out); + // Might have to filter out orphaned docs. + if (plannerOptions & QueryPlannerParams::INCLUDE_SHARD_FILTER) { + root = + new ShardFilterStage(shardingState.getCollectionMetadata(collection->ns()), ws, root); } - // - // Find - // + return PlanExecutor::make(txn, ws, root, collection, yieldPolicy, out); +} + +// +// Find +// namespace { - /** - * Returns true if 'me' is a GTE or GE predicate over the "ts" field. - * Such predicates can be used for the oplog start hack. - */ - bool isOplogTsPred(const mongo::MatchExpression* me) { - if (mongo::MatchExpression::GT != me->matchType() - && mongo::MatchExpression::GTE != me->matchType()) { - return false; - } +/** + * Returns true if 'me' is a GTE or GE predicate over the "ts" field. + * Such predicates can be used for the oplog start hack. + */ +bool isOplogTsPred(const mongo::MatchExpression* me) { + if (mongo::MatchExpression::GT != me->matchType() && + mongo::MatchExpression::GTE != me->matchType()) { + return false; + } - return mongoutils::str::equals(me->path().rawData(), "ts"); - } - - mongo::BSONElement extractOplogTsOptime(const mongo::MatchExpression* me) { - invariant(isOplogTsPred(me)); - return static_cast<const mongo::ComparisonMatchExpression*>(me)->getData(); - } - - Status getOplogStartHack(OperationContext* txn, - Collection* collection, - CanonicalQuery* cq, - PlanExecutor** execOut) { - invariant(collection); - invariant(cq); - unique_ptr<CanonicalQuery> autoCq(cq); - - // A query can only do oplog start finding if it has a top-level $gt or $gte predicate over - // the "ts" field (the operation's timestamp). Find that predicate and pass it to - // the OplogStart stage. - MatchExpression* tsExpr = NULL; - if (MatchExpression::AND == cq->root()->matchType()) { - // The query has an AND at the top-level. See if any of the children - // of the AND are $gt or $gte predicates over 'ts'. - for (size_t i = 0; i < cq->root()->numChildren(); ++i) { - MatchExpression* me = cq->root()->getChild(i); - if (isOplogTsPred(me)) { - tsExpr = me; - break; - } + return mongoutils::str::equals(me->path().rawData(), "ts"); +} + +mongo::BSONElement extractOplogTsOptime(const mongo::MatchExpression* me) { + invariant(isOplogTsPred(me)); + return static_cast<const mongo::ComparisonMatchExpression*>(me)->getData(); +} + +Status getOplogStartHack(OperationContext* txn, + Collection* collection, + CanonicalQuery* cq, + PlanExecutor** execOut) { + invariant(collection); + invariant(cq); + unique_ptr<CanonicalQuery> autoCq(cq); + + // A query can only do oplog start finding if it has a top-level $gt or $gte predicate over + // the "ts" field (the operation's timestamp). Find that predicate and pass it to + // the OplogStart stage. + MatchExpression* tsExpr = NULL; + if (MatchExpression::AND == cq->root()->matchType()) { + // The query has an AND at the top-level. See if any of the children + // of the AND are $gt or $gte predicates over 'ts'. + for (size_t i = 0; i < cq->root()->numChildren(); ++i) { + MatchExpression* me = cq->root()->getChild(i); + if (isOplogTsPred(me)) { + tsExpr = me; + break; } } - else if (isOplogTsPred(cq->root())) { - // The root of the tree is a $gt or $gte predicate over 'ts'. - tsExpr = cq->root(); - } + } else if (isOplogTsPred(cq->root())) { + // The root of the tree is a $gt or $gte predicate over 'ts'. + tsExpr = cq->root(); + } - if (NULL == tsExpr) { - return Status(ErrorCodes::OplogOperationUnsupported, - "OplogReplay query does not contain top-level " - "$gt or $gte over the 'ts' field."); - } + if (NULL == tsExpr) { + return Status(ErrorCodes::OplogOperationUnsupported, + "OplogReplay query does not contain top-level " + "$gt or $gte over the 'ts' field."); + } - boost::optional<RecordId> startLoc = boost::none; + boost::optional<RecordId> startLoc = boost::none; - // See if the RecordStore supports the oplogStartHack - const BSONElement tsElem = extractOplogTsOptime(tsExpr); - if (tsElem.type() == bsonTimestamp) { - StatusWith<RecordId> goal = oploghack::keyForOptime(tsElem.timestamp()); - if (goal.isOK()) { - startLoc = collection->getRecordStore()->oplogStartHack(txn, goal.getValue()); - } + // See if the RecordStore supports the oplogStartHack + const BSONElement tsElem = extractOplogTsOptime(tsExpr); + if (tsElem.type() == bsonTimestamp) { + StatusWith<RecordId> goal = oploghack::keyForOptime(tsElem.timestamp()); + if (goal.isOK()) { + startLoc = collection->getRecordStore()->oplogStartHack(txn, goal.getValue()); } + } - if (startLoc) { - LOG(3) << "Using direct oplog seek"; + if (startLoc) { + LOG(3) << "Using direct oplog seek"; + } else { + LOG(3) << "Using OplogStart stage"; + + // Fallback to trying the OplogStart stage. + WorkingSet* oplogws = new WorkingSet(); + OplogStart* stage = new OplogStart(txn, collection, tsExpr, oplogws); + PlanExecutor* rawExec; + + // Takes ownership of oplogws and stage. + Status execStatus = + PlanExecutor::make(txn, oplogws, stage, collection, PlanExecutor::YIELD_AUTO, &rawExec); + invariant(execStatus.isOK()); + std::unique_ptr<PlanExecutor> exec(rawExec); + + // The stage returns a RecordId of where to start. + startLoc = RecordId(); + PlanExecutor::ExecState state = exec->getNext(NULL, startLoc.get_ptr()); + + // This is normal. The start of the oplog is the beginning of the collection. + if (PlanExecutor::IS_EOF == state) { + return getExecutor( + txn, collection, autoCq.release(), PlanExecutor::YIELD_AUTO, execOut); } - else { - LOG(3) << "Using OplogStart stage"; - - // Fallback to trying the OplogStart stage. - WorkingSet* oplogws = new WorkingSet(); - OplogStart* stage = new OplogStart(txn, collection, tsExpr, oplogws); - PlanExecutor* rawExec; - - // Takes ownership of oplogws and stage. - Status execStatus = PlanExecutor::make(txn, oplogws, stage, collection, - PlanExecutor::YIELD_AUTO, &rawExec); - invariant(execStatus.isOK()); - std::unique_ptr<PlanExecutor> exec(rawExec); - - // The stage returns a RecordId of where to start. - startLoc = RecordId(); - PlanExecutor::ExecState state = exec->getNext(NULL, startLoc.get_ptr()); - - // This is normal. The start of the oplog is the beginning of the collection. - if (PlanExecutor::IS_EOF == state) { - return getExecutor(txn, collection, autoCq.release(), PlanExecutor::YIELD_AUTO, - execOut); - } - // This is not normal. An error was encountered. - if (PlanExecutor::ADVANCED != state) { - return Status(ErrorCodes::InternalError, - "quick oplog start location had error...?"); - } + // This is not normal. An error was encountered. + if (PlanExecutor::ADVANCED != state) { + return Status(ErrorCodes::InternalError, "quick oplog start location had error...?"); } + } - // Build our collection scan... - CollectionScanParams params; - params.collection = collection; - params.start = *startLoc; - params.direction = CollectionScanParams::FORWARD; - params.tailable = cq->getParsed().isTailable(); + // Build our collection scan... + CollectionScanParams params; + params.collection = collection; + params.start = *startLoc; + params.direction = CollectionScanParams::FORWARD; + params.tailable = cq->getParsed().isTailable(); - WorkingSet* ws = new WorkingSet(); - CollectionScan* cs = new CollectionScan(txn, params, ws, cq->root()); - // Takes ownership of 'ws', 'cs', and 'cq'. - return PlanExecutor::make(txn, ws, cs, autoCq.release(), collection, - PlanExecutor::YIELD_AUTO, execOut); - } + WorkingSet* ws = new WorkingSet(); + CollectionScan* cs = new CollectionScan(txn, params, ws, cq->root()); + // Takes ownership of 'ws', 'cs', and 'cq'. + return PlanExecutor::make( + txn, ws, cs, autoCq.release(), collection, PlanExecutor::YIELD_AUTO, execOut); +} -} // namespace +} // namespace - Status getExecutorFind(OperationContext* txn, - Collection* collection, - const NamespaceString& nss, - CanonicalQuery* rawCanonicalQuery, - PlanExecutor::YieldPolicy yieldPolicy, - PlanExecutor** out) { - std::unique_ptr<CanonicalQuery> cq(rawCanonicalQuery); - if (NULL != collection && cq->getParsed().isOplogReplay()) { - return getOplogStartHack(txn, collection, cq.release(), out); - } +Status getExecutorFind(OperationContext* txn, + Collection* collection, + const NamespaceString& nss, + CanonicalQuery* rawCanonicalQuery, + PlanExecutor::YieldPolicy yieldPolicy, + PlanExecutor** out) { + std::unique_ptr<CanonicalQuery> cq(rawCanonicalQuery); + if (NULL != collection && cq->getParsed().isOplogReplay()) { + return getOplogStartHack(txn, collection, cq.release(), out); + } - size_t options = QueryPlannerParams::DEFAULT; - if (shardingState.needCollectionMetadata(txn->getClient(), nss.ns())) { - options |= QueryPlannerParams::INCLUDE_SHARD_FILTER; - } - return getExecutor(txn, collection, cq.release(), PlanExecutor::YIELD_AUTO, out, options); + size_t options = QueryPlannerParams::DEFAULT; + if (shardingState.needCollectionMetadata(txn->getClient(), nss.ns())) { + options |= QueryPlannerParams::INCLUDE_SHARD_FILTER; } + return getExecutor(txn, collection, cq.release(), PlanExecutor::YIELD_AUTO, out, options); +} namespace { - /** - * Wrap the specified 'root' plan stage in a ProjectionStage. Does not take ownership of any - * arguments other than root. - * - * If the projection was valid, then return Status::OK() with a pointer to the newly created - * ProjectionStage. Otherwise, return a status indicating the error reason. - */ - StatusWith<std::unique_ptr<PlanStage>> applyProjection(OperationContext* txn, - const NamespaceString& nsString, - CanonicalQuery* cq, - const BSONObj& proj, - bool allowPositional, - WorkingSet* ws, - std::unique_ptr<PlanStage> root) { - invariant(!proj.isEmpty()); - - ParsedProjection* rawParsedProj; - Status ppStatus = ParsedProjection::make(proj.getOwned(), cq->root(), &rawParsedProj); - if (!ppStatus.isOK()) { - return ppStatus; - } - std::unique_ptr<ParsedProjection> pp(rawParsedProj); - - // ProjectionExec requires the MatchDetails from the query expression when the projection - // uses the positional operator. Since the query may no longer match the newly-updated - // document, we forbid this case. - if (!allowPositional && pp->requiresMatchDetails()) { - return {ErrorCodes::BadValue, - "cannot use a positional projection and return the new document"}; - } - - ProjectionStageParams params(WhereCallbackReal(txn, nsString.db())); - params.projObj = proj; - params.fullExpression = cq->root(); - return {stdx::make_unique<ProjectionStage>(params, ws, root.release())}; +/** + * Wrap the specified 'root' plan stage in a ProjectionStage. Does not take ownership of any + * arguments other than root. + * + * If the projection was valid, then return Status::OK() with a pointer to the newly created + * ProjectionStage. Otherwise, return a status indicating the error reason. + */ +StatusWith<std::unique_ptr<PlanStage>> applyProjection(OperationContext* txn, + const NamespaceString& nsString, + CanonicalQuery* cq, + const BSONObj& proj, + bool allowPositional, + WorkingSet* ws, + std::unique_ptr<PlanStage> root) { + invariant(!proj.isEmpty()); + + ParsedProjection* rawParsedProj; + Status ppStatus = ParsedProjection::make(proj.getOwned(), cq->root(), &rawParsedProj); + if (!ppStatus.isOK()) { + return ppStatus; + } + std::unique_ptr<ParsedProjection> pp(rawParsedProj); + + // ProjectionExec requires the MatchDetails from the query expression when the projection + // uses the positional operator. Since the query may no longer match the newly-updated + // document, we forbid this case. + if (!allowPositional && pp->requiresMatchDetails()) { + return {ErrorCodes::BadValue, + "cannot use a positional projection and return the new document"}; } -} // namespace + ProjectionStageParams params(WhereCallbackReal(txn, nsString.db())); + params.projObj = proj; + params.fullExpression = cq->root(); + return {stdx::make_unique<ProjectionStage>(params, ws, root.release())}; +} - // - // Delete - // +} // namespace - Status getExecutorDelete(OperationContext* txn, - Collection* collection, - ParsedDelete* parsedDelete, - PlanExecutor** execOut) { - const DeleteRequest* request = parsedDelete->getRequest(); - - const NamespaceString& nss(request->getNamespaceString()); - if (!request->isGod()) { - if (nss.isSystem()) { - uassert(12050, - "cannot delete from system namespace", - legalClientSystemNS(nss.ns(), true)); - } - if (nss.ns().find('$') != string::npos) { - log() << "cannot delete from collection with reserved $ in name: " << nss << endl; - uasserted(10100, "cannot delete from collection with reserved $ in name"); - } +// +// Delete +// + +Status getExecutorDelete(OperationContext* txn, + Collection* collection, + ParsedDelete* parsedDelete, + PlanExecutor** execOut) { + const DeleteRequest* request = parsedDelete->getRequest(); + + const NamespaceString& nss(request->getNamespaceString()); + if (!request->isGod()) { + if (nss.isSystem()) { + uassert( + 12050, "cannot delete from system namespace", legalClientSystemNS(nss.ns(), true)); } - - if (collection && collection->isCapped()) { - return Status(ErrorCodes::IllegalOperation, - str::stream() << "cannot remove from a capped collection: " << nss.ns()); + if (nss.ns().find('$') != string::npos) { + log() << "cannot delete from collection with reserved $ in name: " << nss << endl; + uasserted(10100, "cannot delete from collection with reserved $ in name"); } + } - bool userInitiatedWritesAndNotPrimary = txn->writesAreReplicated() && - !repl::getGlobalReplicationCoordinator()->canAcceptWritesFor(nss); - - if (userInitiatedWritesAndNotPrimary) { - return Status(ErrorCodes::NotMaster, - str::stream() << "Not primary while removing from " << nss.ns()); - } + if (collection && collection->isCapped()) { + return Status(ErrorCodes::IllegalOperation, + str::stream() << "cannot remove from a capped collection: " << nss.ns()); + } - DeleteStageParams deleteStageParams; - deleteStageParams.isMulti = request->isMulti(); - deleteStageParams.fromMigrate = request->isFromMigrate(); - deleteStageParams.isExplain = request->isExplain(); - deleteStageParams.returnDeleted = request->shouldReturnDeleted(); - - unique_ptr<WorkingSet> ws(new WorkingSet()); - PlanExecutor::YieldPolicy policy = parsedDelete->canYield() ? PlanExecutor::YIELD_AUTO : - PlanExecutor::YIELD_MANUAL; - - if (!parsedDelete->hasParsedQuery()) { - // This is the idhack fast-path for getting a PlanExecutor without doing the work - // to create a CanonicalQuery. - const BSONObj& unparsedQuery = request->getQuery(); - - if (!collection) { - // Treat collections that do not exist as empty collections. Note that the explain - // reporting machinery always assumes that the root stage for a delete operation is - // a DeleteStage, so in this case we put a DeleteStage on top of an EOFStage. - LOG(2) << "Collection " << nss.ns() << " does not exist." - << " Using EOF stage: " << unparsedQuery.toString(); - DeleteStage* deleteStage = new DeleteStage(txn, deleteStageParams, ws.get(), NULL, - new EOFStage()); - return PlanExecutor::make(txn, ws.release(), deleteStage, nss.ns(), policy, - execOut); + bool userInitiatedWritesAndNotPrimary = txn->writesAreReplicated() && + !repl::getGlobalReplicationCoordinator()->canAcceptWritesFor(nss); - } + if (userInitiatedWritesAndNotPrimary) { + return Status(ErrorCodes::NotMaster, + str::stream() << "Not primary while removing from " << nss.ns()); + } - if (CanonicalQuery::isSimpleIdQuery(unparsedQuery) - && collection->getIndexCatalog()->findIdIndex(txn) - && request->getProj().isEmpty()) { - LOG(2) << "Using idhack: " << unparsedQuery.toString(); - - PlanStage* idHackStage = new IDHackStage(txn, - collection, - unparsedQuery["_id"].wrap(), - ws.get()); - DeleteStage* root = new DeleteStage(txn, deleteStageParams, ws.get(), collection, - idHackStage); - return PlanExecutor::make(txn, ws.release(), root, collection, policy, execOut); - } + DeleteStageParams deleteStageParams; + deleteStageParams.isMulti = request->isMulti(); + deleteStageParams.fromMigrate = request->isFromMigrate(); + deleteStageParams.isExplain = request->isExplain(); + deleteStageParams.returnDeleted = request->shouldReturnDeleted(); - // If we're here then we don't have a parsed query, but we're also not eligible for - // the idhack fast path. We need to force canonicalization now. - Status cqStatus = parsedDelete->parseQueryToCQ(); - if (!cqStatus.isOK()) { - return cqStatus; - } - } + unique_ptr<WorkingSet> ws(new WorkingSet()); + PlanExecutor::YieldPolicy policy = + parsedDelete->canYield() ? PlanExecutor::YIELD_AUTO : PlanExecutor::YIELD_MANUAL; - // This is the regular path for when we have a CanonicalQuery. - std::unique_ptr<CanonicalQuery> cq(parsedDelete->releaseParsedQuery()); + if (!parsedDelete->hasParsedQuery()) { + // This is the idhack fast-path for getting a PlanExecutor without doing the work + // to create a CanonicalQuery. + const BSONObj& unparsedQuery = request->getQuery(); - PlanStage* rawRoot; - QuerySolution* rawQuerySolution; - const size_t defaultPlannerOptions = 0; - Status status = prepareExecution(txn, collection, ws.get(), cq.get(), - defaultPlannerOptions, &rawRoot, &rawQuerySolution); - if (!status.isOK()) { - return status; - } - invariant(rawRoot); - std::unique_ptr<QuerySolution> querySolution(rawQuerySolution); - deleteStageParams.canonicalQuery = cq.get(); - - rawRoot = new DeleteStage(txn, deleteStageParams, ws.get(), collection, rawRoot); - std::unique_ptr<PlanStage> root(rawRoot); - - if (!request->getProj().isEmpty()) { - invariant(request->shouldReturnDeleted()); - - const bool allowPositional = true; - StatusWith<std::unique_ptr<PlanStage>> projStatus = applyProjection(txn, - nss, - cq.get(), - request->getProj(), - allowPositional, - ws.get(), - std::move(root)); - if (!projStatus.isOK()) { - return projStatus.getStatus(); - } - root = std::move(projStatus.getValue()); + if (!collection) { + // Treat collections that do not exist as empty collections. Note that the explain + // reporting machinery always assumes that the root stage for a delete operation is + // a DeleteStage, so in this case we put a DeleteStage on top of an EOFStage. + LOG(2) << "Collection " << nss.ns() << " does not exist." + << " Using EOF stage: " << unparsedQuery.toString(); + DeleteStage* deleteStage = + new DeleteStage(txn, deleteStageParams, ws.get(), NULL, new EOFStage()); + return PlanExecutor::make(txn, ws.release(), deleteStage, nss.ns(), policy, execOut); } - // We must have a tree of stages in order to have a valid plan executor, but the query - // solution may be null. - return PlanExecutor::make(txn, - ws.release(), - root.release(), - querySolution.release(), - cq.release(), - collection, - policy, - execOut); - } + if (CanonicalQuery::isSimpleIdQuery(unparsedQuery) && + collection->getIndexCatalog()->findIdIndex(txn) && request->getProj().isEmpty()) { + LOG(2) << "Using idhack: " << unparsedQuery.toString(); - // - // Update - // + PlanStage* idHackStage = + new IDHackStage(txn, collection, unparsedQuery["_id"].wrap(), ws.get()); + DeleteStage* root = + new DeleteStage(txn, deleteStageParams, ws.get(), collection, idHackStage); + return PlanExecutor::make(txn, ws.release(), root, collection, policy, execOut); + } - namespace { - - // TODO: Make this a function on NamespaceString, or make it cleaner. - inline void validateUpdate(const char* ns , - const BSONObj& updateobj, - const BSONObj& patternOrig) { - uassert(10155 , "cannot update reserved $ collection", strchr(ns, '$') == 0); - if (strstr(ns, ".system.")) { - /* dm: it's very important that system.indexes is never updated as IndexDetails - has pointers into it */ - uassert(10156, - str::stream() << "cannot update system collection: " - << ns << " q: " << patternOrig << " u: " << updateobj, - legalClientSystemNS(ns , true)); - } + // If we're here then we don't have a parsed query, but we're also not eligible for + // the idhack fast path. We need to force canonicalization now. + Status cqStatus = parsedDelete->parseQueryToCQ(); + if (!cqStatus.isOK()) { + return cqStatus; } + } - } // namespace + // This is the regular path for when we have a CanonicalQuery. + std::unique_ptr<CanonicalQuery> cq(parsedDelete->releaseParsedQuery()); - Status getExecutorUpdate(OperationContext* txn, - Collection* collection, - ParsedUpdate* parsedUpdate, - OpDebug* opDebug, - PlanExecutor** execOut) { - const UpdateRequest* request = parsedUpdate->getRequest(); - UpdateDriver* driver = parsedUpdate->getDriver(); + PlanStage* rawRoot; + QuerySolution* rawQuerySolution; + const size_t defaultPlannerOptions = 0; + Status status = prepareExecution( + txn, collection, ws.get(), cq.get(), defaultPlannerOptions, &rawRoot, &rawQuerySolution); + if (!status.isOK()) { + return status; + } + invariant(rawRoot); + std::unique_ptr<QuerySolution> querySolution(rawQuerySolution); + deleteStageParams.canonicalQuery = cq.get(); - const NamespaceString& nsString = request->getNamespaceString(); - UpdateLifecycle* lifecycle = request->getLifecycle(); + rawRoot = new DeleteStage(txn, deleteStageParams, ws.get(), collection, rawRoot); + std::unique_ptr<PlanStage> root(rawRoot); - validateUpdate(nsString.ns().c_str(), request->getUpdates(), request->getQuery()); + if (!request->getProj().isEmpty()) { + invariant(request->shouldReturnDeleted()); - // If there is no collection and this is an upsert, callers are supposed to create - // the collection prior to calling this method. Explain, however, will never do - // collection or database creation. - if (!collection && request->isUpsert()) { - invariant(request->isExplain()); + const bool allowPositional = true; + StatusWith<std::unique_ptr<PlanStage>> projStatus = applyProjection( + txn, nss, cq.get(), request->getProj(), allowPositional, ws.get(), std::move(root)); + if (!projStatus.isOK()) { + return projStatus.getStatus(); } + root = std::move(projStatus.getValue()); + } - // TODO: This seems a bit circuitious. - opDebug->updateobj = request->getUpdates(); + // We must have a tree of stages in order to have a valid plan executor, but the query + // solution may be null. + return PlanExecutor::make(txn, + ws.release(), + root.release(), + querySolution.release(), + cq.release(), + collection, + policy, + execOut); +} + +// +// Update +// - // If this is a user-issued update, then we want to return an error: you cannot perform - // writes on a secondary. If this is an update to a secondary from the replication system, - // however, then we make an exception and let the write proceed. In this case, - // shouldCallLogOp() will be false. - bool userInitiatedWritesAndNotPrimary = txn->writesAreReplicated() && - !repl::getGlobalReplicationCoordinator()->canAcceptWritesFor(nsString); +namespace { - if (userInitiatedWritesAndNotPrimary) { - return Status(ErrorCodes::NotMaster, - str::stream() << "Not primary while performing update on " - << nsString.ns()); - } +// TODO: Make this a function on NamespaceString, or make it cleaner. +inline void validateUpdate(const char* ns, const BSONObj& updateobj, const BSONObj& patternOrig) { + uassert(10155, "cannot update reserved $ collection", strchr(ns, '$') == 0); + if (strstr(ns, ".system.")) { + /* dm: it's very important that system.indexes is never updated as IndexDetails + has pointers into it */ + uassert(10156, + str::stream() << "cannot update system collection: " << ns << " q: " << patternOrig + << " u: " << updateobj, + legalClientSystemNS(ns, true)); + } +} - if (lifecycle) { - lifecycle->setCollection(collection); - driver->refreshIndexKeys(lifecycle->getIndexKeys(txn)); - } +} // namespace - PlanExecutor::YieldPolicy policy = parsedUpdate->canYield() ? PlanExecutor::YIELD_AUTO : - PlanExecutor::YIELD_MANUAL; - - unique_ptr<WorkingSet> ws(new WorkingSet()); - UpdateStageParams updateStageParams(request, driver, opDebug); - - if (!parsedUpdate->hasParsedQuery()) { - // This is the idhack fast-path for getting a PlanExecutor without doing the work - // to create a CanonicalQuery. - const BSONObj& unparsedQuery = request->getQuery(); - - if (!collection) { - // Treat collections that do not exist as empty collections. Note that the explain - // reporting machinery always assumes that the root stage for an update operation is - // an UpdateStage, so in this case we put an UpdateStage on top of an EOFStage. - LOG(2) << "Collection " << nsString.ns() << " does not exist." - << " Using EOF stage: " << unparsedQuery.toString(); - UpdateStage* updateStage = new UpdateStage(txn, updateStageParams, ws.get(), - collection, new EOFStage()); - return PlanExecutor::make(txn, ws.release(), updateStage, nsString.ns(), - policy, execOut); - } +Status getExecutorUpdate(OperationContext* txn, + Collection* collection, + ParsedUpdate* parsedUpdate, + OpDebug* opDebug, + PlanExecutor** execOut) { + const UpdateRequest* request = parsedUpdate->getRequest(); + UpdateDriver* driver = parsedUpdate->getDriver(); - if (CanonicalQuery::isSimpleIdQuery(unparsedQuery) - && collection->getIndexCatalog()->findIdIndex(txn) - && request->getProj().isEmpty()) { + const NamespaceString& nsString = request->getNamespaceString(); + UpdateLifecycle* lifecycle = request->getLifecycle(); - LOG(2) << "Using idhack: " << unparsedQuery.toString(); + validateUpdate(nsString.ns().c_str(), request->getUpdates(), request->getQuery()); - PlanStage* idHackStage = new IDHackStage(txn, - collection, - unparsedQuery["_id"].wrap(), - ws.get()); - UpdateStage* root = new UpdateStage(txn, updateStageParams, ws.get(), collection, - idHackStage); - return PlanExecutor::make(txn, ws.release(), root, collection, policy, execOut); - } + // If there is no collection and this is an upsert, callers are supposed to create + // the collection prior to calling this method. Explain, however, will never do + // collection or database creation. + if (!collection && request->isUpsert()) { + invariant(request->isExplain()); + } - // If we're here then we don't have a parsed query, but we're also not eligible for - // the idhack fast path. We need to force canonicalization now. - Status cqStatus = parsedUpdate->parseQueryToCQ(); - if (!cqStatus.isOK()) { - return cqStatus; - } - } + // TODO: This seems a bit circuitious. + opDebug->updateobj = request->getUpdates(); - // This is the regular path for when we have a CanonicalQuery. - std::unique_ptr<CanonicalQuery> cq(parsedUpdate->releaseParsedQuery()); + // If this is a user-issued update, then we want to return an error: you cannot perform + // writes on a secondary. If this is an update to a secondary from the replication system, + // however, then we make an exception and let the write proceed. In this case, + // shouldCallLogOp() will be false. + bool userInitiatedWritesAndNotPrimary = txn->writesAreReplicated() && + !repl::getGlobalReplicationCoordinator()->canAcceptWritesFor(nsString); - PlanStage* rawRoot; - QuerySolution* rawQuerySolution; - const size_t defaultPlannerOptions = 0; - Status status = prepareExecution(txn, collection, ws.get(), cq.get(), - defaultPlannerOptions, &rawRoot, &rawQuerySolution); - if (!status.isOK()) { - return status; - } - invariant(rawRoot); - std::unique_ptr<QuerySolution> querySolution(rawQuerySolution); - updateStageParams.canonicalQuery = cq.get(); - - rawRoot = new UpdateStage(txn, updateStageParams, ws.get(), collection, rawRoot); - std::unique_ptr<PlanStage> root(rawRoot); - - if (!request->getProj().isEmpty()) { - invariant(request->shouldReturnAnyDocs()); - - // If the plan stage is to return the newly-updated version of the documents, then it - // is invalid to use a positional projection because the query expression need not - // match the array element after the update has been applied. - const bool allowPositional = request->shouldReturnOldDocs(); - StatusWith<std::unique_ptr<PlanStage>> projStatus = applyProjection(txn, - nsString, - cq.get(), - request->getProj(), - allowPositional, - ws.get(), - std::move(root)); - if (!projStatus.isOK()) { - return projStatus.getStatus(); - } - root = std::move(projStatus.getValue()); - } + if (userInitiatedWritesAndNotPrimary) { + return Status(ErrorCodes::NotMaster, + str::stream() << "Not primary while performing update on " << nsString.ns()); + } - // We must have a tree of stages in order to have a valid plan executor, but the query - // solution may be null. Takes ownership of all args other than 'collection' and 'txn' - return PlanExecutor::make(txn, - ws.release(), - root.release(), - querySolution.release(), - cq.release(), - collection, - policy, - execOut); + if (lifecycle) { + lifecycle->setCollection(collection); + driver->refreshIndexKeys(lifecycle->getIndexKeys(txn)); } - // - // Group - // + PlanExecutor::YieldPolicy policy = + parsedUpdate->canYield() ? PlanExecutor::YIELD_AUTO : PlanExecutor::YIELD_MANUAL; - Status getExecutorGroup(OperationContext* txn, - Collection* collection, - const GroupRequest& request, - PlanExecutor::YieldPolicy yieldPolicy, - PlanExecutor** execOut) { - if (!globalScriptEngine) { - return Status(ErrorCodes::BadValue, "server-side JavaScript execution is disabled"); - } + unique_ptr<WorkingSet> ws(new WorkingSet()); + UpdateStageParams updateStageParams(request, driver, opDebug); - unique_ptr<WorkingSet> ws(new WorkingSet()); - PlanStage* root; - QuerySolution* querySolution; + if (!parsedUpdate->hasParsedQuery()) { + // This is the idhack fast-path for getting a PlanExecutor without doing the work + // to create a CanonicalQuery. + const BSONObj& unparsedQuery = request->getQuery(); if (!collection) { - // Treat collections that do not exist as empty collections. Note that the explain - // reporting machinery always assumes that the root stage for a group operation is a - // GroupStage, so in this case we put a GroupStage on top of an EOFStage. - root = new GroupStage(txn, request, ws.get(), new EOFStage()); - return PlanExecutor::make(txn, ws.release(), root, request.ns, yieldPolicy, execOut); + // Treat collections that do not exist as empty collections. Note that the explain + // reporting machinery always assumes that the root stage for an update operation is + // an UpdateStage, so in this case we put an UpdateStage on top of an EOFStage. + LOG(2) << "Collection " << nsString.ns() << " does not exist." + << " Using EOF stage: " << unparsedQuery.toString(); + UpdateStage* updateStage = + new UpdateStage(txn, updateStageParams, ws.get(), collection, new EOFStage()); + return PlanExecutor::make( + txn, ws.release(), updateStage, nsString.ns(), policy, execOut); } - const NamespaceString nss(request.ns); - const WhereCallbackReal whereCallback(txn, nss.db()); - CanonicalQuery* rawCanonicalQuery; - Status canonicalizeStatus = CanonicalQuery::canonicalize(request.ns, - request.query, - request.explain, - &rawCanonicalQuery, - whereCallback); - if (!canonicalizeStatus.isOK()) { - return canonicalizeStatus; - } - unique_ptr<CanonicalQuery> canonicalQuery(rawCanonicalQuery); + if (CanonicalQuery::isSimpleIdQuery(unparsedQuery) && + collection->getIndexCatalog()->findIdIndex(txn) && request->getProj().isEmpty()) { + LOG(2) << "Using idhack: " << unparsedQuery.toString(); - const size_t defaultPlannerOptions = 0; - Status status = prepareExecution(txn, collection, ws.get(), canonicalQuery.get(), - defaultPlannerOptions, &root, &querySolution); - if (!status.isOK()) { - return status; + PlanStage* idHackStage = + new IDHackStage(txn, collection, unparsedQuery["_id"].wrap(), ws.get()); + UpdateStage* root = + new UpdateStage(txn, updateStageParams, ws.get(), collection, idHackStage); + return PlanExecutor::make(txn, ws.release(), root, collection, policy, execOut); } - invariant(root); - root = new GroupStage(txn, request, ws.get(), root); - // We must have a tree of stages in order to have a valid plan executor, but the query - // solution may be null. Takes ownership of all args other than 'collection'. - return PlanExecutor::make(txn, - ws.release(), - root, - querySolution, - canonicalQuery.release(), - collection, - yieldPolicy, - execOut); + // If we're here then we don't have a parsed query, but we're also not eligible for + // the idhack fast path. We need to force canonicalization now. + Status cqStatus = parsedUpdate->parseQueryToCQ(); + if (!cqStatus.isOK()) { + return cqStatus; + } } - // - // Count hack - // + // This is the regular path for when we have a CanonicalQuery. + std::unique_ptr<CanonicalQuery> cq(parsedUpdate->releaseParsedQuery()); - namespace { + PlanStage* rawRoot; + QuerySolution* rawQuerySolution; + const size_t defaultPlannerOptions = 0; + Status status = prepareExecution( + txn, collection, ws.get(), cq.get(), defaultPlannerOptions, &rawRoot, &rawQuerySolution); + if (!status.isOK()) { + return status; + } + invariant(rawRoot); + std::unique_ptr<QuerySolution> querySolution(rawQuerySolution); + updateStageParams.canonicalQuery = cq.get(); + + rawRoot = new UpdateStage(txn, updateStageParams, ws.get(), collection, rawRoot); + std::unique_ptr<PlanStage> root(rawRoot); + + if (!request->getProj().isEmpty()) { + invariant(request->shouldReturnAnyDocs()); + + // If the plan stage is to return the newly-updated version of the documents, then it + // is invalid to use a positional projection because the query expression need not + // match the array element after the update has been applied. + const bool allowPositional = request->shouldReturnOldDocs(); + StatusWith<std::unique_ptr<PlanStage>> projStatus = applyProjection(txn, + nsString, + cq.get(), + request->getProj(), + allowPositional, + ws.get(), + std::move(root)); + if (!projStatus.isOK()) { + return projStatus.getStatus(); + } + root = std::move(projStatus.getValue()); + } - /** - * Returns 'true' if the provided solution 'soln' can be rewritten to use - * a fast counting stage. Mutates the tree in 'soln->root'. - * - * Otherwise, returns 'false'. - */ - bool turnIxscanIntoCount(QuerySolution* soln) { - QuerySolutionNode* root = soln->root.get(); + // We must have a tree of stages in order to have a valid plan executor, but the query + // solution may be null. Takes ownership of all args other than 'collection' and 'txn' + return PlanExecutor::make(txn, + ws.release(), + root.release(), + querySolution.release(), + cq.release(), + collection, + policy, + execOut); +} + +// +// Group +// + +Status getExecutorGroup(OperationContext* txn, + Collection* collection, + const GroupRequest& request, + PlanExecutor::YieldPolicy yieldPolicy, + PlanExecutor** execOut) { + if (!globalScriptEngine) { + return Status(ErrorCodes::BadValue, "server-side JavaScript execution is disabled"); + } - // Root should be a fetch w/o any filters. - if (STAGE_FETCH != root->getType()) { - return false; - } + unique_ptr<WorkingSet> ws(new WorkingSet()); + PlanStage* root; + QuerySolution* querySolution; - if (NULL != root->filter.get()) { - return false; - } + if (!collection) { + // Treat collections that do not exist as empty collections. Note that the explain + // reporting machinery always assumes that the root stage for a group operation is a + // GroupStage, so in this case we put a GroupStage on top of an EOFStage. + root = new GroupStage(txn, request, ws.get(), new EOFStage()); + return PlanExecutor::make(txn, ws.release(), root, request.ns, yieldPolicy, execOut); + } - // Child should be an ixscan. - if (STAGE_IXSCAN != root->children[0]->getType()) { - return false; - } + const NamespaceString nss(request.ns); + const WhereCallbackReal whereCallback(txn, nss.db()); + CanonicalQuery* rawCanonicalQuery; + Status canonicalizeStatus = CanonicalQuery::canonicalize( + request.ns, request.query, request.explain, &rawCanonicalQuery, whereCallback); + if (!canonicalizeStatus.isOK()) { + return canonicalizeStatus; + } + unique_ptr<CanonicalQuery> canonicalQuery(rawCanonicalQuery); + + const size_t defaultPlannerOptions = 0; + Status status = prepareExecution(txn, + collection, + ws.get(), + canonicalQuery.get(), + defaultPlannerOptions, + &root, + &querySolution); + if (!status.isOK()) { + return status; + } + invariant(root); + + root = new GroupStage(txn, request, ws.get(), root); + // We must have a tree of stages in order to have a valid plan executor, but the query + // solution may be null. Takes ownership of all args other than 'collection'. + return PlanExecutor::make(txn, + ws.release(), + root, + querySolution, + canonicalQuery.release(), + collection, + yieldPolicy, + execOut); +} + +// +// Count hack +// - IndexScanNode* isn = static_cast<IndexScanNode*>(root->children[0]); +namespace { - // No filters allowed and side-stepping isSimpleRange for now. TODO: do we ever see - // isSimpleRange here? because we could well use it. I just don't think we ever do see - // it. +/** + * Returns 'true' if the provided solution 'soln' can be rewritten to use + * a fast counting stage. Mutates the tree in 'soln->root'. + * + * Otherwise, returns 'false'. + */ +bool turnIxscanIntoCount(QuerySolution* soln) { + QuerySolutionNode* root = soln->root.get(); - if (NULL != isn->filter.get() || isn->bounds.isSimpleRange) { - return false; - } + // Root should be a fetch w/o any filters. + if (STAGE_FETCH != root->getType()) { + return false; + } - // Make sure the bounds are OK. - BSONObj startKey; - bool startKeyInclusive; - BSONObj endKey; - bool endKeyInclusive; - - if (!IndexBoundsBuilder::isSingleInterval( isn->bounds, - &startKey, - &startKeyInclusive, - &endKey, - &endKeyInclusive )) { - return false; - } + if (NULL != root->filter.get()) { + return false; + } - // Make the count node that we replace the fetch + ixscan with. - CountNode* cn = new CountNode(); - cn->indexKeyPattern = isn->indexKeyPattern; - cn->startKey = startKey; - cn->startKeyInclusive = startKeyInclusive; - cn->endKey = endKey; - cn->endKeyInclusive = endKeyInclusive; - // Takes ownership of 'cn' and deletes the old root. - soln->root.reset(cn); - return true; - } + // Child should be an ixscan. + if (STAGE_IXSCAN != root->children[0]->getType()) { + return false; + } - /** - * Returns true if indices contains an index that can be - * used with DistinctNode. Sets indexOut to the array index - * of PlannerParams::indices. - * Look for the index for the fewest fields. - * Criteria for suitable index is that the index cannot be special - * (geo, hashed, text, ...). - * - * Multikey indices are not suitable for DistinctNode when the projection - * is on an array element. Arrays are flattened in a multikey index which - * makes it impossible for the distinct scan stage (plan stage generated from - * DistinctNode) to select the requested element by array index. - * - * Multikey indices cannot be used for the fast distinct hack if the field is dotted. - * Currently the solution generated for the distinct hack includes a projection stage and - * the projection stage cannot be covered with a dotted field. - */ - bool getDistinctNodeIndex(const std::vector<IndexEntry>& indices, - const std::string& field, size_t* indexOut) { - invariant(indexOut); - bool isDottedField = str::contains(field, '.'); - int minFields = std::numeric_limits<int>::max(); - for (size_t i = 0; i < indices.size(); ++i) { - // Skip special indices. - if (!IndexNames::findPluginName(indices[i].keyPattern).empty()) { - continue; - } - // Skip multikey indices if we are projecting on a dotted field. - if (indices[i].multikey && isDottedField) { - continue; - } - int nFields = indices[i].keyPattern.nFields(); - // Pick the index with the lowest number of fields. - if (nFields < minFields) { - minFields = nFields; - *indexOut = i; - } - } - return minFields != std::numeric_limits<int>::max(); - } + IndexScanNode* isn = static_cast<IndexScanNode*>(root->children[0]); - /** - * Checks dotted field for a projection and truncates the - * field name if we could be projecting on an array element. - * Sets 'isIDOut' to true if the projection is on a sub document of _id. - * For example, _id.a.2, _id.b.c. - */ - std::string getProjectedDottedField(const std::string& field, bool* isIDOut) { - // Check if field contains an array index. - std::vector<std::string> res; - mongo::splitStringDelim(field, &res, '.'); - - // Since we could exit early from the loop, - // we should check _id here and set '*isIDOut' accordingly. - *isIDOut = ("_id" == res[0]); - - // Skip the first dotted component. If the field starts - // with a number, the number cannot be an array index. - int arrayIndex = 0; - for (size_t i = 1; i < res.size(); ++i) { - if (mongo::parseNumberFromStringWithBase(res[i], 10, &arrayIndex).isOK()) { - // Array indices cannot be negative numbers (this is not $slice). - // Negative numbers are allowed as field names. - if (arrayIndex >= 0) { - // Generate prefix of field up to (but not including) array index. - std::vector<std::string> prefixStrings(res); - prefixStrings.resize(i); - // Reset projectedField. Instead of overwriting, joinStringDelim() appends joined string - // to the end of projectedField. - std::string projectedField; - mongo::joinStringDelim(prefixStrings, &projectedField, '.'); - return projectedField; - } - } - } + // No filters allowed and side-stepping isSimpleRange for now. TODO: do we ever see + // isSimpleRange here? because we could well use it. I just don't think we ever do see + // it. - return field; - } + if (NULL != isn->filter.get() || isn->bounds.isSimpleRange) { + return false; + } - /** - * Creates a projection spec for a distinct command from the requested field. - * In most cases, the projection spec will be {_id: 0, key: 1}. - * The exceptions are: - * 1) When the requested field is '_id', the projection spec will {_id: 1}. - * 2) When the requested field could be an array element (eg. a.0), - * the projected field will be the prefix of the field up to the array element. - * For example, a.b.2 => {_id: 0, 'a.b': 1} - * Note that we can't use a $slice projection because the distinct command filters - * the results from the executor using the dotted field name. Using $slice will - * re-order the documents in the array in the results. - */ - BSONObj getDistinctProjection(const std::string& field) { - std::string projectedField(field); - - bool isID = false; - if ("_id" == field) { - isID = true; - } - else if (str::contains(field, '.')) { - projectedField = getProjectedDottedField(field, &isID); - } - BSONObjBuilder bob; - if (!isID) { - bob.append("_id", 0); - } - bob.append(projectedField, 1); - return bob.obj(); - } + // Make sure the bounds are OK. + BSONObj startKey; + bool startKeyInclusive; + BSONObj endKey; + bool endKeyInclusive; - } // namespace + if (!IndexBoundsBuilder::isSingleInterval( + isn->bounds, &startKey, &startKeyInclusive, &endKey, &endKeyInclusive)) { + return false; + } - Status getExecutorCount(OperationContext* txn, - Collection* collection, - const CountRequest& request, - bool explain, - PlanExecutor::YieldPolicy yieldPolicy, - PlanExecutor** execOut) { + // Make the count node that we replace the fetch + ixscan with. + CountNode* cn = new CountNode(); + cn->indexKeyPattern = isn->indexKeyPattern; + cn->startKey = startKey; + cn->startKeyInclusive = startKeyInclusive; + cn->endKey = endKey; + cn->endKeyInclusive = endKeyInclusive; + // Takes ownership of 'cn' and deletes the old root. + soln->root.reset(cn); + return true; +} - unique_ptr<WorkingSet> ws(new WorkingSet()); - PlanStage* root; - QuerySolution* querySolution; - - // If collection exists and the query is empty, no additional canonicalization is needed. - // If the query is empty, then we can determine the count by just asking the collection - // for its number of records. This is implemented by the CountStage, and we don't need - // to create a child for the count stage in this case. - // - // If there is a hint, then we can't use a trival count plan as described above. - if (collection && request.getQuery().isEmpty() && request.getHint().isEmpty()) { - root = new CountStage(txn, collection, request, ws.get(), NULL); - return PlanExecutor::make(txn, - ws.release(), - root, - request.getNs(), - yieldPolicy, - execOut); +/** + * Returns true if indices contains an index that can be + * used with DistinctNode. Sets indexOut to the array index + * of PlannerParams::indices. + * Look for the index for the fewest fields. + * Criteria for suitable index is that the index cannot be special + * (geo, hashed, text, ...). + * + * Multikey indices are not suitable for DistinctNode when the projection + * is on an array element. Arrays are flattened in a multikey index which + * makes it impossible for the distinct scan stage (plan stage generated from + * DistinctNode) to select the requested element by array index. + * + * Multikey indices cannot be used for the fast distinct hack if the field is dotted. + * Currently the solution generated for the distinct hack includes a projection stage and + * the projection stage cannot be covered with a dotted field. + */ +bool getDistinctNodeIndex(const std::vector<IndexEntry>& indices, + const std::string& field, + size_t* indexOut) { + invariant(indexOut); + bool isDottedField = str::contains(field, '.'); + int minFields = std::numeric_limits<int>::max(); + for (size_t i = 0; i < indices.size(); ++i) { + // Skip special indices. + if (!IndexNames::findPluginName(indices[i].keyPattern).empty()) { + continue; } - - unique_ptr<CanonicalQuery> cq; - if (!request.getQuery().isEmpty() || !request.getHint().isEmpty()) { - // If query or hint is not empty, canonicalize the query before working with collection. - typedef MatchExpressionParser::WhereCallback WhereCallback; - CanonicalQuery* rawCq = NULL; - Status canonStatus = CanonicalQuery::canonicalize( - request.getNs(), - request.getQuery(), - BSONObj(), // sort - BSONObj(), // projection - 0, // skip - 0, // limit - request.getHint(), - BSONObj(), // min - BSONObj(), // max - false, // snapshot - explain, - &rawCq, - collection ? - static_cast<const WhereCallback&>(WhereCallbackReal(txn, - collection->ns().db())) : - static_cast<const WhereCallback&>(WhereCallbackNoop())); - if (!canonStatus.isOK()) { - return canonStatus; - } - cq.reset(rawCq); + // Skip multikey indices if we are projecting on a dotted field. + if (indices[i].multikey && isDottedField) { + continue; + } + int nFields = indices[i].keyPattern.nFields(); + // Pick the index with the lowest number of fields. + if (nFields < minFields) { + minFields = nFields; + *indexOut = i; } + } + return minFields != std::numeric_limits<int>::max(); +} - if (!collection) { - // Treat collections that do not exist as empty collections. Note that the explain - // reporting machinery always assumes that the root stage for a count operation is - // a CountStage, so in this case we put a CountStage on top of an EOFStage. - root = new CountStage(txn, collection, request, ws.get(), new EOFStage()); - return PlanExecutor::make(txn, - ws.release(), - root, - request.getNs(), - yieldPolicy, - execOut); +/** + * Checks dotted field for a projection and truncates the + * field name if we could be projecting on an array element. + * Sets 'isIDOut' to true if the projection is on a sub document of _id. + * For example, _id.a.2, _id.b.c. + */ +std::string getProjectedDottedField(const std::string& field, bool* isIDOut) { + // Check if field contains an array index. + std::vector<std::string> res; + mongo::splitStringDelim(field, &res, '.'); + + // Since we could exit early from the loop, + // we should check _id here and set '*isIDOut' accordingly. + *isIDOut = ("_id" == res[0]); + + // Skip the first dotted component. If the field starts + // with a number, the number cannot be an array index. + int arrayIndex = 0; + for (size_t i = 1; i < res.size(); ++i) { + if (mongo::parseNumberFromStringWithBase(res[i], 10, &arrayIndex).isOK()) { + // Array indices cannot be negative numbers (this is not $slice). + // Negative numbers are allowed as field names. + if (arrayIndex >= 0) { + // Generate prefix of field up to (but not including) array index. + std::vector<std::string> prefixStrings(res); + prefixStrings.resize(i); + // Reset projectedField. Instead of overwriting, joinStringDelim() appends joined string + // to the end of projectedField. + std::string projectedField; + mongo::joinStringDelim(prefixStrings, &projectedField, '.'); + return projectedField; + } } + } - invariant(cq.get()); + return field; +} - const size_t plannerOptions = QueryPlannerParams::PRIVATE_IS_COUNT; - Status prepStatus = prepareExecution(txn, collection, ws.get(), cq.get(), plannerOptions, - &root, &querySolution); - if (!prepStatus.isOK()) { - return prepStatus; - } - invariant(root); - - // Make a CountStage to be the new root. - root = new CountStage(txn, collection, request, ws.get(), root); - // We must have a tree of stages in order to have a valid plan executor, but the query - // solution may be NULL. Takes ownership of all args other than 'collection' and 'txn' - return PlanExecutor::make(txn, - ws.release(), - root, - querySolution, - cq.release(), - collection, - yieldPolicy, - execOut); +/** + * Creates a projection spec for a distinct command from the requested field. + * In most cases, the projection spec will be {_id: 0, key: 1}. + * The exceptions are: + * 1) When the requested field is '_id', the projection spec will {_id: 1}. + * 2) When the requested field could be an array element (eg. a.0), + * the projected field will be the prefix of the field up to the array element. + * For example, a.b.2 => {_id: 0, 'a.b': 1} + * Note that we can't use a $slice projection because the distinct command filters + * the results from the executor using the dotted field name. Using $slice will + * re-order the documents in the array in the results. + */ +BSONObj getDistinctProjection(const std::string& field) { + std::string projectedField(field); + + bool isID = false; + if ("_id" == field) { + isID = true; + } else if (str::contains(field, '.')) { + projectedField = getProjectedDottedField(field, &isID); + } + BSONObjBuilder bob; + if (!isID) { + bob.append("_id", 0); } + bob.append(projectedField, 1); + return bob.obj(); +} +} // namespace + +Status getExecutorCount(OperationContext* txn, + Collection* collection, + const CountRequest& request, + bool explain, + PlanExecutor::YieldPolicy yieldPolicy, + PlanExecutor** execOut) { + unique_ptr<WorkingSet> ws(new WorkingSet()); + PlanStage* root; + QuerySolution* querySolution; + + // If collection exists and the query is empty, no additional canonicalization is needed. + // If the query is empty, then we can determine the count by just asking the collection + // for its number of records. This is implemented by the CountStage, and we don't need + // to create a child for the count stage in this case. // - // Distinct hack - // + // If there is a hint, then we can't use a trival count plan as described above. + if (collection && request.getQuery().isEmpty() && request.getHint().isEmpty()) { + root = new CountStage(txn, collection, request, ws.get(), NULL); + return PlanExecutor::make(txn, ws.release(), root, request.getNs(), yieldPolicy, execOut); + } - bool turnIxscanIntoDistinctIxscan(QuerySolution* soln, const string& field) { - QuerySolutionNode* root = soln->root.get(); + unique_ptr<CanonicalQuery> cq; + if (!request.getQuery().isEmpty() || !request.getHint().isEmpty()) { + // If query or hint is not empty, canonicalize the query before working with collection. + typedef MatchExpressionParser::WhereCallback WhereCallback; + CanonicalQuery* rawCq = NULL; + Status canonStatus = CanonicalQuery::canonicalize( + request.getNs(), + request.getQuery(), + BSONObj(), // sort + BSONObj(), // projection + 0, // skip + 0, // limit + request.getHint(), + BSONObj(), // min + BSONObj(), // max + false, // snapshot + explain, + &rawCq, + collection + ? static_cast<const WhereCallback&>(WhereCallbackReal(txn, collection->ns().db())) + : static_cast<const WhereCallback&>(WhereCallbackNoop())); + if (!canonStatus.isOK()) { + return canonStatus; + } + cq.reset(rawCq); + } - // We're looking for a project on top of an ixscan. - if (STAGE_PROJECTION == root->getType() && (STAGE_IXSCAN == root->children[0]->getType())) { - IndexScanNode* isn = static_cast<IndexScanNode*>(root->children[0]); + if (!collection) { + // Treat collections that do not exist as empty collections. Note that the explain + // reporting machinery always assumes that the root stage for a count operation is + // a CountStage, so in this case we put a CountStage on top of an EOFStage. + root = new CountStage(txn, collection, request, ws.get(), new EOFStage()); + return PlanExecutor::make(txn, ws.release(), root, request.getNs(), yieldPolicy, execOut); + } - // An additional filter must be applied to the data in the key, so we can't just skip - // all the keys with a given value; we must examine every one to find the one that (may) - // pass the filter. - if (NULL != isn->filter.get()) { - return false; - } + invariant(cq.get()); - // We only set this when we have special query modifiers (.max() or .min()) or other - // special cases. Don't want to handle the interactions between those and distinct. - // Don't think this will ever really be true but if it somehow is, just ignore this - // soln. - if (isn->bounds.isSimpleRange) { - return false; - } + const size_t plannerOptions = QueryPlannerParams::PRIVATE_IS_COUNT; + Status prepStatus = prepareExecution( + txn, collection, ws.get(), cq.get(), plannerOptions, &root, &querySolution); + if (!prepStatus.isOK()) { + return prepStatus; + } + invariant(root); + + // Make a CountStage to be the new root. + root = new CountStage(txn, collection, request, ws.get(), root); + // We must have a tree of stages in order to have a valid plan executor, but the query + // solution may be NULL. Takes ownership of all args other than 'collection' and 'txn' + return PlanExecutor::make( + txn, ws.release(), root, querySolution, cq.release(), collection, yieldPolicy, execOut); +} + +// +// Distinct hack +// + +bool turnIxscanIntoDistinctIxscan(QuerySolution* soln, const string& field) { + QuerySolutionNode* root = soln->root.get(); + + // We're looking for a project on top of an ixscan. + if (STAGE_PROJECTION == root->getType() && (STAGE_IXSCAN == root->children[0]->getType())) { + IndexScanNode* isn = static_cast<IndexScanNode*>(root->children[0]); + + // An additional filter must be applied to the data in the key, so we can't just skip + // all the keys with a given value; we must examine every one to find the one that (may) + // pass the filter. + if (NULL != isn->filter.get()) { + return false; + } - // Make a new DistinctNode. We swap this for the ixscan in the provided solution. - DistinctNode* dn = new DistinctNode(); - dn->indexKeyPattern = isn->indexKeyPattern; - dn->direction = isn->direction; - dn->bounds = isn->bounds; - - // Figure out which field we're skipping to the next value of. TODO: We currently only - // try to distinct-hack when there is an index prefixed by the field we're distinct-ing - // over. Consider removing this code if we stick with that policy. - dn->fieldNo = 0; - BSONObjIterator it(isn->indexKeyPattern); - while (it.more()) { - if (field == it.next().fieldName()) { - break; - } - dn->fieldNo++; - } + // We only set this when we have special query modifiers (.max() or .min()) or other + // special cases. Don't want to handle the interactions between those and distinct. + // Don't think this will ever really be true but if it somehow is, just ignore this + // soln. + if (isn->bounds.isSimpleRange) { + return false; + } - // Delete the old index scan, set the child of project to the fast distinct scan. - delete root->children[0]; - root->children[0] = dn; - return true; + // Make a new DistinctNode. We swap this for the ixscan in the provided solution. + DistinctNode* dn = new DistinctNode(); + dn->indexKeyPattern = isn->indexKeyPattern; + dn->direction = isn->direction; + dn->bounds = isn->bounds; + + // Figure out which field we're skipping to the next value of. TODO: We currently only + // try to distinct-hack when there is an index prefixed by the field we're distinct-ing + // over. Consider removing this code if we stick with that policy. + dn->fieldNo = 0; + BSONObjIterator it(isn->indexKeyPattern); + while (it.more()) { + if (field == it.next().fieldName()) { + break; + } + dn->fieldNo++; } - return false; + // Delete the old index scan, set the child of project to the fast distinct scan. + delete root->children[0]; + root->children[0] = dn; + return true; } - Status getExecutorDistinct(OperationContext* txn, - Collection* collection, - const BSONObj& query, - const std::string& field, - PlanExecutor::YieldPolicy yieldPolicy, - PlanExecutor** out) { - // This should'a been checked by the distinct command. - invariant(collection); - - // TODO: check for idhack here? - - // When can we do a fast distinct hack? - // 1. There is a plan with just one leaf and that leaf is an ixscan. - // 2. The ixscan indexes the field we're interested in. - // 2a: We are correct if the index contains the field but for now we look for prefix. - // 3. The query is covered/no fetch. - // - // We go through normal planning (with limited parameters) to see if we can produce - // a soln with the above properties. - - QueryPlannerParams plannerParams; - plannerParams.options = QueryPlannerParams::NO_TABLE_SCAN; - - // TODO Need to check if query is compatible with any partial indexes. SERVER-17854. - IndexCatalog::IndexIterator ii = collection->getIndexCatalog()->getIndexIterator(txn,false); - while (ii.more()) { - const IndexDescriptor* desc = ii.next(); - // The distinct hack can work if any field is in the index but it's not always clear - // if it's a win unless it's the first field. - if (desc->keyPattern().firstElement().fieldName() == field) { - plannerParams.indices.push_back(IndexEntry(desc->keyPattern(), - desc->getAccessMethodName(), - desc->isMultikey(txn), - desc->isSparse(), - desc->unique(), - desc->indexName(), - NULL, - desc->infoObj())); - } - } + return false; +} - const WhereCallbackReal whereCallback(txn, collection->ns().db()); +Status getExecutorDistinct(OperationContext* txn, + Collection* collection, + const BSONObj& query, + const std::string& field, + PlanExecutor::YieldPolicy yieldPolicy, + PlanExecutor** out) { + // This should'a been checked by the distinct command. + invariant(collection); - // If there are no suitable indices for the distinct hack bail out now into regular planning - // with no projection. - if (plannerParams.indices.empty()) { - CanonicalQuery* cq; - Status status = CanonicalQuery::canonicalize( - collection->ns().ns(), query, &cq, whereCallback); - if (!status.isOK()) { - return status; - } + // TODO: check for idhack here? - // Takes ownership of 'cq'. - return getExecutor(txn, collection, cq, yieldPolicy, out); + // When can we do a fast distinct hack? + // 1. There is a plan with just one leaf and that leaf is an ixscan. + // 2. The ixscan indexes the field we're interested in. + // 2a: We are correct if the index contains the field but for now we look for prefix. + // 3. The query is covered/no fetch. + // + // We go through normal planning (with limited parameters) to see if we can produce + // a soln with the above properties. + + QueryPlannerParams plannerParams; + plannerParams.options = QueryPlannerParams::NO_TABLE_SCAN; + + // TODO Need to check if query is compatible with any partial indexes. SERVER-17854. + IndexCatalog::IndexIterator ii = collection->getIndexCatalog()->getIndexIterator(txn, false); + while (ii.more()) { + const IndexDescriptor* desc = ii.next(); + // The distinct hack can work if any field is in the index but it's not always clear + // if it's a win unless it's the first field. + if (desc->keyPattern().firstElement().fieldName() == field) { + plannerParams.indices.push_back(IndexEntry(desc->keyPattern(), + desc->getAccessMethodName(), + desc->isMultikey(txn), + desc->isSparse(), + desc->unique(), + desc->indexName(), + NULL, + desc->infoObj())); } + } - // - // If we're here, we have an index prefixed by the field we're distinct-ing over. - // - - // Applying a projection allows the planner to try to give us covered plans that we can turn - // into the projection hack. getDistinctProjection deals with .find() projection semantics - // (ie _id:1 being implied by default). - BSONObj projection = getDistinctProjection(field); + const WhereCallbackReal whereCallback(txn, collection->ns().db()); - // Apply a projection of the key. Empty BSONObj() is for the sort. + // If there are no suitable indices for the distinct hack bail out now into regular planning + // with no projection. + if (plannerParams.indices.empty()) { CanonicalQuery* cq; - Status status = CanonicalQuery::canonicalize(collection->ns().ns(), - query, - BSONObj(), - projection, - &cq, - whereCallback); + Status status = + CanonicalQuery::canonicalize(collection->ns().ns(), query, &cq, whereCallback); if (!status.isOK()) { return status; } - unique_ptr<CanonicalQuery> autoCq(cq); + // Takes ownership of 'cq'. + return getExecutor(txn, collection, cq, yieldPolicy, out); + } - // If there's no query, we can just distinct-scan one of the indices. - // Not every index in plannerParams.indices may be suitable. Refer to - // getDistinctNodeIndex(). - size_t distinctNodeIndex = 0; - if (query.isEmpty() && - getDistinctNodeIndex(plannerParams.indices, field, &distinctNodeIndex)) { - DistinctNode* dn = new DistinctNode(); - dn->indexKeyPattern = plannerParams.indices[distinctNodeIndex].keyPattern; - dn->direction = 1; - IndexBoundsBuilder::allValuesBounds(dn->indexKeyPattern, &dn->bounds); - dn->fieldNo = 0; + // + // If we're here, we have an index prefixed by the field we're distinct-ing over. + // - QueryPlannerParams params; + // Applying a projection allows the planner to try to give us covered plans that we can turn + // into the projection hack. getDistinctProjection deals with .find() projection semantics + // (ie _id:1 being implied by default). + BSONObj projection = getDistinctProjection(field); + + // Apply a projection of the key. Empty BSONObj() is for the sort. + CanonicalQuery* cq; + Status status = CanonicalQuery::canonicalize( + collection->ns().ns(), query, BSONObj(), projection, &cq, whereCallback); + if (!status.isOK()) { + return status; + } - // Takes ownership of 'dn'. - QuerySolution* soln = QueryPlannerAnalysis::analyzeDataAccess(*cq, params, dn); - invariant(soln); + unique_ptr<CanonicalQuery> autoCq(cq); - WorkingSet* ws = new WorkingSet(); - PlanStage* root; - verify(StageBuilder::build(txn, collection, *soln, ws, &root)); + // If there's no query, we can just distinct-scan one of the indices. + // Not every index in plannerParams.indices may be suitable. Refer to + // getDistinctNodeIndex(). + size_t distinctNodeIndex = 0; + if (query.isEmpty() && getDistinctNodeIndex(plannerParams.indices, field, &distinctNodeIndex)) { + DistinctNode* dn = new DistinctNode(); + dn->indexKeyPattern = plannerParams.indices[distinctNodeIndex].keyPattern; + dn->direction = 1; + IndexBoundsBuilder::allValuesBounds(dn->indexKeyPattern, &dn->bounds); + dn->fieldNo = 0; - LOG(2) << "Using fast distinct: " << cq->toStringShort() - << ", planSummary: " << Explain::getPlanSummary(root); + QueryPlannerParams params; - // Takes ownership of its arguments (except for 'collection'). - return PlanExecutor::make(txn, ws, root, soln, autoCq.release(), collection, - yieldPolicy, out); - } + // Takes ownership of 'dn'. + QuerySolution* soln = QueryPlannerAnalysis::analyzeDataAccess(*cq, params, dn); + invariant(soln); - // See if we can answer the query in a fast-distinct compatible fashion. - vector<QuerySolution*> solutions; - status = QueryPlanner::plan(*cq, plannerParams, &solutions); - if (!status.isOK()) { - return getExecutor(txn, collection, autoCq.release(), yieldPolicy, out); - } + WorkingSet* ws = new WorkingSet(); + PlanStage* root; + verify(StageBuilder::build(txn, collection, *soln, ws, &root)); - // We look for a solution that has an ixscan we can turn into a distinctixscan - for (size_t i = 0; i < solutions.size(); ++i) { - if (turnIxscanIntoDistinctIxscan(solutions[i], field)) { - // Great, we can use solutions[i]. Clean up the other QuerySolution(s). - for (size_t j = 0; j < solutions.size(); ++j) { - if (j != i) { - delete solutions[j]; - } - } + LOG(2) << "Using fast distinct: " << cq->toStringShort() + << ", planSummary: " << Explain::getPlanSummary(root); - // Build and return the SSR over solutions[i]. - WorkingSet* ws = new WorkingSet(); - PlanStage* root; - verify(StageBuilder::build(txn, collection, *solutions[i], ws, &root)); + // Takes ownership of its arguments (except for 'collection'). + return PlanExecutor::make( + txn, ws, root, soln, autoCq.release(), collection, yieldPolicy, out); + } - LOG(2) << "Using fast distinct: " << cq->toStringShort() - << ", planSummary: " << Explain::getPlanSummary(root); + // See if we can answer the query in a fast-distinct compatible fashion. + vector<QuerySolution*> solutions; + status = QueryPlanner::plan(*cq, plannerParams, &solutions); + if (!status.isOK()) { + return getExecutor(txn, collection, autoCq.release(), yieldPolicy, out); + } - // Takes ownership of 'ws', 'root', 'solutions[i]', and 'autoCq'. - return PlanExecutor::make(txn, ws, root, solutions[i], autoCq.release(), - collection, yieldPolicy, out); + // We look for a solution that has an ixscan we can turn into a distinctixscan + for (size_t i = 0; i < solutions.size(); ++i) { + if (turnIxscanIntoDistinctIxscan(solutions[i], field)) { + // Great, we can use solutions[i]. Clean up the other QuerySolution(s). + for (size_t j = 0; j < solutions.size(); ++j) { + if (j != i) { + delete solutions[j]; + } } - } - // If we're here, the planner made a soln with the restricted index set but we couldn't - // translate any of them into a distinct-compatible soln. So, delete the solutions and just - // go through normal planning. - for (size_t i = 0; i < solutions.size(); ++i) { - delete solutions[i]; - } + // Build and return the SSR over solutions[i]. + WorkingSet* ws = new WorkingSet(); + PlanStage* root; + verify(StageBuilder::build(txn, collection, *solutions[i], ws, &root)); - // We drop the projection from the 'cq'. Unfortunately this is not trivial. - status = CanonicalQuery::canonicalize(collection->ns().ns(), query, &cq, whereCallback); - if (!status.isOK()) { - return status; + LOG(2) << "Using fast distinct: " << cq->toStringShort() + << ", planSummary: " << Explain::getPlanSummary(root); + + // Takes ownership of 'ws', 'root', 'solutions[i]', and 'autoCq'. + return PlanExecutor::make( + txn, ws, root, solutions[i], autoCq.release(), collection, yieldPolicy, out); } + } - autoCq.reset(cq); + // If we're here, the planner made a soln with the restricted index set but we couldn't + // translate any of them into a distinct-compatible soln. So, delete the solutions and just + // go through normal planning. + for (size_t i = 0; i < solutions.size(); ++i) { + delete solutions[i]; + } - // Takes ownership of 'autoCq'. - return getExecutor(txn, collection, autoCq.release(), yieldPolicy, out); + // We drop the projection from the 'cq'. Unfortunately this is not trivial. + status = CanonicalQuery::canonicalize(collection->ns().ns(), query, &cq, whereCallback); + if (!status.isOK()) { + return status; } + autoCq.reset(cq); + + // Takes ownership of 'autoCq'. + return getExecutor(txn, collection, autoCq.release(), yieldPolicy, out); +} + } // namespace mongo |