summaryrefslogtreecommitdiff
path: root/src/mongo/db/query/planner_access.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/mongo/db/query/planner_access.cpp')
-rw-r--r--src/mongo/db/query/planner_access.cpp320
1 files changed, 106 insertions, 214 deletions
diff --git a/src/mongo/db/query/planner_access.cpp b/src/mongo/db/query/planner_access.cpp
index de294ad661a..e05dfd8a5d1 100644
--- a/src/mongo/db/query/planner_access.cpp
+++ b/src/mongo/db/query/planner_access.cpp
@@ -45,21 +45,14 @@
#include "mongo/db/matcher/expression.h"
#include "mongo/db/matcher/expression_array.h"
#include "mongo/db/matcher/expression_geo.h"
-#include "mongo/db/matcher/expression_internal_expr_comparison.h"
-#include "mongo/db/matcher/expression_leaf.h"
#include "mongo/db/matcher/expression_text.h"
-#include "mongo/db/matcher/expression_tree.h"
-#include "mongo/db/namespace_string.h"
-#include "mongo/db/query/index_bounds.h"
#include "mongo/db/query/index_bounds_builder.h"
#include "mongo/db/query/index_tag.h"
#include "mongo/db/query/indexability.h"
-#include "mongo/db/query/parsed_find_command.h"
#include "mongo/db/query/planner_wildcard_helpers.h"
#include "mongo/db/query/query_knobs_gen.h"
#include "mongo/db/query/query_planner.h"
#include "mongo/db/query/query_planner_common.h"
-#include "mongo/db/query/record_id_range.h"
#include "mongo/db/record_id_helpers.h"
#include "mongo/logv2/log.h"
#include "mongo/util/transitional_tools_do_not_use/vector_spooling.h"
@@ -235,37 +228,27 @@ bool affectedByCollator(const BSONElement& element) {
}
}
-// Set 'curr' to 'newMin' if 'newMin' < 'curr'
-void setLowestRecord(boost::optional<RecordIdBound>& curr, const RecordIdBound& newMin) {
- if (!curr || newMin.recordId() < curr->recordId()) {
- curr = newMin;
+void setMinRecord(CollectionScanNode* collScan, const BSONObj& min) {
+ const auto newMinRecord = record_id_helpers::keyForObj(min);
+ if (!collScan->minRecord || newMinRecord > collScan->minRecord->recordId()) {
+ collScan->minRecord = RecordIdBound(newMinRecord, min);
}
}
-// Set 'curr' to 'newMax' if 'newMax' > 'curr'
-void setHighestRecord(boost::optional<RecordIdBound>& curr, const RecordIdBound& newMax) {
- if (!curr || newMax.recordId() > curr->recordId()) {
- curr = newMax;
+void setMaxRecord(CollectionScanNode* collScan, const BSONObj& max) {
+ const auto newMaxRecord = record_id_helpers::keyForObj(max);
+ if (!collScan->maxRecord || newMaxRecord < collScan->maxRecord->recordId()) {
+ collScan->maxRecord = RecordIdBound(newMaxRecord, max);
}
}
-// Set 'curr' to 'newMin' if 'newMin' < 'curr'
-void setLowestRecord(boost::optional<RecordIdBound>& curr, const BSONObj& newMin) {
- setLowestRecord(curr, RecordIdBound(record_id_helpers::keyForObj(newMin), newMin));
-}
-
-// Set 'curr' to 'newMax' if 'newMax' > 'curr'
-void setHighestRecord(boost::optional<RecordIdBound>& curr, const BSONObj& newMax) {
- setHighestRecord(curr, RecordIdBound(record_id_helpers::keyForObj(newMax), newMax));
-}
-
// Returns whether element is not affected by collators or query and collection collators are
// compatible.
bool compatibleCollator(const QueryPlannerParams& params,
const CollatorInterface* queryCollator,
const BSONElement& element) {
auto const collCollator = params.clusteredCollectionCollator;
- bool compatible = CollatorInterface::collatorsMatch(queryCollator, collCollator);
+ bool compatible = !queryCollator || (collCollator && *queryCollator == *collCollator);
return compatible || !affectedByCollator(element);
}
@@ -276,8 +259,7 @@ bool compatibleCollator(const QueryPlannerParams& params,
void handleRIDRangeMinMax(const CanonicalQuery& query,
CollectionScanNode* collScan,
const QueryPlannerParams& params,
- const CollatorInterface* collator,
- RecordIdRange& recordRange) {
+ const CollatorInterface* collator) {
BSONObj minObj = query.getFindCommandRequest().getMin();
BSONObj maxObj = query.getFindCommandRequest().getMax();
if (minObj.isEmpty() && maxObj.isEmpty()) {
@@ -297,170 +279,88 @@ void handleRIDRangeMinMax(const CanonicalQuery& query,
if (!maxObj.isEmpty() && compatibleCollator(params, collator, maxObj.firstElement())) {
// max() is exclusive.
// Assumes clustered collection scans are only supported with the forward direction.
- recordRange.maybeNarrowMax(
- IndexBoundsBuilder::objFromElement(maxObj.firstElement(), collator),
- false /* NOT inclusive*/);
+ collScan->boundInclusion =
+ CollectionScanParams::ScanBoundInclusion::kIncludeStartRecordOnly;
+ setMaxRecord(collScan, IndexBoundsBuilder::objFromElement(maxObj.firstElement(), collator));
}
if (!minObj.isEmpty() && compatibleCollator(params, collator, minObj.firstElement())) {
// The min() is inclusive as are bounded collection scans by default.
- recordRange.maybeNarrowMin(
- IndexBoundsBuilder::objFromElement(minObj.firstElement(), collator),
- true /* inclusive*/);
+ setMinRecord(collScan, IndexBoundsBuilder::objFromElement(minObj.firstElement(), collator));
}
}
/**
* Helper function to add an RID range to collection scans.
- * If the query solution tree contains a collection scan node with a suitable comparison predicate
- * on '_id', we add a minRecord and maxRecord on the collection node.
- *
- * Returns true if the MatchExpression is a comparison against the cluster key which either:
- * 1) is guaranteed to exclude values of the cluster key which are affected by collation or
- * 2) may return values of the cluster key which are affected by collation, but the query and
- * collection collations match.
- * Otherwise, returns false.
- *
- * For example, assuming the cluster key is "_id":
- * Given {a: {$eq: 2}}, we return false, because the comparison is not against the cluster key.
- * Given {_id: {$gte: 5}}, we return true, because this comparison against the cluster key excludes
- * keys which are affected by collations.
- * Given {_id: {$eq: "str"}}, we return true only if the query and collection collations match.
- *
+ * If the query solution tree contains a collection scan node with a suitable comparison
+ * predicate on '_id', we add a minRecord and maxRecord on the collection node.
*/
-[[nodiscard]] bool handleRIDRangeScan(const MatchExpression* conjunct,
- CollectionScanNode* collScan,
- const QueryPlannerParams& params,
- const CollatorInterface* collator,
- RecordIdRange& recordRange) {
+void handleRIDRangeScan(const MatchExpression* conjunct,
+ CollectionScanNode* collScan,
+ const QueryPlannerParams& params,
+ const CollatorInterface* collator) {
invariant(params.clusteredInfo);
if (conjunct == nullptr) {
- return false;
+ return;
}
auto* andMatchPtr = dynamic_cast<const AndMatchExpression*>(conjunct);
if (andMatchPtr != nullptr) {
- bool atLeastOneConjunctCompatibleCollation = false;
for (size_t index = 0; index < andMatchPtr->numChildren(); index++) {
- if (handleRIDRangeScan(
- andMatchPtr->getChild(index), collScan, params, collator, recordRange)) {
- atLeastOneConjunctCompatibleCollation = true;
- }
+ handleRIDRangeScan(andMatchPtr->getChild(index), collScan, params, collator);
}
-
- // If one of the conjuncts excludes values of the cluster key which are affected by
- // collation, then the entire $and will also exclude those values.
- return atLeastOneConjunctCompatibleCollation;
+ return;
}
if (conjunct->path() !=
clustered_util::getClusterKeyFieldName(params.clusteredInfo->getIndexSpec())) {
// No match on the cluster key.
- return false;
- }
-
- // TODO SERVER-62707: Allow $in with regex to use a clustered index.
- auto inMatch = dynamic_cast<const InMatchExpression*>(conjunct);
- if (inMatch && !inMatch->hasRegex()) {
- // Iterate through the $in equalities to find the min/max values. The min/max bounds for the
- // collscan need to be loose enough to cover all of these values.
- boost::optional<RecordIdBound> minBound;
- boost::optional<RecordIdBound> maxBound;
-
- bool allEltsCollationCompatible = true;
- for (const auto& element : inMatch->getEqualities()) {
- if (compatibleCollator(params, collator, element)) {
- const auto collated = IndexBoundsBuilder::objFromElement(element, collator);
- setLowestRecord(minBound, collated);
- setHighestRecord(maxBound, collated);
- } else {
- // Set coarse min/max bounds based on type when we can't set tight bounds.
- allEltsCollationCompatible = false;
-
- BSONObjBuilder bMin;
- bMin.appendMinForType("", element.type());
- setLowestRecord(minBound, bMin.obj());
-
- BSONObjBuilder bMax;
- bMax.appendMaxForType("", element.type());
- setHighestRecord(maxBound, bMax.obj());
- }
- }
-
- // {min,max}RecordId will bound the range of ids scanned to the highest and lowest present
- // in the InMatchExpression, but the filter is still required to filter to _exactly_ the
- // requested matches.
-
- // Finally, tighten the collscan bounds with the min/max bounds for the $in.
- recordRange.intersectRange(minBound, maxBound);
- return allEltsCollationCompatible;
+ return;
}
- auto match = dynamic_cast<const ComparisonMatchExpressionBase*>(conjunct);
+ auto match = dynamic_cast<const ComparisonMatchExpression*>(conjunct);
if (match == nullptr) {
- return false; // Not a comparison match expression.
+ return; // Not a comparison match expression.
}
const auto& element = match->getData();
- if (!ComparisonMatchExpressionBase::isInternalExprComparison(match->matchType())) {
- // Internal comparisons e.g., $_internalExprGt do _not_ carry type bracketing
- // semantics (consistent with `$expr{$gt:[a,b]}`).
- // For other comparisons which _do_ perform type bracketing, the RecordId bounds
- // may be tightened here.
- BSONObjBuilder minb;
- minb.appendMinForType("", element.type());
- recordRange.maybeNarrowMin(minb.obj(), true /* inclusive */);
+ // Set coarse min/max bounds based on type in case we can't set tight bounds.
+ BSONObjBuilder minb;
+ minb.appendMinForType("", element.type());
+ setMinRecord(collScan, minb.obj());
- BSONObjBuilder maxb;
- maxb.appendMaxForType("", element.type());
- recordRange.maybeNarrowMax(maxb.obj(), true /* inclusive */);
- }
+ BSONObjBuilder maxb;
+ maxb.appendMaxForType("", element.type());
+ setMaxRecord(collScan, maxb.obj());
bool compatible = compatibleCollator(params, collator, element);
if (!compatible) {
- return false; // Collator affects probe and it's not compatible with collection's collator.
+ return; // Collator affects probe and it's not compatible with collection's collator.
}
// Even if the collations don't match at this point, it's fine,
- // because the bounds exclude values that use it.
- const BSONObj collated = IndexBoundsBuilder::objFromElement(element, collator);
- using MType = MatchExpression::MatchType;
- switch (match->matchType()) {
- case MType::EQ:
- case MType::INTERNAL_EXPR_EQ:
- recordRange.maybeNarrowMin(collated, true /* inclusive */);
- recordRange.maybeNarrowMax(collated, true /* inclusive */);
- break;
- case MType::LT:
- case MType::INTERNAL_EXPR_LT:
- recordRange.maybeNarrowMax(collated, false /* EXclusive */);
- break;
- case MType::LTE:
- case MType::INTERNAL_EXPR_LTE:
- recordRange.maybeNarrowMax(collated, true /* inclusive */);
- break;
- case MType::GT:
- case MType::INTERNAL_EXPR_GT:
- recordRange.maybeNarrowMin(collated, false /* EXclusive */);
- break;
- case MType::GTE:
- case MType::INTERNAL_EXPR_GTE:
- recordRange.maybeNarrowMin(collated, true /* inclusive */);
- break;
- default:;
+ // because the bounds exclude values that use it
+ collScan->hasCompatibleCollation = true;
+
+ const auto collated = IndexBoundsBuilder::objFromElement(element, collator);
+ if (dynamic_cast<const EqualityMatchExpression*>(match)) {
+ setMinRecord(collScan, collated);
+ setMaxRecord(collScan, collated);
+ } else if (dynamic_cast<const LTMatchExpression*>(match) ||
+ dynamic_cast<const LTEMatchExpression*>(match)) {
+ setMaxRecord(collScan, collated);
+ } else if (dynamic_cast<const GTMatchExpression*>(match) ||
+ dynamic_cast<const GTEMatchExpression*>(match)) {
+ setMinRecord(collScan, collated);
}
- return true;
}
} // namespace
std::unique_ptr<QuerySolutionNode> QueryPlannerAccess::makeCollectionScan(
const CanonicalQuery& query, bool tailable, const QueryPlannerParams& params, int direction) {
- // The following are expensive to look up, so only do it once for each.
- const mongo::NamespaceString nss = query.nss();
- const bool isOplog = nss.isOplog();
// Make the (only) node, a collection scan.
auto csn = std::make_unique<CollectionScanNode>();
csn->name = query.ns();
@@ -471,7 +371,6 @@ std::unique_ptr<QuerySolutionNode> QueryPlannerAccess::makeCollectionScan(
csn->shouldWaitForOplogVisibility =
params.options & QueryPlannerParams::OPLOG_SCAN_WAIT_FOR_VISIBLE;
csn->direction = direction;
- csn->isOplog = isOplog;
if (params.clusteredInfo) {
csn->clusteredIndex = params.clusteredInfo->getIndexSpec();
@@ -548,29 +447,14 @@ std::unique_ptr<QuerySolutionNode> QueryPlannerAccess::makeCollectionScan(
auto queryCollator = query.getCollator();
auto collCollator = params.clusteredCollectionCollator;
- csn->hasCompatibleCollation = CollatorInterface::collatorsMatch(queryCollator, collCollator);
+ csn->hasCompatibleCollation =
+ !queryCollator || (collCollator && *queryCollator == *collCollator);
if (params.clusteredInfo && !csn->resumeAfterRecordId) {
// This is a clustered collection. Attempt to perform an efficient, bounded collection scan
- // via minRecord and maxRecord if applicable. During this process, we will check if the
- // query is guaranteed to exclude values of the cluster key which are affected by collation.
- // If so, then even if the query and collection collations differ, the collation difference
- // won't affect the query results. In that case, we can say hasCompatibleCollation is true.
-
- RecordIdRange recordRange;
- // min/max records may have been set if oplog or change collection.
- recordRange.intersectRange(csn->minRecord, csn->maxRecord);
- bool compatibleCollation =
- handleRIDRangeScan(csn->filter.get(), csn.get(), params, queryCollator, recordRange);
- csn->hasCompatibleCollation |= compatibleCollation;
-
- handleRIDRangeMinMax(query, csn.get(), params, queryCollator, recordRange);
-
- csn->minRecord = recordRange.getMin();
- csn->maxRecord = recordRange.getMax();
-
- csn->boundInclusion = CollectionScanParams::makeInclusion(recordRange.isMinInclusive(),
- recordRange.isMaxInclusive());
+ // via minRecord and maxRecord if applicable.
+ handleRIDRangeScan(csn->filter.get(), csn.get(), params, queryCollator);
+ handleRIDRangeMinMax(query, csn.get(), params, queryCollator);
}
return csn;
@@ -1230,13 +1114,47 @@ std::vector<std::unique_ptr<QuerySolutionNode>> QueryPlannerAccess::collapseEqui
}
/**
- * This helper determines if a query can be covered depending on the query projection.
+ * Returns true if this is a null query that can retrieve all the information it needs directly from
+ * the index, and so does not need a FETCH stage on top of it. Returns false otherwise.
*/
-bool projNeedsFetch(const CanonicalQuery& query, const QueryPlannerParams& params) {
+bool isCoveredNullQuery(const CanonicalQuery& query,
+ MatchExpression* root,
+ IndexTag* tag,
+ const vector<IndexEntry>& indices,
+ const QueryPlannerParams& params) {
+ // Sparse indexes and hashed indexes should not use this optimization as they will require a
+ // FETCH stage with a filter.
+ if (indices[tag->index].sparse || indices[tag->index].type == IndexType::INDEX_HASHED) {
+ return false;
+ }
+
+ // When the index is not multikey, we can support a query on an indexed field searching for null
+ // values. This optimization can only be done when the index is not multikey, otherwise empty
+ // arrays in the collection will be treated as null/undefined by the index. When the index is
+ // multikey, we can support a query searching for both null and empty array values.
+ const auto multikeyIndex = indices[tag->index].multikey;
+ if (root->matchType() == MatchExpression::MatchType::MATCH_IN) {
+ // Check that the query matches null values, if the index is not multikey, or null and empty
+ // array values, if the index is multikey. Note that the query may match values other than
+ // null (and empty array).
+ const auto node = static_cast<const InMatchExpression*>(root);
+ if (!node->hasNull() || (multikeyIndex && !node->hasEmptyArray())) {
+ return false;
+ }
+ } else if (ComparisonMatchExpressionBase::isEquality(root->matchType()) && !multikeyIndex) {
+ // Check that the query matches null values.
+ const auto node = static_cast<const ComparisonMatchExpressionBase*>(root);
+ if (node->getData().type() != BSONType::jstNULL) {
+ return false;
+ }
+ } else {
+ return false;
+ }
+
// If nothing is being projected, the query is fully covered without a fetch.
// This is trivially true for a count query.
if (params.options & QueryPlannerParams::Options::IS_COUNT) {
- return false;
+ return true;
}
// This optimization can only be used for find when the index covers the projection completely.
@@ -1245,7 +1163,7 @@ bool projNeedsFetch(const CanonicalQuery& query, const QueryPlannerParams& param
// in the multikey case). Hence, only find queries projecting _id are covered.
auto proj = query.getProj();
if (!proj) {
- return true;
+ return false;
}
// We can cover projections on _id and generated fields and expressions depending only on _id.
@@ -1257,38 +1175,10 @@ bool projNeedsFetch(const CanonicalQuery& query, const QueryPlannerParams& param
// Note that it is not possible to project onto dotted paths of _id here, since they may be
// null or missing, and the index cannot differentiate between the two cases, so we would
// still need a FETCH stage.
- if (projFields.size() == 1 && *projFields.begin() == "_id") {
- return false;
- }
+ return projFields.size() == 1 && *projFields.begin() == "_id";
}
- return true;
-}
-
-/**
- * This helper updates a MAYBE_COVERED query tightness to one of EXACT, INEXACT_COVERED, or
- * INEXACT_FETCH, depending on whether we need a FETCH/filter to answer the query projection.
- */
-void refineTightnessForMaybeCoveredQuery(const CanonicalQuery& query,
- const QueryPlannerParams& params,
- IndexBoundsBuilder::BoundsTightness& tightnessOut) {
- // We need to refine the tightness in case we have a "MAYBE_COVERED" tightness bound which
- // depends on the query's projection. We will not have information about the projection
- // later on in order to make this determination, so we do it here.
- const bool noFetchNeededForProj = !projNeedsFetch(query, params);
- if (tightnessOut == IndexBoundsBuilder::EXACT_MAYBE_COVERED) {
- if (noFetchNeededForProj) {
- tightnessOut = IndexBoundsBuilder::EXACT;
- } else {
- tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
- }
- } else if (tightnessOut == IndexBoundsBuilder::INEXACT_MAYBE_COVERED) {
- if (noFetchNeededForProj) {
- tightnessOut = IndexBoundsBuilder::INEXACT_COVERED;
- } else {
- tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
- }
- }
+ return false;
}
bool QueryPlannerAccess::processIndexScans(const CanonicalQuery& query,
@@ -1332,6 +1222,11 @@ bool QueryPlannerAccess::processIndexScans(const CanonicalQuery& query,
// If we're here, we now know that 'child' can use an index directly and the index is
// over the child's field.
+ // We need to track if this is a covered null query so that we can have this information
+ // at hand when handling the filter on an indexed AND.
+ scanState.isCoveredNullQuery =
+ isCoveredNullQuery(query, child, scanState.ixtag, indices, params);
+
// If 'child' is a NOT, then the tag we're interested in is on the NOT's
// child node.
if (MatchExpression::NOT == child->matchType()) {
@@ -1364,7 +1259,6 @@ bool QueryPlannerAccess::processIndexScans(const CanonicalQuery& query,
verify(scanState.currentIndexNumber == scanState.ixtag->index);
scanState.tightness = IndexBoundsBuilder::INEXACT_FETCH;
mergeWithLeafNode(child, &scanState);
- refineTightnessForMaybeCoveredQuery(query, params, scanState.tightness);
handleFilter(&scanState);
} else {
if (nullptr != scanState.currentScan.get()) {
@@ -1384,7 +1278,6 @@ bool QueryPlannerAccess::processIndexScans(const CanonicalQuery& query,
&scanState.tightness,
scanState.getCurrentIETBuilder());
- refineTightnessForMaybeCoveredQuery(query, params, scanState.tightness);
handleFilter(&scanState);
}
}
@@ -1800,12 +1693,6 @@ std::unique_ptr<QuerySolutionNode> QueryPlannerAccess::_buildIndexedDataAccess(
return soln;
}
- // We may be able to avoid adding an extra fetch stage even though the bounds are
- // inexact, for instance if the query is counting null values on an indexed field
- // without projecting that field. We therefore convert "MAYBE_COVERED" bounds into
- // either EXACT or INEXACT, depending on the query projection.
- refineTightnessForMaybeCoveredQuery(query, params, tightness);
-
// If the bounds are exact, the set of documents that satisfy the predicate is
// exactly equal to the set of documents that the scan provides.
//
@@ -1813,7 +1700,11 @@ std::unique_ptr<QuerySolutionNode> QueryPlannerAccess::_buildIndexedDataAccess(
// superset of documents that satisfy the predicate, and we must check the
// predicate.
- if (tightness == IndexBoundsBuilder::EXACT) {
+ // We may also be able to avoid adding an extra fetch stage even though the bounds are
+ // inexact because the query is counting null values on an indexed field without
+ // projecting that field.
+ if (tightness == IndexBoundsBuilder::EXACT ||
+ isCoveredNullQuery(query, root, tag, indices, params)) {
return soln;
} else if (tightness == IndexBoundsBuilder::INEXACT_COVERED &&
!indices[tag->index].multikey) {
@@ -1959,9 +1850,10 @@ void QueryPlannerAccess::handleFilterAnd(ScanBuildingState* scanState) {
// should always be affixed as a filter. We keep 'curChild' in the $and
// for affixing later.
++scanState->curChild;
- } else if (scanState->tightness == IndexBoundsBuilder::EXACT) {
- // The tightness of the bounds is exact. We want to remove this child so that when control
- // returns to handleIndexedAnd we know that we don't need it to create a FETCH stage.
+ } else if (scanState->tightness == IndexBoundsBuilder::EXACT || scanState->isCoveredNullQuery) {
+ // The tightness of the bounds is exact or we are dealing with a covered null query.
+ // Either way, we want to remove this child so that when control returns to handleIndexedAnd
+ // we know that we don't need it to create a FETCH stage.
root->getChildVector()->erase(root->getChildVector()->begin() + scanState->curChild);
} else if (scanState->tightness == IndexBoundsBuilder::INEXACT_COVERED &&
(INDEX_TEXT == index.type || !index.multikey)) {
generated by cgit v1.2.3 (git 2.39.1) at 2026-09-11 10:59:38 +0000