SERVER-34714 Optimize $or with all always-false children to $alwaysFalse

2 files changed, 58 insertions, 1 deletions

diff --git a/src/mongo/db/matcher/expression_optimize_test.cpp b/src/mongo/db/matcher/expression_optimize_test.cpp
index e2f82257a67..036a1146b2f 100644
--- a/src/mongo/db/matcher/expression_optimize_test.cpp
+++ b/src/mongo/db/matcher/expression_optimize_test.cpp
@@ -28,6 +28,7 @@
 
 #include "mongo/db/pipeline/expression.h"
 
+#include "mongo/db/matcher/expression_always_boolean.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"
@@ -358,6 +359,28 @@ TEST(ExpressionOptimizeTest, AndRemovesAlwaysTrueChildren) {
     ASSERT_BSONOBJ_EQ(bob.obj(), fromjson("{a: {$eq: 1}}"));
 }
 
+TEST(ExpressionOptimizeTest, AndWithSingleChildAlwaysTrueOptimizesToEmptyAnd) {
+    BSONObj obj = fromjson("{$and: [{$alwaysTrue: 1}]}");
+    std::unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj));
+    auto optimizedMatchExpression = MatchExpression::optimize(std::move(matchExpression));
+    // TODO SERVER-34759 We want this to optimize to an AlwaysTrueMatchExpression.
+    ASSERT_TRUE(dynamic_cast<AndMatchExpression*>(optimizedMatchExpression.get()));
+    BSONObjBuilder bob;
+    optimizedMatchExpression->serialize(&bob);
+    ASSERT_BSONOBJ_EQ(bob.obj(), fromjson("{}"));
+}
+
+TEST(ExpressionOptimizeTest, AndWithEachChildAlwaysTrueOptimizesToEmptyAnd) {
+    BSONObj obj = fromjson("{$and: [{$alwaysTrue: 1}, {$alwaysTrue: 1}]}");
+    std::unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj));
+    auto optimizedMatchExpression = MatchExpression::optimize(std::move(matchExpression));
+    // TODO SERVER-34759 We want this to optimize to an AlwaysTrueMatchExpression.
+    ASSERT_TRUE(dynamic_cast<AndMatchExpression*>(optimizedMatchExpression.get()));
+    BSONObjBuilder bob;
+    optimizedMatchExpression->serialize(&bob);
+    ASSERT_BSONOBJ_EQ(bob.obj(), fromjson("{}"));
+}
+
 TEST(ExpressionOptimizeTest, NestedAndWithAlwaysFalseOptimizesToAlwaysFalse) {
     BSONObj obj = fromjson("{$and: [{$and: [{$alwaysFalse: 1}, {a: 1}]}, {b: 1}]}");
     std::unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj));
@@ -385,10 +408,32 @@ TEST(ExpressionOptimizeTest, OrRemovesAlwaysFalseChildren) {
     ASSERT_BSONOBJ_EQ(bob.obj(), fromjson("{a: {$eq: 1}}"));
 }
 
+TEST(ExpressionOptimizeTest, OrPromotesSingleAlwaysFalseAfterOptimize) {
+    // The nested predicate is always false. This test is designed to reproduce SERVER-34714.
+    BSONObj obj = fromjson("{$or: [{a: {$all: []}}]}");
+    std::unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj));
+    auto optimizedMatchExpression = MatchExpression::optimize(std::move(matchExpression));
+    ASSERT_TRUE(dynamic_cast<AlwaysFalseMatchExpression*>(optimizedMatchExpression.get()));
+    BSONObjBuilder bob;
+    optimizedMatchExpression->serialize(&bob);
+    ASSERT_BSONOBJ_EQ(bob.obj(), fromjson("{$alwaysFalse: 1}"));
+}
+
 TEST(ExpressionOptimizeTest, OrPromotesSingleAlwaysFalse) {
     BSONObj obj = fromjson("{$or: [{$alwaysFalse: 1}]}");
     std::unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj));
     auto optimizedMatchExpression = MatchExpression::optimize(std::move(matchExpression));
+    ASSERT_TRUE(dynamic_cast<AlwaysFalseMatchExpression*>(optimizedMatchExpression.get()));
+    BSONObjBuilder bob;
+    optimizedMatchExpression->serialize(&bob);
+    ASSERT_BSONOBJ_EQ(bob.obj(), fromjson("{$alwaysFalse: 1}"));
+}
+
+TEST(ExpressionOptimizeTest, OrPromotesMultipleAlwaysFalse) {
+    BSONObj obj = fromjson("{$or: [{$alwaysFalse: 1}, {a: {$all: []}}]}");
+    std::unique_ptr<MatchExpression> matchExpression(parseMatchExpression(obj));
+    auto optimizedMatchExpression = MatchExpression::optimize(std::move(matchExpression));
+    ASSERT_TRUE(dynamic_cast<AlwaysFalseMatchExpression*>(optimizedMatchExpression.get()));
     BSONObjBuilder bob;
     optimizedMatchExpression->serialize(&bob);
     ASSERT_BSONOBJ_EQ(bob.obj(), fromjson("{$alwaysFalse: 1}"));
diff --git a/src/mongo/db/matcher/expression_tree.cpp b/src/mongo/db/matcher/expression_tree.cpp
index bab36caf0ce..9c3d79c0739 100644
--- a/src/mongo/db/matcher/expression_tree.cpp
+++ b/src/mongo/db/matcher/expression_tree.cpp
@@ -129,6 +129,16 @@ MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() c
             children.erase(std::remove(children.begin(), children.end(), nullptr), children.end());
         }
 
+        // Check if the above optimizations eliminated all children. An OR with no children is
+        // always false.
+        // TODO SERVER-34759 It is correct to replace this empty AND with an $alwaysTrue, but we
+        // need to make enhancements to the planner to make it understand an $alwaysTrue and an
+        // empty AND as the same thing. The planner can create inferior plans for $alwaysTrue which
+        // it would not produce for an AND with no children.
+        if (children.empty() && matchType == MatchExpression::OR) {
+            return stdx::make_unique<AlwaysFalseMatchExpression>();
+        }
+
         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
@@ -160,7 +170,6 @@ MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() c
             }
         }
 
-
         return expression;
     };
 }
@@ -256,6 +265,9 @@ void OrMatchExpression::debugString(StringBuilder& debug, int level) const {
 
 void OrMatchExpression::serialize(BSONObjBuilder* out) const {
     if (!numChildren()) {
+        // It is possible for an OrMatchExpression to have no children, resulting in the serialized
+        // expression {$or: []}, which is not a valid query object. An empty $or is logically
+        // equivalent to {$alwaysFalse: 1}.
         out->append(AlwaysFalseMatchExpression::kName, 1);
         return;
     }