diff options
Diffstat (limited to 'src/mongo/db/matcher/expression_tree.cpp')
| -rw-r--r-- | src/mongo/db/matcher/expression_tree.cpp | 195 |
1 files changed, 44 insertions, 151 deletions
diff --git a/src/mongo/db/matcher/expression_tree.cpp b/src/mongo/db/matcher/expression_tree.cpp index 74765949ca5..df70ad278c3 100644 --- a/src/mongo/db/matcher/expression_tree.cpp +++ b/src/mongo/db/matcher/expression_tree.cpp @@ -40,106 +40,16 @@ #include "mongo/db/matcher/expression_text_base.h" namespace mongo { -namespace { - -PathMatchExpression* getEligiblePathMatchForNotSerialization(MatchExpression* expr) { - // Returns a pointer to a PathMatchExpression if 'expr' is such a pointer, otherwise returns - // nullptr. - // - // One exception: while TextMatchExpressionBase derives from PathMatchExpression, text match - // expressions cannot be serialized in the same manner as other PathMatchExpression derivatives. - // This is because the path for a TextMatchExpression is embedded within the $text object, - // whereas for other PathMatchExpressions it is on the left-hand-side, for example {x: {$eq: - // 1}}. - // - // Rather than the following dynamic_cast, we'll do a more performant, but also more verbose - // check. - // dynamic_cast<PathMatchExpression*>(expr) && !dynamic_cast<TextMatchExpressionBase*>(expr) - // - // This version below is less obviously exhaustive, but because this is just a legibility - // optimization, and this function also gets called on the query shape stats recording hot path, - // we think it is worth it. - switch (expr->matchType()) { - // leaf types - case MatchExpression::EQ: - case MatchExpression::LTE: - case MatchExpression::LT: - case MatchExpression::GT: - case MatchExpression::GTE: - case MatchExpression::REGEX: - case MatchExpression::MOD: - case MatchExpression::EXISTS: - case MatchExpression::MATCH_IN: - case MatchExpression::BITS_ALL_SET: - case MatchExpression::BITS_ALL_CLEAR: - case MatchExpression::BITS_ANY_SET: - case MatchExpression::BITS_ANY_CLEAR: - // array types - case MatchExpression::ELEM_MATCH_OBJECT: - case MatchExpression::ELEM_MATCH_VALUE: - case MatchExpression::SIZE: - // special types - case MatchExpression::TYPE_OPERATOR: - case MatchExpression::GEO: - case MatchExpression::GEO_NEAR: - // Internal subclasses of PathMatchExpression: - case MatchExpression::INTERNAL_SCHEMA_ALL_ELEM_MATCH_FROM_INDEX: - case MatchExpression::INTERNAL_SCHEMA_BIN_DATA_ENCRYPTED_TYPE: - case MatchExpression::INTERNAL_SCHEMA_BIN_DATA_FLE2_ENCRYPTED_TYPE: - case MatchExpression::INTERNAL_SCHEMA_BIN_DATA_SUBTYPE: - case MatchExpression::INTERNAL_SCHEMA_MATCH_ARRAY_INDEX: - case MatchExpression::INTERNAL_SCHEMA_MAX_ITEMS: - case MatchExpression::INTERNAL_SCHEMA_MAX_LENGTH: - case MatchExpression::INTERNAL_SCHEMA_MAX_PROPERTIES: - case MatchExpression::INTERNAL_SCHEMA_MIN_ITEMS: - case MatchExpression::INTERNAL_SCHEMA_MIN_LENGTH: - case MatchExpression::INTERNAL_SCHEMA_TYPE: - case MatchExpression::INTERNAL_SCHEMA_UNIQUE_ITEMS: - return static_cast<PathMatchExpression*>(expr); - // purposefully skip TEXT: - case MatchExpression::TEXT: - // Any other type is not considered a PathMatchExpression. - case MatchExpression::AND: - case MatchExpression::OR: - case MatchExpression::NOT: - case MatchExpression::NOR: - case MatchExpression::WHERE: - case MatchExpression::EXPRESSION: - case MatchExpression::ALWAYS_FALSE: - case MatchExpression::ALWAYS_TRUE: - case MatchExpression::INTERNAL_2D_POINT_IN_ANNULUS: - case MatchExpression::INTERNAL_BUCKET_GEO_WITHIN: - case MatchExpression::INTERNAL_EXPR_EQ: - case MatchExpression::INTERNAL_EXPR_GT: - case MatchExpression::INTERNAL_EXPR_GTE: - case MatchExpression::INTERNAL_EXPR_LT: - case MatchExpression::INTERNAL_EXPR_LTE: - case MatchExpression::INTERNAL_SCHEMA_ALLOWED_PROPERTIES: - case MatchExpression::INTERNAL_SCHEMA_COND: - case MatchExpression::INTERNAL_SCHEMA_EQ: - case MatchExpression::INTERNAL_SCHEMA_FMOD: - case MatchExpression::INTERNAL_SCHEMA_MIN_PROPERTIES: - case MatchExpression::INTERNAL_SCHEMA_OBJECT_MATCH: - case MatchExpression::INTERNAL_SCHEMA_ROOT_DOC_EQ: - case MatchExpression::INTERNAL_SCHEMA_XOR: - return nullptr; - default: - MONGO_UNREACHABLE_TASSERT(7800300); - } -}; -} // namespace void ListOfMatchExpression::_debugList(StringBuilder& debug, int indentationLevel) const { for (unsigned i = 0; i < _expressions.size(); i++) _expressions[i]->debugString(debug, indentationLevel + 1); } -void ListOfMatchExpression::_listToBSON(BSONArrayBuilder* out, - const SerializationOptions& opts, - bool includePath) const { +void ListOfMatchExpression::_listToBSON(BSONArrayBuilder* out, bool includePath) const { for (unsigned i = 0; i < _expressions.size(); i++) { BSONObjBuilder childBob(out->subobjStart()); - _expressions[i]->serialize(&childBob, opts, includePath); + _expressions[i]->serialize(&childBob, includePath); } out->doneFast(); } @@ -187,13 +97,12 @@ MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() c std::back_inserter(children)); } - // Remove all children of AND that are $alwaysTrue and all children of OR and NOR that are + // Remove all children of AND that are $alwaysTrue and all children of OR that are // $alwaysFalse. - if (matchType == AND || matchType == OR || matchType == NOR) { + if (matchType == AND || matchType == OR) { for (auto& childExpression : children) if ((childExpression->isTriviallyTrue() && matchType == MatchExpression::AND) || - (childExpression->isTriviallyFalse() && matchType == MatchExpression::OR) || - (childExpression->isTriviallyFalse() && matchType == MatchExpression::NOR)) + (childExpression->isTriviallyFalse() && matchType == MatchExpression::OR)) childExpression = nullptr; // We replaced each destroyed child expression with nullptr. Now we remove those @@ -203,17 +112,13 @@ MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() c // Check if the above optimizations eliminated all children. An OR with no children is // always false. + // TODO SERVER-34759 It is correct to replace this empty AND with an $alwaysTrue, but we + // need to make enhancements to the planner to make it understand an $alwaysTrue and an + // empty AND as the same thing. The planner can create inferior plans for $alwaysTrue which + // it would not produce for an AND with no children. if (children.empty() && matchType == MatchExpression::OR) { return std::make_unique<AlwaysFalseMatchExpression>(); } - // An AND with no children is always true and we need to return an - // EmptyExpression. This ensures that the empty $and[] will be returned that serializes to - // {} (SERVER-34759). A NOR with no children is always true. We treat an empty $nor[] - // similarly. - if (children.empty() && - (matchType == MatchExpression::AND || matchType == MatchExpression::NOR)) { - return std::make_unique<AndMatchExpression>(); - } if (children.size() == 1) { if ((matchType == AND || matchType == OR || matchType == INTERNAL_SCHEMA_XOR)) { @@ -231,8 +136,7 @@ MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() c } } - if (matchType == MatchExpression::AND || matchType == MatchExpression::OR || - matchType == MatchExpression::NOR) { + if (matchType == MatchExpression::AND || matchType == MatchExpression::OR) { for (auto& childExpression : children) { // An AND containing an expression that always evaluates to false can be // optimized to a single $alwaysFalse expression. @@ -245,11 +149,6 @@ MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() c if (childExpression->isTriviallyTrue() && matchType == MatchExpression::OR) { return std::make_unique<AlwaysTrueMatchExpression>(); } - // A NOR containing an expression that always evaluates to true can be - // optimized to a single $alwaysFalse expression. - if (childExpression->isTriviallyTrue() && matchType == MatchExpression::NOR) { - return std::make_unique<AlwaysFalseMatchExpression>(); - } } } @@ -318,19 +217,19 @@ MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() c if (countEquivEqPaths > 1) { tassert(3401202, "There must be a common path", childPath); auto inExpression = std::make_unique<InMatchExpression>(StringData(*childPath)); - std::vector<std::unique_ptr<MatchExpression>> nonEquivOrChildren; - nonEquivOrChildren.reserve(countNonEquivExpr); + auto nonEquivOrExpr = + (countNonEquivExpr > 0) ? std::make_unique<OrMatchExpression>() : nullptr; BSONArrayBuilder bab; for (auto& childExpression : children) { if (*childPath != childExpression->path()) { - nonEquivOrChildren.push_back(std::move(childExpression)); + nonEquivOrExpr->add(std::move(childExpression)); } else if (childExpression->matchType() == MatchExpression::EQ) { std::unique_ptr<EqualityMatchExpression> eqExpressionPtr{ static_cast<EqualityMatchExpression*>(childExpression.release())}; if (isRegEx(eqExpressionPtr->getData()) || eqExpressionPtr->getCollator() != eqCollator) { - nonEquivOrChildren.push_back(std::move(eqExpressionPtr)); + nonEquivOrExpr->add(std::move(eqExpressionPtr)); } else { bab.append(eqExpressionPtr->getData()); } @@ -345,13 +244,13 @@ MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() c "Conversion from OR to IN should always succeed", status == Status::OK()); } else { - nonEquivOrChildren.push_back(std::move(childExpression)); + nonEquivOrExpr->add(std::move(childExpression)); } } children.clear(); tassert(3401204, "Incorrect number of non-equivalent expressions", - nonEquivOrChildren.size() == countNonEquivExpr); + !nonEquivOrExpr || nonEquivOrExpr->numChildren() == countNonEquivExpr); auto backingArr = bab.arr(); std::vector<BSONElement> inEqualities; @@ -375,13 +274,11 @@ MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() c if (countNonEquivExpr > 0) { auto parentOrExpr = std::make_unique<OrMatchExpression>(); parentOrExpr->add(std::move(inExpression)); - - // Move all of the non-equivalent children of the original $or so that they - // become children of the newly constructed $or node. - auto&& childVec = *parentOrExpr->getChildVector(); - std::move(std::make_move_iterator(nonEquivOrChildren.begin()), - std::make_move_iterator(nonEquivOrChildren.end()), - std::back_inserter(childVec)); + if (countNonEquivExpr == 1) { + parentOrExpr->add(nonEquivOrExpr->releaseChild(0)); + } else { + parentOrExpr->add(std::move(nonEquivOrExpr)); + } return parentOrExpr; } return inExpression; @@ -444,9 +341,7 @@ void AndMatchExpression::debugString(StringBuilder& debug, int indentationLevel) _debugList(debug, indentationLevel); } -void AndMatchExpression::serialize(BSONObjBuilder* out, - const SerializationOptions& opts, - bool includePath) const { +void AndMatchExpression::serialize(BSONObjBuilder* out, bool includePath) const { if (!numChildren()) { // It is possible for an AndMatchExpression to have no children, resulting in the serialized // expression {$and: []}, which is not a valid query object. @@ -454,7 +349,7 @@ void AndMatchExpression::serialize(BSONObjBuilder* out, } BSONArrayBuilder arrBob(out->subarrayStart("$and")); - _listToBSON(&arrBob, opts, includePath); + _listToBSON(&arrBob, includePath); arrBob.doneFast(); } @@ -490,9 +385,7 @@ void OrMatchExpression::debugString(StringBuilder& debug, int indentationLevel) _debugList(debug, indentationLevel); } -void OrMatchExpression::serialize(BSONObjBuilder* out, - const SerializationOptions& opts, - bool includePath) const { +void OrMatchExpression::serialize(BSONObjBuilder* out, bool includePath) const { if (!numChildren()) { // It is possible for an OrMatchExpression to have no children, resulting in the serialized // expression {$or: []}, which is not a valid query object. An empty $or is logically @@ -501,7 +394,7 @@ void OrMatchExpression::serialize(BSONObjBuilder* out, return; } BSONArrayBuilder arrBob(out->subarrayStart("$or")); - _listToBSON(&arrBob, opts, includePath); + _listToBSON(&arrBob, includePath); } bool OrMatchExpression::isTriviallyFalse() const { @@ -534,11 +427,9 @@ void NorMatchExpression::debugString(StringBuilder& debug, int indentationLevel) _debugList(debug, indentationLevel); } -void NorMatchExpression::serialize(BSONObjBuilder* out, - const SerializationOptions& opts, - bool includePath) const { +void NorMatchExpression::serialize(BSONObjBuilder* out, bool includePath) const { BSONArrayBuilder arrBob(out->subarrayStart("$nor")); - _listToBSON(&arrBob, opts, includePath); + _listToBSON(&arrBob, includePath); } // ------- @@ -551,10 +442,9 @@ void NotMatchExpression::debugString(StringBuilder& debug, int indentationLevel) void NotMatchExpression::serializeNotExpressionToNor(MatchExpression* exp, BSONObjBuilder* out, - const SerializationOptions& opts, bool includePath) { BSONObjBuilder childBob; - exp->serialize(&childBob, opts, includePath); + exp->serialize(&childBob, includePath); BSONObj tempObj = childBob.obj(); BSONArrayBuilder tBob(out->subarrayStart("$nor")); @@ -562,11 +452,9 @@ void NotMatchExpression::serializeNotExpressionToNor(MatchExpression* exp, tBob.doneFast(); } -void NotMatchExpression::serialize(BSONObjBuilder* out, - const SerializationOptions& opts, - bool includePath) const { +void NotMatchExpression::serialize(BSONObjBuilder* out, bool includePath) const { if (_exp->matchType() == MatchType::AND && _exp->numChildren() == 0) { - opts.appendLiteral(out, "$alwaysFalse", 1); + out->append("$alwaysFalse", 1); return; } @@ -577,10 +465,10 @@ void NotMatchExpression::serialize(BSONObjBuilder* out, // internally, so we un-nest it here to be able to re-parse it. if (_exp->matchType() == MatchType::AND) { for (size_t x = 0; x < _exp->numChildren(); ++x) { - _exp->getChild(x)->serialize(¬Bob, opts, includePath); + _exp->getChild(x)->serialize(¬Bob, includePath); } } else { - _exp->serialize(¬Bob, opts, includePath); + _exp->serialize(¬Bob, includePath); } return; } @@ -593,15 +481,20 @@ void NotMatchExpression::serialize(BSONObjBuilder* out, // It is generally easier to be correct if we just always serialize to a $nor, since this will // delegate the path serialization to lower in the tree where we have the information on-hand. // However, for legibility we preserve a $not with a single path-accepting child as a $not. - if (auto pathMatch = getEligiblePathMatchForNotSerialization(expressionToNegate)) { - auto append = [&](StringData path) { - BSONObjBuilder pathBob(out->subobjStart(path)); - pathBob.append("$not", pathMatch->getSerializedRightHandSide(opts)); - }; - append(opts.serializeFieldPathFromString(pathMatch->path())); + // + // One exception: while TextMatchExpressionBase derives from PathMatchExpression, text match + // expressions cannot be serialized in the same manner as other PathMatchExpression derivatives. + // This is because the path for a TextMatchExpression is embedded within the $text object, + // whereas for other PathMatchExpressions it is on the left-hand-side, for example {x: {$eq: + // 1}}. + if (auto pathMatch = dynamic_cast<PathMatchExpression*>(expressionToNegate); + pathMatch && !dynamic_cast<TextMatchExpressionBase*>(expressionToNegate)) { + const auto path = pathMatch->path(); + BSONObjBuilder pathBob(out->subobjStart(path)); + pathBob.append("$not", pathMatch->getSerializedRightHandSide()); return; } - return serializeNotExpressionToNor(expressionToNegate, out, opts); + return serializeNotExpressionToNor(expressionToNegate, out, includePath); } bool NotMatchExpression::equivalent(const MatchExpression* other) const { |