diff options
| -rw-r--r-- | src/mongo/db/matcher/expression_algo.cpp | 330 | ||||
| -rw-r--r-- | src/mongo/db/matcher/expression_algo.h | 47 | ||||
| -rw-r--r-- | src/mongo/db/matcher/expression_algo_test.cpp | 418 | ||||
| -rw-r--r-- | src/mongo/db/query/get_executor.cpp | 2 | ||||
| -rw-r--r-- | src/mongo/db/query/plan_cache_indexability.cpp | 2 |
5 files changed, 386 insertions, 413 deletions
diff --git a/src/mongo/db/matcher/expression_algo.cpp b/src/mongo/db/matcher/expression_algo.cpp index 9268db2dd00..1e21874a4e1 100644 --- a/src/mongo/db/matcher/expression_algo.cpp +++ b/src/mongo/db/matcher/expression_algo.cpp @@ -28,264 +28,176 @@ * it in the license file. */ -#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kDefault - #include "mongo/platform/basic.h" #include "mongo/db/matcher/expression.h" #include "mongo/db/matcher/expression_leaf.h" -#include "mongo/util/log.h" - -//#define DDD(x) log() << x -#define DDD(x) namespace mongo { - namespace { - - bool _pathMatches(const LeafMatchExpression* left, - const MatchExpression* bar) { - invariant(left); - invariant(bar); - const LeafMatchExpression* right = dynamic_cast<const LeafMatchExpression*>(bar); - if (!right) - return false; - - return left->path() == right->path(); +namespace { + + bool isComparisonMatchExpression(const MatchExpression* expr) { + switch (expr->matchType()) { + case MatchExpression::LT: + case MatchExpression::LTE: + case MatchExpression::EQ: + case MatchExpression::GTE: + case MatchExpression::GT: + return true; + default: + return false; } + } - bool _typeAndPathCompatable(const ComparisonMatchExpression* left, - const ComparisonMatchExpression* right) { - if (!_pathMatches(left, right)) - return false; - - if (left->getData().canonicalType() != right->getData().canonicalType()) - return false; - + bool supportsEquality(const ComparisonMatchExpression* expr) { + switch (expr->matchType()) { + case MatchExpression::LTE: + case MatchExpression::EQ: + case MatchExpression::GTE: return true; + default: + return false; } + } + /** + * Returns true if the documents matched by 'lhs' are a subset of the documents matched by + * 'rhs', i.e. a document matched by 'lhs' must also be matched by 'rhs', and false otherwise. + */ + bool _isSubsetOf(const ComparisonMatchExpression* lhs, const ComparisonMatchExpression* rhs) { + // An expression can only be a subset of another if they are comparing the same field. + if (lhs->path() != rhs->path()) { + return false; + } - bool _isRedundantEQHelp(const ComparisonMatchExpression* left, - const MatchExpression* bar, - bool isLessThan, - bool equalOk) { - const ComparisonMatchExpression* right = - dynamic_cast<const ComparisonMatchExpression*>(bar); - invariant(right); + const BSONElement lhsData = lhs->getData(); + const BSONElement rhsData = rhs->getData(); - if (!_typeAndPathCompatable(left, right)) - return false; + if (lhsData.canonicalType() != rhsData.canonicalType()) { + return false; + } - int cmp = left->getData().woCompare(right->getData(), false); - if (isLessThan) { - if (cmp < 0) - return true; - if (cmp == 0) - return equalOk; - return false; + // Special case the handling for NaN values: NaN compares equal only to itself. + if (std::isnan(lhsData.numberDouble()) || std::isnan(rhsData.numberDouble())) { + if (supportsEquality(lhs) && supportsEquality(rhs)) { + return std::isnan(lhsData.numberDouble()) && std::isnan(rhsData.numberDouble()); } - - if (cmp > 0) - return true; - if (cmp == 0) - return equalOk; return false; } - /** - * @param foo is a literal something that has to match exactly - * @return if the expression bar guarantees returning any document matching foo - */ - bool isRedundantEQ(const MatchExpression* foo, - const MatchExpression* bar) { - const ComparisonMatchExpression* equal = - dynamic_cast<const ComparisonMatchExpression*>(foo); - invariant(equal); - - DDD("isRedundantEQ"); + int cmp = compareElementValues(lhsData, rhsData); - switch(bar->matchType()) { - case MatchExpression::EQ: - // would be handled elsewhere - return false; + // Check whether the two expressions are equivalent. + if (lhs->matchType() == rhs->matchType() && cmp == 0) { + return true; + } + switch (rhs->matchType()) { + case MatchExpression::LT: + case MatchExpression::LTE: + switch (lhs->matchType()) { case MatchExpression::LT: - return _isRedundantEQHelp(equal, bar, true, false); case MatchExpression::LTE: - return _isRedundantEQHelp(equal, bar, true, true); - + case MatchExpression::EQ: + if (rhs->matchType() == MatchExpression::LTE) { + return cmp <= 0; + } + return cmp < 0; + default: + return false; + } + case MatchExpression::GT: + case MatchExpression::GTE: + switch (lhs->matchType()) { case MatchExpression::GT: - return _isRedundantEQHelp(equal, bar, false, false); case MatchExpression::GTE: - return _isRedundantEQHelp(equal, bar, false, true); - - case MatchExpression::EXISTS: { - switch (equal->getData().type()) { - case jstNULL: - case Undefined: - case EOO: - return false; - default: - return _pathMatches(equal, bar); + case MatchExpression::EQ: + if (rhs->matchType() == MatchExpression::GTE) { + return cmp >= 0; } - } - + return cmp > 0; default: return false; } + default: + return false; } + } - bool isRedundantLT(const MatchExpression* foo, - const MatchExpression* bar, - bool equalOk) { - const ComparisonMatchExpression* left = - dynamic_cast<const ComparisonMatchExpression*>(foo); - invariant(left); - - - if(bar->matchType() == MatchExpression::LT || - bar->matchType() == MatchExpression::LTE ) { - - const ComparisonMatchExpression* right = - dynamic_cast<const ComparisonMatchExpression*>(bar); - invariant(right); - - if (!_typeAndPathCompatable(left, right)) - return false; - - int cmp = left->getData().woCompare(right->getData(), false); - if (cmp == 0) { - if(bar->matchType() == MatchExpression::LTE) - return true; - if(!equalOk) - return true; - return false; - } - return cmp < 0; - } - else if(bar->matchType() == MatchExpression::EXISTS) { - return _pathMatches(left, bar); - } - + /** + * Returns true if the documents matched by 'lhs' are a subset of the documents matched by + * 'rhs', i.e. a document matched by 'lhs' must also be matched by 'rhs', and false otherwise. + */ + bool _isSubsetOf(const MatchExpression* lhs, const ExistsMatchExpression* rhs) { + // An expression can only be a subset of another if they are comparing the same field. + if (lhs->path() != rhs->path()) { return false; } - bool isRedundantGT(const MatchExpression* foo, - const MatchExpression* bar, - bool equalOk) { - const ComparisonMatchExpression* left = - dynamic_cast<const ComparisonMatchExpression*>(foo); - invariant(left); - - - if(bar->matchType() == MatchExpression::GT || - bar->matchType() == MatchExpression::GTE ) { - - const ComparisonMatchExpression* right = - dynamic_cast<const ComparisonMatchExpression*>(bar); - invariant(right); - - if (!_typeAndPathCompatable(left, right)) - return false; - - int cmp = left->getData().woCompare(right->getData(), false); - if (cmp == 0) { - if(bar->matchType() == MatchExpression::GTE) - return true; - if(!equalOk) - return true; - return false; - } - return cmp > 0; - } - else if(bar->matchType() == MatchExpression::EXISTS) { - return _pathMatches(left, bar); - } + if (lhs->matchType() == MatchExpression::TYPE_OPERATOR) { + return true; + } - return false; + if (isComparisonMatchExpression(lhs)) { + const ComparisonMatchExpression* cme = + static_cast<const ComparisonMatchExpression*>(lhs); + // CompareMatchExpression::init() prohibits creating a match expression with EOO or + // Undefined types, so only need to ensure that the value is not of type jstNULL. + return cme->getData().type() != jstNULL; } + // TODO: Add support for using $exists with other query operators. + return false; } +} // namespace +namespace expression { - namespace expression { - - bool isClauseRedundant(const MatchExpression* foo, - const MatchExpression* bar) { + bool isSubsetOf(const MatchExpression* lhs, const MatchExpression* rhs) { + invariant(lhs); + invariant(rhs); - if (bar == NULL || - foo == bar) { - return true; - } - if (foo == NULL) { - return false; - } - - - DDD("isClauseRedundant\n" - << "foo: " << foo->toString() - << "bar: " << bar->toString()); - - if (foo->equivalent(bar)) { - DDD("t equivalent!"); - return true; - } + if (lhs->equivalent(rhs)) { + return true; + } - switch(foo->matchType()) { - case MatchExpression::AND: { - for (size_t i = 0; i < foo->numChildren(); i++ ) { - if(isClauseRedundant(foo->getChild(i), bar)) { - return true; - } + if (rhs->matchType() == MatchExpression::AND) { + // 'lhs' must be a subset of each clause of 'rhs'. + for (size_t i = 0; i < rhs->numChildren(); i++) { + if (!isSubsetOf(lhs, rhs->getChild(i))) { + return false; } + } + return true; + } - if (bar->matchType() == MatchExpression::AND) { - // everything in bar has to appear in foo - for (size_t i = 0; i < bar->numChildren(); i++ ) { - if(!isClauseRedundant(foo, bar->getChild(i))) { - return false; - } - } + if (lhs->matchType() == MatchExpression::AND) { + // At least one clause of 'lhs' must be a subset of 'rhs'. + for (size_t i = 0; i < lhs->numChildren(); i++) { + if (isSubsetOf(lhs->getChild(i), rhs)) { return true; } - - return false; - } - case MatchExpression::OR: { - // TODO: $or each clause has to be redundant - return false; } + return false; + } - case MatchExpression::EQ: - return isRedundantEQ(foo, bar); - - case MatchExpression::LT: - return isRedundantLT(foo, bar, false); - case MatchExpression::LTE: - return isRedundantLT(foo, bar, true); - - case MatchExpression::GT: - return isRedundantGT(foo, bar, false); - case MatchExpression::GTE: - return isRedundantGT(foo, bar, true); - - case MatchExpression::TYPE_OPERATOR: { - if (bar->matchType() != MatchExpression::EXISTS) { - return false; - } - - const TypeMatchExpression* a = dynamic_cast<const TypeMatchExpression*>(foo); - const ExistsMatchExpression* b = dynamic_cast<const ExistsMatchExpression*>(bar); - - return a->path() == b->path(); - } + // TODO: Add support for $or in queries. + if (lhs->matchType() == MatchExpression::OR) { + return false; + } - default: - return false; - } + if (isComparisonMatchExpression(lhs) && isComparisonMatchExpression(rhs)) { + return _isSubsetOf(static_cast<const ComparisonMatchExpression*>(lhs), + static_cast<const ComparisonMatchExpression*>(rhs)); + } - return false; + if (rhs->matchType() == MatchExpression::EXISTS) { + return _isSubsetOf(lhs, static_cast<const ExistsMatchExpression*>(rhs)); } + + return false; } -} + +} // namespace expression +} // namespace mongo diff --git a/src/mongo/db/matcher/expression_algo.h b/src/mongo/db/matcher/expression_algo.h index 8e3b7bd701c..0ee4459c56f 100644 --- a/src/mongo/db/matcher/expression_algo.h +++ b/src/mongo/db/matcher/expression_algo.h @@ -30,21 +30,34 @@ namespace mongo { - class MatchExpression; + class MatchExpression; - namespace expression { - /** - * In filtered index case, a is the query, b is the filter. - * @return If 'b' cannot reduce the set of returned documents that would - * be returned with 'a' as the only filter. - * Everything that matches a also must match b. - * The document set returned by applying a is a subset of the document - * set returned by applying b. - * Examples: - * a: { x : 5 } b: { x : { $lte : 5 } } = true - * a: { x : { $lte : 5 } b: { x : 5 } = false - */ - bool isClauseRedundant(const MatchExpression* a, - const MatchExpression* b); - } -} +namespace expression { + + /** + * Returns true if the documents matched by 'lhs' are a subset of the documents matched by + * 'rhs', i.e. a document matched by 'lhs' must also be matched by 'rhs', and false otherwise. + * + * With respect to partial indexes, 'lhs' corresponds to the query specification and 'rhs' + * corresponds to the filter specification. + * + * e.g. + * + * Suppose that + * + * lhs = { x : 4 } + * rhs = { x : { $lte : 5 } } + * + * ==> true + * + * Suppose that + * + * lhs = { x : { $gte: 6 } } + * rhs = { x : 7 } + * + * ==> false + */ + bool isSubsetOf(const MatchExpression* lhs, const MatchExpression* rhs); + +} // namespace expression +} // namespace mongo diff --git a/src/mongo/db/matcher/expression_algo_test.cpp b/src/mongo/db/matcher/expression_algo_test.cpp index 65309c0d3a3..9e162c6eb7a 100644 --- a/src/mongo/db/matcher/expression_algo_test.cpp +++ b/src/mongo/db/matcher/expression_algo_test.cpp @@ -1,7 +1,7 @@ // expression_algo_test.cpp /** - * Copyright (C) 2013 10gen Inc. + * Copyright (C) 2015 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, @@ -30,7 +30,7 @@ #include "mongo/unittest/unittest.h" -#include <boost/scoped_ptr.hpp> +#include <memory> #include "mongo/db/jsobj.h" #include "mongo/db/json.h" @@ -38,241 +38,289 @@ #include "mongo/db/matcher/expression_algo.h" #include "mongo/db/matcher/expression_parser.h" -#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kDefault -#include "mongo/util/log.h" - namespace mongo { - using boost::scoped_ptr; - /** - * A MatchExpression does not hold the memory for BSONElements. - * So using this we can tie the life cycle of a MatchExpression to its data. + * A MatchExpression does not hold the memory for BSONElements, so use ParsedMatchExpression to + * ensure that the BSONObj outlives the MatchExpression. */ - struct Parsed { - Parsed(const char* str) { - obj = fromjson(str); - _parse(); + class ParsedMatchExpression { + public: + ParsedMatchExpression(const std::string& str) + : _obj(fromjson(str)) { + StatusWithMatchExpression result = MatchExpressionParser::parse(_obj); + ASSERT_OK(result.getStatus()); + _expr.reset(result.getValue()); } - Parsed(const BSONObj& o) - : obj(o) { - _parse(); - } + const MatchExpression* get() const { return _expr.get(); } - void _parse() { - StatusWithMatchExpression result = MatchExpressionParser::parse(obj); - if (!result.isOK()) { - log() << "failed to parse expression: " << obj; - invariant(false); - } - exp.reset(result.getValue()); - } + private: + const BSONObj _obj; + std::unique_ptr<MatchExpression> _expr; + }; - const MatchExpression* get() const { return exp.get(); } + TEST(ExpressionAlgoIsSubsetOf, NullAndOmittedField) { + // Verify that ComparisonMatchExpression::init() prohibits creating a match expression with + // an Undefined type. + BSONObj undefined = fromjson("{a: undefined}"); + ASSERT_EQUALS(ErrorCodes::BadValue, MatchExpressionParser::parse(undefined).getStatus()); - BSONObj obj; - scoped_ptr<MatchExpression> exp; - }; + ParsedMatchExpression empty("{}"); + ParsedMatchExpression null("{a: null}"); - TEST(ExpressionAlgoRedundant, Equal1) { - Parsed foo("{ x : 5 }"); - Parsed bar1("{ x : 5 }"); - Parsed bar2("{ x : 6 }"); - Parsed bar3("{ a : 5 }"); - ASSERT_TRUE(expression::isClauseRedundant(foo.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar3.get())); - } + ASSERT_TRUE(expression::isSubsetOf(null.get(), empty.get())); + ASSERT_FALSE(expression::isSubsetOf(empty.get(), null.get())); - TEST(ExpressionAlgoRedundant, AndEqual1) { - Parsed foo("{ a : 3, x : 5 }"); - Parsed bar1("{ x : 5 }"); - Parsed bar2("{ x : 6 }"); - Parsed bar3("{ a : 5 }"); - ASSERT_TRUE(expression::isClauseRedundant(foo.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar3.get())); - ASSERT_FALSE(expression::isClauseRedundant(bar1.get(), foo.get())); - } + ParsedMatchExpression b1("{b: 1}"); + ParsedMatchExpression aNullB1("{a: null, b: 1}"); + + ASSERT_TRUE(expression::isSubsetOf(aNullB1.get(), b1.get())); + ASSERT_FALSE(expression::isSubsetOf(b1.get(), aNullB1.get())); - TEST(ExpressionAlgoRedundant, DifferentTypes1) { - // Comparison of different canonical types is not redundant. - Parsed foo("{x: {$gt: \"a\"}}"); - Parsed bar("{x: {$gt: 1}}"); - ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar.get())); - ASSERT_FALSE(expression::isClauseRedundant(bar.get(), foo.get())); + ParsedMatchExpression a1C3("{a: 1, c: 3}"); + ParsedMatchExpression a1BNullC3("{a: 1, b: null, c: 3}"); + + ASSERT_TRUE(expression::isSubsetOf(a1BNullC3.get(), a1C3.get())); + ASSERT_FALSE(expression::isSubsetOf(a1C3.get(), a1BNullC3.get())); } - TEST(ExpressionAlgoRedundant, DifferentTypes2) { - Parsed foo("{x: null}"); - Parsed bar("{x: {$exists: true}}"); - ASSERT_FALSE(expression::isClauseRedundant(foo.get(), bar.get())); + TEST(ExpressionAlgoIsSubsetOf, NullAndExists) { + ParsedMatchExpression null("{x: null}"); + ParsedMatchExpression exists("{x: {$exists: true}}"); + ASSERT_FALSE(expression::isSubsetOf(null.get(), exists.get())); + ASSERT_FALSE(expression::isSubsetOf(exists.get(), null.get())); } - TEST(ExpressionAlgoRedundant, PointToRange) { - Parsed foo1("{ x : 4 }"); - Parsed foo2("{ x : 5 }"); - Parsed foo3("{ a : 4 }"); - Parsed foo4("{ x : 6 }"); - Parsed foo5("{ a : 6 }"); - - Parsed bar1("{ x : { $lte : 5 } }"); - Parsed bar2("{ x : { $lt : 5 } }"); - Parsed bar3("{ x : { $gte : 5 } }"); - Parsed bar4("{ x : { $gt : 5 } }"); - - ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar1.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(bar1.get(), foo1.get())); - - ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo2.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar2.get())); - - ASSERT_FALSE(expression::isClauseRedundant(foo1.get(), bar3.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar3.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar3.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo4.get(), bar3.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar3.get())); - - ASSERT_FALSE(expression::isClauseRedundant(foo1.get(), bar4.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo2.get(), bar4.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar4.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo4.get(), bar4.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar4.get())); + TEST(ExpressionAlgoIsSubsetOf, Compare_NaN) { + ParsedMatchExpression nan("{x: NaN}"); + ParsedMatchExpression lt("{x: {$lt: 5}}"); + ParsedMatchExpression lte("{x: {$lte: 5}}"); + ParsedMatchExpression gte("{x: {$gte: 5}}"); + ParsedMatchExpression gt("{x: {$gt: 5}}"); + + ASSERT_TRUE(expression::isSubsetOf(nan.get(), nan.get())); + ASSERT_FALSE(expression::isSubsetOf(nan.get(), lt.get())); + ASSERT_FALSE(expression::isSubsetOf(lt.get(), nan.get())); + ASSERT_FALSE(expression::isSubsetOf(nan.get(), lte.get())); + ASSERT_FALSE(expression::isSubsetOf(lte.get(), nan.get())); + ASSERT_FALSE(expression::isSubsetOf(nan.get(), gte.get())); + ASSERT_FALSE(expression::isSubsetOf(gte.get(), nan.get())); + ASSERT_FALSE(expression::isSubsetOf(nan.get(), gt.get())); + ASSERT_FALSE(expression::isSubsetOf(gt.get(), nan.get())); } - TEST(ExpressionAlgoRedundant, LessThanToLessThan) { - Parsed foo1("{ x : { $lte : 4 } }"); - Parsed foo2("{ x : { $lt : 5 } }"); - Parsed foo3("{ x : { $lte : 5 } }"); - Parsed foo4("{ x : { $lte : 6 } }"); - Parsed foo5("{ a : { $lte : 4 } }"); + TEST(ExpressionAlgoIsSubsetOf, Compare_EQ) { + ParsedMatchExpression a5("{a: 5}"); + ParsedMatchExpression a6("{a: 6}"); + ParsedMatchExpression b5("{b: 5}"); - Parsed bar1("{ x : { $lte : 5 } }"); - Parsed bar2("{ x : { $lt : 5 } }"); + ASSERT_TRUE(expression::isSubsetOf(a5.get(), a5.get())); + ASSERT_FALSE(expression::isSubsetOf(a5.get(), a6.get())); + ASSERT_FALSE(expression::isSubsetOf(a5.get(), b5.get())); + } - ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar1.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar1.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo3.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar1.get())); + TEST(ExpressionAlgoIsSubsetOf, CompareAnd_EQ) { + ParsedMatchExpression a1B2("{a: 1, b: 2}"); + ParsedMatchExpression a1B7("{a: 1, b: 7}"); + ParsedMatchExpression a1("{a: 1}"); + ParsedMatchExpression b2("{b: 2}"); - ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar2.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar2.get())); + ASSERT_TRUE(expression::isSubsetOf(a1B2.get(), a1B2.get())); + ASSERT_FALSE(expression::isSubsetOf(a1B2.get(), a1B7.get())); + ASSERT_TRUE(expression::isSubsetOf(a1B2.get(), a1.get())); + ASSERT_TRUE(expression::isSubsetOf(a1B2.get(), b2.get())); + ASSERT_FALSE(expression::isSubsetOf(a1B7.get(), b2.get())); } - TEST(ExpressionAlgoRedundant, GreaterThanToGreaterThan) { - Parsed foo1("{ x : { $gte : 6 } }"); - Parsed foo2("{ x : { $gt : 5 } }"); - Parsed foo3("{ x : { $gte : 5 } }"); - Parsed foo4("{ x : { $gte : 4 } }"); - Parsed foo5("{ a : { $gte : 6 } }"); - - Parsed bar1("{ x : { $gte : 5 } }"); - Parsed bar2("{ x : { $gt : 5 } }"); + TEST(ExpressionAlgoIsSubsetOf, CompareAnd_GT) { + ParsedMatchExpression filter("{a: {$gt: 5}, b: {$gt: 6}}"); + ParsedMatchExpression query("{a: {$gt: 5}, b: {$gt: 6}, c: {$gt: 7}}"); - ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar1.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar1.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo3.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar1.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar1.get())); + ASSERT_TRUE(expression::isSubsetOf(query.get(), filter.get())); + ASSERT_FALSE(expression::isSubsetOf(filter.get(), query.get())); + } - ASSERT_TRUE(expression::isClauseRedundant(foo1.get(), bar2.get())); - ASSERT_TRUE(expression::isClauseRedundant(foo2.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo3.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo4.get(), bar2.get())); - ASSERT_FALSE(expression::isClauseRedundant(foo5.get(), bar2.get())); + TEST(ExpressionAlgoIsSubsetOf, DifferentCanonicalTypes) { + ParsedMatchExpression number("{x: {$gt: 1}}"); + ParsedMatchExpression string("{x: {$gt: 'a'}}"); + ASSERT_FALSE(expression::isSubsetOf(number.get(), string.get())); + ASSERT_FALSE(expression::isSubsetOf(string.get(), number.get())); + } + TEST(ExpressionAlgoIsSubsetOf, DifferentNumberTypes) { + ParsedMatchExpression numberDouble("{x: 5.0}"); + ParsedMatchExpression numberInt("{x: NumberInt(5)}"); + ParsedMatchExpression numberLong("{x: NumberLong(5)}"); + + ASSERT_TRUE(expression::isSubsetOf(numberDouble.get(), numberInt.get())); + ASSERT_TRUE(expression::isSubsetOf(numberDouble.get(), numberLong.get())); + ASSERT_TRUE(expression::isSubsetOf(numberInt.get(), numberDouble.get())); + ASSERT_TRUE(expression::isSubsetOf(numberInt.get(), numberLong.get())); + ASSERT_TRUE(expression::isSubsetOf(numberLong.get(), numberDouble.get())); + ASSERT_TRUE(expression::isSubsetOf(numberLong.get(), numberInt.get())); } - TEST(ExpressionAlgoRedundant, Exists1) { - Parsed a("{a : { $exists : 1 } }"); - Parsed b("{b : { $exists : 1 } }"); - Parsed ab("{a : { $exists : 1 }, b : { $exists: 1 } }"); - Parsed abc("{a : { $exists : 1 }, b : { $exists: 1 }, c : 5 }"); + TEST(ExpressionAlgoIsSubsetOf, PointInUnboundedRange) { + ParsedMatchExpression a4("{a: 4}"); + ParsedMatchExpression a5("{a: 5}"); + ParsedMatchExpression a6("{a: 6}"); + ParsedMatchExpression b5("{b: 5}"); + + ParsedMatchExpression lt5("{a: {$lt: 5}}"); + ParsedMatchExpression lte5("{a: {$lte: 5}}"); + ParsedMatchExpression gte5("{a: {$gte: 5}}"); + ParsedMatchExpression gt5("{a: {$gt: 5}}"); + + ASSERT_TRUE(expression::isSubsetOf(a4.get(), lte5.get())); + ASSERT_TRUE(expression::isSubsetOf(a5.get(), lte5.get())); + ASSERT_FALSE(expression::isSubsetOf(a6.get(), lte5.get())); + + ASSERT_TRUE(expression::isSubsetOf(a4.get(), lt5.get())); + ASSERT_FALSE(expression::isSubsetOf(a5.get(), lt5.get())); + ASSERT_FALSE(expression::isSubsetOf(a6.get(), lt5.get())); + + ASSERT_FALSE(expression::isSubsetOf(a4.get(), gte5.get())); + ASSERT_TRUE(expression::isSubsetOf(a5.get(), gte5.get())); + ASSERT_TRUE(expression::isSubsetOf(a6.get(), gte5.get())); + + ASSERT_FALSE(expression::isSubsetOf(a4.get(), gt5.get())); + ASSERT_FALSE(expression::isSubsetOf(a5.get(), gt5.get())); + ASSERT_TRUE(expression::isSubsetOf(a6.get(), gt5.get())); + + // An unbounded range query does not match a subset of documents of a point query. + ASSERT_FALSE(expression::isSubsetOf(lt5.get(), a5.get())); + ASSERT_FALSE(expression::isSubsetOf(lte5.get(), a5.get())); + ASSERT_FALSE(expression::isSubsetOf(gte5.get(), a5.get())); + ASSERT_FALSE(expression::isSubsetOf(gt5.get(), a5.get())); + + // Cannot be a subset if comparing different field names. + ASSERT_FALSE(expression::isSubsetOf(b5.get(), lt5.get())); + ASSERT_FALSE(expression::isSubsetOf(b5.get(), lte5.get())); + ASSERT_FALSE(expression::isSubsetOf(b5.get(), gte5.get())); + ASSERT_FALSE(expression::isSubsetOf(b5.get(), gt5.get())); + } - ASSERT_TRUE(expression::isClauseRedundant(a.get(), a.get())); - ASSERT_FALSE(expression::isClauseRedundant(a.get(), b.get())); - ASSERT_FALSE(expression::isClauseRedundant(b.get(), a.get())); + TEST(ExpressionAlgoIsSubsetOf, PointInBoundedRange) { + ParsedMatchExpression filter("{a: {$gt: 5, $lt: 10}}"); + ParsedMatchExpression query("{a: 6}"); - ASSERT_TRUE(expression::isClauseRedundant(ab.get(), a.get())); - ASSERT_TRUE(expression::isClauseRedundant(ab.get(), b.get())); + ASSERT_TRUE(expression::isSubsetOf(query.get(), filter.get())); + ASSERT_FALSE(expression::isSubsetOf(filter.get(), query.get())); + } - ASSERT_TRUE(expression::isClauseRedundant(abc.get(), a.get())); - ASSERT_TRUE(expression::isClauseRedundant(abc.get(), b.get())); + TEST(ExpressionAlgoIsSubsetOf, PointInBoundedRange_FakeAnd) { + ParsedMatchExpression filter("{a: {$gt: 5, $lt: 10}}"); + ParsedMatchExpression query("{$and: [{a: 6}, {a: 6}]}"); - ASSERT_TRUE(expression::isClauseRedundant(abc.get(), ab.get())); - ASSERT_FALSE(expression::isClauseRedundant(ab.get(), abc.get())); + ASSERT_TRUE(expression::isSubsetOf(query.get(), filter.get())); + ASSERT_FALSE(expression::isSubsetOf(filter.get(), query.get())); } - TEST(ExpressionAlgoRedundant, Exists2) { - Parsed filter("{a : { $exists : 1 } }"); - Parsed query1("{a : 1}"); - Parsed query2("{a : { $gt : 4 } }"); - Parsed query3("{a : { $lt : 4 } }"); + TEST(ExpressionAlgoIsSubsetOf, PointInCompoundRange) { + ParsedMatchExpression filter("{a: {$gt: 5}, b: {$gt: 6}, c: {$gt: 7}}"); + ParsedMatchExpression query("{a: 10, b: 10, c: 10}"); - ASSERT_TRUE(expression::isClauseRedundant(query1.get(), filter.get())); - ASSERT_TRUE(expression::isClauseRedundant(query2.get(), filter.get())); - ASSERT_TRUE(expression::isClauseRedundant(query3.get(), filter.get())); - ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query1.get())); + ASSERT_TRUE(expression::isSubsetOf(query.get(), filter.get())); + ASSERT_FALSE(expression::isSubsetOf(filter.get(), query.get())); } - TEST(ExpressionAlgoRedundant, Exists3) { - Parsed filter("{a : { $exists : 1 } }"); - Parsed query1("{a : { $type : 5 } }"); + TEST(ExpressionAlgoIsSubsetOf, Compare_LT_LTE) { + ParsedMatchExpression lte4("{x: {$lte: 4}}"); + ParsedMatchExpression lt5("{x: {$lt: 5}}"); + ParsedMatchExpression lte5("{x: {$lte: 5}}"); + ParsedMatchExpression lt6("{x: {$lt: 6}}"); + + ASSERT_TRUE(expression::isSubsetOf(lte4.get(), lte5.get())); + ASSERT_TRUE(expression::isSubsetOf(lt5.get(), lte5.get())); + ASSERT_TRUE(expression::isSubsetOf(lte5.get(), lte5.get())); + ASSERT_FALSE(expression::isSubsetOf(lt6.get(), lte5.get())); + + ASSERT_TRUE(expression::isSubsetOf(lte4.get(), lt5.get())); + ASSERT_TRUE(expression::isSubsetOf(lt5.get(), lt5.get())); + ASSERT_FALSE(expression::isSubsetOf(lte5.get(), lt5.get())); + ASSERT_FALSE(expression::isSubsetOf(lt6.get(), lt5.get())); + } - ASSERT_TRUE(expression::isClauseRedundant(query1.get(), filter.get())); - ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query1.get())); + TEST(ExpressionAlgoIsSubsetOf, Compare_GT_GTE) { + ParsedMatchExpression gte6("{x: {$gte: 6}}"); + ParsedMatchExpression gt5("{x: {$gt: 5}}"); + ParsedMatchExpression gte5("{x: {$gte: 5}}"); + ParsedMatchExpression gt4("{x: {$gt: 4}}"); + + ASSERT_TRUE(expression::isSubsetOf(gte6.get(), gte5.get())); + ASSERT_TRUE(expression::isSubsetOf(gt5.get(), gte5.get())); + ASSERT_TRUE(expression::isSubsetOf(gte5.get(), gte5.get())); + ASSERT_FALSE(expression::isSubsetOf(gt4.get(), gte5.get())); + + ASSERT_TRUE(expression::isSubsetOf(gte6.get(), gt5.get())); + ASSERT_TRUE(expression::isSubsetOf(gt5.get(), gt5.get())); + ASSERT_FALSE(expression::isSubsetOf(gte5.get(), gt5.get())); + ASSERT_FALSE(expression::isSubsetOf(gt4.get(), gt5.get())); } - TEST(ExpressionAlgoRedundant, Exists4) { - Parsed filter("{a : { $exists : 1 } }"); - Parsed query1("{b : { $type : 5 } }"); + TEST(ExpressionAlgoIsSubsetOf, BoundedRangeInUnboundedRange) { + ParsedMatchExpression filter("{a: {$gt: 1}}"); + ParsedMatchExpression query("{a: {$gt: 5, $lt: 10}}"); - ASSERT_FALSE(expression::isClauseRedundant(query1.get(), filter.get())); - ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query1.get())); + ASSERT_TRUE(expression::isSubsetOf(query.get(), filter.get())); + ASSERT_FALSE(expression::isSubsetOf(filter.get(), query.get())); } - TEST(ExpressionAlgoRedundant, Type1) { - Parsed a("{a : { $type : 4 } }"); - Parsed a2("{a : { $type : 4 } }"); - Parsed b("{a : { $type : 7 } }"); + TEST(ExpressionAlgoIsSubsetOf, Exists) { + ParsedMatchExpression aExists("{a: {$exists: true}}"); + ParsedMatchExpression bExists("{b: {$exists: true}}"); + ParsedMatchExpression aExistsBExists("{a: {$exists: true}, b: {$exists: true}}"); + ParsedMatchExpression aExistsBExistsC5("{a: {$exists: true}, b: {$exists: true}, c: 5}"); - ASSERT_TRUE(expression::isClauseRedundant(a.get(), a2.get())); - ASSERT_FALSE(expression::isClauseRedundant(a.get(), b.get())); - } + ASSERT_TRUE(expression::isSubsetOf(aExists.get(), aExists.get())); + ASSERT_FALSE(expression::isSubsetOf(aExists.get(), bExists.get())); - TEST(ExpressionAlgoRedundant, Subset1) { - Parsed filter("{ a : 5, b : 6 }"); - Parsed query("{ a : 5, b : 6, c : 7 }"); + ASSERT_TRUE(expression::isSubsetOf(aExistsBExists.get(), aExists.get())); + ASSERT_TRUE(expression::isSubsetOf(aExistsBExists.get(), bExists.get())); + ASSERT_FALSE(expression::isSubsetOf(aExistsBExists.get(), aExistsBExistsC5.get())); - ASSERT_TRUE(expression::isClauseRedundant(query.get(), filter.get())); - ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query.get())); + ASSERT_TRUE(expression::isSubsetOf(aExistsBExistsC5.get(), aExists.get())); + ASSERT_TRUE(expression::isSubsetOf(aExistsBExistsC5.get(), bExists.get())); + ASSERT_TRUE(expression::isSubsetOf(aExistsBExistsC5.get(), aExistsBExists.get())); } - TEST(ExpressionAlgoRedundant, Subset2) { - Parsed filter("{ a : { $gt : 5 }, b : { $gt : 6 } }"); - Parsed query1("{ a : { $gt : 5 }, b : { $gt : 6 }, c : { $gt : 7 } }"); - Parsed query2("{ a : 10, b : 10, c : 10 }"); + TEST(ExpressionAlgoIsSubsetOf, Compare_Exists) { + ParsedMatchExpression exists("{a: {$exists: true}}"); + ParsedMatchExpression eq("{a: 1}"); + ParsedMatchExpression gt("{a: {$gt: 4}}"); + ParsedMatchExpression lte("{a: {$lte: 7}}"); - ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query1.get())); - ASSERT_FALSE(expression::isClauseRedundant(filter.get(), query2.get())); + ASSERT_TRUE(expression::isSubsetOf(eq.get(), exists.get())); + ASSERT_TRUE(expression::isSubsetOf(gt.get(), exists.get())); + ASSERT_TRUE(expression::isSubsetOf(lte.get(), exists.get())); - ASSERT_TRUE(expression::isClauseRedundant(query1.get(), filter.get())); - ASSERT_TRUE(expression::isClauseRedundant(query2.get(), filter.get())); + ASSERT_FALSE(expression::isSubsetOf(exists.get(), eq.get())); + ASSERT_FALSE(expression::isSubsetOf(exists.get(), gt.get())); + ASSERT_FALSE(expression::isSubsetOf(exists.get(), lte.get())); + } + + TEST(ExpressionAlgoIsSubsetOf, Type) { + ParsedMatchExpression aType1("{a: {$type: 1}}"); + ParsedMatchExpression aType2("{a: {$type: 2}}"); + ParsedMatchExpression bType2("{b: {$type: 2}}"); + + ASSERT_FALSE(expression::isSubsetOf(aType1.get(), aType2.get())); + ASSERT_FALSE(expression::isSubsetOf(aType2.get(), aType1.get())); + ASSERT_TRUE(expression::isSubsetOf(aType2.get(), aType2.get())); + ASSERT_FALSE(expression::isSubsetOf(aType2.get(), bType2.get())); } -} + TEST(ExpressionAlgoIsSubsetOf, TypeAndExists) { + ParsedMatchExpression aExists("{a: {$exists: true}}"); + ParsedMatchExpression aType2("{a: {$type: 2}}"); + ParsedMatchExpression bType2("{b: {$type: 2}}"); + + ASSERT_TRUE(expression::isSubsetOf(aType2.get(), aExists.get())); + ASSERT_FALSE(expression::isSubsetOf(aExists.get(), aType2.get())); + ASSERT_FALSE(expression::isSubsetOf(bType2.get(), aExists.get())); + } +} // namespace mongo diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp index 183a60ec8af..7a9ad59a693 100644 --- a/src/mongo/db/query/get_executor.cpp +++ b/src/mongo/db/query/get_executor.cpp @@ -127,7 +127,7 @@ namespace mongo { return true; } - return !expression::isClauseRedundant(queryPredicates, filter); + return !expression::isSubsetOf(queryPredicates, filter); } } // namespace diff --git a/src/mongo/db/query/plan_cache_indexability.cpp b/src/mongo/db/query/plan_cache_indexability.cpp index e7d3577c34d..043ba1d7a40 100644 --- a/src/mongo/db/query/plan_cache_indexability.cpp +++ b/src/mongo/db/query/plan_cache_indexability.cpp @@ -64,7 +64,7 @@ namespace mongo { if (!filterExpr->isLogical()) { _pathDiscriminatorsMap[filterExpr->path()].push_back( [filterExpr] (const MatchExpression* queryExpr) { - return expression::isClauseRedundant(queryExpr, filterExpr); + return expression::isSubsetOf(queryExpr, filterExpr); } ); } |