diff options
| -rw-r--r-- | src/mongo/db/matcher/SConscript | 15 | ||||
| -rw-r--r-- | src/mongo/db/matcher/rewrite_expr.cpp | 337 | ||||
| -rw-r--r-- | src/mongo/db/matcher/rewrite_expr.h | 114 | ||||
| -rw-r--r-- | src/mongo/db/matcher/rewrite_expr_test.cpp | 312 | ||||
| -rw-r--r-- | src/mongo/db/pipeline/SConscript | 3 | ||||
| -rw-r--r-- | src/mongo/db/pipeline/expression.h | 12 | ||||
| -rw-r--r-- | src/mongo/db/query/SConscript | 1 |
7 files changed, 780 insertions, 14 deletions
diff --git a/src/mongo/db/matcher/SConscript b/src/mongo/db/matcher/SConscript index f3096cfc1c1..a795325d185 100644 --- a/src/mongo/db/matcher/SConscript +++ b/src/mongo/db/matcher/SConscript @@ -30,6 +30,7 @@ env.Library( target='expressions', source=[ 'expression.cpp', + 'expression_algo.cpp', 'expression_array.cpp', 'expression_expr.cpp', 'expression_geo.cpp', @@ -49,6 +50,7 @@ env.Library( 'matchable.cpp', 'matcher.cpp', 'matcher_type_set.cpp', + 'rewrite_expr.cpp', 'schema/expression_internal_schema_all_elem_match_from_index.cpp', 'schema/expression_internal_schema_allowed_properties.cpp', 'schema/expression_internal_schema_cond.cpp', @@ -133,24 +135,15 @@ env.CppUnitTest( ], ) -env.Library( - target='expression_algo', - source=[ - 'expression_algo.cpp', - ], - LIBDEPS=[ - 'expressions', - ], -) - env.CppUnitTest( target='expression_algo_test', source=[ 'expression_algo_test.cpp', + 'rewrite_expr_test.cpp', ], LIBDEPS=[ '$BUILD_DIR/mongo/db/query/collation/collator_interface_mock', - 'expression_algo', + 'expressions', ], ) diff --git a/src/mongo/db/matcher/rewrite_expr.cpp b/src/mongo/db/matcher/rewrite_expr.cpp new file mode 100644 index 00000000000..d5d0e4605ac --- /dev/null +++ b/src/mongo/db/matcher/rewrite_expr.cpp @@ -0,0 +1,337 @@ +/*- + * 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. + */ + +#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kQuery + +#include "mongo/platform/basic.h" + +#include "mongo/db/matcher/rewrite_expr.h" + +#include "mongo/db/matcher/expression_leaf.h" +#include "mongo/db/matcher/expression_tree.h" +#include "mongo/util/log.h" + +namespace mongo { + +using CmpOp = ExpressionCompare::CmpOp; + +RewriteExpr::RewriteResult RewriteExpr::rewrite( + const boost::intrusive_ptr<Expression>& expression) { + LOG(5) << "Expression prior to rewrite: " << expression->serialize(false); + + RewriteExpr rewriteExpr; + std::unique_ptr<MatchExpression> matchExpression; + + if (auto matchTree = rewriteExpr._rewriteExpression(expression)) { + matchExpression = std::move(matchTree); + LOG(5) << "Post-rewrite MatchExpression: " << matchExpression->toString(); + } + + // TODO SERVER-30989: Optimize via MatchExpression::optimize(). + + return {std::move(matchExpression), + std::move(rewriteExpr._matchExprStringStorage), + std::move(rewriteExpr._matchExprElemStorage)}; +} + +std::unique_ptr<MatchExpression> RewriteExpr::_rewriteExpression( + const boost::intrusive_ptr<Expression>& currExprNode) { + + if (auto expr = dynamic_cast<ExpressionAnd*>(currExprNode.get())) { + return _rewriteAndExpression(expr); + } else if (auto expr = dynamic_cast<ExpressionOr*>(currExprNode.get())) { + return _rewriteOrExpression(expr); + } else if (auto expr = dynamic_cast<ExpressionCompare*>(currExprNode.get())) { + return _rewriteComparisonExpression(expr); + } else if (auto expr = dynamic_cast<ExpressionIn*>(currExprNode.get())) { + return _rewriteInExpression(expr); + } + + return nullptr; +} + +std::unique_ptr<MatchExpression> RewriteExpr::_rewriteAndExpression( + const boost::intrusive_ptr<ExpressionAnd>& currExprNode) { + + auto andMatch = stdx::make_unique<AndMatchExpression>(); + + for (auto&& child : currExprNode->getOperandList()) { + if (auto childMatch = _rewriteExpression(child)) { + andMatch->add(childMatch.release()); + } + } + + if (andMatch->numChildren() > 0) { + return std::move(andMatch); + } + + return nullptr; +} + +std::unique_ptr<MatchExpression> RewriteExpr::_rewriteOrExpression( + const boost::intrusive_ptr<ExpressionOr>& currExprNode) { + + auto orMatch = stdx::make_unique<OrMatchExpression>(); + for (auto&& child : currExprNode->getOperandList()) { + if (auto childExpr = _rewriteExpression(child)) { + orMatch->add(childExpr.release()); + } else { + // If any child cannot be rewritten to a MatchExpression then we must abandon adding + // this $or clause. + return nullptr; + } + } + + if (orMatch->numChildren() > 0) { + return std::move(orMatch); + } + + return nullptr; +} + +std::unique_ptr<MatchExpression> RewriteExpr::_rewriteInExpression( + const boost::intrusive_ptr<ExpressionIn>& currExprNode) { + + if (!_isValidMatchIn(currExprNode)) { + return nullptr; + } + + const auto& operandList = currExprNode->getOperandList(); + ExpressionFieldPath* lhsExpression = dynamic_cast<ExpressionFieldPath*>(operandList[0].get()); + BSONArrayBuilder arrBuilder; + + if (ExpressionArray* rhsArray = dynamic_cast<ExpressionArray*>(operandList[1].get())) { + for (auto&& item : rhsArray->getOperandList()) { + auto exprConst = dynamic_cast<ExpressionConstant*>(item.get()); + arrBuilder << exprConst->getValue(); + } + } else { + auto exprConst = dynamic_cast<ExpressionConstant*>(operandList[1].get()); + invariant(exprConst); + + auto valueArr = exprConst->getValue(); + invariant(valueArr.isArray()); + + for (auto val : valueArr.getArray()) { + arrBuilder << val; + } + } + + _matchExprStringStorage.push_back(lhsExpression->getFieldPath().tail().fullPath()); + const auto& fieldPath = _matchExprStringStorage.back(); + + BSONObj inValues = arrBuilder.obj(); + _matchExprElemStorage.push_back(inValues); + std::vector<BSONElement> elementList; + inValues.elems(elementList); + + auto matchInExpr = stdx::make_unique<InMatchExpression>(); + uassertStatusOK(matchInExpr->init(fieldPath)); + uassertStatusOK(matchInExpr->setEqualities(elementList)); + + return std::move(matchInExpr); +} + +std::unique_ptr<MatchExpression> RewriteExpr::_rewriteComparisonExpression( + const boost::intrusive_ptr<ExpressionCompare>& currExprNode) { + + if (!_isValidMatchComparison(currExprNode)) { + return nullptr; + } + + return _buildComparisonMatchExpression(currExprNode); +} + +std::unique_ptr<MatchExpression> RewriteExpr::_buildComparisonMatchExpression( + const boost::intrusive_ptr<ExpressionCompare>& expr) { + const auto& operandList = expr->getOperandList(); + invariant(operandList.size() == 2); + + ExpressionFieldPath* lhs{nullptr}; + ExpressionConstant* rhs{nullptr}; + CmpOp cmpOperator = expr->getOp(); + + // Build left-hand and right-hand MatchExpression components and modify the operator if + // required. + if ((lhs = dynamic_cast<ExpressionFieldPath*>(operandList[0].get()))) { + rhs = dynamic_cast<ExpressionConstant*>(operandList[1].get()); + invariant(rhs); + } else { + lhs = dynamic_cast<ExpressionFieldPath*>(operandList[1].get()); + rhs = dynamic_cast<ExpressionConstant*>(operandList[0].get()); + invariant(lhs && rhs); + + // When converting an Expression that has a field path on the RHS we will need to move to + // the LHS. This may require an inversion of the operator used as well. + // For example: {$gt: [3, '$foo']} => {foo: {$lt: 3}} + switch (cmpOperator) { + case ExpressionCompare::CmpOp::GT: + cmpOperator = CmpOp::LT; + break; + case ExpressionCompare::CmpOp::GTE: + cmpOperator = CmpOp::LTE; + break; + case ExpressionCompare::CmpOp::LT: + cmpOperator = CmpOp::GT; + break; + case ExpressionCompare::CmpOp::LTE: + cmpOperator = CmpOp::GTE; + break; + default: // No need to convert EQ or NE. CMP is not valid for rewrite. + break; + } + } + + // Build argument for ComparisonMatchExpression. + const auto fieldPath = lhs->getFieldPath().tail(); + BSONObjBuilder bob; + bob << fieldPath.fullPath() << rhs->getValue(); + auto cmpObj = bob.obj(); + _matchExprElemStorage.push_back(cmpObj); + + return _buildComparisonMatchExpression(cmpOperator, cmpObj.firstElement()); +} + +std::unique_ptr<MatchExpression> RewriteExpr::_buildComparisonMatchExpression( + ExpressionCompare::CmpOp comparisonOp, BSONElement fieldAndValue) { + + std::unique_ptr<ComparisonMatchExpression> compMatchExpr; + std::unique_ptr<NotMatchExpression> notMatchExpr; + + switch (comparisonOp) { + case ExpressionCompare::EQ: { + compMatchExpr = stdx::make_unique<EqualityMatchExpression>(); + break; + } + case ExpressionCompare::NE: { + compMatchExpr = stdx::make_unique<EqualityMatchExpression>(); + notMatchExpr = stdx::make_unique<NotMatchExpression>(); + break; + } + case ExpressionCompare::GT: { + compMatchExpr = stdx::make_unique<GTMatchExpression>(); + break; + } + case ExpressionCompare::GTE: { + compMatchExpr = stdx::make_unique<GTEMatchExpression>(); + break; + } + case ExpressionCompare::LT: { + compMatchExpr = stdx::make_unique<LTMatchExpression>(); + break; + } + case ExpressionCompare::LTE: { + compMatchExpr = stdx::make_unique<LTEMatchExpression>(); + break; + } + default: + MONGO_UNREACHABLE; + } + + uassertStatusOK(compMatchExpr->init(fieldAndValue.fieldName(), fieldAndValue)); + + if (notMatchExpr) { + uassertStatusOK(notMatchExpr->init(compMatchExpr.release())); + return std::move(notMatchExpr); + } + + return std::move(compMatchExpr); +} + +bool RewriteExpr::_isValidFieldPath(const FieldPath& fieldPath) const { + // We can only rewrite field paths that contain ROOT plus a field path of length 1. Expression + // and MatchExpression treat dotted paths in a different manner and will not produce the same + // results. + return fieldPath.getPathLength() == 2; +} + +bool RewriteExpr::_isValidMatchIn(const boost::intrusive_ptr<ExpressionIn>& expr) const { + const auto& operandList = expr->getOperandList(); + + auto fieldPathExpr = dynamic_cast<ExpressionFieldPath*>(operandList[0].get()); + if (!fieldPathExpr || !fieldPathExpr->isRootFieldPath()) { + // A left-hand-side local document field path is required to translate to match. + return false; + } + + if (!_isValidFieldPath(fieldPathExpr->getFieldPath())) { + return false; + } + + if (ExpressionArray* rhsArray = dynamic_cast<ExpressionArray*>(operandList[1].get())) { + for (auto&& item : rhsArray->getOperandList()) { + if (!dynamic_cast<ExpressionConstant*>(item.get())) { + // All array values must be constant. + return false; + } + } + + return true; + } + + if (ExpressionConstant* constArr = dynamic_cast<ExpressionConstant*>(operandList[1].get())) { + return constArr->getValue().isArray(); + } + + return false; +} + +bool RewriteExpr::_isValidMatchComparison( + const boost::intrusive_ptr<ExpressionCompare>& expression) const { + if (expression->getOp() == ExpressionCompare::CMP) { + return false; + } + + const auto& operandList = expression->getOperandList(); + bool hasFieldPath = false; + + for (auto operand : operandList) { + if (auto exprFieldPath = dynamic_cast<ExpressionFieldPath*>(operand.get())) { + if (!exprFieldPath->isRootFieldPath()) { + // This field path refers to a variable rather than a local document field path. + return false; + } + + if (hasFieldPath) { + // Match does not allow for more than one local document field path. + return false; + } + + if (!_isValidFieldPath(exprFieldPath->getFieldPath())) { + return false; + } + + hasFieldPath = true; + } else if (!dynamic_cast<ExpressionConstant*>(operand.get())) { + return false; + } + } + + return hasFieldPath; +} +} // namespace mongo diff --git a/src/mongo/db/matcher/rewrite_expr.h b/src/mongo/db/matcher/rewrite_expr.h new file mode 100644 index 00000000000..ec5be2c2641 --- /dev/null +++ b/src/mongo/db/matcher/rewrite_expr.h @@ -0,0 +1,114 @@ +/*- + * 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. + */ + +#pragma once + +#include <string> +#include <vector> + +#include "mongo/db/matcher/expression.h" +#include "mongo/db/matcher/expression_leaf.h" +#include "mongo/db/matcher/expression_tree.h" +#include "mongo/db/pipeline/expression.h" + +namespace mongo { + +class RewriteExpr final { +public: + /** + * Holds the result of an Expression rewrite operation. + */ + class RewriteResult final { + public: + RewriteResult(std::unique_ptr<MatchExpression> matchExpression, + std::vector<std::string> matchExprStringStorage, + std::vector<BSONObj> matchExprElemStorage) + : _matchExpression(std::move(matchExpression)), + _matchExprStringStorage(std::move(matchExprStringStorage)), + _matchExprElemStorage(std::move(matchExprElemStorage)) {} + + const MatchExpression* matchExpression() const { + return _matchExpression.get(); + } + + private: + std::unique_ptr<MatchExpression> _matchExpression; + + // MatchExpression nodes are constructed with BSONElement and StringData arguments that are + // externally owned and expected to outlive the MatchExpression. '_matchExprStringStorage' + // and '_matchExprElemStorage' hold the underlying std::string and BSONObj storage for these + // arguments. + std::vector<std::string> _matchExprStringStorage; + std::vector<BSONObj> _matchExprElemStorage; + }; + + /** + * Attempts to construct a MatchExpression that will match against either an identical set or a + * superset of the documents matched by 'expr'. Returns the MatchExpression as a RewriteResult. + * If a rewrite is not possible, RewriteResult::matchExpression() will return a nullptr. + */ + static RewriteResult rewrite(const boost::intrusive_ptr<Expression>& expr); + +private: + // Returns rewritten MatchExpression or null unique_ptr if not rewritable. + std::unique_ptr<MatchExpression> _rewriteExpression( + const boost::intrusive_ptr<Expression>& currExprNode); + + // Returns rewritten MatchExpression or null unique_ptr if not rewritable. + std::unique_ptr<MatchExpression> _rewriteAndExpression( + const boost::intrusive_ptr<ExpressionAnd>& currExprNode); + + // Returns rewritten MatchExpression or null unique_ptr if not rewritable. + std::unique_ptr<MatchExpression> _rewriteOrExpression( + const boost::intrusive_ptr<ExpressionOr>& currExprNode); + + // Returns rewritten MatchExpression or null unique_ptr if not rewritable. + std::unique_ptr<MatchExpression> _rewriteInExpression( + const boost::intrusive_ptr<ExpressionIn>& currExprNode); + + // Returns rewritten MatchExpression or null unique_ptr if not rewritable. + std::unique_ptr<MatchExpression> _rewriteComparisonExpression( + const boost::intrusive_ptr<ExpressionCompare>& currExprNode); + + bool _isValidMatchComparison(const boost::intrusive_ptr<ExpressionCompare>& expr) const; + + bool _isValidMatchIn(const boost::intrusive_ptr<ExpressionIn>& expr) const; + + bool _isValidFieldPath(const FieldPath& fieldPath) const; + + std::unique_ptr<MatchExpression> _buildComparisonMatchExpression( + const boost::intrusive_ptr<ExpressionCompare>& expr); + + std::unique_ptr<MatchExpression> _buildComparisonMatchExpression( + ExpressionCompare::CmpOp comparisonOp, BSONElement fieldAndValue); + + std::vector<BSONObj> _matchExprElemStorage; + std::vector<std::string> _matchExprStringStorage; +}; + +} // namespace mongo diff --git a/src/mongo/db/matcher/rewrite_expr_test.cpp b/src/mongo/db/matcher/rewrite_expr_test.cpp new file mode 100644 index 00000000000..bb86ae761f7 --- /dev/null +++ b/src/mongo/db/matcher/rewrite_expr_test.cpp @@ -0,0 +1,312 @@ +/** + * 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/platform/basic.h" + +#include "mongo/bson/json.h" +#include "mongo/db/matcher/rewrite_expr.h" +#include "mongo/db/pipeline/expression_context_for_test.h" +#include "mongo/unittest/unittest.h" + +namespace mongo { +namespace { + +/** + * Attempts to rewrite an Expression ('expr') and confirms that the resulting + * MatchExpression ('expectedMatch') is as expected. As it is not always possible to completely + * rewrite an Expression to MatchExpression the result can represent one of: + * - A full rewrite + * - A partial rewrite matching on a superset of documents + * - No MatchExpression (when full or superset rewrite is not possible) + */ +void testExprRewrite(BSONObj expr, BSONObj expectedMatch) { + boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest()); + + auto expression = + Expression::parseOperand(expCtx, expr.firstElement(), expCtx->variablesParseState); + + auto result = RewriteExpr::rewrite(expression); + + // Confirm expected match. + if (!expectedMatch.isEmpty()) { + ASSERT(result.matchExpression()); + BSONObjBuilder bob; + result.matchExpression()->serialize(&bob); + ASSERT_BSONOBJ_EQ(expectedMatch, bob.obj()); + } else { + ASSERT_FALSE(result.matchExpression()); + } +} + +// +// Expressions that can be fully translated to MatchExpression. +// +TEST(RewriteExpr, EqWithOneFieldPathRewritesToMatch) { + BSONObj expr = fromjson("{$expr: {$eq: ['$x', 3]}}"); + const BSONObj expectedMatch = fromjson("{x: {$eq: 3}}"); + testExprRewrite(expr, expectedMatch); + + expr = fromjson("{$expr: {$eq: [3, '$x']}}"); + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, NeWithOneFieldPathRewritesToMatch) { + BSONObj expr = fromjson("{$expr: {$ne: ['$x', 3]}}"); + BSONObj expectedMatch = fromjson("{$nor: [{x: {$eq: 3}}]}"); + testExprRewrite(expr, expectedMatch); + + expr = fromjson("{$expr: {$ne: [3, '$x']}}"); + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, GtWithOneFieldPathRewritesToMatch) { + BSONObj expr = fromjson("{$expr: {$gt: ['$x', 3]}}"); + BSONObj expectedMatch = fromjson("{x: {$gt: 3}}"); + testExprRewrite(expr, expectedMatch); + + expr = fromjson("{$expr: {$gt: [3, '$x']}}"); + expectedMatch = fromjson("{x: {$lt: 3}}"); + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, GteWithOneFieldPathRewritesToMatch) { + BSONObj expr = fromjson("{$expr: {$gte: ['$x', 3]}}"); + BSONObj expectedMatch = fromjson("{x: {$gte: 3}}"); + testExprRewrite(expr, expectedMatch); + + expr = fromjson("{$expr: {$gte: [3, '$x']}}"); + expectedMatch = fromjson("{x: {$lte: 3}}"); + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, LtWithOneFieldPathRewritesToMatch) { + BSONObj expr = fromjson("{$expr: {$lt: ['$x', 3]}}"); + BSONObj expectedMatch = fromjson("{x: {$lt: 3}}"); + testExprRewrite(expr, expectedMatch); + + expr = fromjson("{$expr: {$lt: [3, '$x']}}"); + expectedMatch = fromjson("{x: {$gt: 3}}"); + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, LteWithOneFieldPathRewritesToMatch) { + BSONObj expr = fromjson("{$expr: {$lte: ['$x', 3]}}"); + BSONObj expectedMatch = fromjson("{x: {$lte: 3}}"); + testExprRewrite(expr, expectedMatch); + + expr = fromjson("{$expr: {$lte: [3, '$x']}}"); + expectedMatch = fromjson("{x: {$gte: 3}}"); + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, AndRewritesToMatch) { + const BSONObj expr = fromjson("{$expr: {$and: [{$eq: ['$x', 3]}, {$ne: ['$y', 4]}]}}"); + const BSONObj expectedMatch = fromjson("{$and: [{x: {$eq: 3}}, {$nor: [{y: {$eq: 4}}]}]}"); + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, OrRewritesToMatch) { + const BSONObj expr = fromjson("{$expr: {$or: [{$lte: ['$x', 3]}, {$gte: ['$y', 4]}]}}"); + const BSONObj expectedMatch = fromjson("{$or: [{x: {$lte: 3}}, {y: {$gte: 4}}]}"); + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, AndNestedWithinOrRewritesToMatch) { + const BSONObj expr = fromjson( + "{$expr: {$or: [{$and: [{$eq: ['$x', 3]}, {$gt: ['$z', 5]}]}, {$lt: ['$y', 4]}]}}"); + const BSONObj expectedMatch = + fromjson("{$or: [{$and: [{x: {$eq: 3}}, {z: {$gt: 5}}]}, {y: {$lt: 4}}]}"); + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, OrNestedWithinAndRewritesToMatch) { + const BSONObj expr = fromjson( + "{$expr: {$and: [{$or: [{$eq: ['$x', 3]}, {$eq: ['$z', 5]}]}, {$eq: ['$y', 4]}]}}"); + const BSONObj expectedMatch = + fromjson("{$and: [{$or: [{x: {$eq: 3}}, {z: {$eq: 5}}]}, {y: {$eq: 4}}]}"); + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, InWithLhsFieldPathRewritesToMatch) { + const BSONObj expr = fromjson("{$expr: {$in: ['$x', [1, 2, 3]]}}"); + const BSONObj expectedMatch = fromjson("{x: {$in: [1, 2, 3]}}"); + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, InWithLhsFieldPathAndArrayAsConstRewritesToMatch) { + const BSONObj expr = fromjson("{$expr: {$in: ['$x', {$const: [1, 2, 3]}]}}"); + const BSONObj expectedMatch = fromjson("{x: {$in: [1, 2, 3]}}"); + + testExprRewrite(expr, expectedMatch); +} + + +// +// Expressions that cannot be rewritten (partially or fully) to MatchExpression. +// + +TEST(RewriteExpr, CmpDoesNotRewriteToMatch) { + const BSONObj expr = fromjson("{$expr: {$cmp: ['$x', 3]}}"); + const BSONObj expectedMatch; + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, ConstantExpressionDoesNotRewriteToMatch) { + const BSONObj expr = fromjson("{$expr: 1}"); + const BSONObj expectedMatch; + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, EqWithTwoFieldPathsDoesNotRewriteToMatch) { + const BSONObj expr = fromjson("{$expr: {$eq: ['$x', '$y']}}"); + const BSONObj expectedMatch; + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, EqWithTwoConstantsDoesNotRewriteToMatch) { + const BSONObj expr = fromjson("{$expr: {$eq: [3, 4]}}"); + const BSONObj expectedMatch; + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, EqWithDottedFieldPathDoesNotRewriteToMatch) { + const BSONObj expr = fromjson("{$expr: {$eq: ['$x.y', 3]}}"); + const BSONObj expectedMatch; + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, InWithDottedFieldPathDoesNotRewriteToMatch) { + const BSONObj expr = fromjson("{$expr: {$in: ['$x.y', [1, 2, 3]]}}"); + const BSONObj expectedMatch; + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, AndWithoutMatchSubtreeDoesNotRewriteToMatch) { + const BSONObj expr = fromjson("{$expr: {$and: [{$eq: ['$w', '$x']}, {$eq: ['$y', '$z']}]}}"); + const BSONObj expectedMatch; + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, OrWithDistinctMatchAndNonMatchSubTreeDoesNotRewriteToMatch) { + const BSONObj expr = fromjson("{$expr: {$or: [{$eq: ['$x', 1]}, {$eq: ['$y', '$z']}]}}"); + const BSONObj expectedMatch; + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, InWithoutLhsFieldPathDoesNotRewriteToMatch) { + const BSONObj expr = fromjson("{$expr: {$in: [2, [1, 2, 3]]}}"); + const BSONObj expectedMatch; + + testExprRewrite(expr, expectedMatch); +} + +// +// Expressions that can be partially rewritten to MatchExpression. Partial rewrites are expected to +// match against a superset of documents. +// + +TEST(RewriteExpr, NestedAndWithTwoFieldPathsWithinOrPartiallyRewriteToMatch) { + const BSONObj expr = fromjson( + "{$expr: {$or: [{$and: [{$eq: ['$x', '$w']}, {$eq: ['$z', 5]}]}, {$eq: ['$y', 4]}]}}"); + const BSONObj expectedMatch = fromjson("{$or: [{$and: [{z: {$eq: 5}}]}, {y: {$eq: 4}}]}"); + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, AndWithDistinctMatchAndNonMatchSubTreeSplitsOnRewrite) { + const BSONObj expr = fromjson("{$expr: {$and: [{$eq: ['$x', 1]}, {$eq: ['$y', '$z']}]}}"); + const BSONObj expectedMatch = fromjson("{$and: [{x: {$eq: 1}}]}"); + + testExprRewrite(expr, expectedMatch); +} + +// Rewrites an Expression that contains a mix of rewritable and non-rewritable statements to a +// MatchExpression superset. +TEST(RewriteExpr, ComplexSupersetMatchRewritesToMatchSuperset) { + const BSONObj expr = fromjson( + "{" + " $expr: {" + " $and: [" + " {$eq: ['$a', 1]}," + " {$eq: ['$b', '$c']}," + " {" + " $or: [" + " {$eq: ['$d', 1]}," + " {$eq: ['$e', 3]}," + " {" + " $and: [" + " {$eq: ['$f', 1]}," + " {$eq: ['$g', '$h']}," + " {$or: [{$eq: ['$i', 3]}, {$eq: ['$j', '$k']}]}" + " ]" + " }" + " ]" + " }" + " ]" + " }" + "}"); + const BSONObj expectedMatch = fromjson( + "{" + " $and: [" + " {a: {$eq: 1}}," + " {" + " $or: [" + " {d: {$eq: 1}}," + " {e: {$eq: 3}}," + " {$and: [{f: {$eq: 1}}]}" + " ]" + " }" + " ]" + "}"); + + testExprRewrite(expr, expectedMatch); +} + +TEST(RewriteExpr, OrWithAndContainingMatchAndNonMatchChildPartiallyRewritesToMatch) { + const BSONObj expr = fromjson( + "{$expr: {$or: [{$eq: ['$x', 3]}, {$and: [{$eq: ['$y', 4]}, {$eq: ['$y', '$z']}]}]}}"); + const BSONObj expectedMatch = fromjson("{$or: [{x: {$eq: 3}}, {$and: [{y: {$eq: 4}}]}]}"); + + testExprRewrite(expr, expectedMatch); +} + +} // namespace +} // namespace mongo diff --git a/src/mongo/db/pipeline/SConscript b/src/mongo/db/pipeline/SConscript index 6266ae8a199..4d249a56456 100644 --- a/src/mongo/db/pipeline/SConscript +++ b/src/mongo/db/pipeline/SConscript @@ -270,7 +270,6 @@ docSourceEnv.Library( '$BUILD_DIR/mongo/db/bson/dotted_path_support', '$BUILD_DIR/mongo/db/index/key_generator', '$BUILD_DIR/mongo/db/logical_session_cache_impl', - '$BUILD_DIR/mongo/db/matcher/expression_algo', '$BUILD_DIR/mongo/db/matcher/expressions', '$BUILD_DIR/mongo/db/pipeline/lite_parsed_document_source', '$BUILD_DIR/mongo/db/repl/oplog_entry', @@ -439,7 +438,7 @@ env.Library( LIBDEPS=[ 'expression', 'field_path', - '$BUILD_DIR/mongo/db/matcher/expression_algo', + '$BUILD_DIR/mongo/db/matcher/expressions', ] ) diff --git a/src/mongo/db/pipeline/expression.h b/src/mongo/db/pipeline/expression.h index 6532be87fb0..ed95bcdc2f1 100644 --- a/src/mongo/db/pipeline/expression.h +++ b/src/mongo/db/pipeline/expression.h @@ -268,6 +268,10 @@ public: BSONElement bsonExpr, const VariablesParseState& vps); + const ExpressionVector& getOperandList() const { + return vpOperand; + } + protected: explicit ExpressionNary(const boost::intrusive_ptr<ExpressionContext>& expCtx) : Expression(expCtx) {} @@ -785,6 +789,10 @@ public: Value evaluate(const Document& root) const final; const char* getOpName() const final; + CmpOp getOp() const { + return cmpOp; + } + static boost::intrusive_ptr<Expression> parse( const boost::intrusive_ptr<ExpressionContext>& expCtx, BSONElement bsonExpr, @@ -1032,6 +1040,10 @@ public: class ExpressionFieldPath final : public Expression { public: + bool isRootFieldPath() const { + return _variable == Variables::kRootId; + } + boost::intrusive_ptr<Expression> optimize() final; Value evaluate(const Document& root) const final; Value serialize(bool explain) const final; diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript index 55304b39f7a..c468639bf77 100644 --- a/src/mongo/db/query/SConscript +++ b/src/mongo/db/query/SConscript @@ -37,7 +37,6 @@ env.Library( "$BUILD_DIR/mongo/db/bson/dotted_path_support", "$BUILD_DIR/mongo/db/index/expression_params", "$BUILD_DIR/mongo/db/index_names", - "$BUILD_DIR/mongo/db/matcher/expression_algo", "$BUILD_DIR/mongo/db/matcher/expressions", "$BUILD_DIR/mongo/db/server_parameters", "collation/collator_interface", |