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.cpp244
1 files changed, 155 insertions, 89 deletions
diff --git a/src/mongo/db/query/planner_access.cpp b/src/mongo/db/query/planner_access.cpp
index e05dfd8a5d1..ef0956dc56f 100644
--- a/src/mongo/db/query/planner_access.cpp
+++ b/src/mongo/db/query/planner_access.cpp
@@ -228,27 +228,37 @@ bool affectedByCollator(const BSONElement& element) {
}
}
-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 'newMin' if 'newMin' < 'curr'
+void setLowestRecord(boost::optional<RecordIdBound>& curr, const RecordIdBound& newMin) {
+ if (!curr || newMin.recordId() < curr->recordId()) {
+ curr = newMin;
}
}
-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 'newMax' if 'newMax' > 'curr'
+void setHighestRecord(boost::optional<RecordIdBound>& curr, const RecordIdBound& newMax) {
+ if (!curr || newMax.recordId() > curr->recordId()) {
+ curr = newMax;
}
}
+// 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 = !queryCollator || (collCollator && *queryCollator == *collCollator);
+ bool compatible = CollatorInterface::collatorsMatch(queryCollator, collCollator);
return compatible || !affectedByCollator(element);
}
@@ -281,47 +291,106 @@ void handleRIDRangeMinMax(const CanonicalQuery& query,
// Assumes clustered collection scans are only supported with the forward direction.
collScan->boundInclusion =
CollectionScanParams::ScanBoundInclusion::kIncludeStartRecordOnly;
- setMaxRecord(collScan, IndexBoundsBuilder::objFromElement(maxObj.firstElement(), collator));
+ setLowestRecord(collScan->maxRecord,
+ IndexBoundsBuilder::objFromElement(maxObj.firstElement(), collator));
}
if (!minObj.isEmpty() && compatibleCollator(params, collator, minObj.firstElement())) {
// The min() is inclusive as are bounded collection scans by default.
- setMinRecord(collScan, IndexBoundsBuilder::objFromElement(minObj.firstElement(), collator));
+ setHighestRecord(collScan->minRecord,
+ 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.
+ * 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.
+ *
*/
-void handleRIDRangeScan(const MatchExpression* conjunct,
- CollectionScanNode* collScan,
- const QueryPlannerParams& params,
- const CollatorInterface* collator) {
+[[nodiscard]] bool handleRIDRangeScan(const MatchExpression* conjunct,
+ CollectionScanNode* collScan,
+ const QueryPlannerParams& params,
+ const CollatorInterface* collator) {
invariant(params.clusteredInfo);
if (conjunct == nullptr) {
- return;
+ return false;
}
auto* andMatchPtr = dynamic_cast<const AndMatchExpression*>(conjunct);
if (andMatchPtr != nullptr) {
+ bool atLeastOneConjunctCompatibleCollation = false;
for (size_t index = 0; index < andMatchPtr->numChildren(); index++) {
- handleRIDRangeScan(andMatchPtr->getChild(index), collScan, params, collator);
+ if (handleRIDRangeScan(andMatchPtr->getChild(index), collScan, params, collator)) {
+ atLeastOneConjunctCompatibleCollation = true;
+ }
}
- return;
+
+ // 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;
}
if (conjunct->path() !=
clustered_util::getClusterKeyFieldName(params.clusteredInfo->getIndexSpec())) {
// No match on the cluster key.
- return;
+ 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());
+ }
+ }
+
+ // Finally, tighten the collscan bounds with the min/max bounds for the $in.
+ if (minBound) {
+ setHighestRecord(collScan->minRecord, *minBound);
+ }
+ if (maxBound) {
+ setLowestRecord(collScan->maxRecord, *maxBound);
+ }
+ return allEltsCollationCompatible;
}
auto match = dynamic_cast<const ComparisonMatchExpression*>(conjunct);
if (match == nullptr) {
- return; // Not a comparison match expression.
+ return false; // Not a comparison match expression.
}
const auto& element = match->getData();
@@ -329,32 +398,32 @@ void handleRIDRangeScan(const MatchExpression* conjunct,
// 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());
+ setHighestRecord(collScan->minRecord, minb.obj());
BSONObjBuilder maxb;
maxb.appendMaxForType("", element.type());
- setMaxRecord(collScan, maxb.obj());
+ setLowestRecord(collScan->maxRecord, maxb.obj());
bool compatible = compatibleCollator(params, collator, element);
if (!compatible) {
- return; // Collator affects probe and it's not compatible with collection's collator.
+ return false; // 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
- collScan->hasCompatibleCollation = true;
-
const auto collated = IndexBoundsBuilder::objFromElement(element, collator);
if (dynamic_cast<const EqualityMatchExpression*>(match)) {
- setMinRecord(collScan, collated);
- setMaxRecord(collScan, collated);
+ setHighestRecord(collScan->minRecord, collated);
+ setLowestRecord(collScan->maxRecord, collated);
} else if (dynamic_cast<const LTMatchExpression*>(match) ||
dynamic_cast<const LTEMatchExpression*>(match)) {
- setMaxRecord(collScan, collated);
+ setLowestRecord(collScan->maxRecord, collated);
} else if (dynamic_cast<const GTMatchExpression*>(match) ||
dynamic_cast<const GTEMatchExpression*>(match)) {
- setMinRecord(collScan, collated);
+ setHighestRecord(collScan->minRecord, collated);
}
+
+ return true;
}
} // namespace
@@ -447,13 +516,18 @@ std::unique_ptr<QuerySolutionNode> QueryPlannerAccess::makeCollectionScan(
auto queryCollator = query.getCollator();
auto collCollator = params.clusteredCollectionCollator;
- csn->hasCompatibleCollation =
- !queryCollator || (collCollator && *queryCollator == *collCollator);
+ csn->hasCompatibleCollation = CollatorInterface::collatorsMatch(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.
- handleRIDRangeScan(csn->filter.get(), csn.get(), params, queryCollator);
+ // 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.
+ bool compatibleCollation =
+ handleRIDRangeScan(csn->filter.get(), csn.get(), params, queryCollator);
+ csn->hasCompatibleCollation |= compatibleCollation;
+
handleRIDRangeMinMax(query, csn.get(), params, queryCollator);
}
@@ -1114,47 +1188,13 @@ std::vector<std::unique_ptr<QuerySolutionNode>> QueryPlannerAccess::collapseEqui
}
/**
- * 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.
+ * This helper determines if a query can be covered depending on the query projection.
*/
-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;
- }
-
+bool projNeedsFetch(const CanonicalQuery& query, const QueryPlannerParams& params) {
// 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 true;
+ return false;
}
// This optimization can only be used for find when the index covers the projection completely.
@@ -1163,7 +1203,7 @@ bool isCoveredNullQuery(const CanonicalQuery& query,
// in the multikey case). Hence, only find queries projecting _id are covered.
auto proj = query.getProj();
if (!proj) {
- return false;
+ return true;
}
// We can cover projections on _id and generated fields and expressions depending only on _id.
@@ -1175,10 +1215,38 @@ bool isCoveredNullQuery(const CanonicalQuery& query,
// 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.
- return projFields.size() == 1 && *projFields.begin() == "_id";
+ if (projFields.size() == 1 && *projFields.begin() == "_id") {
+ return false;
+ }
}
- return false;
+ 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;
+ }
+ }
}
bool QueryPlannerAccess::processIndexScans(const CanonicalQuery& query,
@@ -1222,11 +1290,6 @@ 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()) {
@@ -1259,6 +1322,7 @@ 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()) {
@@ -1278,6 +1342,7 @@ bool QueryPlannerAccess::processIndexScans(const CanonicalQuery& query,
&scanState.tightness,
scanState.getCurrentIETBuilder());
+ refineTightnessForMaybeCoveredQuery(query, params, scanState.tightness);
handleFilter(&scanState);
}
}
@@ -1693,6 +1758,12 @@ 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.
//
@@ -1700,11 +1771,7 @@ std::unique_ptr<QuerySolutionNode> QueryPlannerAccess::_buildIndexedDataAccess(
// superset of documents that satisfy the predicate, and we must check the
// predicate.
- // 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)) {
+ if (tightness == IndexBoundsBuilder::EXACT) {
return soln;
} else if (tightness == IndexBoundsBuilder::INEXACT_COVERED &&
!indices[tag->index].multikey) {
@@ -1850,10 +1917,9 @@ 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 || 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.
+ } 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.
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 13:07:00 +0000