diff options
Diffstat (limited to 'src/mongo')
37 files changed, 768 insertions, 438 deletions
diff --git a/src/mongo/db/exec/geo_near.cpp b/src/mongo/db/exec/geo_near.cpp index 5349bfaa3e5..9da6af59370 100644 --- a/src/mongo/db/exec/geo_near.cpp +++ b/src/mongo/db/exec/geo_near.cpp @@ -543,6 +543,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + R2Annulus _annulus; }; diff --git a/src/mongo/db/exec/subplan.cpp b/src/mongo/db/exec/subplan.cpp index 021bf3efd5a..f8b30a6a7a3 100644 --- a/src/mongo/db/exec/subplan.cpp +++ b/src/mongo/db/exec/subplan.cpp @@ -161,7 +161,7 @@ std::unique_ptr<MatchExpression> SubplanStage::rewriteToRootedOr( } // Normalize and sort the resulting match expression. - orChild = std::unique_ptr<MatchExpression>(CanonicalQuery::normalizeTree(orChild.release())); + orChild = MatchExpression::optimize(std::move(orChild)); CanonicalQuery::sortTree(orChild.get()); return orChild; diff --git a/src/mongo/db/matcher/SConscript b/src/mongo/db/matcher/SConscript index a795325d185..c34afea4be4 100644 --- a/src/mongo/db/matcher/SConscript +++ b/src/mongo/db/matcher/SConscript @@ -89,6 +89,7 @@ env.CppUnitTest( 'expression_expr_test.cpp', 'expression_geo_test.cpp', 'expression_leaf_test.cpp', + 'expression_optimize_test.cpp', 'expression_parser_geo_test.cpp', 'expression_test.cpp', 'expression_tree_test.cpp', @@ -114,6 +115,7 @@ env.CppUnitTest( ], LIBDEPS=[ '$BUILD_DIR/mongo/db/query/collation/collator_interface_mock', + '$BUILD_DIR/mongo/db/query/query_planner', 'expressions', ], ) diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h index 768c265d3ea..d7cb4acbff7 100644 --- a/src/mongo/db/matcher/expression.h +++ b/src/mongo/db/matcher/expression.h @@ -38,6 +38,7 @@ #include "mongo/db/matcher/match_details.h" #include "mongo/db/matcher/matchable.h" #include "mongo/db/pipeline/dependencies.h" +#include "mongo/stdx/functional.h" #include "mongo/stdx/memory.h" namespace mongo { @@ -120,6 +121,20 @@ public: INTERNAL_SCHEMA_XOR, }; + /** + * Make simplifying changes to the structure of a MatchExpression tree without altering its + * semantics. This function may return: + * - a pointer to the original, unmodified MatchExpression, + * - a pointer to the original MatchExpression that has been mutated, or + * - a pointer to a new MatchExpression. + * + * The value of 'expression' must not be nullptr. + */ + static std::unique_ptr<MatchExpression> optimize(std::unique_ptr<MatchExpression> expression) { + auto optimizer = expression->getOptimizer(); + return optimizer(std::move(expression)); + } + MatchExpression(MatchType type); virtual ~MatchExpression() {} @@ -261,6 +276,15 @@ public: protected: /** + * An ExpressionOptimizerFunc implements tree simplifications for a MatchExpression tree with a + * specific type of MatchExpression at the root. Except for requiring a specific MatchExpression + * subclass, an ExpressionOptimizerFunc has the same requirements and functionality as described + * in the specification of MatchExpression::getOptimizer(std::unique_ptr<MatchExpression>). + */ + using ExpressionOptimizerFunc = + stdx::function<std::unique_ptr<MatchExpression>(std::unique_ptr<MatchExpression>)>; + + /** * Subclasses that are collation-aware must implement this method in order to capture changes * to the collator that occur after initialization time. */ @@ -271,6 +295,23 @@ protected: void _debugAddSpace(StringBuilder& debug, int level) const; private: + /** + * Subclasses should implement this function to provide an ExpressionOptimizerFunc specific to + * the subclass. This function is only called by + * MatchExpression::optimize(std::unique_ptr<MatchExpression>), which is responsible for calling + * MatchExpression::getOptimizer() on its input MatchExpression and then passing the same + * MatchExpression to the resulting ExpressionOptimizerFunc. There should be no other callers + * to this function. + * + * Any MatchExpression subclass that stores child MatchExpression objects is responsible for + * returning an ExpressionOptimizerFunc that recursively calls + * MatchExpression::optimize(std::unique_ptr<MatchExpression>) on those children. + * + * See the descriptions of MatchExpression::optimize(std::unique_ptr<MatchExpression>) and + * ExpressionOptimizerFunc for additional explanation of their interfaces and functionality. + */ + virtual ExpressionOptimizerFunc getOptimizer() const = 0; + MatchType _matchType; std::unique_ptr<TagData> _tagData; }; diff --git a/src/mongo/db/matcher/expression_always_boolean.h b/src/mongo/db/matcher/expression_always_boolean.h index a22b8b1e479..f15035f2d4f 100644 --- a/src/mongo/db/matcher/expression_always_boolean.h +++ b/src/mongo/db/matcher/expression_always_boolean.h @@ -82,6 +82,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + bool _value; }; diff --git a/src/mongo/db/matcher/expression_arity.h b/src/mongo/db/matcher/expression_arity.h index dc43269a91a..e6f71395941 100644 --- a/src/mongo/db/matcher/expression_arity.h +++ b/src/mongo/db/matcher/expression_arity.h @@ -147,6 +147,20 @@ protected: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { + for (auto& subExpression : + static_cast<FixedArityMatchExpression&>(*expression)._expressions) { + // Since 'subExpression' is a reference to a member of the + // FixedArityMatchExpression's child array, this assignment replaces the original + // child with the optimized child. + subExpression = MatchExpression::optimize(std::move(subExpression)); + } + + return expression; + }; + } + std::array<std::unique_ptr<MatchExpression>, nargs> _expressions; }; diff --git a/src/mongo/db/matcher/expression_array.cpp b/src/mongo/db/matcher/expression_array.cpp index b80e321b976..84c544df2bf 100644 --- a/src/mongo/db/matcher/expression_array.cpp +++ b/src/mongo/db/matcher/expression_array.cpp @@ -108,6 +108,14 @@ void ElemMatchObjectMatchExpression::serialize(BSONObjBuilder* out) const { out->append(path(), BSON("$elemMatch" << subBob.obj())); } +MatchExpression::ExpressionOptimizerFunc ElemMatchObjectMatchExpression::getOptimizer() const { + return [](std::unique_ptr<MatchExpression> expression) { + auto& elemExpression = static_cast<ElemMatchObjectMatchExpression&>(*expression); + elemExpression._sub = MatchExpression::optimize(std::move(elemExpression._sub)); + + return expression; + }; +} // ------- @@ -184,6 +192,19 @@ void ElemMatchValueMatchExpression::serialize(BSONObjBuilder* out) const { out->append(path(), BSON("$elemMatch" << emBob.obj())); } +MatchExpression::ExpressionOptimizerFunc ElemMatchValueMatchExpression::getOptimizer() const { + return [](std::unique_ptr<MatchExpression> expression) { + auto& subs = static_cast<ElemMatchValueMatchExpression&>(*expression)._subs; + + for (MatchExpression*& subExpression : subs) { + auto optimizedSubExpression = + MatchExpression::optimize(std::unique_ptr<MatchExpression>(subExpression)); + subExpression = optimizedSubExpression.release(); + } + + return expression; + }; +} // --------- diff --git a/src/mongo/db/matcher/expression_array.h b/src/mongo/db/matcher/expression_array.h index 1ea6df0a10a..f4090c0a8b0 100644 --- a/src/mongo/db/matcher/expression_array.h +++ b/src/mongo/db/matcher/expression_array.h @@ -111,6 +111,8 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final; + std::unique_ptr<MatchExpression> _sub; }; @@ -155,6 +157,8 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final; + bool _arrayElementMatchesAll(const BSONElement& e) const; std::vector<MatchExpression*> _subs; @@ -199,6 +203,10 @@ public: } private: + virtual ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + int _size; // >= 0 real, < 0, nothing will match }; } diff --git a/src/mongo/db/matcher/expression_expr.cpp b/src/mongo/db/matcher/expression_expr.cpp index 8344ffbca7c..8963dd003d8 100644 --- a/src/mongo/db/matcher/expression_expr.cpp +++ b/src/mongo/db/matcher/expression_expr.cpp @@ -74,4 +74,13 @@ std::unique_ptr<MatchExpression> ExprMatchExpression::shallowClone() const { return stdx::make_unique<ExprMatchExpression>(std::move(clonedExpr), _expCtx); } + +MatchExpression::ExpressionOptimizerFunc ExprMatchExpression::getOptimizer() const { + return [](std::unique_ptr<MatchExpression> expression) { + auto& exprMatchExpr = static_cast<ExprMatchExpression&>(*expression); + exprMatchExpr._expression = exprMatchExpr._expression->optimize(); + + return expression; + }; +} } // namespace mongo diff --git a/src/mongo/db/matcher/expression_expr.h b/src/mongo/db/matcher/expression_expr.h index 7818d75a339..e97cce982dc 100644 --- a/src/mongo/db/matcher/expression_expr.h +++ b/src/mongo/db/matcher/expression_expr.h @@ -83,6 +83,8 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final; + void _doAddDependencies(DepsTracker* deps) const final { if (_expression) { _expression->addDependencies(deps); @@ -91,7 +93,6 @@ private: boost::intrusive_ptr<ExpressionContext> _expCtx; - // TODO SERVER-30991: '_expression' should be optimized as part of MatchExpression::optimize(). boost::intrusive_ptr<Expression> _expression; }; diff --git a/src/mongo/db/matcher/expression_expr_test.cpp b/src/mongo/db/matcher/expression_expr_test.cpp index e0dfae1bb38..c3d2395e62e 100644 --- a/src/mongo/db/matcher/expression_expr_test.cpp +++ b/src/mongo/db/matcher/expression_expr_test.cpp @@ -93,19 +93,48 @@ TEST(ExprMatchExpression, ComparisonThrowsWithUnboundVariable) { ASSERT_THROWS(ExprMatchExpression pipelineExpr(expression.firstElement(), expCtx), DBException); } -// TODO SERVER-30991: Uncomment once MatchExpression::optimize() is in place and handles -// optimization of the Expression held by ExprMatchExpression. Also add a second expression, -// BSON("$expr" << "$$var"), with $$var bound to 4 to confirm it optimizes to {$const: 4} as -// well. -/* TEST(ExprMatchExpression, IdenticalPostOptimizedExpressionsAreEquivalent) { BSONObj expression = BSON("$expr" << BSON("$multiply" << BSON_ARRAY(2 << 2))); BSONObj expressionEquiv = BSON("$expr" << BSON("$const" << 4)); BSONObj expressionNotEquiv = BSON("$expr" << BSON("$const" << 10)); + // Create and optimize an ExprMatchExpression. const boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest()); - ExprMatchExpression pipelineExpr(expression.firstElement(), expCtx); - pipelineExpr::optimize(); + std::unique_ptr<MatchExpression> matchExpr = + stdx::make_unique<ExprMatchExpression>(expression.firstElement(), expCtx); + matchExpr = MatchExpression::optimize(std::move(matchExpr)); + + // We expect that the optimized 'matchExpr' is still an ExprMatchExpression. + std::unique_ptr<ExprMatchExpression> pipelineExpr( + dynamic_cast<ExprMatchExpression*>(matchExpr.release())); + ASSERT_TRUE(pipelineExpr); + + ASSERT_TRUE(pipelineExpr->equivalent(pipelineExpr.get())); + + ExprMatchExpression pipelineExprEquiv(expressionEquiv.firstElement(), expCtx); + ASSERT_TRUE(pipelineExpr->equivalent(&pipelineExprEquiv)); + + ExprMatchExpression pipelineExprNotEquiv(expressionNotEquiv.firstElement(), expCtx); + ASSERT_FALSE(pipelineExpr->equivalent(&pipelineExprNotEquiv)); +} + +TEST(ExprMatchExpression, ExpressionOptimizeRewritesVariableDereferenceAsConstant) { + const boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest()); + auto varId = expCtx->variablesParseState.defineVariable("var"); + expCtx->variables.setValue(varId, Value(4)); + + BSONObj expression = BSON("$expr" + << "$$var"); + BSONObj expressionEquiv = BSON("$expr" << BSON("$const" << 4)); + BSONObj expressionNotEquiv = BSON("$expr" << BSON("$const" << 10)); + + // Create and optimize an ExprMatchExpression. + std::unique_ptr<MatchExpression> matchExpr = + stdx::make_unique<ExprMatchExpression>(expression.firstElement(), expCtx); + matchExpr = MatchExpression::optimize(std::move(matchExpr)); + + // We expect that the optimized 'matchExpr' is still an ExprMatchExpression. + auto& pipelineExpr = dynamic_cast<ExprMatchExpression&>(*matchExpr); ASSERT_TRUE(pipelineExpr.equivalent(&pipelineExpr)); ExprMatchExpression pipelineExprEquiv(expressionEquiv.firstElement(), expCtx); @@ -114,7 +143,6 @@ TEST(ExprMatchExpression, IdenticalPostOptimizedExpressionsAreEquivalent) { ExprMatchExpression pipelineExprNotEquiv(expressionNotEquiv.firstElement(), expCtx); ASSERT_FALSE(pipelineExpr.equivalent(&pipelineExprNotEquiv)); } -*/ TEST(ExprMatchExpression, ShallowClonedExpressionIsEquivalentToOriginal) { BSONObj expression = BSON("$expr" << BSON("$eq" << BSON_ARRAY("$a" << 5))); diff --git a/src/mongo/db/matcher/expression_geo.h b/src/mongo/db/matcher/expression_geo.h index 875adedf616..87b9624a5be 100644 --- a/src/mongo/db/matcher/expression_geo.h +++ b/src/mongo/db/matcher/expression_geo.h @@ -110,6 +110,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + // The original geo specification provided by the user. BSONObj _rawObj; @@ -187,6 +191,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + // The original geo specification provided by the user. BSONObj _rawObj; diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp index 6a3502566e8..a1fc305b3cf 100644 --- a/src/mongo/db/matcher/expression_leaf.cpp +++ b/src/mongo/db/matcher/expression_leaf.cpp @@ -539,6 +539,43 @@ Status InMatchExpression::addRegex(std::unique_ptr<RegexMatchExpression> expr) { return Status::OK(); } +MatchExpression::ExpressionOptimizerFunc InMatchExpression::getOptimizer() const { + return [](std::unique_ptr<MatchExpression> expression) -> std::unique_ptr<MatchExpression> { + // NOTE: We do not recursively call optimize() on the RegexMatchExpression children in the + // _regexes list. We assume that optimize() on a RegexMatchExpression is a no-op. + + auto& regexList = static_cast<InMatchExpression&>(*expression)._regexes; + auto& equalitySet = static_cast<InMatchExpression&>(*expression)._equalitySet; + auto collator = static_cast<InMatchExpression&>(*expression).getCollator(); + if (regexList.size() == 1 && equalitySet.empty()) { + // Simplify IN of exactly one regex to be a regex match. + auto& childRe = regexList.front(); + invariant(!childRe->getTag()); + + auto simplifiedExpression = stdx::make_unique<RegexMatchExpression>(); + invariantOK(simplifiedExpression->init( + expression->path(), childRe->getString(), childRe->getFlags())); + if (expression->getTag()) { + simplifiedExpression->setTag(expression->getTag()->clone()); + } + + return simplifiedExpression; + } else if (equalitySet.size() == 1 && regexList.empty()) { + // Simplify IN of exactly one equality to be an EqualityMatchExpression. + auto simplifiedExpression = stdx::make_unique<EqualityMatchExpression>(); + invariantOK(simplifiedExpression->init(expression->path(), *(equalitySet.begin()))); + simplifiedExpression->setCollator(collator); + if (expression->getTag()) { + simplifiedExpression->setTag(expression->getTag()->clone()); + } + + return simplifiedExpression; + } + + return expression; + }; +} + // ----------- Status BitTestMatchExpression::init(StringData path, std::vector<uint32_t> bitPositions) { diff --git a/src/mongo/db/matcher/expression_leaf.h b/src/mongo/db/matcher/expression_leaf.h index c53c553382c..dd225c57763 100644 --- a/src/mongo/db/matcher/expression_leaf.h +++ b/src/mongo/db/matcher/expression_leaf.h @@ -127,6 +127,11 @@ protected: // Collator used to compare elements. By default, simple binary comparison will be used. const CollatorInterface* _collator = nullptr; + +private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } }; class EqualityMatchExpression : public ComparisonMatchExpression { @@ -236,6 +241,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + std::string _regex; std::string _flags; std::unique_ptr<pcrecpp::RE> _re; @@ -272,6 +281,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + int _divisor; int _remainder; }; @@ -298,6 +311,11 @@ public: virtual void serialize(BSONObjBuilder* out) const; virtual bool equivalent(const MatchExpression* other) const; + +private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } }; /** @@ -352,6 +370,8 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final; + // Whether or not '_equalities' has a jstNULL element in it. bool _hasNull = false; @@ -421,6 +441,10 @@ protected: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + /** * Performs bit test using bit positions on 'eValue' and returns whether or not the bit test * passes. diff --git a/src/mongo/db/matcher/expression_optimize_test.cpp b/src/mongo/db/matcher/expression_optimize_test.cpp new file mode 100644 index 00000000000..07b54d639c4 --- /dev/null +++ b/src/mongo/db/matcher/expression_optimize_test.cpp @@ -0,0 +1,356 @@ +/** + * Copyright (C) 2017 MongoDB Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License, version 3, + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the GNU Affero General Public License in all respects + * for all of the code used other than as permitted herein. If you modify + * file(s) with this exception, you may extend this exception to your + * version of the file(s), but you are not obligated to do so. If you do not + * wish to do so, delete this exception statement from your version. If you + * delete this exception statement from all source files in the program, + * then also delete it in the license file. + */ + +#include "mongo/db/pipeline/expression.h" + +#include "mongo/db/pipeline/expression_context_for_test.h" +#include "mongo/db/query/canonical_query.h" +#include "mongo/db/query/collation/collator_interface_mock.h" +#include "mongo/db/query/index_tag.h" +#include "mongo/unittest/unittest.h" + +namespace mongo { +namespace { + +static const NamespaceString nss("testdb.testcoll"); + +using unittest::assertGet; + +/** + * Helper function to parse the given BSON object as a MatchExpression, checks the status, + * and return the MatchExpression*. + */ +MatchExpression* parseMatchExpression(const BSONObj& obj) { + const CollatorInterface* collator = nullptr; + const boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest()); + StatusWithMatchExpression status = + MatchExpressionParser::parse(obj, + collator, + expCtx, + ExtensionsCallbackNoop(), + MatchExpressionParser::kAllowAllSpecialFeatures); + if (!status.isOK()) { + mongoutils::str::stream ss; + ss << "failed to parse query: " << obj.toString() + << ". Reason: " << status.getStatus().toString(); + FAIL(ss); + } + + return status.getValue().release(); +} + +/** + * Helper function which parses and normalizes 'queryStr', and returns whether the given + * (expression tree, query request) tuple passes CanonicalQuery::isValid(). + * Returns Status::OK() if the tuple is valid, else returns an error Status. + */ +Status isValid(const std::string& queryStr, const QueryRequest& qrRaw) { + BSONObj queryObj = fromjson(queryStr); + std::unique_ptr<MatchExpression> me(parseMatchExpression(queryObj)); + me = MatchExpression::optimize(std::move(me)); + return CanonicalQuery::isValid(me.get(), qrRaw); +} + +TEST(ExpressionOptimizeTest, IsValidText) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + ASSERT_OK(qr->validate()); + + // Valid: regular TEXT. + ASSERT_OK(isValid("{$text: {$search: 's'}}", *qr)); + + // Valid: TEXT inside OR. + ASSERT_OK( + isValid("{$or: [" + " {$text: {$search: 's'}}," + " {a: 1}" + "]}", + *qr)); + + // Valid: TEXT outside NOR. + ASSERT_OK(isValid("{$text: {$search: 's'}, $nor: [{a: 1}, {b: 1}]}", *qr)); + + // Invalid: TEXT inside NOR. + ASSERT_NOT_OK(isValid("{$nor: [{$text: {$search: 's'}}, {a: 1}]}", *qr)); + + // Invalid: TEXT inside NOR. + ASSERT_NOT_OK( + isValid("{$nor: [" + " {$or: [" + " {$text: {$search: 's'}}," + " {a: 1}" + " ]}," + " {a: 2}" + "]}", + *qr)); + + // Invalid: >1 TEXT. + ASSERT_NOT_OK( + isValid("{$and: [" + " {$text: {$search: 's'}}," + " {$text: {$search: 't'}}" + "]}", + *qr)); + + // Invalid: >1 TEXT. + ASSERT_NOT_OK( + isValid("{$and: [" + " {$or: [" + " {$text: {$search: 's'}}," + " {a: 1}" + " ]}," + " {$or: [" + " {$text: {$search: 't'}}," + " {b: 1}" + " ]}" + "]}", + *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidTextTailable) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + qr->setTailableMode(TailableMode::kTailable); + ASSERT_OK(qr->validate()); + + // Invalid: TEXT and tailable. + ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidGeo) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + ASSERT_OK(qr->validate()); + + // Valid: regular GEO_NEAR. + ASSERT_OK(isValid("{a: {$near: [0, 0]}}", *qr)); + + // Valid: GEO_NEAR inside nested AND. + ASSERT_OK( + isValid("{$and: [" + " {$and: [" + " {a: {$near: [0, 0]}}," + " {b: 1}" + " ]}," + " {c: 1}" + "]}", + *qr)); + + // Invalid: >1 GEO_NEAR. + ASSERT_NOT_OK( + isValid("{$and: [" + " {a: {$near: [0, 0]}}," + " {b: {$near: [0, 0]}}" + "]}", + *qr)); + + // Invalid: >1 GEO_NEAR. + ASSERT_NOT_OK( + isValid("{$and: [" + " {a: {$geoNear: [0, 0]}}," + " {b: {$near: [0, 0]}}" + "]}", + *qr)); + + // Invalid: >1 GEO_NEAR. + ASSERT_NOT_OK( + isValid("{$and: [" + " {$and: [" + " {a: {$near: [0, 0]}}," + " {b: 1}" + " ]}," + " {$and: [" + " {c: {$near: [0, 0]}}," + " {d: 1}" + " ]}" + "]}", + *qr)); + + // Invalid: GEO_NEAR inside NOR. + ASSERT_NOT_OK( + isValid("{$nor: [" + " {a: {$near: [0, 0]}}," + " {b: 1}" + "]}", + *qr)); + + // Invalid: GEO_NEAR inside OR. + ASSERT_NOT_OK( + isValid("{$or: [" + " {a: {$near: [0, 0]}}," + " {b: 1}" + "]}", + *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidTextAndGeo) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + ASSERT_OK(qr->validate()); + + // Invalid: TEXT and GEO_NEAR. + ASSERT_NOT_OK(isValid("{$text: {$search: 's'}, a: {$near: [0, 0]}}", *qr)); + + // Invalid: TEXT and GEO_NEAR. + ASSERT_NOT_OK(isValid("{$text: {$search: 's'}, a: {$geoNear: [0, 0]}}", *qr)); + + // Invalid: TEXT and GEO_NEAR. + ASSERT_NOT_OK( + isValid("{$or: [" + " {$text: {$search: 's'}}," + " {a: 1}" + " ]," + " b: {$near: [0, 0]}}", + *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidTextAndNaturalAscending) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + qr->setSort(fromjson("{$natural: 1}")); + ASSERT_OK(qr->validate()); + + // Invalid: TEXT and {$natural: 1} sort order. + ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidTextAndNaturalDescending) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + qr->setSort(fromjson("{$natural: -1}")); + ASSERT_OK(qr->validate()); + + // Invalid: TEXT and {$natural: -1} sort order. + ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidTextAndHint) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + qr->setHint(fromjson("{a: 1}")); + ASSERT_OK(qr->validate()); + + // Invalid: TEXT and {$natural: -1} sort order. + ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); +} + +// SERVER-14366 +TEST(ExpressionOptimizeTest, IsValidGeoNearNaturalSort) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + qr->setSort(fromjson("{$natural: 1}")); + ASSERT_OK(qr->validate()); + + // Invalid: GEO_NEAR and {$natural: 1} sort order. + ASSERT_NOT_OK(isValid("{a: {$near: {$geometry: {type: 'Point', coordinates: [0, 0]}}}}", *qr)); +} + +// SERVER-14366 +TEST(ExpressionOptimizeTest, IsValidGeoNearNaturalHint) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + qr->setHint(fromjson("{$natural: 1}")); + ASSERT_OK(qr->validate()); + + // Invalid: GEO_NEAR and {$natural: 1} hint. + ASSERT_NOT_OK(isValid("{a: {$near: {$geometry: {type: 'Point', coordinates: [0, 0]}}}}", *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidTextAndSnapshot) { + // Filter inside QueryRequest is not used. + auto qr = stdx::make_unique<QueryRequest>(nss); + qr->setSnapshot(true); + ASSERT_OK(qr->validate()); + + // Invalid: TEXT and snapshot. + ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidNaturalSortIndexHint) { + const bool isExplain = false; + auto qr = assertGet(QueryRequest::makeFromFindCommand( + nss, fromjson("{find: 'testcoll', sort: {$natural: 1}, hint: {a: 1}}"), isExplain)); + + // Invalid: {$natural: 1} sort order and index hint. + ASSERT_NOT_OK(isValid("{}", *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidNaturalSortNaturalHint) { + const bool isExplain = false; + auto qr = assertGet(QueryRequest::makeFromFindCommand( + nss, fromjson("{find: 'testcoll', sort: {$natural: 1}, hint: {$natural: 1}}"), isExplain)); + + // Valid: {$natural: 1} sort order and {$natural: 1} hint. + ASSERT_OK(isValid("{}", *qr)); +} + +TEST(ExpressionOptimizeTest, IsValidNaturalSortNaturalHintDifferentDirections) { + const bool isExplain = false; + auto qr = assertGet(QueryRequest::makeFromFindCommand( + nss, fromjson("{find: 'testcoll', sort: {$natural: 1}, hint: {$natural: -1}}"), isExplain)); + + // Invalid: {$natural: 1} sort order and {$natural: -1} hint. + ASSERT_NOT_OK(isValid("{}", *qr)); +} + +TEST(ExpressionOptimizeTest, NormalizeWithInPreservesTags) { + BSONObj obj = fromjson("{x: {$in: [1]}}"); + std::unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj)); + matchExpression->setTag(new IndexTag(2U, 1U, false)); + matchExpression = MatchExpression::optimize(std::move(matchExpression)); + IndexTag* tag = dynamic_cast<IndexTag*>(matchExpression->getTag()); + ASSERT(tag); + ASSERT_EQ(2U, tag->index); +} + +TEST(ExpressionOptimizeTest, NormalizeWithInAndRegexPreservesTags) { + BSONObj obj = fromjson("{x: {$in: [/a.b/]}}"); + std::unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj)); + matchExpression->setTag(new IndexTag(2U, 1U, false)); + matchExpression = MatchExpression::optimize(std::move(matchExpression)); + IndexTag* tag = dynamic_cast<IndexTag*>(matchExpression->getTag()); + ASSERT(tag); + ASSERT_EQ(2U, tag->index); +} + +TEST(ExpressionOptimizeTest, NormalizeWithInPreservesCollator) { + CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString); + BSONObj obj = fromjson("{'': 'string'}"); + auto inMatchExpression = stdx::make_unique<InMatchExpression>(); + inMatchExpression->setCollator(&collator); + std::vector<BSONElement> equalities{obj.firstElement()}; + ASSERT_OK(inMatchExpression->setEqualities(std::move(equalities))); + auto matchExpression = MatchExpression::optimize(std::move(inMatchExpression)); + ASSERT(matchExpression->matchType() == MatchExpression::MatchType::EQ); + EqualityMatchExpression* eqMatchExpression = + static_cast<EqualityMatchExpression*>(matchExpression.get()); + ASSERT_EQ(eqMatchExpression->getCollator(), &collator); +} + +} // namespace +} // namespace mongo diff --git a/src/mongo/db/matcher/expression_text_base.h b/src/mongo/db/matcher/expression_text_base.h index 045a9d88a32..ac51e137ee1 100644 --- a/src/mongo/db/matcher/expression_text_base.h +++ b/src/mongo/db/matcher/expression_text_base.h @@ -68,6 +68,11 @@ public: void serialize(BSONObjBuilder* out) const final; bool equivalent(const MatchExpression* other) const final; + +private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } }; } // namespace mongo diff --git a/src/mongo/db/matcher/expression_tree.cpp b/src/mongo/db/matcher/expression_tree.cpp index 370b1e675b1..3a60e9aabf8 100644 --- a/src/mongo/db/matcher/expression_tree.cpp +++ b/src/mongo/db/matcher/expression_tree.cpp @@ -62,6 +62,71 @@ void ListOfMatchExpression::_listToBSON(BSONArrayBuilder* out) const { out->doneFast(); } +MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() const { + return [](std::unique_ptr<MatchExpression> expression) -> std::unique_ptr<MatchExpression> { + auto& children = static_cast<ListOfMatchExpression&>(*expression)._expressions; + + // Recursively apply optimizations to child expressions. + for (auto& childExpression : children) { + // Since 'childExpression' is a reference to a member of the ListOfMatchExpression's + // child array, this assignment replaces the original child with the optimized child. + std::unique_ptr<MatchExpression> childExpressionPtr(childExpression); + auto optimizedExpression = MatchExpression::optimize(std::move(childExpressionPtr)); + childExpression = optimizedExpression.release(); + } + + // Associativity of AND and OR: an AND absorbs the children of any ANDs among its children + // (and likewise for any OR with OR children). + MatchType matchType = expression->matchType(); + if (matchType == AND || matchType == OR) { + std::vector<MatchExpression*> absorbedExpressions; + for (MatchExpression*& childExpression : children) { + if (childExpression->matchType() == matchType) { + // Move this child out of the children array. + std::unique_ptr<ListOfMatchExpression> childExpressionPtr( + static_cast<ListOfMatchExpression*>(childExpression)); + childExpression = nullptr; // NULL out this child's entry in _expressions, so + // that it will be deleted by the erase call below. + + // Move all of the grandchildren from the child expression to + // absorbedExpressions. + auto& grandChildren = childExpressionPtr->_expressions; + absorbedExpressions.insert( + absorbedExpressions.end(), grandChildren.begin(), grandChildren.end()); + grandChildren.clear(); + + // Note that 'childExpressionPtr' will now be destroyed. + } + } + + // We replaced each destroyed child expression with nullptr. Now we remove those + // nullptrs from the array. + children.erase(std::remove(children.begin(), children.end(), nullptr), children.end()); + + // Append the absorbed children to the end of the array. + children.insert(children.end(), absorbedExpressions.begin(), absorbedExpressions.end()); + } + + if (children.size() == 1) { + if ((matchType == AND || matchType == OR || matchType == INTERNAL_SCHEMA_XOR)) { + // Simplify AND/OR/XOR with exactly one operand to an expression consisting of just + // that operand. + MatchExpression* simplifiedExpression = children.front(); + children.clear(); + return std::unique_ptr<MatchExpression>(simplifiedExpression); + } else if (matchType == NOR) { + // Simplify NOR of exactly one operand to NOT of that operand. + auto simplifiedExpression = stdx::make_unique<NotMatchExpression>(); + invariantOK(simplifiedExpression->init(children.front())); + children.clear(); + return simplifiedExpression; + } + } + + return expression; + }; +} + bool ListOfMatchExpression::equivalent(const MatchExpression* other) const { if (matchType() != other->matchType()) return false; @@ -214,4 +279,14 @@ bool NotMatchExpression::equivalent(const MatchExpression* other) const { return _exp->equivalent(other->getChild(0)); } + + +MatchExpression::ExpressionOptimizerFunc NotMatchExpression::getOptimizer() const { + return [](std::unique_ptr<MatchExpression> expression) { + auto& notExpression = static_cast<NotMatchExpression&>(*expression); + notExpression._exp = MatchExpression::optimize(std::move(notExpression._exp)); + + return expression; + }; +} } diff --git a/src/mongo/db/matcher/expression_tree.h b/src/mongo/db/matcher/expression_tree.h index 5bfd86820ee..a0c1cc088be 100644 --- a/src/mongo/db/matcher/expression_tree.h +++ b/src/mongo/db/matcher/expression_tree.h @@ -99,6 +99,8 @@ protected: void _listToBSON(BSONArrayBuilder* out) const; private: + ExpressionOptimizerFunc getOptimizer() const final; + std::vector<MatchExpression*> _expressions; }; @@ -237,6 +239,8 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final; + std::unique_ptr<MatchExpression> _exp; }; } diff --git a/src/mongo/db/matcher/expression_type.h b/src/mongo/db/matcher/expression_type.h index e63d68f5def..c9ac6a2129d 100644 --- a/src/mongo/db/matcher/expression_type.h +++ b/src/mongo/db/matcher/expression_type.h @@ -105,6 +105,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + // The set of matching types. MatcherTypeSet _typeSet; }; diff --git a/src/mongo/db/matcher/expression_where_base.h b/src/mongo/db/matcher/expression_where_base.h index ec1d2d97915..32033ea675a 100644 --- a/src/mongo/db/matcher/expression_where_base.h +++ b/src/mongo/db/matcher/expression_where_base.h @@ -80,6 +80,10 @@ protected: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + const std::string _code; const BSONObj _scope; // Owned. }; diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_all_elem_match_from_index.h b/src/mongo/db/matcher/schema/expression_internal_schema_all_elem_match_from_index.h index 374e9e1b32b..6237e1b9a3b 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_all_elem_match_from_index.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_all_elem_match_from_index.h @@ -89,6 +89,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + long long _index; std::unique_ptr<ExpressionWithPlaceholder> _expression; }; diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_allowed_properties.h b/src/mongo/db/matcher/schema/expression_internal_schema_allowed_properties.h index 76945fd4983..479341d07e6 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_allowed_properties.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_allowed_properties.h @@ -159,6 +159,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + /** * Helper function for matches() and matchesSingleElement(). */ diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_eq.h b/src/mongo/db/matcher/schema/expression_internal_schema_eq.h index 7905671c7a8..2f73ccf534e 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_eq.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_eq.h @@ -76,6 +76,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + UnorderedFieldsBSONElementComparator _eltCmp; BSONElement _rhsElem; }; diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_fmod.h b/src/mongo/db/matcher/schema/expression_internal_schema_fmod.h index 179a4b06d58..25a7b3c3945 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_fmod.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_fmod.h @@ -68,6 +68,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + Decimal128 _divisor; Decimal128 _remainder; }; diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_match_array_index.h b/src/mongo/db/matcher/schema/expression_internal_schema_match_array_index.h index acf83d71d50..6c66dda8484 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_match_array_index.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_match_array_index.h @@ -89,6 +89,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + long long _index = 0; std::unique_ptr<ExpressionWithPlaceholder> _expression; }; diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_num_array_items.h b/src/mongo/db/matcher/schema/expression_internal_schema_num_array_items.h index 86e1281c0fd..05dd873d772 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_num_array_items.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_num_array_items.h @@ -72,6 +72,10 @@ protected: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + StringData _name; long long _numItems = 0; }; diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_num_properties.h b/src/mongo/db/matcher/schema/expression_internal_schema_num_properties.h index 67f3a6e880b..ced6529a668 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_num_properties.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_num_properties.h @@ -81,6 +81,10 @@ protected: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + long long _numProperties; std::string _name; }; diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_object_match.h b/src/mongo/db/matcher/schema/expression_internal_schema_object_match.h index 53f387752b7..5d3eb8b3bea 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_object_match.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_object_match.h @@ -77,6 +77,10 @@ public: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + std::unique_ptr<MatchExpression> _sub; }; } // namespace mongo diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_root_doc_eq.h b/src/mongo/db/matcher/schema/expression_internal_schema_root_doc_eq.h index cdb69aab699..e6f53658eda 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_root_doc_eq.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_root_doc_eq.h @@ -93,6 +93,10 @@ protected: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + UnorderedFieldsBSONObjComparator _objCmp; BSONObj _rhsObj; }; diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_str_length.h b/src/mongo/db/matcher/schema/expression_internal_schema_str_length.h index f83c6d584dc..90830577432 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_str_length.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_str_length.h @@ -72,6 +72,10 @@ protected: } private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + StringData _name; long long _strLen = 0; }; diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_unique_items.h b/src/mongo/db/matcher/schema/expression_internal_schema_unique_items.h index 07beff92319..f41b9e0ef34 100644 --- a/src/mongo/db/matcher/schema/expression_internal_schema_unique_items.h +++ b/src/mongo/db/matcher/schema/expression_internal_schema_unique_items.h @@ -83,6 +83,10 @@ public: std::unique_ptr<MatchExpression> shallowClone() const final; private: + ExpressionOptimizerFunc getOptimizer() const final { + return [](std::unique_ptr<MatchExpression> expression) { return expression; }; + } + // The comparator to use when comparing BSONElements, which will never use a collation. UnorderedFieldsBSONElementComparator _comparator; }; diff --git a/src/mongo/db/pipeline/document_source_lookup_test.cpp b/src/mongo/db/pipeline/document_source_lookup_test.cpp index 03ea80c5d7d..66931114dbe 100644 --- a/src/mongo/db/pipeline/document_source_lookup_test.cpp +++ b/src/mongo/db/pipeline/document_source_lookup_test.cpp @@ -678,7 +678,10 @@ TEST_F(DocumentSourceLookUpTest, auto subPipeline = lookupStage->getSubPipeline_forTest(DOC("_id" << 5)); ASSERT(subPipeline); - // TODO SERVER-30991: $match within $facet should optimize to $const. + // TODO: The '$$var1' in this expression actually gets optimized to a constant expression with + // value 5, but the explain output does not reflect that change. SERVER-31292 will make that + // optimization visible here, so we will need to replace '$$var1' with a $const expression for + // this test to pass. auto expectedPipe = fromjson(str::stream() << "[{mock: {}}, {$match: {x:1}}, {$sort: {sortKey: {x: 1}}}, " << sequentialCacheStageObj() @@ -688,6 +691,43 @@ TEST_F(DocumentSourceLookUpTest, ASSERT_VALUE_EQ(Value(subPipeline->writeExplainOps(kExplain)), Value(BSONArray(expectedPipe))); } +TEST_F(DocumentSourceLookUpTest, ExprEmbeddedInMatchExpressionShouldBeOptimized) { + auto expCtx = getExpCtx(); + NamespaceString fromNs("test", "coll"); + expCtx->setResolvedNamespace(fromNs, {fromNs, std::vector<BSONObj>{}}); + + // This pipeline includes a $match stage that itself includes a $expr expression. + auto docSource = DocumentSourceLookUp::createFromBson( + fromjson("{$lookup: {let: {var1: '$_id'}, pipeline: [{$match: {$expr: {$eq: " + "['$_id','$$var1']}}}], from: 'coll', as: 'as'}}") + .firstElement(), + expCtx); + + auto lookupStage = static_cast<DocumentSourceLookUp*>(docSource.get()); + ASSERT(lookupStage); + + lookupStage->injectMongodInterface( + std::shared_ptr<MockMongodInterface>(new MockMongodInterface({}))); + + auto subPipeline = lookupStage->getSubPipeline_forTest(DOC("_id" << 5)); + ASSERT(subPipeline); + + auto sources = subPipeline->getSources(); + ASSERT_GTE(sources.size(), 2u); + + // The first source is our mock data source, and the second should be the $match expression. + auto secondSource = *(++sources.begin()); + auto& matchSource = dynamic_cast<const DocumentSourceMatch&>(*secondSource); + + // Ensure that the '$$var' in the embedded expression got optimized to ExpressionConstant. + BSONObjBuilder builder; + matchSource.getMatchExpression()->serialize(&builder); + auto serializedMatch = builder.obj(); + auto expectedMatch = fromjson("{$expr: {$eq: ['$_id', {$const: 5}]}}"); + + ASSERT_VALUE_EQ(Value(serializedMatch), Value(expectedMatch)); +} + TEST_F(DocumentSourceLookUpTest, ShouldIgnoreLocalVariablesShadowingLetVariablesWhenFindingNonCorrelatedPrefix) { auto expCtx = getExpCtx(); diff --git a/src/mongo/db/pipeline/document_source_match.cpp b/src/mongo/db/pipeline/document_source_match.cpp index 5a954c63358..b9ca0a90977 100644 --- a/src/mongo/db/pipeline/document_source_match.cpp +++ b/src/mongo/db/pipeline/document_source_match.cpp @@ -68,8 +68,7 @@ intrusive_ptr<DocumentSource> DocumentSourceMatch::optimize() { return nullptr; } - // TODO SERVER-30991: thread optimization down to the MatchExpression. - //_expression->optimize(); + _expression = MatchExpression::optimize(std::move(_expression)); return this; } diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp index 1df80364b65..35db8dbb914 100644 --- a/src/mongo/db/query/canonical_query.cpp +++ b/src/mongo/db/query/canonical_query.cpp @@ -160,7 +160,7 @@ StatusWith<std::unique_ptr<CanonicalQuery>> CanonicalQuery::canonicalize( Status initStatus = cq->init(std::move(qr), parsingCanProduceNoopMatchNodes(extensionsCallback, allowedFeatures), - me.release(), + std::move(me), std::move(collator)); if (!initStatus.isOK()) { @@ -194,7 +194,7 @@ StatusWith<std::unique_ptr<CanonicalQuery>> CanonicalQuery::canonicalize( std::unique_ptr<CanonicalQuery> cq(new CanonicalQuery()); Status initStatus = cq->init(std::move(qr), baseQuery.canHaveNoopMatchNodes(), - root->shallowClone().release(), + root->shallowClone(), std::move(collator)); if (!initStatus.isOK()) { @@ -205,7 +205,7 @@ StatusWith<std::unique_ptr<CanonicalQuery>> CanonicalQuery::canonicalize( Status CanonicalQuery::init(std::unique_ptr<QueryRequest> qr, bool canHaveNoopMatchNodes, - MatchExpression* root, + std::unique_ptr<MatchExpression> root, std::unique_ptr<CollatorInterface> collator) { _qr = std::move(qr); _collator = std::move(collator); @@ -214,11 +214,9 @@ Status CanonicalQuery::init(std::unique_ptr<QueryRequest> qr, _isIsolated = QueryRequest::isQueryIsolated(_qr->getFilter()); // Normalize, sort and validate tree. - root = normalizeTree(root); - - sortTree(root); - _root.reset(root); - Status validStatus = isValid(root, *_qr); + _root = MatchExpression::optimize(std::move(root)); + sortTree(_root.get()); + Status validStatus = isValid(_root.get(), *_qr); if (!validStatus.isOK()) { return validStatus; } @@ -284,120 +282,6 @@ bool CanonicalQuery::isSimpleIdQuery(const BSONObj& query) { } // static -MatchExpression* CanonicalQuery::normalizeTree(MatchExpression* root) { - if (MatchExpression::AND == root->matchType() || MatchExpression::OR == root->matchType()) { - // We could have AND of AND of AND. Make sure we clean up our children before merging them. - for (size_t i = 0; i < root->getChildVector()->size(); ++i) { - (*root->getChildVector())[i] = normalizeTree(root->getChild(i)); - } - - // If any of our children are of the same logical operator that we are, we remove the - // child's children and append them to ourselves after we examine all children. - std::vector<MatchExpression*> absorbedChildren; - - for (size_t i = 0; i < root->numChildren();) { - MatchExpression* child = root->getChild(i); - if (child->matchType() == root->matchType()) { - // AND of an AND or OR of an OR. Absorb child's children into ourself. - for (size_t j = 0; j < child->numChildren(); ++j) { - absorbedChildren.push_back(child->getChild(j)); - } - // TODO(opt): this is possibly n^2-ish - root->getChildVector()->erase(root->getChildVector()->begin() + i); - child->getChildVector()->clear(); - // Note that this only works because we cleared the child's children - delete child; - // Don't increment 'i' as the current child 'i' used to be child 'i+1' - } else { - ++i; - } - } - - root->getChildVector()->insert( - root->getChildVector()->end(), absorbedChildren.begin(), absorbedChildren.end()); - - // AND of 1 thing is the thing, OR of 1 thing is the thing. - if (1 == root->numChildren()) { - MatchExpression* ret = root->getChild(0); - root->getChildVector()->clear(); - delete root; - return ret; - } - } else if (MatchExpression::NOR == root->matchType()) { - // First clean up children. - for (size_t i = 0; i < root->getChildVector()->size(); ++i) { - (*root->getChildVector())[i] = normalizeTree(root->getChild(i)); - } - - // NOR of one thing is NOT of the thing. - if (1 == root->numChildren()) { - // Detach the child and assume ownership. - std::unique_ptr<MatchExpression> child(root->getChild(0)); - root->getChildVector()->clear(); - - // Delete the root when this goes out of scope. - std::unique_ptr<NorMatchExpression> ownedRoot(static_cast<NorMatchExpression*>(root)); - - // Make a NOT to be the new root and transfer ownership of the child to it. - auto newRoot = stdx::make_unique<NotMatchExpression>(); - newRoot->init(child.release()).transitional_ignore(); - - return newRoot.release(); - } - } else if (MatchExpression::NOT == root->matchType()) { - // Normalize the rest of the tree hanging off this NOT node. - NotMatchExpression* nme = static_cast<NotMatchExpression*>(root); - MatchExpression* child = nme->releaseChild(); - // normalizeTree(...) takes ownership of 'child', and then - // transfers ownership of its return value to 'nme'. - nme->resetChild(normalizeTree(child)); - } else if (MatchExpression::ELEM_MATCH_OBJECT == root->matchType()) { - // Normalize the rest of the tree hanging off this ELEM_MATCH_OBJECT node. - ElemMatchObjectMatchExpression* emome = static_cast<ElemMatchObjectMatchExpression*>(root); - auto child = emome->releaseChild(); - // normalizeTree(...) takes ownership of 'child', and then - // transfers ownership of its return value to 'emome'. - emome->resetChild(std::unique_ptr<MatchExpression>(normalizeTree(child.release()))); - } else if (MatchExpression::ELEM_MATCH_VALUE == root->matchType()) { - // Just normalize our children. - for (size_t i = 0; i < root->getChildVector()->size(); ++i) { - (*root->getChildVector())[i] = normalizeTree(root->getChild(i)); - } - } else if (MatchExpression::MATCH_IN == root->matchType()) { - std::unique_ptr<InMatchExpression> in(static_cast<InMatchExpression*>(root)); - - // IN of 1 regex is the regex. - if (in->getRegexes().size() == 1 && in->getEqualities().empty()) { - RegexMatchExpression* childRe = in->getRegexes().begin()->get(); - invariant(!childRe->getTag()); - - // Create a new RegexMatchExpression, because 'childRe' does not have a path. - auto re = stdx::make_unique<RegexMatchExpression>(); - re->init(in->path(), childRe->getString(), childRe->getFlags()).transitional_ignore(); - if (in->getTag()) { - re->setTag(in->getTag()->clone()); - } - return normalizeTree(re.release()); - } - - // IN of 1 equality is the equality. - if (in->getEqualities().size() == 1 && in->getRegexes().empty()) { - auto eq = stdx::make_unique<EqualityMatchExpression>(); - eq->init(in->path(), *(in->getEqualities().begin())).transitional_ignore(); - eq->setCollator(in->getCollator()); - if (in->getTag()) { - eq->setTag(in->getTag()->clone()); - } - return eq.release(); - } - - return in.release(); - } - - return root; -} - -// static void CanonicalQuery::sortTree(MatchExpression* tree) { for (size_t i = 0; i < tree->numChildren(); ++i) { sortTree(tree->getChild(i)); diff --git a/src/mongo/db/query/canonical_query.h b/src/mongo/db/query/canonical_query.h index 392c75ca704..db2cb578b12 100644 --- a/src/mongo/db/query/canonical_query.h +++ b/src/mongo/db/query/canonical_query.h @@ -148,13 +148,6 @@ public: static Status isValid(MatchExpression* root, const QueryRequest& parsed); /** - * Returns the normalized version of the subtree rooted at 'root'. - * - * Takes ownership of 'root'. - */ - static MatchExpression* normalizeTree(MatchExpression* root); - - /** * Traverses expression tree post-order. * Sorts children at each non-leaf node by (MatchType, path(), children, number of children) */ @@ -192,7 +185,7 @@ private: Status init(std::unique_ptr<QueryRequest> qr, bool canHaveNoopMatchNodes, - MatchExpression* root, + std::unique_ptr<MatchExpression> root, std::unique_ptr<CollatorInterface> collator); std::unique_ptr<QueryRequest> _qr; diff --git a/src/mongo/db/query/canonical_query_test.cpp b/src/mongo/db/query/canonical_query_test.cpp index 04048242c64..9a027de5599 100644 --- a/src/mongo/db/query/canonical_query_test.cpp +++ b/src/mongo/db/query/canonical_query_test.cpp @@ -28,15 +28,10 @@ #include "mongo/db/query/canonical_query.h" -#include "mongo/client/dbclientinterface.h" #include "mongo/db/json.h" -#include "mongo/db/matcher/extensions_callback_noop.h" -#include "mongo/db/namespace_string.h" -#include "mongo/db/operation_context.h" #include "mongo/db/pipeline/expression_context_for_test.h" #include "mongo/db/query/collation/collator_factory_interface.h" #include "mongo/db/query/collation/collator_interface_mock.h" -#include "mongo/db/query/index_tag.h" #include "mongo/db/query/query_test_service_context.h" #include "mongo/unittest/unittest.h" @@ -72,17 +67,6 @@ MatchExpression* parseMatchExpression(const BSONObj& obj) { return status.getValue().release(); } -/** - * Helper function which parses and normalizes 'queryStr', and returns whether the given - * (expression tree, query request) tuple passes CanonicalQuery::isValid(). - * Returns Status::OK() if the tuple is valid, else returns an error Status. - */ -Status isValid(const std::string& queryStr, const QueryRequest& qrRaw) { - BSONObj queryObj = fromjson(queryStr); - unique_ptr<MatchExpression> me(CanonicalQuery::normalizeTree(parseMatchExpression(queryObj))); - return CanonicalQuery::isValid(me.get(), qrRaw); -} - void assertEquivalent(const char* queryStr, const MatchExpression* expected, const MatchExpression* actual) { @@ -109,222 +93,6 @@ void assertNotEquivalent(const char* queryStr, FAIL(ss); } - -TEST(CanonicalQueryTest, IsValidText) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - ASSERT_OK(qr->validate()); - - // Valid: regular TEXT. - ASSERT_OK(isValid("{$text: {$search: 's'}}", *qr)); - - // Valid: TEXT inside OR. - ASSERT_OK( - isValid("{$or: [" - " {$text: {$search: 's'}}," - " {a: 1}" - "]}", - *qr)); - - // Valid: TEXT outside NOR. - ASSERT_OK(isValid("{$text: {$search: 's'}, $nor: [{a: 1}, {b: 1}]}", *qr)); - - // Invalid: TEXT inside NOR. - ASSERT_NOT_OK(isValid("{$nor: [{$text: {$search: 's'}}, {a: 1}]}", *qr)); - - // Invalid: TEXT inside NOR. - ASSERT_NOT_OK( - isValid("{$nor: [" - " {$or: [" - " {$text: {$search: 's'}}," - " {a: 1}" - " ]}," - " {a: 2}" - "]}", - *qr)); - - // Invalid: >1 TEXT. - ASSERT_NOT_OK( - isValid("{$and: [" - " {$text: {$search: 's'}}," - " {$text: {$search: 't'}}" - "]}", - *qr)); - - // Invalid: >1 TEXT. - ASSERT_NOT_OK( - isValid("{$and: [" - " {$or: [" - " {$text: {$search: 's'}}," - " {a: 1}" - " ]}," - " {$or: [" - " {$text: {$search: 't'}}," - " {b: 1}" - " ]}" - "]}", - *qr)); -} - -TEST(CanonicalQueryTest, IsValidTextTailable) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - qr->setTailableMode(TailableMode::kTailable); - ASSERT_OK(qr->validate()); - - // Invalid: TEXT and tailable. - ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); -} - -TEST(CanonicalQueryTest, IsValidGeo) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - ASSERT_OK(qr->validate()); - - // Valid: regular GEO_NEAR. - ASSERT_OK(isValid("{a: {$near: [0, 0]}}", *qr)); - - // Valid: GEO_NEAR inside nested AND. - ASSERT_OK( - isValid("{$and: [" - " {$and: [" - " {a: {$near: [0, 0]}}," - " {b: 1}" - " ]}," - " {c: 1}" - "]}", - *qr)); - - // Invalid: >1 GEO_NEAR. - ASSERT_NOT_OK( - isValid("{$and: [" - " {a: {$near: [0, 0]}}," - " {b: {$near: [0, 0]}}" - "]}", - *qr)); - - // Invalid: >1 GEO_NEAR. - ASSERT_NOT_OK( - isValid("{$and: [" - " {a: {$geoNear: [0, 0]}}," - " {b: {$near: [0, 0]}}" - "]}", - *qr)); - - // Invalid: >1 GEO_NEAR. - ASSERT_NOT_OK( - isValid("{$and: [" - " {$and: [" - " {a: {$near: [0, 0]}}," - " {b: 1}" - " ]}," - " {$and: [" - " {c: {$near: [0, 0]}}," - " {d: 1}" - " ]}" - "]}", - *qr)); - - // Invalid: GEO_NEAR inside NOR. - ASSERT_NOT_OK( - isValid("{$nor: [" - " {a: {$near: [0, 0]}}," - " {b: 1}" - "]}", - *qr)); - - // Invalid: GEO_NEAR inside OR. - ASSERT_NOT_OK( - isValid("{$or: [" - " {a: {$near: [0, 0]}}," - " {b: 1}" - "]}", - *qr)); -} - -TEST(CanonicalQueryTest, IsValidTextAndGeo) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - ASSERT_OK(qr->validate()); - - // Invalid: TEXT and GEO_NEAR. - ASSERT_NOT_OK(isValid("{$text: {$search: 's'}, a: {$near: [0, 0]}}", *qr)); - - // Invalid: TEXT and GEO_NEAR. - ASSERT_NOT_OK(isValid("{$text: {$search: 's'}, a: {$geoNear: [0, 0]}}", *qr)); - - // Invalid: TEXT and GEO_NEAR. - ASSERT_NOT_OK( - isValid("{$or: [" - " {$text: {$search: 's'}}," - " {a: 1}" - " ]," - " b: {$near: [0, 0]}}", - *qr)); -} - -TEST(CanonicalQueryTest, IsValidTextAndNaturalAscending) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - qr->setSort(fromjson("{$natural: 1}")); - ASSERT_OK(qr->validate()); - - // Invalid: TEXT and {$natural: 1} sort order. - ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); -} - -TEST(CanonicalQueryTest, IsValidTextAndNaturalDescending) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - qr->setSort(fromjson("{$natural: -1}")); - ASSERT_OK(qr->validate()); - - // Invalid: TEXT and {$natural: -1} sort order. - ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); -} - -TEST(CanonicalQueryTest, IsValidTextAndHint) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - qr->setHint(fromjson("{a: 1}")); - ASSERT_OK(qr->validate()); - - // Invalid: TEXT and {$natural: -1} sort order. - ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); -} - -// SERVER-14366 -TEST(CanonicalQueryTest, IsValidGeoNearNaturalSort) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - qr->setSort(fromjson("{$natural: 1}")); - ASSERT_OK(qr->validate()); - - // Invalid: GEO_NEAR and {$natural: 1} sort order. - ASSERT_NOT_OK(isValid("{a: {$near: {$geometry: {type: 'Point', coordinates: [0, 0]}}}}", *qr)); -} - -// SERVER-14366 -TEST(CanonicalQueryTest, IsValidGeoNearNaturalHint) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - qr->setHint(fromjson("{$natural: 1}")); - ASSERT_OK(qr->validate()); - - // Invalid: GEO_NEAR and {$natural: 1} hint. - ASSERT_NOT_OK(isValid("{a: {$near: {$geometry: {type: 'Point', coordinates: [0, 0]}}}}", *qr)); -} - -TEST(CanonicalQueryTest, IsValidTextAndSnapshot) { - // Filter inside QueryRequest is not used. - auto qr = stdx::make_unique<QueryRequest>(nss); - qr->setSnapshot(true); - ASSERT_OK(qr->validate()); - - // Invalid: TEXT and snapshot. - ASSERT_NOT_OK(isValid("{$text: {$search: 's'}}", *qr)); -} - TEST(CanonicalQueryTest, IsValidSortKeyMetaProjection) { QueryTestServiceContext serviceContext; auto opCtx = serviceContext.makeOperationContext(); @@ -350,33 +118,6 @@ TEST(CanonicalQueryTest, IsValidSortKeyMetaProjection) { } } -TEST(CanonicalQueryTest, IsValidNaturalSortIndexHint) { - const bool isExplain = false; - auto qr = assertGet(QueryRequest::makeFromFindCommand( - nss, fromjson("{find: 'testcoll', sort: {$natural: 1}, hint: {a: 1}}"), isExplain)); - - // Invalid: {$natural: 1} sort order and index hint. - ASSERT_NOT_OK(isValid("{}", *qr)); -} - -TEST(CanonicalQueryTest, IsValidNaturalSortNaturalHint) { - const bool isExplain = false; - auto qr = assertGet(QueryRequest::makeFromFindCommand( - nss, fromjson("{find: 'testcoll', sort: {$natural: 1}, hint: {$natural: 1}}"), isExplain)); - - // Valid: {$natural: 1} sort order and {$natural: 1} hint. - ASSERT_OK(isValid("{}", *qr)); -} - -TEST(CanonicalQueryTest, IsValidNaturalSortNaturalHintDifferentDirections) { - const bool isExplain = false; - auto qr = assertGet(QueryRequest::makeFromFindCommand( - nss, fromjson("{find: 'testcoll', sort: {$natural: 1}, hint: {$natural: -1}}"), isExplain)); - - // Invalid: {$natural: 1} sort order and {$natural: -1} hint. - ASSERT_NOT_OK(isValid("{}", *qr)); -} - // // Tests for CanonicalQuery::sortTree // @@ -510,12 +251,19 @@ TEST(CanonicalQueryTest, NormalizeQueryTree) { testNormalizeQuery("{$or: [{b: 1}]}", "{b: 1}"); // Single-child $and elimination. testNormalizeQuery("{$or: [{$and: [{a: 1}]}, {b: 1}]}", "{$or: [{a: 1}, {b: 1}]}"); + // Single-child $_internalSchemaXor elimination. + testNormalizeQuery("{$_internalSchemaXor: [{b: 1}]}", "{b: 1}"); // $or absorbs $or children. testNormalizeQuery("{$or: [{a: 1}, {$or: [{b: 1}, {$or: [{c: 1}]}]}, {d: 1}]}", "{$or: [{a: 1}, {b: 1}, {c: 1}, {d: 1}]}"); // $and absorbs $and children. testNormalizeQuery("{$and: [{$and: [{a: 1}, {b: 1}]}, {c: 1}]}", "{$and: [{a: 1}, {b: 1}, {c: 1}]}"); + // $_internalSchemaXor _does not_ absorb any children. + testNormalizeQuery( + "{$_internalSchemaXor: [{$and: [{a: 1}, {b:1}]}, {$_internalSchemaXor: [{c: 1}, {d: 1}]}]}", + "{$_internalSchemaXor: [{$and: [{a: 1}, {b:1}]}, {$_internalSchemaXor: [{c: 1}, {d: " + "1}]}]}"); // $in with one argument is rewritten as an equality or regex predicate. testNormalizeQuery("{a: {$in: [1]}}", "{a: {$eq: 1}}"); testNormalizeQuery("{a: {$in: [/./]}}", "{a: {$regex: '.'}}"); @@ -524,41 +272,15 @@ TEST(CanonicalQueryTest, NormalizeQueryTree) { testNormalizeQuery("{a: {$in: [/./, 3]}}", "{a: {$in: [/./, 3]}}"); // Child of $elemMatch object expression is normalized. testNormalizeQuery("{a: {$elemMatch: {$or: [{b: 1}]}}}", "{a: {$elemMatch: {b: 1}}}"); -} - -TEST(CanonicalQueryTest, NormalizeWithInPreservesTags) { - BSONObj obj = fromjson("{x: {$in: [1]}}"); - unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj)); - matchExpression->setTag(new IndexTag(2U, 1U, false)); - matchExpression.reset(CanonicalQuery::normalizeTree(matchExpression.release())); - IndexTag* tag = dynamic_cast<IndexTag*>(matchExpression->getTag()); - ASSERT(tag); - ASSERT_EQ(2U, tag->index); -} -TEST(CanonicalQueryTest, NormalizeWithInAndRegexPreservesTags) { - BSONObj obj = fromjson("{x: {$in: [/a.b/]}}"); - unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj)); - matchExpression->setTag(new IndexTag(2U, 1U, false)); - matchExpression.reset(CanonicalQuery::normalizeTree(matchExpression.release())); - IndexTag* tag = dynamic_cast<IndexTag*>(matchExpression->getTag()); - ASSERT(tag); - ASSERT_EQ(2U, tag->index); -} - -TEST(CanonicalQueryTest, NormalizeWithInPreservesCollator) { - CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString); - BSONObj obj = fromjson("{'': 'string'}"); - auto inMatchExpression = stdx::make_unique<InMatchExpression>(); - inMatchExpression->setCollator(&collator); - std::vector<BSONElement> equalities{obj.firstElement()}; - ASSERT_OK(inMatchExpression->setEqualities(std::move(equalities))); - unique_ptr<MatchExpression> matchExpression( - CanonicalQuery::normalizeTree(inMatchExpression.release())); - ASSERT(matchExpression->matchType() == MatchExpression::MatchType::EQ); - EqualityMatchExpression* eqMatchExpression = - static_cast<EqualityMatchExpression*>(matchExpression.get()); - ASSERT_EQ(eqMatchExpression->getCollator(), &collator); + // All three children of $_internalSchemaCond are normalized. + testNormalizeQuery( + "{$_internalSchemaCond: [" + " {$and: [{a: 1}]}," + " {$or: [{b: 1}]}," + " {$_internalSchemaXor: [{c: 1}]}" + "]}", + "{$_internalSchemaCond: [{a: 1}, {b: 1}, {c: 1}]}"); } TEST(CanonicalQueryTest, CanonicalizeFromBaseQuery) { diff --git a/src/mongo/db/query/planner_access.cpp b/src/mongo/db/query/planner_access.cpp index 5a47f4b4470..8494fc320f4 100644 --- a/src/mongo/db/query/planner_access.cpp +++ b/src/mongo/db/query/planner_access.cpp @@ -691,8 +691,7 @@ std::vector<QuerySolutionNode*> QueryPlannerAccess::collapseEquivalentScans( collapsedFilter->add(collapseIntoFetch->filter.release()); // Normalize the filter and add it to 'into'. - collapseIntoFetch->filter.reset( - CanonicalQuery::normalizeTree(collapsedFilter.release())); + collapseIntoFetch->filter = MatchExpression::optimize(std::move(collapsedFilter)); } else { // Scans are not equivalent and can't be collapsed. collapsedScans.push_back(std::move(ownedScans[i])); |